QUESTION

Given a set S of first N non-negative integers i.e. S = {0, 1, 2, …, N}.\n\nFind number of ways of choosing a K size subset of S with the property that the XOR-sum of all chosen integers has exactly B set bits in its binary representation (i.e. the bits that are equal to 1). \n\nSince the answer can be large, output it modulo (10^9 + 7). Please refer to notes section for formal definition of XOR-sum.\n\nInput\nThe first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.\n\nThe only line of each test case contains three space-separated integers N, K and B.\n\nOutput\nFor each test case, output a single line containing the answer to the corresponding test case.\n.

ANSWER

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
 
#define MOD 1000000007
using namespace std;
 
int T,n,K,B;
int f[32][32][2][1<<7] , num[1<<7] , c[1<<7][1<<7] ;
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	cin>>T;
	while(T--){
		scanf("%d%d%d",&n,&K,&B);
		
		num[0]=0;
		for ( int l=1;l<(1<<K);l++ ) 
			num[l] = num[l>>1]^(l&1) ;
		
		memset( c,-1,sizeof(c) );
		for ( int k=0 ; k<(1<<K) ; k++ )
			for ( int l=0 ; l<(1<<K) ; l++ ) {
				if ( !(k&1) ) continue ;
				
				int t1 = 1 , t2 , ok = 1 , nk = k ;
				for ( t2=2 ; t2<=K+1 ; t2++ ) 
					if ( t2==K+1 || ( k&(1<<t2-1) ) ) {
						int app = 0 ;
						for ( int p = t1 ; p < t2 ; p++ ) {
							if ( l&(1<<p-1) )
								if ( app == 1 ) ok = 0 ; else;
							else {
								if (!app) nk |= (1<<p-1) ;
								app = 1 ;
							}
						}
						t1 = t2 ; 
					}
				if ( !ok ) continue ;
				c[k][l] = nk ; 
			}
		
		
		memset( f,0,sizeof(f) );
		f[31][0][1][1] = 1 ;
		for ( int i=31;i>=1;i-- )
			for ( int j=0;j<=B;j++ )
				for ( int o=0;o<=1;o++ )
					for ( int k=0;k<(1<<K);k++ ) {
						if ( !f[i][j][o][k] ) continue ;
						
						for ( int l=0;l<(1<<K);l++ ) {
							if ( c[k][l]==-1 ) continue;
							if ( o && (l&1) && !( (1<<i-1)&n ) ) continue ;
							
							int nk = c[k][l] ;
							int no ;
							if ( !o ) no = 0 ;
								else {
									if ( l&1 ) no = 1 ; else
									if ( !((1<<i-1)&n) ) no = 1 ; else 
									no = 0 ;
								}
							
							f[i-1][j+num[l]][no][nk] += f[i][j][o][k] ;
							f[i-1][j+num[l]][no][nk] %= MOD ;
						}
					}
		int ans = 0 ;
		ans += f[0][B][1][(1<<K)-1] ;
		ans += f[0][B][0][(1<<K)-1] ;
		ans %= MOD ;
		printf( "%d\n",ans );
	}
	
	return 0;
}