#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <time.h>

#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;

typedef unsigned long long llu;
typedef long long lld;

const int MAXN = 2e5 + 10;
const int INF = 1e9;
const int BASE = 10000;

int gcd(int a, int b)
{
	if (a == 0)return b;
	if (b == 0)return a;
	if (a%b == 0)return b;
	return gcd(b, a%b);
}

struct BigNum
{
	static int MOD_LEN;
	int len;
	int dig[256];
	BigNum()
	{
		Clear();
	}
	void Clear()
	{
		len = 1;
		memset(dig, 0, sizeof(dig));
	}

	void Mod()
	{
		while (len > MOD_LEN)
		{
			len--;
			dig[len] = 0;
		}
	}

	void SetNum(const char* s)
	{
		Clear();
		int slen = strlen(s);
		len = 0;
		for (int i = slen - 1; i >= 0;)
		{
			int d = 0;
			int t = 1;
			for (int j = 0; j < 4 && i >= 0; j++, i--)
			{
				d += t * (s[i] - '0');
				t *= 10;
			}

			dig[len] = d;
			len++;
		}
		RemoveLeadingZero();
		Mod();
	}

	void SetNum(int n)
	{
		Clear();
		if (n == 0)
		{
			return;
		}

		len = 0;
		while (n)
		{
			dig[len] = n % BASE;
			n /= BASE;
			len++;
		}

		Mod();
	}

	void Print()
	{
		printf("%d", dig[len - 1]);
		for (int i = len - 2; i >= 0; i--)
		{
			printf("%04d", dig[i]);
		}
	}

	int Compare(const BigNum& other) const
	{
		if(len<other.len)
		{
			return -1;
		}
		else if (len > other.len)
		{
			return 1;
		}
		else
		{
			for (int i = len - 1; i >= 0; i--)
			{
				if (dig[i] != other.dig[i])
				{
					return dig[i] - other.dig[i];
				}
			}
			return 0;
		}
	}

	void operator++()
	{
		dig[0]++;
		int i = 0;
		while (dig[i] >= BASE)
		{
			dig[i] -= BASE;
			dig[i + 1]++;
			i++;
		}
		if (dig[len])
		{
			len++;
		}

		Mod();
	}

	void operator*=(const BigNum& other)
	{
		lld dc[256] = { 0 };

		int lenc = len + other.len;
		if (lenc > MOD_LEN)
		{
			lenc = MOD_LEN;
		}

		for (int i = 0; i < len && i < MOD_LEN; i++)
		{
			for (int j = 0; j < other.len && i + j < MOD_LEN; j++)
			{
				dc[i + j] += dig[i] * other.dig[j];
			}
		}

		for (int i = 0; i < lenc; i++)
		{
			if (dc[i] >= BASE)
			{
				dc[i + 1] += dc[i] / BASE;
				dc[i] %= BASE;
			}

			dig[i] = dc[i];
		}

		len = lenc;
		RemoveLeadingZero();

		Mod();
	}

	void RemoveLeadingZero()
	{
		while (len > 1 && dig[len - 1] == 0)
		{
			len--;
		}
	}

	void operator+=(const BigNum& other)
	{
		len = max(len, other.len);
		for (int i = 0; i < len; i++)
		{
			dig[i] += other.dig[i];
			if (dig[i] >= BASE)
			{
				dig[i + 1]++;
				dig[i] -= BASE;
			}
		}

		if (dig[len])
		{
			len++;
		}

		Mod();
	}

	void operator/=(int d)
	{
		if (d == 1)
		{
			return;
		}
		for (int i = len - 1; i > 0; i--)
		{
			dig[i - 1] += (dig[i] % d)*BASE;
			dig[i] /= d;
		}

		if (dig[0] % d != 0)
		{
			while (1)
			{
				cout << "error" << endl;
			}
		}

		dig[0] /= d;

		RemoveLeadingZero();

		Mod();
	}

	BigNum operator-(const BigNum& other) const
	{
		BigNum c;
		c.len = len;
		for (int i = 0; i < len; i++)
		{
			c.dig[i] = dig[i] - other.dig[i];
		}

		for(int i=0;i<len;i++)
		{ 
			if (c.dig[i] < 0)
			{
				c.dig[i] += BASE;
				c.dig[i + 1]--;
			}
		}

		c.RemoveLeadingZero();
		c.Mod();
		return c;
	}

};

int BigNum::MOD_LEN = 1;

BigNum f[16][16];

void ReadBigNum(BigNum& N)
{
	char s[256];
	scanf("%s", s);
	N.SetNum(s);
}

BigNum Pow(BigNum n, int m)
{
	BigNum ret;
	ret.SetNum(1);
	while (m)
	{
		if (m & 1)
		{
			ret *= n;
		}

		n *= n;
		m >>= 1;
	}

	return ret;
}

BigNum SolveSimple(const BigNum& L, const BigNum& N, int m)
{
	BigNum iter;
	iter.SetNum(1);
	
	BigNum tempL = L;

	for (int i = 0; iter.Compare(N) <= 0; ++iter, i++)
	{
		f[0][i] = Pow(L, m);
	}

	BigNum ans;
	return ans;
}

BigNum SolveCombination(int m, const BigNum& L, int k, int last)
{
	BigNum M1;
	M1.SetNum(m + 1);
	BigNum ans = SolveSimple(L, M1, m);

	for (int i = 1; i <= m; i++)
	{
		for (int j = i; j <= m; j++)
		{
			f[i][j] = f[i - 1][j] - f[i - 1][j - 1];
		}
	}

	BigNum count = N - M1;

	BigNum com;
	com.SetNum(1);
	for (int i = 1; i <= m + 1; i++)
	{
		com *= count;
		com /= i;
		f[i - 1][m] *= com;
		ans += f[i - 1][m];

		++count;
	}

	return ans;
}

lld Brt(const BigNum& N, int m)
{
	lld ans = 0;
	for (int i = 1; i <= N.dig[0]; i++)
	{
		lld x = 1;
		for (int j = 0; j < m; j++)
		{
			x *= i;
		}

		ans += x;
	}

	return ans;
}

int main(int argc, char *argv[]) {
	
	int T;
	cin >> T;
	while (T--)
	{
		int m;
		cin >> m;
		BigNum L;
		ReadBigNum(L);
		int k;
		int last;
		cin >> k >> last;

		BigNum::MOD_LEN = (last + 3) / 4;

		BigNum a[16];
		for (int i = m; i >= 0; i--)
		{
			ReadBigNum(a[i]);
		}
		
		BigNum ans = SolveCombination(m, L, k, last);
		ans.Print();
		cout << endl;		
	}
	return 0;
}

/*

*/