#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <random>
#include <chrono>
#include <vector>
#include <queue>
#include <array>
#include <numeric>
using namespace std;
//#define int long long

using ll = long long;

constexpr int N = 3e5 + 5, MOD = 1e9 + 7, HSMOD = 1610612741, HSMOD2 = 998244353; // Remember to change

template<int mod> class ModInt {
public:
	// Constractor definition
	ModInt(long long v = 0) noexcept : val(v% mod) {
		if (val < 0) val += mod;
	}

	// Operator overriding
	constexpr ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
	constexpr ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
	constexpr ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
	constexpr ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
	constexpr ModInt& operator+=(const ModInt& x) {
		val += x.val;
		if (val >= mod) val -= mod;
		return *this;
	}
	constexpr ModInt& operator-=(const ModInt& x) {
		val -= x.val;
		if (val < 0) val += mod;
		return *this;
	}
	constexpr ModInt& operator*=(const ModInt& x) {
		val *= x.val;
		val %= mod;
		if (val < 0) val += mod;
		return *this;
	}
	constexpr ModInt& operator/=(const ModInt& x) {
		long long a = mod, b = x.val;
		long long s = 1, t = 0, ns = 0, nt = 1;
		while (a % b != 0) {
			int q = a / b;
			int r = a % b;
			int tmps = s - q * ns;
			int tmpt = t - q * nt;

			a = b;
			b = r;
			s = ns;
			t = nt;
			ns = tmps;
			nt = tmpt;
		}
		val = val * nt % mod;
		if (val < 0) val += mod;
		return *this;
	}
	friend constexpr std::ostream& operator<<(std::ostream& o, const ModInt<mod>& x) {
		return o << x.val;
	}

public:
	long long val = 0;
};

using mint = ModInt<MOD>;

int mod = 998244353, grt = 3;

class poly {
private:
	std::vector<int> data;

	void out(void) {
		for (int i = 0; i < (int)data.size(); ++i) printf("%d ", data[i]);
		puts("");
	}

public:
	poly(std::size_t len = std::size_t(0)) { data = std::vector<int>(len); }

	poly(const std::vector<int>& b) { data = b; }

	poly(const poly& b) { data = b.data; }

	void resize(std::size_t len, int val = 0) { data.resize(len, val); }

	std::size_t size(void) const { return data.size(); }

	void clear(void) { data.clear(); }
#if __cplusplus >= 201103L
	void shrink_to_fit(void) { data.shrink_to_fit(); }
#endif
	int& operator[](std::size_t b) { return data[b]; }

	const int& operator[](std::size_t b) const { return data[b]; }

	poly operator*(const poly& h) const;
	poly operator*=(const poly& h);
	poly operator*(const int& h) const;
	poly operator*=(const int& h);
	poly operator+(const poly& h) const;
	poly operator+=(const poly& h);
	poly operator-(const poly& h) const;
	poly operator-=(const poly& h);
	poly operator<<(const std::size_t& b) const;
	poly operator<<=(const std::size_t& b);
	poly operator>>(const std::size_t& b) const;
	poly operator>>=(const std::size_t& b);
	poly operator/(const int& h) const;
	poly operator/=(const int& h);
	poly operator==(const poly& h) const;
	poly operator!=(const poly& h) const;
	poly operator+(const int& h) const;
	poly operator+=(const int& h);
	poly inv(void) const;
	poly inv(const int& h) const;
	friend poly sqrt(const poly& h);
	friend poly log(const poly& h);
	friend poly exp(const poly& h);
};

int qpow(int a, int b, int p = mod) {
	int res = 1;
	while (b) {
		if (b & 1) res = (ll)res * a % p;
		a = (ll)a * a % p, b >>= 1;
	}
	return res;
}

std::vector<int> rev;

