And Tuples question of october lunch time contest

general
1

please provide the c language code for AND TUPLES

2

change all cin to scanf , cout to printf

 #include<stdio.h>


#include<functional.h>
#include<string.h>
#define ll long long int
#define llu long long int
#define mod 1000000009
#define f first
#define s second
#define yo cout<<"yo\n"
ll k,sz;
llu n;
ll memo[64][100];
ll dp(ll i,ll carry){
if(i==64){
if(!carry) return 1;
return 0;
}
if(memo[i][carry]>=0) return memo[i][carry];
memo[i][carry]=0;
for(int s=0;s<=k;s++){
ll b=(n&(1LL<<i));
if(b) b=1;
if((s+carry)%2==b){	
memo[i][carry]+=dp(i+1,(s+carry)/2);
memo[i][carry]%=mod;
}	
}
return memo[i][carry];
}
int main(){
yup;
ll t;
cin>>t;
while(t--){
cin>>k>>n;
for(int i=0;i<64;i++) for(int j=0;j<100;j++) memo[i][j]=-1;
llu r=n;
while(r){
r/=2;
sz++;
}
cout<<dp(0,0)%mod<<"\n";;
}	
}