/*
*/

//#pragma comment(linker, "/STACK:16777216")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define prev asdgadsgashah

#define eps 1e-8
//#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 256

const int N = 700050;

using namespace std;

int tests;
int n, k, l;
int dp[22][1 << 22];
long long C[50][50];
long long pw[500];

void add(int &a, int b)
{
	a += b;
	if (a >= bs)
		a -= bs;
}

int main(){
	//freopen("route.in","r",stdin);
	//freopen("route.out","w",stdout);
	//	freopen("F:/in.txt","r",stdin);
	//freopen("F:/output.txt","w",stdout);
	ios_base::sync_with_stdio(0);
	//cin.tie(0);

	for (int i = 0; i < 25; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if (j == 0 || j == i)
				C[i][j] = 1;
			else
				C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % bs;
		}
	}

	cin >> tests;
	//tests = 1;

	for (; tests; --tests)
	{
		cin >> n >> k >> l;

		//n = k = 20;
		//l = 1000000;

		pw[0] = 1;
		for (int i = 1; i <= n; i++)
		{
			if (l <= k)
				pw[i] = 0;
			else
				pw[i] = (1ll * pw[i - 1] * (l - k)) % bs;
		}

		for (int i = 0; i <= n; i++)
		{
			for (int j = 0; j < (1<<k)*2; j++)
			{
				dp[i][j] = 0;
			}
		}

		int ans = 0;

		dp[0][1] = 1;

		int mag = (1 << k)*2;
		--mag;
		/*
		int qmask = (1 << 15);
		--qmask;
		cout << ((qmask | (qmask << 20))&mag) << endl;
		*/

		for (int iter = 0; iter < n; iter++)
		{
			for (int mask = 0; mask < 2*(1 << k); mask++)
			{
				if (dp[iter][mask] == 0)
					continue;
				for (int nxt = 0; nxt <= l&&nxt <= k; nxt++)
				{
					add(dp[iter + 1][(mask | (mask << nxt))&mag], dp[iter][mask]);
				}
			}
		}
		/*
		for (int mask = 0; mask < 2*(1 << k); mask++)
		{
			if (mask&(1 << k))
				add(ans, dp[n][mask]);
		}
		*/
		for (int cnt = 0; cnt <= n; cnt++)
		{
			for (int mask = 0; mask < 2 * (1 << k); mask++)
			{
				if (mask&(1 << k))
					ans = (ans + 1ll * dp[cnt][mask] * pw[n - cnt] % bs*C[n][cnt] % bs) % bs;
			}
		}

		cout << ans << endl;

	}
	cin.get(); cin.get();
	return 0;
}