#ifndef HIDDEN_IN_VS // 折りたたみ用

// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS

// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;

// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
using pii = pair<int, int>;	using pll = pair<ll, ll>;	using pil = pair<int, ll>;	using pli = pair<ll, int>;
using vi = vector<int>;		using vvi = vector<vi>;		using vvvi = vector<vvi>;	using vvvvi = vector<vvvi>;
using vl = vector<ll>;		using vvl = vector<vl>;		using vvvl = vector<vvl>;	using vvvvl = vector<vvvl>;
using vb = vector<bool>;	using vvb = vector<vb>;		using vvvb = vector<vvb>;
using vc = vector<char>;	using vvc = vector<vc>;		using vvvc = vector<vvc>;
using vd = vector<double>;	using vvd = vector<vd>;		using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;

// 定数の定義
const double PI = acos(-1);
int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;

// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;

// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x)))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x)))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定

// 汎用関数の定義
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline int getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod

// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }

#endif // 折りたたみ用


#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;

#ifdef _MSC_VER
#include "localACL.hpp"
#endif

//using mint = modint998244353;
using mint = static_modint<(int)1e9+7>;
//using mint = modint; // mint::set_mod(m);

using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif


#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
int mute_dump = 0;
int frac_print = 0;
#if __has_include(<atcoder/all>)
namespace atcoder {
	inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
	inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
#endif
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す
#endif


//【線形漸化式の発見】O(n^2)
/*
* 与えられた数列 a[0..n) に対し，以下の等式を満たす c[0..m) で m を最小とするものを返す：
*		a[i] = Σj∈[0..m) c[j] a[i-1-j]  (∀i∈[m..n))
*
* 制約 : mint::mod は大きい素数
*/
vm berlekamp_massey(const vm& a) {
	// 参考 : https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm
	// verify : https://judge.yosupo.jp/problem/find_linear_recurrence

	vm S(a), C{ 1 }, B{ 1 };
	int N = sz(a), m = 1; mint b = 1;

	rep(n, N) {
		mint d = 0;
		rep(i, sz(C)) d += C[i] * S[n - i];

		if (d == 0) {
			m++;
		}
		else if (2 * (sz(C) - 1) <= n) {
			vm T(C);

			mint coef = d * b.inv();
			C.resize(max(sz(C), sz(B) + m));
			rep(j, sz(B)) C[j + m] -= coef * B[j];

			B = T;
			b = d;
			m = 1;
		}
		else {
			mint coef = d * b.inv();
			C.resize(max(sz(C), sz(B) + m));
			rep(j, sz(B)) C[j + m] -= coef * B[j];

			m++;
		}
	}

	C.erase(C.begin());
	rep(i, sz(C)) C[i] *= -1;

	return C;
}


//【畳込み（素朴）】O(n m)
/*
* a[0..n) と b[0..m) を畳み込んだ数列 c[0..n+m-1) を返す．
* すなわち c[k] = Σ_(i+j=k) a[i] b[j] である．
*/
template <class T>
vector<T> naive_convolution(const vector<T>& a, const vector<T>& b) {
	// verify : https://atcoder.jp/contests/abc214/tasks/abc214_g

	int n = sz(a), m = sz(b);
	if (n == 0 || m == 0) return vector<T>();

	// c[k] = Σ_(i+j=k) a[i] b[j]
	vector<T> c(n + m - 1);
	if (n < m) {
		rep(i, n) rep(j, m) c[i + j] += a[i] * b[j];
	}
	else {
		rep(j, m) rep(i, n) c[i + j] += a[i] * b[j];
	}

	return c;
}


//【形式的冪級数】
/*
* MFPS() : O(1)
*	零多項式 f = 0 で初期化する．
*
* MFPS(mint c0) : O(1)
*	定数多項式 f = c0 で初期化する．
*
* MFPS(mint c0, int n) : O(n)
*	n 次未満の項をもつ定数多項式 f = c0 で初期化する．
*
* MFPS(vm c) : O(n)
*	f(z) = c[0] + c[1] z + ... + c[n - 1] z^(n-1) で初期化する．
*
* set_conv(vm(*CONV)(const vm&, const vm&)) : O(1)
*	畳込み用の関数を CONV に設定する．
*
* c + f, f + c : O(1)	f + g : O(n)
* f - c : O(1)			c - f, f - g, -f : O(n)
* c * f, f * c : O(n)	f * g : O(n log n)		f * g_sp : O(n |g|)
* f / c : O(n)			f / g : O(n log n)		f / g_sp : O(n |g|)
*	形式的冪級数としての和，差，積，商の結果を返す．
*	g_sp はスパース多項式であり，{次数, 係数} の次数昇順の組の vector で表す．
*	制約 : 商では g(0) != 0
*
* MFPS f.inv(int d) : O(n log n)
*	1 / f mod z^d を返す．
*	制約 : f(0) != 0
*
* MFPS f.quotient(MFPS g) : O(n log n)
* MFPS f.reminder(MFPS g) : O(n log n)
* pair<MFPS, MFPS> f.quotient_remainder(MFPS g) : O(n log n)
*	多項式としての f を g で割った商，余り，商と余りの組を返す．
*	制約 : g の最高次の係数は 0 でない
*
* int f.deg(), int f.size() : O(1)
*	多項式 f の次数[項数]を返す．
*
* MFPS::monomial(int d, mint c = 1) : O(d)
*	単項式 c z^d を返す．
*
* mint f.assign(mint c) : O(n)
*	多項式 f の不定元 z に c を代入した値を返す．
*
* f.resize(int d) : O(1)
*	mod z^d をとる．
*
* f.resize() : O(n)
*	不要な高次の項を削る．
*
* f >> d, f << d : O(n)
*	係数列を d だけ右[左]シフトした多項式を返す．
*  （右シフトは z^d の乗算，左シフトは z^d で割った商と等価）
*
* f.push_back(c) : O(1)
*	最高次の係数として c を追加する．
*/
struct MFPS {
	using SMFPS = vector<pim>;

	int n; // 係数の個数（次数 + 1）
	vm c; // 係数列
	inline static vm(*CONV)(const vm&, const vm&) = convolution; // 畳込み用の関数

	// コンストラクタ（0，定数，係数列で初期化）
	MFPS() : n(0) {}
	MFPS(mint c0) : n(1), c({ c0 }) {}
	MFPS(int c0) : n(1), c({ mint(c0) }) {}
	MFPS(mint c0, int d) : n(d), c(n) { if (n > 0) c[0] = c0; }
	MFPS(int c0, int d) : n(d), c(n) { if (n > 0) c[0] = c0; }
	MFPS(const vm& c_) : n(sz(c_)), c(c_) {}
	MFPS(const vi& c_) : n(sz(c_)), c(n) { rep(i, n) c[i] = c_[i]; }

	// 代入
	MFPS(const MFPS& f) = default;
	MFPS& operator=(const MFPS& f) = default;
	MFPS& operator=(const mint& c0) { n = 1; c = { c0 }; return *this; }

	void push_back(mint cn) { c.emplace_back(cn); ++n; }
	void pop_back() { c.pop_back(); --n; }
	[[nodiscard]] mint back() { return c.back(); }

	// 比較
	[[nodiscard]] bool operator==(const MFPS& g) const { return c == g.c; }
	[[nodiscard]] bool operator!=(const MFPS& g) const { return c != g.c; }

	// アクセス
	inline mint const& operator[](int i) const { return c[i]; }
	inline mint& operator[](int i) { return c[i]; }

	// 次数
	[[nodiscard]] int deg() const { return n - 1; }
	[[nodiscard]] int size() const { return n; }

	static void set_conv(vm(*CONV_)(const vm&, const vm&)) {
		// verify : https://atcoder.jp/contests/tdpc/tasks/tdpc_fibonacci

		CONV = CONV_;
	}

