#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;
typedef long long LL;
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define REP(k,a) for(int k=0; k < (a); ++k)

#ifdef HOME
int __builtin_popcount(int a)
{
	int res = 0;
	while(a)
	{
		a&=a-1;
		++res;
	}
	return res;
}

#endif

int main( int argc, char* argv[] ) {
#ifdef HOME	
	freopen("in.txt","r",stdin);
	freopen("out.txt","wb",stdout);
#endif
	const int MOD = 1e9 + 7;
	int T,N,B,K,newmask;
	scanf("%d",&T);
	assert(T>0 && T<=5);
	int dp[32][32][1<<7];
	while(T--)
	{
		scanf("%d %d %d",&N,&K,&B);
		assert(N>=0 && N<=1e9);
		assert(K<=7 && K>=0);
		assert(B<=32 && B>=0);
		memset(dp,0,sizeof dp);
		dp[0][0][0] = 1; //1) current pos,2) used bits from B,3) mask how many number is ok 
		//3) more detail:
		//1 bit is 1 number is strictly less than N
		//2 bit is 1st number is strictly greater than than the 2nd
		//3 bit is 2nd number is strictly greater than than the 3rd etc
		int KK = 1 << K;
		REP(i,31)
		{
			int currBitOfN = (N >> (30-i))&1;
			REP(used,B+1) REP(mask,KK) if(dp[i][used][mask])
			{
				REP(pred,KK)
				{
					newmask = mask;
					if(!(mask&1))//1st number is equal N yet
					{
						if(currBitOfN<(pred&1))
							continue;
						else if(currBitOfN>(pred&1))
						{
							newmask|=1;
						}
					}
					bool ok = true;
					FOR(j,1,K) 
					{
						if(!(mask&(1<<j)))
						{
							int tmp = ((pred>>(j-1))&3) ;
							if(tmp == 2)
							{
								pred |= ((1<<(j-1))-1);
								ok=false;
								break;
							}
							else if(tmp == 1)
							{
								newmask |= 1<<j;
							}
						}
					}
					if(ok)
					{
						int& act = dp[i+1][used + (__builtin_popcount(pred)&1)][newmask];
						act+=dp[i][used][mask];
						if(act>=MOD)
							act-=MOD;
					}
				}
			}
		}
		LL ans = 0;
		ans+=dp[31][B][KK-1];
		if(ans>=MOD)
			ans-=MOD;
		ans+=dp[31][B][KK-2];
		if(ans>=MOD)
			ans-=MOD;
		printf("%lld\n",ans);
	}

	return 0;
}