void dft_for_module(std::vector<int>& f, int n, int b) {
	static std::vector<int> w;
	w.resize(n);
	for (int i = 0; i < n; ++i)
		if (i < rev[i]) std::swap(f[i], f[rev[i]]);
	for (int i = 2; i <= n; i <<= 1) {
		w[0] = 1, w[1] = qpow(grt, (mod - 1) / i);
		if (b == -1) w[1] = qpow(w[1], mod - 2);
		for (int j = 2; j < i / 2; ++j) w[j] = (ll)w[j - 1] * w[1] % mod;
		for (int j = 0; j < n; j += i)
			for (int k = 0; k < i / 2; ++k) {
				int p = f[j + k], q = (ll)f[j + k + i / 2] * w[k] % mod;
				f[j + k] = (p + q) % mod, f[j + k + i / 2] = (p - q + mod) % mod;
			}
	}
}

poly poly::operator*(const poly& h) const {
	int N = 1;
	while (N < (int)(size() + h.size() - 1)) N <<= 1;
	std::vector<int> f(this->data), g(h.data);
	f.resize(N), g.resize(N);
	rev.resize(N);
	for (int i = 0; i < N; ++i)
		rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? N >> 1 : 0);
	dft_for_module(f, N, 1), dft_for_module(g, N, 1);
	for (int i = 0; i < N; ++i) f[i] = (ll)f[i] * g[i] % mod;
	dft_for_module(f, N, -1), f.resize(size() + h.size() - 1);
	for (int i = 0, inv = qpow(N, mod - 2); i < (int)f.size(); ++i)
		f[i] = (ll)f[i] * inv % mod;
	return f;
}

poly poly::operator*=(const poly& h) { return *this = *this * h; }

poly poly::operator*(const int& h) const {
	std::vector<int> f(this->data);
	for (int i = 0; i < (int)f.size(); ++i) f[i] = (ll)f[i] * h % mod;
	return f;
}

poly poly::operator*=(const int& h) {
	for (int i = 0; i < (int)size(); ++i) data[i] = (ll)data[i] * h % mod;
	return *this;
}

poly poly::operator+(const poly& h) const {
	std::vector<int> f(this->data);
	if (f.size() < h.size()) f.resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) f[i] = (f[i] + h[i]) % mod;
	return f;
}

poly poly::operator+=(const poly& h) {
	std::vector<int>& f = this->data;
	if (f.size() < h.size()) f.resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) f[i] = (f[i] + h[i]) % mod;
	return f;
}

poly poly::operator-(const poly& h) const {
	std::vector<int> f(this->data);
	if (f.size() < h.size()) f.resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) f[i] = (f[i] - h[i] + mod) % mod;
	return f;
}

poly poly::operator-=(const poly& h) {
	std::vector<int>& f = this->data;
	if (f.size() < h.size()) f.resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) f[i] = (f[i] - h[i] + mod) % mod;
	return f;
}

poly poly::operator<<(const std::size_t& b) const {
	std::vector<int> f(size() + b);
	for (int i = 0; i < (int)size(); ++i) f[i + b] = data[i];
	return f;
}

poly poly::operator<<=(const std::size_t& b) { return *this = (*this) << b; }

poly poly::operator>>(const std::size_t& b) const {
	std::vector<int> f(size() - b);
	for (int i = 0; i < (int)f.size(); ++i) f[i] = data[i + b];
	return f;
}

poly poly::operator>>=(const std::size_t& b) { return *this = (*this) >> b; }

poly poly::operator/(const int& h) const {
	std::vector<int> f(this->data);
	int inv = qpow(h, mod - 2);
	for (int i = 0; i < (int)f.size(); ++i) f[i] = (ll)f[i] * inv % mod;
	return f;
}

poly poly::operator/=(const int& h) {
	int inv = qpow(h, mod - 2);
	for (int i = 0; i < (int)data.size(); ++i) data[i] = (ll)data[i] * inv % mod;
	return *this;
}