	// 加算
	MFPS& operator+=(const MFPS& g) {
		if (n >= g.n) rep(i, g.n) c[i] += g.c[i];
		else {
			rep(i, n) c[i] += g.c[i];
			repi(i, n, g.n - 1)	c.push_back(g.c[i]);
			n = g.n;
		}
		return *this;
	}
	[[nodiscard]] MFPS operator+(const MFPS& g) const { return MFPS(*this) += g; }

	// 定数加算
	MFPS& operator+=(const mint& sc) {
		if (n == 0) { n = 1; c = { sc }; }
		else { c[0] += sc; }
		return *this;
	}
	[[nodiscard]] MFPS operator+(const mint& sc) const { return MFPS(*this) += sc; }
	[[nodiscard]] friend MFPS operator+(const mint& sc, const MFPS& f) { return f + sc; }
	MFPS& operator+=(const int& sc) { *this += mint(sc); return *this; }
	[[nodiscard]] MFPS operator+(const int& sc) const { return MFPS(*this) += sc; }
	[[nodiscard]] friend MFPS operator+(const int& sc, const MFPS& f) { return f + sc; }

	// 減算
	MFPS& operator-=(const MFPS& g) {
		if (n >= g.n) rep(i, g.n) c[i] -= g.c[i];
		else {
			rep(i, n) c[i] -= g.c[i];
			repi(i, n, g.n - 1) c.push_back(-g.c[i]);
			n = g.n;
		}
		return *this;
	}
	[[nodiscard]] MFPS operator-(const MFPS& g) const { return MFPS(*this) -= g; }

	// 定数減算
	MFPS& operator-=(const mint& sc) { *this += -sc; return *this; }
	[[nodiscard]] MFPS operator-(const mint& sc) const { return MFPS(*this) -= sc; }
	[[nodiscard]] friend MFPS operator-(const mint& sc, const MFPS& f) { return -(f - sc); }
	MFPS& operator-=(const int& sc) { *this += -sc; return *this; }
	[[nodiscard]] MFPS operator-(const int& sc) const { return MFPS(*this) -= sc; }
	[[nodiscard]] friend MFPS operator-(const int& sc, const MFPS& f) { return -(f - sc); }

	// 加法逆元
	[[nodiscard]] MFPS operator-() const { return MFPS(*this) *= -1; }

	// 定数倍
	MFPS& operator*=(const mint& sc) { rep(i, n) c[i] *= sc; return *this; }
	[[nodiscard]] MFPS operator*(const mint& sc) const { return MFPS(*this) *= sc; }
	[[nodiscard]] friend MFPS operator*(const mint& sc, const MFPS& f) { return f * sc; }
	MFPS& operator*=(const int& sc) { *this *= mint(sc); return *this; }
	[[nodiscard]] MFPS operator*(const int& sc) const { return MFPS(*this) *= sc; }
	[[nodiscard]] friend MFPS operator*(const int& sc, const MFPS& f) { return f * sc; }

	// 右からの定数除算
	MFPS& operator/=(const mint& sc) { *this *= sc.inv(); return *this; }
	[[nodiscard]] MFPS operator/(const mint& sc) const { return MFPS(*this) /= sc; }
	MFPS& operator/=(const int& sc) { *this /= mint(sc); return *this; }
	[[nodiscard]] MFPS operator/(const int& sc) const { return MFPS(*this) /= sc; }

	// 積
	MFPS& operator*=(const MFPS& g) { c = CONV(c, g.c); n = sz(c); return *this; }
	[[nodiscard]] MFPS operator*(const MFPS& g) const { return MFPS(*this) *= g; }

	// 除算
	[[nodiscard]] MFPS inv(int d) const {
		// 参考：https://nyaannyaan.github.io/library/fps/formal-power-series.hpp
		// verify : https://judge.yosupo.jp/problem/inv_of_formal_power_series

		//【方法】
		// 1 / f mod z^d を求めることは，
		//		f g = 1 (mod z^d)
		// なる g を求めることである．
		// この d の部分を 1, 2, 4, ..., 2^i と倍々にして求めていく．
		//
		// d = 1 のときについては
		//		g = 1 / f[0] (mod z^1)
		// である．
		//
		// 次に，
		//		g = h (mod z^k)
		// が求まっているとして
		//		g mod z^(2 k)
		// を求める．最初の式を変形していくことで
		//		g - h = 0 (mod z^k)
		//		⇒ (g - h)^2 = 0 (mod z^(2 k))
		//		⇔ g^2 - 2 g h + h^2 = 0 (mod z^(2 k))
		//		⇒ f g^2 - 2 f g h + f h^2 = 0 (mod z^(2 k))
		//		⇔ g - 2 h + f h^2 = 0 (mod z^(2 k)) 　(f g = 1 (mod z^d) より)
		//		⇔ g = (2 - f h) h (mod z^(2 k))
		// を得る．
		//
		// この手順を d ≦ 2^i となる i まで繰り返し，d 次以上の項を削除すればよい．

		Assert(!c.empty());
		Assert(c[0] != 0);

		MFPS g(c[0].inv());
		for (int k = 1; k < d; k <<= 1) {
			int len = max(min(2 * k, d), 1);
			MFPS tmp(0, len);
			rep(i, min(len, n)) tmp[i] = -c[i];	// -f
			tmp *= g;							// -f h
			tmp.resize(len);
			tmp[0] += 2;						// 2 - f h
			g *= tmp;							// (2 - f h) h
			g.resize(len);
		}

		return g;
	}
	MFPS& operator/=(const MFPS& g) { return *this *= g.inv(max(n, g.n)); }
	[[nodiscard]] MFPS operator/(const MFPS& g) const { return MFPS(*this) /= g; }

	// 余り付き除算
	[[nodiscard]] MFPS quotient(const MFPS& g) const {
		// 参考 : https://nyaannyaan.github.io/library/fps/formal-power-series.hpp
		// verify : https://judge.yosupo.jp/problem/division_of_polynomials

		//【方法】
		// f(x) = g(x) q(x) + r(x) となる q(x) を求める．
		// f の次数は n-1, g の次数は m-1 とする．(n ≧ m)
		// 従って q の次数は n-m，r の次数は m-2 となる．
		// 
		// f^R で f の係数列を逆順にした多項式を表す．すなわち
		//		f^R(x) := f(1/x) x^(n-1)
		// である．他の多項式も同様とする．
		//
		// 最初の式で x → 1/x と置き換えると，
		//		f(1/x) = g(1/x) q(1/x) + r(1/x)
		//		⇔ f(1/x) x^(n-1) = g(1/x) q(1/x) x^(n-1) + r(1/x) x^(n-1)
		//		⇔ f(1/x) x^(n-1) = g(1/x) x^(m-1) q(1/x) x^(n-m) + r(1/x) x^(m-2) x^(n-m+1)
		//		⇔ f^R(x) = g^R(x) q^R(x) + r^R(x) x^(n-m+1)
		//		⇒ f^R(x) = g^R(x) q^R(x) (mod x^(n-m+1))
		// 	    ⇒ q^R(x) = f^R(x) / g^R(x)  (mod x^(n-m+1))
		// を得る．
		// 	   
		// これで q を mod x^(n-m+1) で正しく求めることができることになるが，
		// q の次数は n-m であったから，q 自身を正しく求めることができた．

		if (n < g.n) return MFPS();
		return ((this->rev() / g.rev()).resize(n - g.n + 1)).rev();
	}
	[[nodiscard]] MFPS reminder(const MFPS& g) const {
		// verify : https://judge.yosupo.jp/problem/division_of_polynomials

		return (*this - this->quotient(g) * g).resize();
	}
	[[nodiscard]] pair<MFPS, MFPS> quotient_remainder(const MFPS& g) const {
		// verify : https://judge.yosupo.jp/problem/division_of_polynomials

		pair<MFPS, MFPS> res;
		res.first = this->quotient(g);
		res.second = (*this - res.first * g).resize();
		return res;
	}

