結果
| 問題 |
No.1561 connect x connect
|
| ユーザー |
 ecottea
|
| 提出日時 | 2025-09-01 17:52:23 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 418 ms / 2,000 ms |
| コード長 | 51,101 bytes |
| コンパイル時間 | 6,088 ms |
| コンパイル使用メモリ | 306,780 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-09-01 17:52:35 |
| 合計ジャッジ時間 | 11,880 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
#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(BellB(n))（n=11 くらいまで動く）
/*
* [0..n) の分割全てからなるリストを返す．
* 例えば [0..6) の分割の 1 つに {{0, 1, 4}, {2, 5}, {3}} がある．
*/
vvvi set_partitions(int n) {
// verify : https://yukicoder.me/problems/no/1561
//【具体例】
// n = 3 のとき：
// 0: {0, 1, 2}
// 1: {0, 1}, {2}
// 2: {0, 2}, {1}
// 3: {0}, {1, 2}
// 4: {0}, {1}, {2}
vvvi sps; vvi sp;
function<void(int)> rf = [&](int x) {
// 全ての要素の所属を決め終えた場合
if (x == n) {
sps.push_back(sp);
return;
}
// 要素 x を既に存在する集合に含める場合
rep(i, sz(sp)) {
sp[i].push_back(x);
rf(x + 1);
sp[i].pop_back();
}
// 要素 x を単独で新たな集合とする場合
sp.push_back(vi{ x });
rf(x + 1);
sp.pop_back();
return;
};
rf(0);
return sps;
}
//【線形漸化式の発見】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 seq9 = { 0, 45, 9779, 3749816, 187692415, 131617800, 403247903, 408395779, 233426110, 197302784, 177620321, 206888828, 835061252, 770003207, 167817536, 517820843, 580617827, 469175694, 251779825, 370582103, 72645164, 713328911, 277616510, 902795788, 659852725, 220506451, 987735057, 337008278, 326694483, 929531709, 623473947, 796684890, 777051644, 795130911, 868689620, 888962474, 15266105, 133906102, 896971307, 432781360, 609904712, 139195228, 582320632, 810000435, 144947710, 694533822, 353828777, 974567746, 545012102, 655590198, 684583110, 709008352, 516538184, 177659042, 730381723, 46966182, 70580724, 546296538, 649380101, 839329069, 521579662, 795443379, 918648017, 416884199, 467381920, 180180330, 922394205, 388926319, 338398209, 519862997, 15436054, 832899909, 25205988, 638023458, 397967187, 958525485, 625245409, 761065828, 308642848, 984865575, 166574801, 351074508, 483949359, 826042702, 587151802, 332893090, 23588721, 198575871, 217064634, 935342647, 875830166, 870762060, 431430866, 714037905, 451514552, 118685251, 876908840, 648215587, 848279668, 60298648, 631459253, 423970402, 946540283, 520092027, 98956341, 792001638, 336970096, 931916670, 592163792, 698538791, 255778677, 599081543, 736931826, 498542055, 487642144, 167722474, 425497074, 479036070, 196741185, 39983686, 490171826, 41410688, 950392180, 499418290, 916512858, 995578975, 364239372, 287759310, 305160181, 776807436, 795631950, 394372202, 993536736, 574952319, 609892554, 374430406, 859025147, 436507546, 532241817, 70196027, 667557733, 86629981, 53437441, 215255354, 775586987, 386301783, 329730035, 202594580, 163573385, 90440286, 830055244, 592282175, 146234819, 713607860, 431108208, 391672172, 89707230, 227887893, 635772628, 670074546, 823064293, 429723599, 720075550, 708101376, 728992627, 35839866, 649628048, 777233024, 769395244, 273231976, 452388241, 103609465, 50984607, 571111271, 37433616, 645071594, 241717405, 852257157, 792730997, 762093846, 260970344, 710690387, 581362111, 325183396, 887018246, 894572200, 248056865, 450822007, 28780679, 485097554, 610718927, 844021940, 806875641, 356112859, 159635847, 788536148, 115844061, 32006334, 343606685, 949709181, 501111333, 368083991, 85114366, 231716730, 758617505, 42613424, 792424028, 406591750, 7556235, 372313392, 875852936, 303229657, 493990389, 413068577, 970321428, 914931582, 883280547, 348694252, 48829705, 693879473, 956820845, 494398843, 524838672, 55642290, 291803820, 838072276, 937627886, 352806075, 872719356, 645619108, 203657091, 833772501, 188791198, 15808272, 336497713, 294256664, 801099446, 152749995, 41154832, 192492036, 312034558, 714016971, 939095632, 362217612, 344871905, 183574935, 889188174, 138994256, 960429161, 296389559, 883734447, 484177868, 83759713, 357767259, 405799384, 404997964, 179592455, 903922102, 309177362, 762328559, 846181321, 186860329, 535482051, 303516149, 218656364, 107450950, 239712834, 878534309, 957325925, 369018716, 743188094, 890784475, 179418699, 403243176, 82350077, 760467414, 628649939, 536068242, 546840675, 460160401, 131727617, 556807821, 103868149, 100658424, 320228785, 310512098, 723638547, 644759206, 54096166, 438468025, 280923557, 715718353, 545633130, 123399383, 171267284, 991718619, 983352761, 402614189, 319762846, 922715169, 183148106, 404824713, 482568353, 237420087, 669034731, 275370689, 906758281, 912995718, 736734514, 669078916, 551700747, 844999682, 490707946, 397056376, 72201274, 440950741, 308110319, 99342341, 252577468, 439457763, 862615164, 97430404, 650977533, 227567872, 732837766, 486412310, 424158571, 314727501, 706889056, 657623511, 936876993, 355562470, 9669720, 793140369, 959968300, 899351234, 219020216, 880286167, 595856391, 493610283, 799709671, 824990610, 720595839, 329639104, 976749337, 936889221, 809494863, 315709609, 237042146, 110330913, 567862810, 101728268, 746956576, 529866255, 586725298, 648040801, 779748452, 153236583, 914584631, 749408847, 513718701, 14088744, 993137657, 564190068, 564615128, 218058108, 134675641, 474742395, 687879968, 690548088, 277156362, 833518401, 580665444, 577772528, 19376544, 299323127, 895099027, 299338547, 839803398, 687138570, 578794727, 71021961, 41918341, 510329763, 609712540, 451003507, 709704951, 186996194, 578245109, 487769767, 658075788, 864769755, 506366568, 233278984, 86797707, 695583509, 153704084, 307322932, 831266923, 199868472, 103620682, 993020713, 659107946, 396528525, 448813397, 73914984, 907386095, 831778457, 594736347, 150616395, 988883526, 366215643, 167086401, 868932945, 313717943, 593312471, 235565012, 521329248, 311252446, 123949902, 964499849, 144982401, 326364967, 391588166, 501164095, 279706676, 683502822, 592927881, 202357005, 297878695, 111559939, 437962853, 837545570, 371947446, 187758155, 101943565, 305769633, 487510260, 916387514, 682044268, 61059324, 657929288, 460684128, 163896142, 161536407, 538311886, 723564214, 36418739, 327436336, 989827281, 124248645, 832708688, 882308790, 710452531, 77716353, 875129876, 836074411, 531835865, 56875321, 833407105, 423331035, 393581722, 167353704, 46338145, 795984501, 429448793, 921170554, 895713357, 399606530, 448677100, 376663936, 565811400, 301582936, 103096130, 89229646, 456280484, 935984940, 257863967, 62176804, 520077003, 989724020, 230216016, 198426323, 232816551, 723398169, 947598119, 145563483, 543560195, 769283254, 687695853, 412141785, 458246892, 322562821, 870174788, 792046447, 992281653, 261650102, 321433331, 28258915, 361339155, 916537223, 304030644, 26483722, 311683688, 962388783, 635976431, 109322303, 111089464, 562711339, 932659823, 884184806, 961770497, 482763443, 787907009, 283606372, 844167426, 96801505, 102993913, 616787769, 332259272, 90020691, 33473958, 108789187, 901500422, 168357636, 853210301, 871337077, 376008840, 609311701, 33409148, 458480523, 530786778, 390698056, 481382022, 680007463, 849208790, 270019810, 368593263, 287960378, 683678741, 840373286, 472091096, 256821798, 909688373, 636672904, 857109891, 992260814, 638259714, 682582093, 715207690, 600484323, 181860536, 177868141, 849248564, 743213709, 255749170, 601589780, 577202203, 715681221, 735331176, 522995960, 337047396, 380280967, 562020808, 449068543, 963757501, 321956499, 151307217, 161277903, 285233282, 762020021, 339297753, 69679348, 52568303, 535629098, 658030018, 319086680, 600634301, 532594728, 293331051, 603165887, 881090116, 441710021, 197876329, 311209998, 65489057, 438038471, 846586492, 841740111, 900892505, 272268279, 272662986, 89882804, 789135775, 548746487, 93712454, 214835785, 687205843, 809953436, 716639879, 931867150, 5763196, 404820388, 529438877, 222826259, 393767310, 372063277, 755012934, 553961581, 34305285, 137826363, 970617902, 758748623, 22630688, 297099624, 233382191, 919549105, 715661682, 204181124, 621028315, 733111353, 820512193, 577134999, 902996456, 829943695, 846032894, 905693877, 542196551, 252622955, 523732069, 530997965, 533006837, 460888302, 533952669, 844001205, 812367056, 483211338, 158530789, 288773918, 681553155, 968699783, 254686618, 449601998, 599196037, 225007854, 290070160, 539848030, 608861062, 188322344, 747926660, 538066172, 847178687, 798739308, 292443380, 645523492, 583709863, 519984309, 947227788, 785996221, 849492107, 217296632, 379082083, 328454321, 948218307, 458921548, 733036260, 335345610, 773876458, 744463437, 69765238, 106787889, 312188870, 578318834, 7590839, 644251670, 957688430, 335704885, 472634567, 890314526, 887231598, 869685716, 675313178, 908538033, 362098899, 320019526, 244292819, 322269049, 505039770, 483852205, 866472202, 694039567, 823738103, 892325140, 758360001, 346368562, 815348254, 412182503, 471602176, 990001493, 666290216, 161636116, 879511684, 412410210, 446019037, 337121630, 658855385, 784637957, 536675583, 404218240, 960104489, 897138435, 48992282, 548012990, 560174715, 792156454, 160189169, 705905872, 573054279, 928960434, 598430005, 723118328, 3133966, 709956394, 400173006, 843883821, 846982537, 379029168, 361068204, 661888589, 887835679, 493479920, 976133608, 354917572, 765784969, 49078976, 364396665, 502948009, 205972104, 807960031, 802286021, 744327814, 245246294, 420470862, 538828146, 696329703, 411129575, 588274570, 6230560, 547505555, 473360733, 576825268, 869928171, 485124875, 32250130, 382711654, 49947367, 690021132, 761491956, 113839876, 634613886, 973389949, 360297061, 350465803, 385111971, 501526753, 394165342, 117902532, 47188185, 669058037, 586179392, 803534253, 9867730, 117081149, 270343570, 869732012, 535560128, 74135321, 913166862, 745264069, 367865464, 623137053, 135895289, 799585395, 704614475, 888437551, 472048245, 210649737, 887519734, 367380507, 467654308, 310951744, 120246371, 1570185, 489874614, 177001364, 639465634, 752300677, 618186089, 125694494, 282846280, 736316609, 953882934, 653497932, 841032400, 979929908, 640731760, 744566282, 956866912, 308789171, 978715397, 648405630, 702106874, 252210450, 37223998, 173800106, 569247455, 870763443, 145425498, 15568087, 948078131, 543632996, 464071584, 555186162, 273468192, 844935944, 319095366, 541561522, 462755462, 976898547, 38432185, 745007341, 431518992, 996017081, 641720868, 979768983, 850953140, 572191500, 305562385, 828023713, 101969831, 319513329, 411569368, 498489858, 687104004, 861506575, 386766011, 47630047, 485950686, 906252626, 435904945, 523398217, 237981274, 184197706, 269135307, 723734629, 996762583, 961708129, 184077468, 987996423, 232884778, 412092659, 38185479, 920544354, 863648751, 226193943, 388570440, 67028234, 139276129, 987378193, 100903448, 903580344, 405505214, 867338867, 333622878, 921218665, 511487222, 463201346, 414182967, 124574190, 125984615, 331268678, 712901251, 926814813, 792501262, 571854656, 980486453, 67546855, 150063837, 986275190, 522883996, 773384884, 81195741, 381162217, 512867735, 787522767, 774407258, 380624609, 500979859, 425339121, 963880441, 911568272, 792258594, 350130673, 602869571, 264295247, 559699881, 354311181, 316717483, 974583423, 385148768, 775793636, 276045306, 192338240, 677282938, 975826894, 376504882, 438875821, 650005503, 18308145, 573861618, 505201938, 646594656, 659950897, 130894025, 249286645, 298317355, 654311532, 836465450, 865286055, 895177950, 246676014, 195480007, 816931196, 479506395, 881134448, 708030910, 402627578, 94318479, 239737460, 50326524, 124781860, 692461839, 182412976, 588599601, 905280444, 671991486, 149716817, 47905658, 64714287, 716724851, 557647216, 28241812, 713896117, 846376494, 206401418, 428739231, 942397989, 324941900, 306688147, 258918808, 206428157, 459115203, 714606128, 901629112, 466484868, 310408763, 294905148, 749311051, 394101771, 403806550, 498739596, 248404900, 190125924, 522025988, 356210447, 962389205, 814535861, 3980315, 250331408, 790031419, 402340345, 314834487, 602818980, 373056826, 513025448, 514106359, 330630795, 280415656, 110664532, 260357566, 438075255, 589257527, 858090853, 422891205, 620257075, 790506377, 952563016, 765975974, 960893637, 543352842, 365161673, 624020379, 800469365, 251809505, 622790780, 765922253, 402911760, 997555042, 559439272, 29544238, 878217449, 228591540, 899811201, 871109199, 546784719, 253989180, 599758115, 684560325, 694533607, 280703340, 236096123, 66961640, 589317182, 148043719, 775804319, 268637104, 330635805, 56702421, 125110763, 721113904, 467948371, 559561215, 304843404, 297100892, 617590242, 296473496, 369817637, 718004636, 526124218, 325406214, 131642557, 869709758, 216629105, 687991036, 573256824, 311737341, 758758392, 234589476, 806451920, 213768729, 631008009, 285161193, 822185858, 233315562, 217016673, 677480896, 804760339, 303459984, 221413383, 399022533, 365958714, 40799195, 381705662, 789465567, 637528335, 343565435, 451970239, 746068672, 166867880, 819274545, 76504657, 397541090, 634573222, 532288800, 461447953, 593079116, 206340568, 73124197, 802335966, 905865702, 467513529, 84938694, 290540136, 695515463, 3667894, 705686513, 717484972, 407798786, 866250512, 73759857, 988625790, 225509686, 921183249, 230949763, 381533094, 278804584, 32480390, 574582357, 123789423, 768169179, 487732014, 297765428, 731832401, 432860256, 598148966, 289492130, 97013575, 442023507, 762069525, 931825284, 458140597, 189544522, 921471521, 275855481, 956391146, 193634695, 84677511, 113885808, 830941679, 431684736, 119795183, 940323412, 300483044, 11521577, 885580158, 695593645, 494983307, 139383566, 821276667, 477452984, 683243183, 361935517, 273621685, 4025495, 476432519, 678629225, 920228510, 134283532, 278793091, 224178916, 869681152, 174441945, 438098978 };
vm coef9 = { 1373, 999112539, 363234030, 487044577, 474461697, 736811294, 276396212, 336657236, 573970133, 534082066, 626827671, 528295550, 625583652, 909279400, 36408031, 616610190, 7132279, 612032950, 609058435, 824112264, 472362569, 92495648, 4965734, 24442386, 229205123, 681001833, 581723000, 75799334, 919203262, 553393619, 960986363, 912090722, 846561018, 924576857, 966861803, 163950453, 916483745, 729277841, 703239176, 393727716, 421239709, 250955109, 67425251, 467214041, 361904102, 351734304, 200705515, 795230510, 44728247, 247969785, 691160446, 118461776, 838243257, 851653435, 990928860, 982762964, 815547726, 435917752, 669307579, 260787714, 292363503, 46730087, 782078189, 685881258, 479849773, 937350474, 172640051, 168280429, 681019654, 773527080, 192283832, 894728427, 686808904, 406528255, 3743037, 206407963, 843460439, 885287590, 606343844, 571843157, 100786457, 194315162, 185836566, 35566838, 212615396, 182872810, 527040895, 298481966, 639314360, 378292155, 508633965, 43501006, 265622117, 6181897, 397856606, 75580028, 127948073, 858336552, 921396800, 468434741, 89372209, 146311060, 980705971, 79756239, 969726186, 718446013, 392065416, 957542649, 417440614, 985342618, 465089046, 844186449, 974589567, 864373942, 692235234, 233500497, 879858195, 500378564, 689153253, 857990387, 849973669, 371946935, 866616280, 676132013, 87223496, 375006758, 22417025, 26429844, 387361422, 220263905, 278060295, 819232075, 862777044, 588383320, 874037138, 986621843, 606114438, 933438992, 336883041, 535158361, 513863961, 810436081, 130117806, 697945319, 364925247, 951385954, 478594784, 510699943, 253706620, 36766679, 469747230, 574954812, 688547380, 139659150, 819400531, 842434642, 546131633, 602894226, 190080722, 411536968, 984685739, 339089395, 195437554, 164783176, 231676684, 629814994, 308684140, 619414856, 921325876, 760321486, 844313540, 905322254, 940401847, 779159922, 315720449, 782709985, 890108823, 462466013, 211449547, 506181324, 601673943, 899345361, 908181133, 251054122, 986032901, 415013, 882850647, 844205537, 428585123, 157252748, 972380579, 291756877, 444545025, 867289978, 640741374, 350745175, 903926437, 835376151, 304184895, 566214306, 855297710, 712991148, 791513698, 417537036, 181191483, 375805622, 170635157, 232674776, 625807710, 616148791, 261642303, 220867908, 501693025, 671804528, 522686064, 441590606, 628790771, 43680825, 691403900, 882666383, 706124787, 229685576, 982214178, 785726393, 795415888, 998114655, 219082955, 388567789, 363428578, 911017492, 779038626, 863258340, 811568333, 636003704, 434978177, 251376838, 32948255, 494772807, 23495604, 516666830, 691664929, 747996214, 257424620, 882433049, 683837046, 673937246, 63891186, 208127144, 249226065, 888008896, 883036223, 779291719, 303874151, 66140233, 353491162, 763514288, 979143511, 20105688, 39955309, 861367478, 456499233, 115941481, 762570557, 941778559, 954242433, 230328535, 552828043, 668447955, 77165130, 747035484, 335773832, 816977675, 393734840, 660696318, 740176904, 613111714, 543575273, 735280570, 457594191, 938985793, 420442433, 429166682, 326276720, 76634144, 536259551, 535675944, 755298928, 491517534, 244841317, 691961899, 131223874, 114826667, 785710365, 88751557, 778277464, 172866047, 499014682, 774578808, 752694299, 478539595, 607876533, 911606091, 78075009, 329720970, 490624769, 434961208, 79715447, 24695651, 801365067, 480270454, 831922281, 320857997, 640370096, 645434223, 537481426, 361689635, 879701971, 286487315, 254952187, 552193376, 770894605, 306312372, 32261280, 11833150, 521349341, 65070839, 743978423, 500438933, 861096878, 163039996, 283185542, 365511419, 4954198, 996420415, 625164445, 255724358, 909619496, 742226851, 359391562, 323120420, 569983954, 87808947, 595695080, 689806378, 881067230, 33050782, 456717468, 110720700, 318344195, 904247742, 267661435, 201042497, 611886089, 131154703, 936566040, 878950902, 614882653, 150088545, 930088996, 878777455, 564144702, 322673544, 103317270, 327224873, 864286440, 812002048, 241919085, 145389011, 753143429, 388909435, 695554090, 876611554, 926777682, 121689809, 591340728, 484254062, 713466529, 683401520, 953041599, 146395920, 567125738, 988967741, 409018854, 205634967, 451246043, 369141919, 410366532, 963224553, 975509411, 304587474, 575872263, 146865713, 208418860, 727333779, 428234655, 450562135, 946241343, 346004116, 472905020, 107484882, 491920069, 777484375, 449491845, 613093731, 279115721, 399511751, 638141694, 825256622, 608027733, 481490178, 689545240, 814013063, 821208531, 415185334, 357859148, 187216549, 306195372, 76438381, 574628019, 169865211, 512877992, 118171172, 129859986, 186831158, 711673916, 757182008, 374272871, 772529225, 205233673, 685624410, 86926035, 375589662, 109182833, 759190463, 943592978, 268176601, 498084897, 972523792, 451754997, 283650879, 475831968, 582230354, 991413125, 968833137, 367050828, 111438697, 870445064, 380603441, 960374761, 765139327, 708613696, 259336875, 664163117, 213257451, 894842210, 35402879, 310807881, 904264073, 525445091, 459833081, 879943567, 426203964, 473697228, 620647886, 664749651, 908067535, 975543492, 344642305, 822174349, 726368697, 296849851, 320613543, 139052731, 31216065, 488715013, 360509094, 421511852, 322158747, 833999598, 397692982, 14980331, 76271004, 270523697, 863890303, 715250736, 477162541, 602483974, 926943299, 998920667, 374622157, 277317320, 231178115, 418427027, 49235085, 253129041, 555665252, 334125156, 338622350, 59004595, 36918332, 922721728, 422768891, 757463617, 325080890, 484088747, 140571557, 41446360, 428587248, 286992979, 771928655, 672724819, 556781080, 86445195, 392258996, 207848678, 486149604, 467123152, 860373968, 747110908, 324833347, 436958738, 629151854, 402732726, 78931861, 446699127, 278919716, 100566464, 218566106, 664032120, 789305794, 494961151, 335717950, 7236424, 661974300, 806502174, 123537496, 523034982, 832428797, 185075432, 678826539, 699322020, 537285748, 291876780, 778131759, 551298946, 836352924, 83644047, 218488486, 900706043, 726688593, 836582369, 854365026, 91220959, 190363391, 162234408, 579167612, 760904660, 198681981, 146105825, 399354733, 92372467, 237815553, 206706839, 114350550, 844577350, 355256562, 989793273, 856098692, 694079756, 824315188, 999161335, 133055685, 516683338, 55895763, 757996822, 753560918, 660891568, 717326867, 556273817, 536457050, 364279278, 568208239, 549990319, 444357405, 761908778, 538782523, 229671017, 8127403, 477249779, 177718552, 612259526, 112388546, 888464349, 488821659, 340551058, 402753580, 293041334, 999485174, 890756318, 165786504, 862914412, 901148362, 898311896, 891300698, 112858367, 670529433, 691306227, 671538507, 574400193, 473774359, 551735476, 111889310, 520511517, 136783298, 682932199, 240564673, 407782364, 739719249, 958480479, 839917237, 139673980, 503550606, 504331298, 765668705, 550426804, 823095534, 906787208, 41898550, 454984571, 179032373, 436703536, 663314897, 576419988, 12910271, 215888490, 121254150, 464579053, 583603822, 514567288, 902805791, 169725521, 475093194, 938053557, 563265485, 822443456, 85083402, 867831644, 111310514, 673399191, 165690377, 211384514, 283766253, 109033451, 310852344, 36254487, 705218987, 755512431, 351697842, 301562506, 43939543, 937350889, 877547174, 768316279, 820815612, 129524904, 907933309, 247978623, 137283191, 864547605, 690157179, 503237577, 718924217, 941924656, 476187236, 398869819, 405134890, 478474246, 76355146, 731228204, 812215696, 896182432, 581173512, 655351049, 170318880, 651905378, 436610238, 862335426, 980794966, 190339452, 113563060, 50355775, 134392006, 29926729, 180433797, 919515640, 643718324, 426153875, 607690834, 821644724, 478036928, 699159958, 175968852, 876053188, 471334551, 637316176, 600844968, 546563709, 340276970, 242114808, 892118077, 6479853, 257766520, 302472546, 932636171, 897145276, 449734141, 470780779, 387816709, 336929400, 394001600, 265352410, 572188769, 821684206, 123335994, 746452480, 39411297, 350606536, 835177890, 926763555, 373609036, 668043505, 352021924, 506995194, 101282065, 485159331, 37122329, 277564511, 339935752, 258853931, 986080842, 592139593, 255927745, 198264631, 112200355, 809615945, 13382701, 906100119, 317596899, 31706760, 851576786, 671421865, 950159077, 451051960, 355130395, 338516851, 700105368, 171941283, 916395278, 984388748, 665003299, 743132541, 205927141, 610525411, 634998871, 81613114, 555094671, 978814371, 312436959, 238285653, 261567873, 238993858, 247252247, 135342762, 661342217, 841840577, 279097948, 258280312, 187831537, 203407493, 277733303, 72760622, 562059091, 506070511, 509519077, 294314094, 851232594, 514016563, 910873137, 67633679, 605688733, 125722720, 523832772, 493915455, 437553668, 923236042, 909092340, 148360251, 32687305, 276680120, 248303960, 47151665, 899183233, 421578802, 138064107, 961910789, 678041497, 982617730, 988475552, 407608456, 494036034, 537746049, 891296982, 392625446, 360866289, 113918492, 277005797, 938165613, 592517616, 543307666, 538239896, 869041371, 488915081, 945937316, 929224143, 710035264, 635199808, 11027019, 976128342, 914854913, 181790898, 82363799, 497135348, 964649823, 184548947, 10368090, 857019874, 201750536, 762375659, 393756072, 135168347, 881372959, 900963708, 957761070, 653659352, 454726215, 432984694, 279670656, 176520163, 117070520, 615604429, 202117348, 704049478, 650220053, 965845652, 572194436, 270401083, 950721076, 206109073, 70108855, 253766837, 452538849, 477182337, 18581826, 984806586, 958218838, 363864686, 422419861, 994035764, 935482642, 943231071, 619174586, 984283929, 216591282, 537516518, 367672652, 151148053, 938572456, 194332482, 823966662, 581529950, 144527920, 311376611, 544091444, 970383684, 566840147, 774660870, 259607723, 111064201, 334896996, 393755252, 497986292, 611239147, 223211479, 722731070, 762065800, 899800379, 725042799, 544785396, 260606497, 667279007, 269172633, 850895593, 491849556, 382846772, 304895322, 71158983, 485987409, 675923988, 645159736, 92715379, 318367556, 722106969, 120975884, 148208771, 162410542, 647825034, 480348996, 217437132, 797343280, 644487726, 9790715, 509319856, 491035478, 606866261, 416983817, 281348799, 499720195, 697147603, 654720117, 698899680, 499713962, 91860103, 203029320, 247716921, 794098127, 357288085, 183749922, 694782320, 810592891, 949482295, 581545407, 875911264, 211509859, 754208824, 965513330, 602467230, 889366627, 16831320, 731579972, 736876138, 199893332, 277058476, 274352225, 512420251, 231661754, 999397014, 806966131, 370571040, 833726991, 650387677, 828892011, 237764615, 732529224, 572358928, 986616293, 597898077, 601059933, 122017790, 361146428, 284913651, 879777357, 136277824, 808157757, 44920089, 801592783, 94225970, 862918862, 655328128, 625707008, 323389980, 423625417, 366389466, 103647365, 975023823, 156289439, 422448055, 702845272, 949542175, 727010238, 937046663, 289307289, 212599524, 136519547, 899538216, 365041943, 746076536, 62430827, 180186341, 483058896, 23521573, 83291903, 519318359, 676683256, 5804359, 680044442, 279972335, 360410206, 768513153, 596270311, 697764385, 727596733, 554679759, 389598903, 30851994, 611658107, 409524531, 362643820, 432141852, 183654243, 430338950, 659183865, 605708447, 523751029, 421134812, 110833422, 952886192, 479571223, 663457539, 725220998, 175792609, 676014155, 370669572, 600620970, 917338140, 530764338, 749740314, 332377433, 610416698, 676727798, 314171138, 416975856, 437567050, 404554374, 843626425, 591767698, 639099914, 484205598, 454657297, 815852772, 81189131, 67557227, 179686656, 820317869, 34459798, 870272864, 88630856, 647420253, 961453572, 904312475, 28919847, 347438399, 843937275, 389520987, 97955240, 990662712, 698010320, 756374648, 738791536, 621020108, 757373993, 248640051, 31419980, 606831498, 75678195, 352248491, 443709799, 127022932, 199173386, 800689697, 562905962, 340573521, 422090894, 339951019, 162084187, 606092764, 57478078, 744195645, 49932710, 565592991, 199736, 159920602, 882691364, 117033078, 697838160, 190495543, 157273456, 26388002, 577100270, 708794080, 360080558, 697441880, 924634280, 664129160, 160651563, 819161060, 924408316, 170512886, 692272234, 761158998, 669209225, 497381086, 522856316, 16104936, 294486527, 230063565, 423471922, 533136942, 139856322, 25243987, 732380182, 174808640, 358273345, 655759625, 99324530, 789447370, 314922165, 771851381, 874752618, 630547320, 895703772, 288638932, 750131445, 265236905, 705495750, 307600795, 138504910, 293250090, 325540387, 555833992, 921557810, 1797781, 999997177, 1 };
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
// 縦に細長い格子として受け取る．
ll H; int w;
cin >> w >> H;
MFPS::set_conv(naive_convolution);
// TLE するので埋め込み
if (w == 9) {
EXIT(linearly_recurrent_sequence(seq9, coef9, H));
}
// pats : 一行あたりの彩色パターンのリスト
// [0..K) は黒マスであることを表す（同じ色は連結，違う色は非連結）
// -1 は白マスを表す
vvi pats; int K = 5;
// 黒の連の連結の仕方としてあり得るもの（辞書順で最小のものだけ）
vvvi maps(K + 1);
repi(k, 0, K) {
// sps : [0..k) の分割
auto sps = set_partitions(k);
// 分割に基づき彩色する．
repe(sp, sps) {
vi map(k);
rep(i, sz(sp)) repe(x, sp[i]) map[x] = i;
// 交差（i1<j1<i2<j2 で i1,i2 が同じ色，j1,j2 が同じ色，i1,j1 が異なる色）は許さない
bool ok = true;
rep(i1, k) repi(i2, i1 + 2, k - 2) {
if (map[i1] != map[i2]) continue;
repi(j1, i1 + 1, i2 - 1) {
if (map[i1] == map[j1]) continue;
repi(j2, i2 + 1, k - 1) {
if (map[j1] != map[j2]) continue;
ok = false;
}
}
}
if (ok) maps[k].push_back(map);
}
}
//dump("maps:"); dumpel(maps);
// set : 黒に塗る列の集合
repb(set, w) {
// pat_tmp : 隣接マスが連結であることだけを考慮して set を彩色したもの
vi pat_tmp(w, -1);
// k : 黒の連の個数
int k = 0;
rep(j, w) {
if (!getb(set, j)) continue;
pat_tmp[j] = k;
if (j == w - 1 || !getb(set, j + 1)) k++;
}
// pat_tmp をもとにして，上の行における連結の仕方も加味して再彩色する．
repe(map, maps[k]) {
vi pat(pat_tmp);
rep(j, w) if (pat[j] != -1) pat[j] = map[pat[j]];
pats.push_back(pat);
}
}
//dump("pats:"); dumpel(pats);
// 彩色パターンに通し番号を振る．
map<vi, int> pat_to_id; int L = 0;
repe(pat, pats) pat_to_id[pat] = L++;
// 塗り終わりを意味する彩色パターンを追加する．
pats.push_back(pats[0]);
// オートマトン（状態 L は塗り終わりを意味する）
vector<vector<int>> g(L + 1);
rep(pat_id, L) {
auto pat = pats[pat_id];
// 以降の uf で共通の部分は先に作っておく．
dsu uf_tmp(2 * w + K);
rep(j, w) if (pat[j] != -1) uf_tmp.merge(j, 2 * w + pat[j]);
repb(set, w) {
// 塗り終わり
if (set == 0) {
if (pat_id == 0) {
g[0].push_back(0);
}
else if (K == 1 || uf_tmp.size(2 * w + 1) == 1) {
g[pat_id].push_back(L);
}
continue;
}
// uf : 彩色パターン pat をもつ行と次の行 set の連結性を管理する．
// [0..w):patの行，[w..2w):setの行，[2w..2w+K):色
auto uf(uf_tmp);
rep(j, w) {
if (getb(set, j) && pat[j] != -1) uf.merge(j, w + j);
if (j > 0 && getb(set, j - 1)) uf.merge(w + j, w + (j - 1));
}
// set の行を左から順に見ていき，新たな連結成分を見つけるたびに新しい番号を与える．
vi npat(w, -1); vi map(2 * w + K, -1); int k = 0;
rep(j, w) {
if (!getb(set, j)) continue;
int ld = uf.leader(w + j);
if (map[ld] == -1) {
npat[j] = k;
map[ld] = k;
k++;
}
else {
npat[j] = map[ld];
}
}
// connected : pat の行と set の行が連結しているか
bool connected = true;
rep(j, w) if (pat[j] != -1 && map[uf.leader(j)] == -1) {
connected = false;
break;
}
// 連結でないなら遷移を許さない．
if (!connected) continue;
g[pat_id].push_back(pat_to_id[npat]);
}
}
g[L].push_back(L); // 塗り終わったなら塗りを再開できない．
//dump("g:"); dumpel(g);
// 数え上げ DP
vm dp(L + 1, 0);
dp[0] = 1;
//dump(dp);
vm seq;
int h = 2 * L + 10;
rep(i, h) {
// 遷移
vm ndp(L + 1, 0);
rep(s, L + 1) for (auto t : g[s]) ndp[t] += dp[s];
dp = move(ndp);
seq.push_back(dp[L]);
//dump(dp);
}
auto coef = berlekamp_massey(seq);
dump(L, sz(coef));
seq.resize(sz(coef));
dump_math(seq);
dump_math(coef);
EXIT(linearly_recurrent_sequence(seq, coef, H));
}