poly poly::inv(void) const {
	int N = 1;
	while (N < (int)(size() + size() - 1)) N <<= 1;
	std::vector<int> f(N), g(N), d(this->data);
	d.resize(N), f[0] = qpow(d[0], mod - 2);
	for (int w = 2; w < N; w <<= 1) {
		for (int i = 0; i < w; ++i) g[i] = d[i];
		rev.resize(w << 1);
		for (int i = 0; i < w * 2; ++i)
			rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? w : 0);
		dft_for_module(f, w << 1, 1), dft_for_module(g, w << 1, 1);
		for (int i = 0; i < w * 2; ++i)
			f[i] = (ll)f[i] * (2 + mod - (ll)f[i] * g[i] % mod) % mod;
		dft_for_module(f, w << 1, -1);
		for (int i = 0, inv = qpow(w << 1, mod - 2); i < w; ++i)
			f[i] = (ll)f[i] * inv % mod;
		for (int i = w; i < w * 2; ++i) f[i] = 0;
	}
	f.resize(size());
	return f;
}

poly poly::operator==(const poly& h) const {
	if (size() != h.size()) return 0;
	for (int i = 0; i < (int)size(); ++i)
		if (data[i] != h[i]) return 0;
	return 1;
}

poly poly::operator!=(const poly& h) const {
	if (size() != h.size()) return 1;
	for (int i = 0; i < (int)size(); ++i)
		if (data[i] != h[i]) return 1;
	return 0;
}

poly poly::operator+(const int& h) const {
	poly f(this->data);
	f[0] = (f[0] + h) % mod;
	return f;
}

poly poly::operator+=(const int& h) { return *this = (*this) + h; }

poly poly::inv(const int& h) const {
	poly f(*this);
	f.resize(h);
	return f.inv();
}

int modsqrt(int h, int p = mod) { return 1; }

poly sqrt(const poly& h) {
	int N = 1;
	while (N < (int)(h.size() + h.size() - 1)) N <<= 1;
	poly f(N), g(N), d(h);
	d.resize(N), f[0] = modsqrt(d[0]);
	for (int w = 2; w < N; w <<= 1) {
		g.resize(w);
		for (int i = 0; i < w; ++i) g[i] = d[i];
		f = (f + f.inv(w) * g) / 2;
		f.resize(w);
	}
	f.resize(h.size());
	return f;
}

poly log(const poly& h) {
	poly f(h);
	for (int i = 1; i < (int)f.size(); ++i) f[i - 1] = (ll)f[i] * i % mod;
	f[f.size() - 1] = 0, f = f * h.inv(), f.resize(h.size());
	for (int i = (int)f.size() - 1; i > 0; --i)
		f[i] = (ll)f[i - 1] * qpow(i, mod - 2) % mod;
	f[0] = 0;
	return f;
}

poly exp(const poly& h) {
	int N = 1;
	while (N < (int)(h.size() + h.size() - 1)) N <<= 1;
	poly f(N), g(N), d(h);
	f[0] = 1, d.resize(N);
	for (int w = 2; w < N; w <<= 1) {
		f.resize(w), g.resize(w);
		for (int i = 0; i < w; ++i) g[i] = d[i];
		f = f * (g + 1 - log(f));
		f.resize(w);
	}
	f.resize(h.size());
	return f;
}

struct comp {
	long double x, y;

	comp(long double _x = 0, long double _y = 0) : x(_x), y(_y) {}

	comp operator*(const comp& b) const {
		return comp(x * b.x - y * b.y, x * b.y + y * b.x);
	}

	comp operator+(const comp& b) const { return comp(x + b.x, y + b.y); }

	comp operator-(const comp& b) const { return comp(x - b.x, y - b.y); }

	comp conj(void) { return comp(x, -y); }
};

const int EPS = 1e-9;

template <typename FLOAT_T>
FLOAT_T fabs(const FLOAT_T& x) {
	return x > 0 ? x : -x;
}