	// スパース積
	MFPS& operator*=(const SMFPS& g) {
		// g の定数項だけ例外処理
		auto it0 = g.begin();
		mint g0 = 0;
		if (it0->first == 0) {
			g0 = it0->second;
			it0++;
		}

		// 後ろからインライン配る DP
		repir(i, n - 1, 0) {
			// 上位項に係数倍して配っていく．
			for (auto it = it0; it != g.end(); it++) {
				auto [j, gj] = *it;

				if (i + j >= n) break;

				c[i + j] += c[i] * gj;
			}

			// 定数項は最後に配るか消去しないといけない．
			c[i] *= g0;
		}

		return *this;
	}
	[[nodiscard]] MFPS operator*(const SMFPS& g) const { return MFPS(*this) *= g; }

	// スパース商
	MFPS& operator/=(const SMFPS& g) {
		// g の定数項だけ例外処理
		auto it0 = g.begin();
		Assert(it0->first == 0 && it0->second != 0);
		mint g0_inv = it0->second.inv();
		it0++;

		// 前からインライン配る DP（後ろに累積効果あり）
		rep(i, n) {

			// 定数項は最初に配らないといけない．
			c[i] *= g0_inv;

			// 上位項に係数倍して配っていく．
			for (auto it = it0; it != g.end(); it++) {
				auto [j, gj] = *it;

				if (i + j >= n) break;

				c[i + j] -= c[i] * gj;
			}
		}

		return *this;
	}
	[[nodiscard]] MFPS operator/(const SMFPS& g) const { return MFPS(*this) /= g; }

	// 係数反転
	[[nodiscard]] MFPS rev() const { MFPS h = *this; reverse(all(h.c)); return h; }

	// 単項式
	[[nodiscard]] static MFPS monomial(int d, mint coef = 1) {
		MFPS mono(0, d + 1);
		mono[d] = coef;
		return mono;
	}

	// 不要な高次項の除去
	MFPS& resize() {
		// 最高次の係数が非 0 になるまで削る．
		while (n > 0 && c[n - 1] == 0) {
			c.pop_back();
			n--;
		}
		return *this;
	}

	// x^d 以上の項を除去する．
	MFPS& resize(int d) {
		n = d;
		c.resize(d);
		return *this;
	}

	// 不定元への代入
	[[nodiscard]] mint assign(const mint& x) const {
		mint val = 0;
		repir(i, n - 1, 0) val = val * x + c[i];
		return val;
	}