template <typename FLOAT_T>
FLOAT_T sin(const FLOAT_T& x, const long double& EPS = 1e-8) {
	FLOAT_T res = 0, delt = x;
	int d = 0;
	while (fabs(delt) > EPS) {
		res += delt, ++d;
		delt *= -x * x / ((2 * d) * (2 * d + 1));
	}
	return res;
}

template <typename FLOAT_T>
FLOAT_T cos(const FLOAT_T& x, const long double& EPS = 1e-8) {
	FLOAT_T res = 0, delt = 1;
	int d = 0;
	while (fabs(delt) > EPS) {
		res += delt, ++d;
		delt *= -x * x / ((2 * d) * (2 * d - 1));
	}
	return res;
}

const long double PI = std::acos((long double)(-1));

void dft_for_complex(std::vector<comp>& f, int n, int b) {
	static std::vector<comp> w;
	w.resize(n);
	for (int i = 0; i < n; ++i)
		if (i < rev[i]) std::swap(f[i], f[rev[i]]);
	for (int i = 2; i <= n; i <<= 1) {
		w[0] = comp(1, 0), w[1] = comp(cos(2 * PI / i), b * sin(2 * PI / i));
		for (int j = 2; j < i / 2; ++j) w[j] = w[j - 1] * w[1];
		for (int j = 0; j < n; j += i)
			for (int k = 0; k < i / 2; ++k) {
				comp p = f[j + k], q = f[j + k + i / 2] * w[k];
				f[j + k] = p + q, f[j + k + i / 2] = p - q;
			}
	}
}

class arbitrary_module_poly {
private:
	std::vector<int> data;

	int construct_element(int D, ll x, ll y, ll z) const {
		x %= mod, y %= mod, z %= mod;
		return ((ll)D * D * x % mod + (ll)D * y % mod + z) % mod;
	}

public:
	int mod;

	arbitrary_module_poly(std::size_t len = std::size_t(0),
		int module_value = 1e9 + 7) {
		mod = module_value;
		data = std::vector<int>(len);
	}

	arbitrary_module_poly(const std::vector<int>& b, int module_value = 1e9 + 7) {
		mod = module_value;
		data = b;
	}

	arbitrary_module_poly(const arbitrary_module_poly& b) {
		mod = b.mod;
		data = b.data;
	}

	void resize(std::size_t len, const int& val = 0) { data.resize(len, val); }

	std::size_t size(void) const { return data.size(); }

	void clear(void) { data.clear(); }
#if __cplusplus >= 201103L
	void shrink_to_fit(void) { data.shrink_to_fit(); }
#endif
	int& operator[](std::size_t b) { return data[b]; }

	const int& operator[](std::size_t b) const { return data[b]; }

	arbitrary_module_poly operator*(const arbitrary_module_poly& h) const;
	arbitrary_module_poly operator*=(const arbitrary_module_poly& h);
	arbitrary_module_poly operator*(const int& h) const;
	arbitrary_module_poly operator*=(const int& h);
	arbitrary_module_poly operator+(const arbitrary_module_poly& h) const;
	arbitrary_module_poly operator+=(const arbitrary_module_poly& h);
	arbitrary_module_poly operator-(const arbitrary_module_poly& h) const;
	arbitrary_module_poly operator-=(const arbitrary_module_poly& h);
	arbitrary_module_poly operator<<(const std::size_t& b) const;
	arbitrary_module_poly operator<<=(const std::size_t& b);
	arbitrary_module_poly operator>>(const std::size_t& b) const;
	arbitrary_module_poly operator>>=(const std::size_t& b);
	arbitrary_module_poly operator/(const int& h) const;
	arbitrary_module_poly operator/=(const int& h);
	arbitrary_module_poly operator==(const arbitrary_module_poly& h) const;
	arbitrary_module_poly operator!=(const arbitrary_module_poly& h) const;
	arbitrary_module_poly inv(void) const;
	arbitrary_module_poly inv(const int& h) const;
	friend arbitrary_module_poly sqrt(const arbitrary_module_poly& h);
	friend arbitrary_module_poly log(const arbitrary_module_poly& h);
};

arbitrary_module_poly arbitrary_module_poly::operator*(
	const arbitrary_module_poly& h) const {
	int N = 1;
	while (N < (int)(size() + h.size() - 1)) N <<= 1;
	std::vector<comp> f(N), g(N), p(N), q(N);
	const int D = std::sqrt(mod);
	for (int i = 0; i < (int)size(); ++i)
		f[i].x = data[i] / D, f[i].y = data[i] % D;
	for (int i = 0; i < (int)h.size(); ++i) g[i].x = h[i] / D, g[i].y = h[i] % D;
	rev.resize(N);
	for (int i = 0; i < N; ++i)
		rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? N >> 1 : 0);
	dft_for_complex(f, N, 1), dft_for_complex(g, N, 1);
	for (int i = 0; i < N; ++i) {
		p[i] = (f[i] + f[(N - i) % N].conj()) * comp(0.50, 0) * g[i];
		q[i] = (f[i] - f[(N - i) % N].conj()) * comp(0, -0.5) * g[i];
	}
	dft_for_complex(p, N, -1), dft_for_complex(q, N, -1);
	std::vector<int> r(size() + h.size() - 1);
	for (int i = 0; i < (int)r.size(); ++i)
		r[i] = construct_element(D, p[i].x / N + 0.5, (p[i].y + q[i].x) / N + 0.5,
			q[i].y / N + 0.5);
	return arbitrary_module_poly(r, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator*=(
	const arbitrary_module_poly& h) {
	return *this = *this * h;
}

arbitrary_module_poly arbitrary_module_poly::operator*(const int& h) const {
	std::vector<int> f(this->data);
	for (int i = 0; i < (int)f.size(); ++i) f[i] = (ll)f[i] * h % mod;
	return arbitrary_module_poly(f, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator*=(const int& h) {
	for (int i = 0; i < (int)size(); ++i) data[i] = (ll)data[i] * h % mod;
	return *this;
}

arbitrary_module_poly arbitrary_module_poly::operator+(
	const arbitrary_module_poly& h) const {
	std::vector<int> f(this->data);
	if (f.size() < h.size()) f.resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) f[i] = (f[i] + h[i]) % mod;
	return arbitrary_module_poly(f, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator+=(
	const arbitrary_module_poly& h) {
	if (size() < h.size()) resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) data[i] = (data[i] + h[i]) % mod;
	return *this;
}

arbitrary_module_poly arbitrary_module_poly::operator-(
	const arbitrary_module_poly& h) const {
	std::vector<int> f(this->data);
	if (f.size() < h.size()) f.resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i) f[i] = (f[i] + mod - h[i]) % mod;
	return arbitrary_module_poly(f, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator-=(
	const arbitrary_module_poly& h) {
	if (size() < h.size()) resize(h.size());
	for (int i = 0; i < (int)h.size(); ++i)
		data[i] = (data[i] + mod - h[i]) % mod;
	return *this;
}

arbitrary_module_poly arbitrary_module_poly::operator<<(
	const std::size_t& b) const {
	std::vector<int> f(size() + b);
	for (int i = 0; i < (int)size(); ++i) f[i + b] = data[i];
	return arbitrary_module_poly(f, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator<<=(const std::size_t& b) {
	return *this = (*this) << b;
}

arbitrary_module_poly arbitrary_module_poly::operator>>(
	const std::size_t& b) const {
	std::vector<int> f(size() - b);
	for (int i = 0; i < (int)f.size(); ++i) f[i] = data[i + b];
	return arbitrary_module_poly(f, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator>>=(const std::size_t& b) {
	return *this = (*this) >> b;
}

arbitrary_module_poly arbitrary_module_poly::inv(void) const {
	int N = 1;
	while (N < (int)(size() + size() - 1)) N <<= 1;
	arbitrary_module_poly f(1, mod), g(N, mod), h(*this), f2(1, mod);
	f[0] = qpow(data[0], mod - 2, mod), h.resize(N), f2[0] = 2;
	for (int w = 2; w < N; w <<= 1) {
		g.resize(w);
		for (int i = 0; i < w; ++i) g[i] = h[i];
		f = f * (f * g - f2) * (mod - 1);
		f.resize(w);
	}
	f.resize(size());
	return f;
}

arbitrary_module_poly arbitrary_module_poly::inv(const int& h) const {
	arbitrary_module_poly f(*this);
	f.resize(h);
	return f.inv();
}

arbitrary_module_poly arbitrary_module_poly::operator/(const int& h) const {
	int inv = qpow(h, mod - 2, mod);
	std::vector<int> f(this->data);
	for (int i = 0; i < (int)f.size(); ++i) f[i] = (ll)f[i] * inv % mod;
	return arbitrary_module_poly(f, mod);
}

arbitrary_module_poly arbitrary_module_poly::operator/=(const int& h) {
	int inv = qpow(h, mod - 2, mod);
	for (int i = 0; i < (int)size(); ++i) data[i] = (ll)data[i] * inv % mod;
	return *this;
}

arbitrary_module_poly arbitrary_module_poly::operator==(
	const arbitrary_module_poly& h) const {
	if (size() != h.size() || mod != h.mod) return 0;
	for (int i = 0; i < (int)size(); ++i)
		if (data[i] != h[i]) return 0;
	return 1;
}

arbitrary_module_poly arbitrary_module_poly::operator!=(
	const arbitrary_module_poly& h) const {
	if (size() != h.size() || mod != h.mod) return 1;
	for (int i = 0; i < (int)size(); ++i)
		if (data[i] != h[i]) return 1;
	return 0;
}

arbitrary_module_poly sqrt(const arbitrary_module_poly& h) {
	int N = 1;
	while (N < (int)(h.size() + h.size() - 1)) N <<= 1;
	arbitrary_module_poly f(1, mod), g(N, mod), d(h);
	f[0] = modsqrt(h[0], mod), d.resize(N);
	for (int w = 2; w < N; w <<= 1) {
		g.resize(w);
		for (int i = 0; i < w; ++i) g[i] = d[i];
		f = (f + f.inv(w) * g) / 2;
		f.resize(w);
	}
	f.resize(h.size());
	return f;
}

arbitrary_module_poly log(const arbitrary_module_poly& h) {
	arbitrary_module_poly f(h);
	for (int i = 1; i < (int)f.size(); ++i) f[i - 1] = (ll)f[i] * i % f.mod;
	f[f.size() - 1] = 0, f = f * h.inv(), f.resize(h.size());
	for (int i = (int)f.size() - 1; i > 0; --i)
		f[i] = (ll)f[i - 1] * qpow(i, f.mod - 2, f.mod) % f.mod;
	f[0] = 0;
	return f;
}

using m_poly = arbitrary_module_poly;

struct custom_hash
{
	static uint64_t splitmix64(uint64_t x) {
		x ^= x << 13;
		x ^= x >> 7;
		x ^= x << 17;
		return x;
	}
	size_t operator () (uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); // 时间戳
		return splitmix64(x + FIXED_RANDOM);
	}
};

constexpr int M = 5;

struct Matrix
{
	array<array<int, M>, M> v;
	Matrix()
	{
		for (int i = 0; i < M; i++) v[i].fill(0);
	}
	void CLEAR()
	{
		for (int i = 0; i < M; i++) v[i].fill(0);
	}
	friend Matrix operator*(const Matrix& a, const Matrix& b) noexcept
	{
		Matrix c;
		for (int i = 0; i < M; i++)
		{
			for (int j = 0; j < M; j++)
			{
				for (int k = 0; k < M; k++)
				{
					c.v[i][j] = (c.v[i][j] + 1ll * a.v[i][k] * b.v[k][j] % MOD) % MOD;
				}
			}
		}
		return c;
	}
};

/*
struct FastMod
{
	using ull=unsigned long long;
	using L=__int128;
	ull b,m;
	FastMod(ull b):b(b),m(ull((L(1)<<64)/b)){}
	ull reduce(ull a)// return a mod b
	{
		ull q=(ull)((L(m)*a)>>64),r=a-q*b;
		return r>=b?r-b:r;
	}
}F(330); // change the MOD*/

class Union_Find
{
public:
	array<int, N> fa;
	void Init()
	{
		for (int i = 0; i < N; i++) fa[i] = i;
	}
	int find(int u)
	{
		return (fa[u] == u ? u : fa[u] = find(fa[u]));
	}
	void merge(int u, int v)
	{
		fa[find(u)] = find(v);
	}
}uf;

struct tws
{
	ll v1, v2;
	tws() = default;
	tws(ll x, ll y) :v1(x), v2(y) {}
	bool operator==(const tws x) const
	{
		return (v1 == x.v1 && v2 == x.v2);
	}
	bool operator!=(const tws x) const
	{
		return (v1 != x.v1 || v2 != x.v2);
	}
	tws operator+(const ll x)
	{
		return tws((v1 + x) % HSMOD, (v2 + x) % HSMOD2);
	}
	tws operator-(const ll x)
	{
		return tws((v1 - x + HSMOD) % HSMOD, (v2 - x + HSMOD2) % HSMOD2);
	}
	tws operator-(const tws x)
	{
		return tws((v1 - x.v1 + HSMOD) % HSMOD, (v2 - x.v2 + HSMOD2) % HSMOD2);
	}
	tws operator*(const ll x)
	{
		return tws((v1 * x) % HSMOD, (v2 * x) % HSMOD2);
	}
	tws operator+(const tws x)
	{
		return tws((v1 + x.v1) % HSMOD, (v2 + x.v2) % HSMOD2);
	}
	tws operator*(const tws x)
	{
		return tws((v1 * x.v1) % HSMOD, (v2 * x.v2) % HSMOD2);
	}
};

long long fspow(long long a, long long b)
{
	long long res = 1ll, base = a;
	while (b)
	{
		if (b & 1ll) res = res * base % MOD;
		base = base * base % MOD;
		b >>= 1ll;
	}
	return res;
}

double dist(double X0, double Y0, double X1, double Y1)
{
	return sqrt((X0 - X1) * (X0 - X1) + (Y0 - Y1) * (Y0 - Y1));
}

inline bool isprime(int x)
{
	if (x == 1) return 0;
	for (int i = 2; 1ll * i * i <= x; i++) if (x % i == 0) return 0;
	return 1;
}

int t, n;
ll m;
array<int, N> b;

int main()
{
	//freopen("*.in", "r", stdin);
	//freopen("*.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		int ec = m / n;
		for (int i = 1; i <= n; i++)
		{
			cin >> b[i];
			b[i] -= ec;
		}
		poly ve;
		ve.resize(2 * n + 1);
		for (int i = 1; i <= n; i++) ve[b[i] + n]++;
		poly res, base = ve;
		res.resize(2 * n + 1);
		res[n] = 1;
		int x = n;
		while (x)
		{
			if (x & 1)
			{
				res = res * base;
				poly nr;
				nr.resize(2 * n + 1);
				for (int i = 0; i < res.size(); i++)
				{
					int nj = i - 2 * n;
					if (nj >= -n && nj <= n) nr[nj + n] += res[i];
				}
				res = nr;
			}
			base = base * base;
			poly nr;
			nr.resize(2 * n + 1);
			for (int i = 0; i < base.size(); i++)
			{
				int nj = i - 2 * n;
				if (nj >= -n && nj <= n) nr[nj + n] += base[i];
			}
			base = nr;
			x >>= 1;
		}
		cout << (res[n + m % n] ? "Yes\n" : "No\n");
	}
	return 0;
}

/*
1
5 25
0 1 2 3 4
*/