	// 係数のシフト
	MFPS& operator>>=(int d) {
		n += d;
		c.insert(c.begin(), d, 0);
		return *this;
	}
	MFPS& operator<<=(int d) {
		n -= d;
		if (n <= 0) { c.clear(); n = 0; }
		else c.erase(c.begin(), c.begin() + d);
		return *this;
	}
	[[nodiscard]] MFPS operator>>(int d) const { return MFPS(*this) >>= d; }
	[[nodiscard]] MFPS operator<<(int d) const { return MFPS(*this) <<= d; }

#ifdef _MSC_VER
	friend ostream& operator<<(ostream& os, const MFPS& f) {
		if (f.n == 0) os << 0;
		else {
			rep(i, f.n) {
				os << f[i] << "z^" << i;
				if (i < f.n - 1) os << " + ";
			}
		}
		return os;
	}
#endif
};


//【展開係数】O(n log n log N)
/*
* [z^N] f(z)/g(z) を返す．
*
* 制約 : deg f < deg g, g[0] ≠ 0
*/
mint bostan_mori(MFPS f, MFPS g, ll N) {
	// 参考 : http://q.c.titech.ac.jp/docs/progs/polynomial_division.html
	// verify : https://judge.yosupo.jp/problem/kth_term_of_linearly_recurrent_sequence

	//【方法】
	// 分母分子に g(-z) を掛けることにより
	//		f(z) / g(z) = f(z) g(-z) / g(z) g(-z)
	// を得る．ここで g(z) g(-z) は偶多項式なので
	//		g(z) g(-z) = e(z^2)
	// と表すことができる．
	// 
	// 分子について
	//		f(z) g(-z) = E(z^2) + z O(z^2)
	// というように偶多項式部分と奇多項式部分に分けると，N が偶数のときは
	//		[z^N] f(z) g(-z) / g(z) g(-z)
	//		= [z^N] E(z^2) / e(z^2)
	//		= [z^(N/2)] E(z) / e(z)
	// となり，N が奇数のときは
	//		[z^N] f(z) g(-z) / g(z) g(-z)
	//		= [z^N] z O(z^2) / e(z^2)
	//		= [z^((N-1)/2)] O(z) / e(z)
	// となる．
	//
	// これを繰り返せば N を半分ずつに減らしていくことができる．

	Assert(g.n >= 1 && g[0] != 0);

	// f(z) = 0 のときは 0 を返す．
	if (f.n == 0) return 0;

	while (N > 0) {
		// f2(z) = f(z) g(-z), g2(z) = g(z) g(-z) を求める．
		MFPS f2, g2 = g;
		rep(i, g2.n) if (i & 1) g2[i] *= -1;
		f2 = f * g2;
		g2 *= g;

		// f3(z) = E(z) or O(z), g3(z) = e(z) を求める．
		f.c.clear(); g.c.clear();
		if (N & 1) rep(i, min<ll>(f2.n / 2, N / 2 + 1)) f.c.push_back(f2[2 * i + 1]);
		else rep(i, min<ll>((f2.n + 1) / 2, N / 2 + 1)) f.c.push_back(f2[2 * i]);
		f.n = sz(f.c);
		rep(i, min<ll>((g2.n + 1) / 2, N / 2 + 1)) g.c.push_back(g2[2 * i]);
		g.n = sz(g.c);

		// N を半分にして次のステップに進む．
		N /= 2;
	}

	// N = 0 になったら定数項を返す．
	return f[0] / g[0];
}


//【線形漸化式】O(n log n log N)
/*
* 初項 a[0..n) と漸化式 a[i] = Σj∈[0..n) c[j] a[i-1-j] で定義される
* 数列 a について，a[N] の値を返す．
*
* 利用：【展開係数】
*/
mint linearly_recurrent_sequence(const vm& a, const vm& c, ll N) {
	// verify : https://judge.yosupo.jp/problem/kth_term_of_linearly_recurrent_sequence

	int n = sz(c);
	if (n == 0) return 0;

	MFPS A(a), C(c);
	MFPS Dnm = 1 - (C >> 1);
	MFPS Num = (Dnm * A).resize(n);
	return bostan_mori(Num, Dnm, N);
}


vm seq1 = { 1,2,4,7,11,16 };
vm seq2 = { 1,4,14,41,109,276,682,1665 };
vm seq3 = { 1,7,41,219,1127,5727,28993,146643,741557,3749817,18961451,95880895,484833213,451616851,396892233,686360043 }; 
vm seq4 = { 1,11,109,1127,11507,116167,1168587,11749135,118127409,187692416,941503422,64334503,171422004,349404640,414370692,229496054,914944380,534647147,212952523,902520682,724503479,619605103,166273791,619390877,836310386,686953732,577520664,729784802 }; 
vm seq5 = { 1,16,276,5727,116167,2301878,45280510,889477657,470102990,131617801,543346539,672693082,528691885,433100320,259856353,631703747,121492785,65000964,67868822,431503521,556143264,898859210,822402658,746831348,942022315,42461887,245383966,159194956,442319966,719053965,735342088,986228636,385914411,746460381,499191315,294132891,429534326,53306516,69797920,520148742,67524591,131525007,212068790,48189164,744481803,784588218,472300216,20257574,506104403,129522485,887689194,43853834,543027099,470146769,95649761,578040017,125364573,32787915,139313991,713541878,395048005,58211161,741163083,279667842,863539084,628324241 };
vm seq6 = { 1,22,682,28993,1168587,45280510,732082735,37461993,885687206,403247904,630794367,96311200,188560386,132214958,81864960,656832814,129969438,337127918,885747692,994734032,901081507,113735511,330166804,692897483,221245903,823578679,149151768,513212824,565413379,343413793,552163985,401017126,775469315,768705742,822998670,524634566,141276344,644398113,617812250,791340224,983870516,203398183,625614816,683890376,368195929,142285465,986226418,160965036,405204828,206471234,652493151,587867821,808610902,707659601,22802537,445444836,187616184,160982745,457176051,436730257,169883894,240716121,405440670,340484061,656210818,36771328,96126499,306426250,814430156,444930213,988328254,540530996,382743353,520556012,247236453,220449494,166029982,836928893,713012423,954252271,210134678,648105609,574260822,257748963,442563485,914128914,335893402,10612420,644215156,701674252,791425434,275022107,639393770,990275299,335101603,666947296,13086670,924423723,440358686,58917455,854634654,222563676,986452945,446560407,446339800,591900595,128960648,452436635,623814115,525257516,200495504,761757852,718952410,535847883,645061700,693963654,46678720,466133475,594295563,399559392,11097963,461778955,483386288,217580795,516089911,909297530,427249010,903830873,948864755,417535750,861690115,993338478,163694489,704688998,410415746,819049618,768562309,219587991,988235141,638477010,906083356,986424231 };
vm seq7 = { 1,29,1665,146643,11749135,889477657,37461993,949940563,34890375,408395780,465431124,169444073,476095425,659247955,873440608,926228359,615656155,946323265,52968125,753942505,466886221,131497624,574943443,651491967,558045774,251030381,281770572,626734328,538734010,338782740,544266405,882070772,638524753,866251040,377115308,677270991,923683804,407681395,135644898,799433051,734586419,252356852,562319012,202766612,459305662,237631149,937873189,999735042,471421438,196454675,548587823,155433695,513218159,425727802,201766012,618282734,853358525,794224020,317787455,420202006,208101996,561508158,165138108,680690786,440574803,642204070,1519936,740668821,993620893,358321041,609591538,544950608,452208171,885834625,821590677,398458088,516061105,713420419,988022778,345184827,285034176,821685365,13669477,704448104,129864473,272789357,791468168,22642556,191074949,725893031,621310462,91319076,716141216,100651621,124026882,366140816,685675712,544588614,31892810,733368800,814661721,416829951,25354706,920576065,404858751,224503154,408647841,32879425,449601452,954308701,384324117,674296839,792515238,188224956,323348586,972509241,558237932,478379645,769454590,5532216,665030505,378063245,50177023,152536856,592607000,936002696,561844588,98320628,393845744,234288388,975460551,94761065,230083311,437478028,493404366,809166707,952865396,30537949,269093030,454344597,528546170,743583992,647074730,593751774,863574929,753557945,354148308,464934710,275033860,450276862,375178857,24286588,880771044,120621726,710396663,135056588,742687866,845401043,8181487,277891375,585736420,570298111,955283695,601817564,141857658,613931528,134904118,127307581,914760873,56527074,515151065,85256391,867641312,644658124,516456197,546485054,695768128,950249036,737354236,328196922,664437559,654797168,540686072,250077161,487287553,591837922,979485088,490297243,633678447,990298549,379642971,702481129,584942894,361720239,825880867,772590736,172182905,754431547,299502653,249050692,335001905,230296478,624204289,692367469,559310444,838878898,487986150,566227277,518043210,592538137,138670607,504405050,252553467,871876659,899807948,483430874,691627538,222857970,795092245,368293696,768052891,697322359,573816333,825591678,652492802,526261994,975704776,677628082,116620384,439967591,362128952,672319243,574102272,350904082,199464685,849463039,886655362,223485421,319695723,767450462,688429207,598751130,225406155,353550553,98188262,962586133,351427960,41167574,126283439,801928141,530774618,44264408,602460016,61008883,302058087,906154633,231505142,652491962,47839346,55293957,145231826,307920924,408202726,510473598,75219689,157343986,917480790,103605311,842950391,101027708,28793071,717261126,758732083,158282974,502041349,88400442,587778290,226310005,574669992,764559582,756363640,614962462,790643572,149324329,145554686,437398155,438739803,922467739,388741007,833892012,180024032,324080540,286487276,308749487,290106847,520867997,591917944,627868972,364622579,921885726,965742314,948877023,704039083,956113452,678857978,321401848,167938673,393856198,808025504,320963439,706550785,844136493,669955529,297253669,394528416,834378235,984963757,943035613,889279747,691625658,151511815,633374999,11156662,177860661,526965345,720117943,677315005,43154459,29163606,704506503,683525033,315857848,191280598,827302312,699421299,212010428,794556815,913280490,139164874,268649426,876508476,417530150,801828701,557926860,663339430,431411357,247878362,567938232,396918036,536975308,23869545,213323066,829981562,293484930,745338800,612848889,700199509,304928069,637237107,510637207 };
vm seq8 = { 1,37,4041,741557,118127409,470102990,885687206,34890375,247777017,233426111,328755372,705627254,787442873,382905969,14599214,54410762,601006293,612557412,15449457,990194964,286282086,699722726,781620770,840139027,489073873,334785850,435236312,109774735,741619355,198733962,979223832,316303899,39151098,758722724,846456338,302710768,751509520,910422867,269441529,739223080,47041873,144990979,835832182,94144833,432122372,718847362,143249506,202420880,524474078,175432351,259981776,949834435,650788362,314338902,308488394,925015946,735629953,55340123,870087005,914406438,652461933,824517284,13384792,734924499,195917203,347913013,345009224,72962602,728865666,529666844,443583544,797807891,499559113,582526184,750449604,794171250,339435368,795879915,610395114,651525516,665256280,771083633,124044839,103256299,555278858,168723783,37135887,926137425,193565945,44104252,848927129,311714531,740363206,103826477,426742611,675142275,731839744,444416324,663478469,724122697,351972778,394976530,438819548,910482233,104665902,409225877,167205683,514913256,760105146,29299319,710711306,114816264,854763815,393789741,110116603,971095518,965304628,656067528,345333182,54369788,393350948,645767329,278297448,584309443,643959647,760481448,306899118,556007297,90782545,501999192,487093903,851119020,214855165,290938705,483935412,931413699,87706721,543982302,557974405,993894345,617966932,450284947,530064542,635450111,955879321,855098871,534537884,745899212,102957102,662330956,760521287,880202514,410332360,896841551,21942389,327590994,607470932,510274102,755158990,271684725,681115729,979634386,116288825,441075063,869557220,498624605,668265456,563569497,411144208,372553916,26571456,299681787,483501146,332251238,514296632,262088006,767350801,242709546,312245271,625558061,630739737,166453362,987400269,534085289,177342294,635886217,360697927,830064108,142999668,796390631,541632627,524331980,832128251,56784303,599770935,420185003,36118709,960687381,886180311,494123323,256629997,167297431,422622752,387880448,805197258,990906674,197392118,409215678,751867400,114891718,20016318,539423304,506437723,420323844,17970684,326175156,607163025,810675078,843118081,586603098,332437403,683685950,604167446,591515393,281318476,78155303,77262871,295568743,84378565,642943805,12418389,229594264,734305605,17384829,186823880,593406288,961690929,25278272,599757508,378599084,885999373,931931155,847818733,310703307,179718038,657210251,145528036,460498836,941558184,335135034,141616630,159440569,260876849,890714212,188331961,684788952,962770201,647749366,692000111,84789891,537064227,34450694,41361160,550194873,245249511,900342928,708273456,11582751,128969775,512056025,55621841,349004104,637116328,221258620,579454605,113893156,576214566,70474671,23918407,481813327,650352629,246808993,284149774,322921321,932867441,994253317,940618753,728504629,428989278,122474884,119546568,24132990,106306058,431011677,611024276,216092723,58878210,120907054,721629564,912245907,362994492,77928370,598179976,862251409,302060802,740845852,459478021,470575532,272055897,271404800,997912851,546477556,102801687,821058457,253389282,766070117,630671871,387593407,363890600,503970374,198459012,993364984,210948548,542855601,819226190,105570791,913838630,104902493,762607731,954174416,72362183,262189043,660554699,644882932,306650492,22189922,453123536,325669078,343206526,974951458,351413354,739439728,691749301,370158156,944047088,188614449,382554561,385741342,62378862,740868824,256532721,721260793,546722313,476298564,606762614,98776598,898445056,605244417,333859176,433695416,401161556,572855901,243667257,85343276,675159112,922771404,996753884,954048793,469148682,19943311,296231984,99393047,204271243,312577415,956614051,159362748,723539465,111719270,894138284,588450713,602782642,981925082,900433723,180543977,267328360,522848270,4196877,67000222,107779276,321728789,528597010,269434053,964941753,949825536,975030570,458728261,549511658,418171229,245570032,648210003,972434487,581872842,635344874,319802132,678265431,806155029,954458489,526854317,847377933,635338259,992797406,996032139,354562942,45336906,183006407,369367987,247817600,491651792,494803389,962480390,263666034,589248788,333002563,984917437,533517315,834849850,760791456,813814451,264438766,491534109,918145305,179243082,160538846,82373669,881806228,278695930,385349194,933393280,582444057,773641997,840937520,96345614,817752725,256578508,578658132,888553231,520544389,456331129,516837373,204008970,759828335,835082257,253914434,679107130,399776525,263641486,965389469,273920467,217978643,525012340,943300400,526528431,502684772,227319751,184383545,997961185,602742229,532755276,833719431,885093195,163222310,767604093,441111498,336002326,145020302,447897867,342728411,567522452,559761514,223634211,733274355,395895537,441758546,522228316,742539358,836415814,737295438,84803432,254857485,689895715,104233343,56504994,929273451,508576899,983431327,316933463,434800356,77235159,345405177,120253753,548205525,600098258,35022115,875707260,680477576,229617111,897981712,958283445,278645047,201461954,518254721,89544140,76537050,809062577,929661491,534619097,351906999,474321903,94774221,583374083,381426482,793949123,40598041,690138090,751409586,895948818,358453902,541996186,679215363,827412724,194647956,494116926,627452577,386736436,992534556,583458453,458954191,452395539,433411191,83035942,133921864,36174666,36124418,426067769,240516214,298321038,125731963,829618799,226783968,849360164,9358419,878892635,654427981,444939352,483762654,124363485,740949639,814981767,173769880,401679992,749523230,669826908,170072114,276845070,269247536,53714363,162616523,8844102,27290502,3600441,467904458,40008618,7204185,150738856,792362730,45598949,977261012,853230685,179122539,735619417,100129993,662288907,901642909,419357330,601897967,32519959,147937254,520035582,619074118,761871431,445631923,243303160,827711029,744937947,15911547,957399972,741820067,751442972,181021121,285585127,43235484,248795236,854000667,173641304,266839483,987409221,378563960,468878418,63384716,583634818,600378382,929835762,523740003,728955447,590492615,34458125,279343929,195735677,46664994,254933368,505006550,771021822,874348003,296227213,746790823,973757368,201451383,930317102,405949761,947854926,140353037,684244004,636049743,835378431,463831115,304603586,373625601,891807971,621955730,786099783,899819252,848424804,509286582,363251433,837152965,634098024,745841579,774669132,866733360,655971756,187393847,319922128,720057339,143719635,477088748,425291431,398255803,256131422,78883327,114100114,770420843,755327184,747258720,996552065,520685783,833372309,601862213,109744430,366033630,504910344,728140839,674391947,378179747,992539473,211011763,925730352,267475380,758877347,369571470,653353828,563034116,972310823,277104697,915590076,98810073,731606998,640278520,307568694,685441808,172167424,978621117,961852573,989826956,21291180,563398916,103195668,973253925,911079602,629605747,358705718,195136342,795674612,183783797,818543004,40310635,782810419,506472562,654359105,180610995,51656372,687758531,813242080,800205442,351202197,975494088,55601798,373634347,439431460,619119165,647304543,891479812,431853458,287487484,629742588,569968709,111438527,474687259,615835251,934504677,992813175,600110972,868747474,62311161,187294886,726603667,580421911,107504751,202518336,209401215,750362164,238391155,329709554,897244203,199259179,241103457,64575666,317473109,680196001,87902609,83745240,854416433,54536240,902020202,94740979,4164168,864704158,181992096,923657279,435521610,884744269,55567693,126570865,647074372,51553579,913812424,98567379,329986816,663376245,225267302,973160222,539136221,217559249,931911787,587428634,94744816,353928524,341411647,307460309,496935115,652278862,272604012,138888597,650279117,670561850,116115966,506649522,54437251,781668256,374349845,387395282,686586781,545916574,167122732,606102165,593079413,780490690,308961218,256330328,24468605,309417560,112329603,872817314,45580420,633389597,696124582,32022074,985630150,435259200,22149075,446732552,787947189,50464753,734799327,913174573,294271785,866788059,928220339,85287708,945950496,115564252,106618803,718345726,645319475,293372195,975736385,664216921,947025832,958418035,13767822,349045970,79327832,946042176,154207668,712307427,223878963,770796471,215613927,380195536,789269126,581405899,366770514,10514845,924391406,794660132,685109944,832803205,455727684,548316762,773390724,620488938,485658506,206841057,330838323,372915324,438743304,698869852,361619475,537311341,59971663,348382524,547779211,921054245,944718929,385330421,56048325,26672557,163338773,63970118,234730457,490340751,607318819,155083256 };
vm seq9=  { 1,46,9780,3749817,187692416,131617801,403247904,408395780,233426111,197302785,177620322,206888829,835061253,770003208,167817537,517820844,580617828,469175695,251779826,370582104,72645165,713328912,277616511,902795789,659852726,220506452,987735058,337008279,326694484,929531710,623473948,796684891,777051645,795130912,868689621,888962475,15266106,133906103,896971308,432781361,609904713,139195229,582320633,810000436,144947711,694533823,353828778,974567747,545012103,655590199,684583111,709008353,516538185,177659043,730381724,46966183,70580725,546296539,649380102,839329070,521579663,795443380,918648018,416884200,467381921,180180331,922394206,388926320,338398210,519862998,15436055,832899910,25205989,638023459,397967188,958525486,625245410,761065829,308642849,984865576,166574802,351074509,483949360,826042703,587151803,332893091,23588722,198575872,217064635,935342648,875830167,870762061,431430867,714037906,451514553,118685252,876908841,648215588,848279669,60298649,631459254,423970403,946540284,520092028,98956342,792001639,336970097,931916671,592163793,698538792,255778678,599081544,736931827,498542056,487642145,167722475,425497075,479036071,196741186,39983687,490171827,41410689,950392181,499418291,916512859,995578976,364239373,287759311,305160182,776807437,795631951,394372203,993536737,574952320,609892555,374430407,859025148,436507547,532241818,70196028,667557734,86629982,53437442,215255355,775586988,386301784,329730036,202594581,163573386,90440287,830055245,592282176,146234820,713607861,431108209,391672173,89707231,227887894,635772629,670074547,823064294,429723600,720075551,708101377,728992628,35839867,649628049,777233025,769395245,273231977,452388242,103609466,50984608,571111272,37433617,645071595,241717406,852257158,792730998,762093847,260970345,710690388,581362112,325183397,887018247,894572201,248056866,450822008,28780680,485097555,610718928,844021941,806875642,356112860,159635848,788536149,115844062,32006335,343606686,949709182,501111334,368083992,85114367,231716731,758617506,42613425,792424029,406591751,7556236,372313393,875852937,303229658,493990390,413068578,970321429,914931583,883280548,348694253,48829706,693879474,956820846,494398844,524838673,55642291,291803821,838072277,937627887,352806076,872719357,645619109,203657092,833772502,188791199,15808273,336497714,294256665,801099447,152749996,41154833,192492037,312034559,714016972,939095633,362217613,344871906,183574936,889188175,138994257,960429162,296389560,883734448,484177869,83759714,357767260,405799385,404997965,179592456,903922103,309177363,762328560,846181322,186860330,535482052,303516150,218656365,107450951,239712835,878534310,957325926,369018717,743188095,890784476,179418700,403243177,82350078,760467415,628649940,536068243,546840676,460160402,131727618,556807822,103868150,100658425,320228786,310512099,723638548,644759207,54096167,438468026,280923558,715718354,545633131,123399384,171267285,991718620,983352762,402614190,319762847,922715170,183148107,404824714,482568354,237420088,669034732,275370690,906758282,912995719,736734515,669078917,551700748,844999683,490707947,397056377,72201275,440950742,308110320,99342342,252577469,439457764,862615165,97430405,650977534,227567873,732837767,486412311,424158572,314727502,706889057,657623512,936876994,355562471,9669721,793140370,959968301,899351235,219020217,880286168,595856392,493610284,799709672,824990611,720595840,329639105,976749338,936889222,809494864,315709610,237042147,110330914,567862811,101728269,746956577,529866256,586725299,648040802,779748453,153236584,914584632,749408848,513718702,14088745,993137658,564190069,564615129,218058109,134675642,474742396,687879969,690548089,277156363,833518402,580665445,577772529,19376545,299323128,895099028,299338548,839803399,687138571,578794728,71021962,41918342,510329764,609712541,451003508,709704952,186996195,578245110,487769768,658075789,864769756,506366569,233278985,86797708,695583510,153704085,307322933,831266924,199868473,103620683,993020714,659107947,396528526,448813398,73914985,907386096,831778458,594736348,150616396,988883527,366215644,167086402,868932946,313717944,593312472,235565013,521329249,311252447,123949903,964499850,144982402,326364968,391588167,501164096,279706677,683502823,592927882,202357006,297878696,111559940,437962854,837545571,371947447,187758156,101943566,305769634,487510261,916387515,682044269,61059325,657929289,460684129,163896143,161536408,538311887,723564215,36418740,327436337,989827282,124248646,832708689,882308791,710452532,77716354,875129877,836074412,531835866,56875322,833407106,423331036,393581723,167353705,46338146,795984502,429448794,921170555,895713358,399606531,448677101,376663937,565811401,301582937,103096131,89229647,456280485,935984941,257863968,62176805,520077004,989724021,230216017,198426324,232816552,723398170,947598120,145563484,543560196,769283255,687695854,412141786,458246893,322562822,870174789,792046448,992281654,261650103,321433332,28258916,361339156,916537224,304030645,26483723,311683689,962388784,635976432,109322304,111089465,562711340,932659824,884184807,961770498,482763444,787907010,283606373,844167427,96801506,102993914,616787770,332259273,90020692,33473959,108789188,901500423,168357637,853210302,871337078,376008841,609311702,33409149,458480524,530786779,390698057,481382023,680007464,849208791,270019811,368593264,287960379,683678742,840373287,472091097,256821799,909688374,636672905,857109892,992260815,638259715,682582094,715207691,600484324,181860537,177868142,849248565,743213710,255749171,601589781,577202204,715681222,735331177,522995961,337047397,380280968,562020809,449068544,963757502,321956500,151307218,161277904,285233283,762020022,339297754,69679349,52568304,535629099,658030019,319086681,600634302,532594729,293331052,603165888,881090117,441710022,197876330,311209999,65489058,438038472,846586493,841740112,900892506,272268280,272662987,89882805,789135776,548746488,93712455,214835786,687205844,809953437,716639880,931867151,5763197,404820389,529438878,222826260,393767311,372063278,755012935,553961582,34305286,137826364,970617903,758748624,22630689,297099625,233382192,919549106,715661683,204181125,621028316,733111354,820512194,577135000,902996457,829943696,846032895,905693878,542196552,252622956,523732070,530997966,533006838,460888303,533952670,844001206,812367057,483211339,158530790,288773919,681553156,968699784,254686619,449601999,599196038,225007855,290070161,539848031,608861063,188322345,747926661,538066173,847178688,798739309,292443381,645523493,583709864,519984310,947227789,785996222,849492108,217296633,379082084,328454322,948218308,458921549,733036261,335345611,773876459,744463438,69765239,106787890,312188871,578318835,7590840,644251671,957688431,335704886,472634568,890314527,887231599,869685717,675313179,908538034,362098900,320019527,244292820,322269050,505039771,483852206,866472203,694039568,823738104,892325141,758360002,346368563,815348255,412182504,471602177,990001494,666290217,161636117,879511685,412410211,446019038,337121631,658855386,784637958,536675584,404218241,960104490,897138436,48992283,548012991,560174716,792156455,160189170,705905873,573054280,928960435,598430006,723118329,3133967,709956395,400173007,843883822,846982538,379029169,361068205,661888590,887835680,493479921,976133609,354917573,765784970,49078977,364396666,502948010,205972105,807960032,802286022,744327815,245246295,420470863,538828147,696329704,411129576,588274571,6230561,547505556,473360734,576825269,869928172,485124876,32250131,382711655,49947368,690021133,761491957,113839877,634613887,973389950,360297062,350465804,385111972,501526754,394165343,117902533,47188186,669058038,586179393,803534254,9867731,117081150,270343571,869732013,535560129,74135322,913166863,745264070,367865465,623137054,135895290,799585396,704614476,888437552,472048246,210649738,887519735,367380508,467654309,310951745,120246372,1570186,489874615,177001365,639465635,752300678,618186090,125694495,282846281,736316610,953882935,653497933,841032401,979929909,640731761,744566283,956866913,308789172,978715398,648405631,702106875,252210451,37223999,173800107,569247456,870763444,145425499,15568088,948078132,543632997,464071585,555186163,273468193,844935945,319095367,541561523,462755463,976898548,38432186,745007342,431518993,996017082,641720869,979768984,850953141,572191501,305562386,828023714,101969832,319513330,411569369,498489859,687104005,861506576,386766012,47630048,485950687,906252627,435904946,523398218,237981275,184197707,269135308,723734630,996762584,961708130,184077469,987996424,232884779,412092660,38185480,920544355,863648752,226193944,388570441,67028235,139276130,987378194,100903449,903580345,405505215,867338868,333622879,921218666,511487223,463201347,414182968,124574191,125984616,331268679,712901252,926814814,792501263,571854657,980486454,67546856,150063838,986275191,522883997,773384885,81195742,381162218,512867736,787522768,774407259,380624610,500979860,425339122,963880442,911568273,792258595,350130674,602869572,264295248,559699882,354311182,316717484,974583424,385148769,775793637,276045307,192338241,677282939,975826895,376504883,438875822,650005504,18308146,573861619,505201939,646594657,659950898,130894026,249286646,298317356,654311533,836465451,865286056,895177951,246676015,195480008,816931197,479506396,881134449,708030911,402627579,94318480,239737461,50326525,124781861,692461840,182412977,588599602,905280445,671991487,149716818,47905659,64714288,716724852,557647217,28241813,713896118,846376495,206401419,428739232,942397990,324941901,306688148,258918809,206428158,459115204,714606129,901629113,466484869,310408764,294905149,749311052,394101772,403806551,498739597,248404901,190125925,522025989,356210448,962389206,814535862,3980316,250331409,790031420,402340346,314834488,602818981,373056827,513025449,514106360,330630796,280415657,110664533,260357567,438075256,589257528,858090854,422891206,620257076,790506378,952563017,765975975,960893638,543352843,365161674,624020380,800469366,251809506,622790781,765922254,402911761,997555043,559439273,29544239,878217450,228591541,899811202,871109200,546784720,253989181,599758116,684560326,694533608,280703341,236096124,66961641,589317183,148043720,775804320,268637105,330635806,56702422,125110764,721113905,467948372,559561216,304843405,297100893,617590243,296473497,369817638,718004637,526124219,325406215,131642558,869709759,216629106,687991037,573256825,311737342,758758393,234589477,806451921,213768730,631008010,285161194,822185859,233315563,217016674,677480897,804760340,303459985,221413384,399022534,365958715,40799196,381705663,789465568,637528336,343565436,451970240,746068673,166867881,819274546,76504658,397541091,634573223,532288801,461447954,593079117,206340569,73124198,802335967,905865703,467513530,84938695,290540137,695515464,3667895,705686514,717484973,407798787,866250513,73759858,988625791,225509687,921183250,230949764,381533095,278804585,32480391,574582358,123789424,768169180,487732015,297765429,731832402,432860257,598148967,289492131,97013576,442023508,762069526,931825285,458140598,189544523,921471522,275855482,956391147,193634696,84677512,113885809,830941680,431684737,119795184,940323413,300483045,11521578,885580159,695593646,494983308,139383567,821276668,477452985,683243184,361935518,273621686,4025496,476432520,678629226,920228511,134283533,278793092,224178917,869681153,174441946,438098979,983179207,95895203,212167017,740312753,803874004,175587644,682522860,614355471,789583549,847033913,169737233,530620006,88772532,124677419,888667521,371396197,533931067,718748123,595057221,818722082,914450671,942041352,945793216,348969832,626292932,303397118,228838069,28916733,335304965,558461572,648732066,362862479,645644153,836900146,226072037,2526316,607200857,425579579,179811244,154007535,607302125,644236318,755830591,814364820,673316614,798276162,280639295,493837698,855032351,45181310,777088306,745591285,708716411,549107663,822401713,509694538,125152561,82670993,21672030,486308263,786883338,423502354,712553577,411344742,338677376,263290619,867769040,160383232,747625086,158201607,951443406,636334679,370222791,47943414,484867606,423903457,195175358,135571000,484368557,553009496,600618820,998008533,125481235,313440081,920261883,141597503,241150506,304599833,625027134,525327907,403705484,358303342,111176419,565802336,647347974,84084620,413409785,98657399,549857136,645338752,115503606,27438391,361281134,63172598,827084013,331296038,321019197,410360525,940056260,627749533,909583588,88552552,542413907,383291310,559639077,304848869,722521733,404559231,974891849,856618042,727192122,440882717,357385881,625575815,986372631,598036231,475047519,300390056,9429002,183656169,489248287,603599133,790100303,112821279,47100937,350806697,596073571,738678594,827711872,956260833,515497446,239015996,141398666,978710489,932138574,211644991,69622608,146322048,960086592,50754322,258647930,623274857,429936370,639417108,639838854,463415691,813254091,772158635,68864658,505224574,513238127,837886282,424691907,304708275,744472834,487313665,527962525,959121264,715211507,413909676,908374832,523434902,623521801,445933853,320082837,950943024,805095571,663591179,529212627,576553606,178217864,410938915,233628376,674716905,927857658,624900205,812851140,923751810,613484034,598986240,555815481,298430585,375503658,216250067,107640920,599468145,372254846,146275234,348445244,3736570,473913954,774580514,872930813,971064287,113593434,755600997,59421537,345733678,714514284,393472942,284259834,66346459,60599228,898108188,885301207,338900846,823960071,752754991,871763194,13437677,995457576,827388896,138774795,88257955,210382349,237031441,661262363,540978457,892491155,779545858,322170980,313090905,426594063,917483948,934592311,990532568,577509126,842813130,999017291,549290279,728719754,321942882,929766893,730300037,200992824,699813639,685221290,27876709,677732676,269423083,37263800,680630120,334849061,494381128,899855482,655871085,478790165,337285211,668973816,829719211,154932014,945447777,354565235,188909928,26478797,427248629,100374713,484166983,638445033,389803106,439559793,625484915,637565829,232886119,158083028,9949127,795003658,777100117,322723751,94449895,336166350,767710962,72289166,822399582,822536668,631926300,488957748,563805212,967059927,200175104,438942932,621375448,582250169,95903295,240626067,704361331,5324048,358290543,824270341,594650048,481626520,109910172,836534098,139527563,727522408,282454977,293768653,950465195,743463556,95510747,355298666,151822404,679831207,351265219,588321976,262821349,454551692,611140416,609356077,819432485,658052976,441877003,521076891,701933874,181693644,894728821,188780266,663526655,936240899,276957934,71383933,176921632,636364473,950228478,755325107,270309801,283362254,65964329,945450827,883072593,283017532,163753841,629962123,924289906,269083765,350448020,241173354,503068731,374915412,690044046,476763019,529093197,83953112,807773788,190737226,592880773,128861260,920158794,976439830,149582722,725610801,563408586,795135702,297679144,722991875,120759126,234535660,350691247,185524440,465467496,945535837,407852844,240477928,127597924,405118132,764817822,825937670,99817945,657122325,214895062,444406130,292779825,30228727,855635792,766735168,374009868,947636631,759009573,497279183,812952234,518490716,54973594,273418098,677091603,173154464,863054860,784083710,593826879,95367717,495334795,366868772,792941673,743593741,904401878,814070824,701065353,324710571,64654013,513389134,982548521,11880341,834731321,353228177,72087134,924358983,627408411,610588580,378726664,767884209,205003392,758826431,593451981,495758782,159964915,715021741,300528670,453133480,218060641,69091113,675955730,723034591,374621866,30140948,460969418,786469432,388218888,175188963,505882354,597716,251923589,251882615,353426207,685115099,312159881,946592999,922736518,927074544,615884437,408627211,256719337,870141145,565754625,631816225,222574335,883046825,600474475,91024646,164387223,763626805,852905124,519473869,882853864,150040999,11874415,662434711,771194543,838481127,6826401,881104436,787042181,353504333,531218758,688576548,284766727,140283683,189681966,750797791,429995099,776590865,941914151,410950058,645663695,416021641,539155118,183107106,416501345,702413495,193941496,423036902,525462975,24483855,765084491,189714431,567472866,915980144,997919227,211919297,326446039,32628158,378998439,758546383,288779949,609505739,813183942,408284866,452003624,287525076,401804287,206290443,988161847,801839542,151830174,867397632,175108307,749806211,468794026,866149313,580861559,389737291,90689202,26122573,565363135,687468123,316515230,354771116,337815088,952429678,77238091,119422175,808070499,395928288,612912437,700711842,360089654,576425103,858444173,605766815,168797548,734732671,47718292,948073182,863642131,293978642,489042818,492878448,575332276,522359575,128094955,998575427,899056056,199745230,458014045,231345161,747509531,134332778,816829025,434559917,215320669,570748337,724511741,642894595,817001871,591815774,585728927,805160549,129156322,323741975,587816789,556190291,730033128,940945131,887592269,784127143,140325068,991252459,989815228,938912137,767203152,769211907,202660243,3055076,109812763,289061335,958975267,787469483,830547223,591670517,317997511,555825300,818351834,950932501,96948710,464666135,701717712,261711253,392990099,514778583,788492898,98204686,27871873,306441469,298261797,314990656,901922270,183708265,320315378,772270444,969207680,56213436,754566014,295204017,638042145,512461161,534080860,211216030,312938918,379434760,761712810,612549103,542408219,726420691,77809135,890283181,94223299,834986202,38105881,151359342,566086535,474024470,286206612,744092672,47982564,661790628,938995786,148669250,516050490,443371999,678975242,826165716,412155761,184396254,734233661,351284020,82746784,33911816,560327112,230572942,203338582,690715252,474233371,433708987,639500659,912061534,800463038,81575316,387105820,882343084,447429234,113528189,401916087,48943567,134221256,375153154,760159171,933211560,55535116,590504660,194075283,789301319,277423470,726863780,663247936,873395202,373333895,364551294,31189404,700469040,382353125,106684798,800481783,486224066,249420094,653078727,765153869,672800678,623092800,629288644,189744879,757525516,191241172,461997647,435723808,549129852,566998529,559887889,694540513,941307097,43905754,351086194,543098356,786673853,709316018,418907660,836838236,723477873,745843185,20899821,197443436,203672721,440290961,818296491,907084952,321106523,558770813,929358908,103126774,521597453,711751351,766378771,239547476,530480278,858949149,167341128,252508305,783766412,466089321,981866532,874123084,816384551,136994751,424897755,352365351,36184651,686827495,365942619,81989355,996836148,675761898,426457007,149112750,150461698,91588069,697763291,798065579,484958321,82345406,721191673,997093279,622107167,840026596,484170732,435289436,151924099,106451740,424752731,850991094,528912645,765869833,293486325,178913034,653855719,315141173,123307813,219951281,782068750,730790152,747291806,315550438,281904039,269510986,11604657,355598968,954185656,206947523,247199461,531740344,8487174,600140064,276160086,37421443,948766250,357431291,508882773,337705497,76973223,75016300,470478359,405880707,215490224,827104361,810763286,320607347,775921295,729321381,132812568,687269251,237671298,373232617,391519048,557453516,781430516,901179778,444729518,988673846,934408482,63515250,614046277,708463385,119642100,33832272,460420492,560017623,675566304,451515383,6009418,226052166,995813319,873941638,402946019,271921201,885619521,990968533,7123845,860998916,394017607,385362715,774026157,742870954,125653088,993602639,423050930,684242399,831643949,741000089,104521791,222652742,442215668,265606031,367579221,278578792,584945826,186640896,787539894,30589524,777312421,553437569,273942380,230804299,26737924,552583024,699396818,702381535,15711968,907718520,389379841,919233451,953856753,160243942,296643904,706537776,853346154,588591761,350456459,491133453,377268421,54418476,478077485,895811079,199072462,968190753,170299546,693649096,913310446,581697209,929543225,382439456,206172481,655055967,619165809,963120920,745124581,658802882,58852188,583855208,765802265,120963811,93567786,446043927,691474685,395775311,840639136,716120666,895228642,565400287,571984859,220519461,949770866,845623936,172382729,651641263,357048753,486596824,484113507,572200046,286010308,753527985,377405211,757488569,252229183,331455700,721414119,353099660,816913837,733223873,27461697,345655362,85928886,644299865,959162008,686255084,81381933,583532830,510770717,798372547,950184007,23000547,638597880,429324939,146042227,883204565,630068697,634681873,105233712,418446522,748137521,7839896,153777848,344724660,789768537,280206851,872474831,555866185,228690838,21630533,660105336,83589513,904715466,397062559,712620210,119208551,887025472,163888958,130339176,278018362,863978615,837630856,488681815,822341214,263572554,447882377,443677798,40281902,824963044,411662627,18020791,295380617,596869132,443477525,804459554,412633426,483984551,279892596,168323270,169245582,983854745,365181175,933025176,572832390,347030619,658069209,73400599,311850605,227341852,274491679,193063964,978375368,57449581,406009999,152978527,155295105,784339301,856384839,817737759,178178116,392729557,621136702,357830623,231996215,336924831,822065726,134743212,571038938,429634670,563224769,374970899,213658716,637666109,960502964,338376857,474566095,211684683,420994073,596206069,617221645,406034842,728151290,158230594,619279153,864296957,293353135,819153382,539861948,717329835,943592877,975140989,32687150,145151992,486513263,979284748,221490819,238144031,637945317,46613024,29417550,336161295,993895968,670089057,309459539,194011436,246077156,973939778,654970119,129829721,355999523,270284378,922082632,653672455,51493626,339497448,606351225,54403783,874254925,471915964,746169072,279251946,943730489,873498488,739024602,813821550,19556734,525174824,422769854,53369114,357810378,400647361,418624967,805722848,143662898,585477651,333130410,616623806,109332099,917991564,176310281,105887208,213463601,77766013,557503970,191824435,250281348,651531309,690085544,152675209,774649753,715426905,549413231,978334201,402930283,300496881,902529647,261127195,528906511,603204367,203946909,773390665,550383730,887913053,772806174,748202002,628980688,859780259,289996437,638466494,330158241,218133294,290564888,21814475,324298575,648621696,537494533,228993580,778087512,46312596,695846189,280115111,796484070,982003447,915570266,626360484,119834324,697738358,608622186,469955861,223291521,502143211,378401509,258807906,430014221,26880697,992159719,183587197,146409632,39789668,775645765,241705435,644838290,678415700,874357584,696278545,664210845,151798602,575057262,951650693 };

int main() {
//	input_from_file("input.txt");
//	output_to_file("output.txt");

	//【方法】
	// 愚直を書いて集めたデータをもとに DFA を復元する．

	//【使い方】
	// 1. mint naive(文字列) を実装する．
	// 2. embed_DFA(文字の種類数, 検証用文字列の集合) を実行する．
	// 3. 出力を solve() 内に貼って適切な DP の型を書く．
	// 4. solve<答えの型>(文字列) で勝手に DP してくれる．
	
	// --------------------- 埋め込み用 ---------------------
	//{
	//	auto start = chrono::system_clock::now();
	//	// (文字の種類数，長さの最大値，1回で追加する文字列の量，反復回数, 検証用文字列集合)
	//	auto [nxts, ac] = embed_DFA(1 << W, 11, 1, 100, 1, ssB);
	//	int DIM = sz(ac);
	//	auto dp = solve<mint>(2 * DIM, nxts, ac);
	//	auto coef = berlekamp_massey(dp);
	//	dp.resize(sz(coef) * 2);
	//	dump_math(dp);
	//	auto now = chrono::system_clock::now();
	//	auto msec = chrono::duration_cast<chrono::milliseconds>(now - start).count();
	//	dump(msec, "msec"); // W=9: 5041465 msec（84 分，2h30m のコンテストなので間に合っている）
	//	return 0;
	//}
	// ------------------------------------------------------

	vvm seqs{ vm(), seq1, seq2, seq3, seq4, seq5, seq6, seq7, seq8, seq9 };

	int n; ll m;
	cin >> n >> m;

	auto coef = berlekamp_massey(seqs[n]);

	MFPS::set_conv(naive_convolution);

	// 提出時は不要な部分を削除する．
	EXIT(linearly_recurrent_sequence(seqs[n], coef, m) - 1);
}