結果
| 問題 |
No.1561 connect x connect
|
| ユーザー |
 ecottea
|
| 提出日時 | 2025-09-09 01:46:43 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 61,132 bytes |
| コンパイル時間 | 8,880 ms |
| コンパイル使用メモリ | 338,128 KB |
| 実行使用メモリ | 7,720 KB |
| 最終ジャッジ日時 | 2025-09-09 01:46:56 |
| 合計ジャッジ時間 | 11,806 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 RE * 8 |
ソースコード
#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
// 愚直
int W;
bool naive(const string& s) {
int h = sz(s);
if (h == 0) return 1;
vi a(h * W);
rep(i, h) {
int val = s[i] - '0';
rep(j, W) {
int u = i * W + j;
a[u] = getb(val, j);
}
}
dsu d(h * W + 1);
rep(i, h) rep(j, W - 1) {
int u = i * W + j;
int v = i * W + (j + 1);
if (a[u] && a[v]) d.merge(u, v);
}
rep(i, h - 1) rep(j, W) {
int u = i * W + j;
int v = (i + 1) * W + j;
if (a[u] && a[v]) d.merge(u, v);
}
rep(i, h) rep(j, W) {
int u = i * W + j;
if (!a[u]) d.merge(u, h * W);
}
return sz(d.groups()) <= 2;
}
// DFA 埋め込み用のコードを出力する（状態数は最小とは限らない）
pair<vvi, vb> embed_DFA(int COL, int len_max, int L_max1, int L_max2, int loop_cnt, vector<string> ssB) {
mt19937_64 mt((int)time(NULL));
uniform_int_distribution<int> rnd_len(1, len_max);
uniform_int_distribution<int> rnd_col(0, COL - 1);
uniform_int_distribution<int> rnd(0, INF);
vector<string> ssT{ "" };
ssB.push_back("");
queue<string> q;
rep(loop, loop_cnt) {
repe(sT, ssT) q.push(sT);
ssT.clear();
// ランダムな文字列を追加する．
rep(hoge, L_max1) {
int len = rnd_len(mt);
string s;
rep(fuga, len) s += '0' + rnd_col(mt);
ssB.push_back(s);
}
// 偶然では入りにくそうなランダム文字列を追加するならここ（長いうねうねを入れる）
rep(hoge, L_max2) {
int h = 11;
vvb c(h, vb(W));
priority_queue<tuple<int, int, int>> q;
int t = 0;
int x = rnd(mt) % h;
int y = rnd(mt) % W;
q.emplace(rnd(mt) % 5 + t++, x, y);
while (!q.empty()) {
auto [pri, x, y] = q.top(); q.pop();
int cnt = 0;
rep(k, 4) {
int nx = x + DX[k];
int ny = y + DY[k];
if (inQ(nx, ny, 0, 0, h, W) && c[nx][ny]) cnt++;
}
if (cnt >= 2) continue;
c[x][y] = 1;
rep(k, 4) {
int nx = x + DX[k];
int ny = y + DY[k];
if (inQ(nx, ny, 0, 0, h, W) && !c[nx][ny]) q.emplace(rnd(mt) % 5 + t++, nx, ny);
}
}
//dumpel(c);
string s;
rep(i, h) {
int val = 0;
rep(j, W) val = val * 2 + (int)c[i][j];
s += '0' + val;
}
rep(i, sz(s)) {
ssB.push_back(s.substr(i));
}
}
uniq(ssB);
int LB = sz(ssB);
// 区別が付く限り ssT を伸ばす．
vvb mat; set<vb> rows;
while (!q.empty()) {
auto sT = q.front(); q.pop();
vb row(LB);
rep(j, LB) row[j] = naive(sT + ssB[j]);
if (rows.count(row)) continue;
mat.push_back(row);
rows.insert(row);
ssT.push_back(sT);
rep(c, COL) q.push(sT + (char)('0' + c));
}
int LT = sz(ssT);
// ユニークな列番号を抜き出す（文字列は短いものを優先する）
map<vb, string> columns_to_sB;
rep(j, LB) {
vb column(LT);
rep(i, LT) column[i] = mat[i][j];
if (!columns_to_sB.count(column)) {
columns_to_sB[column] = ssB[j];
}
else {
auto sB = columns_to_sB[column];
if (sz(sB) > sz(ssB[j])) columns_to_sB[column] = ssB[j];
}
}
ssB.clear();
for (auto [column, sB] : columns_to_sB) ssB.push_back(sB);
sort(all(ssB));
LB = sz(ssB);
// 途中再開用
if (loop % 1 == 0) {
dump("//loop:", loop, "LT:", LT, "LB:", LB);
string eb;
eb += "vvi ssB_int = {";
rep(j, LB) {
eb += "{";
repe(c, ssB[j]) {
eb += to_string(smod(c - '0', 256));
eb += ",";
}
if (eb.back() == ',') eb.pop_back();
eb += "},";
}
if (eb.back() == ',') eb.pop_back();
eb += "};\n\n";
cerr << eb;
}
}
int LT = sz(ssT);
int LB = sz(ssB);
// row_to_i[row] : row の mat における行番号（状態番号）
map<vb, int> row_to_i;
// ac[i] : 状態 i が受理状態か
vb ac(LT);
rep(i, LT) {
vb row(LB);
rep(j, LB) row[j] = naive(ssT[i] + ssB[j]);
row_to_i[row] = i;
ac[i] = row[0];
}
// 各文字による遷移を求める．
vvi nxts(COL, vi(LT));
rep(c, COL) {
rep(i, LT) {
vb row(LB);
rep(j, LB) row[j] = naive(ssT[i] + (char)('0' + c) + ssB[j]);
nxts[c][i] = row_to_i[row];
}
}
// スパース埋め込み用の文字列を出力する．
//string eb;
//eb = "constexpr int DIM = ";
//eb += to_string(LT);
//eb += ";\n";
//eb += "constexpr int COL = ";
//eb += to_string(COL);
//eb += ";\n";
//eb += "int nxts[COL][DIM] = {\n";
//rep(c, COL) {
// eb += "{";
// rep(i, LT) {
// eb += to_string(nxts[c][i]);
// eb += ",";
// }
// eb.pop_back();
// eb += "},\n";
//}
//eb.pop_back();
//eb.pop_back();
//eb += "};\n";
//eb += "bool ac[DIM] = {";
//rep(i, LT) {
// eb += to_string(ac[i]);
// eb += ",";
//}
//eb.pop_back();
//eb += "};\n";
//cout << eb;
//exit(0);
return { nxts, ac };
}
template <class VTYPE>
vector<VTYPE> solve(int n, const vvi& nxts, const vb& ac) {
int DIM = sz(ac);
int COL = sz(nxts);
// 数え上げ DP
vector<VTYPE> dp(DIM);
dp[0] = 1;
auto apply = [&](const vector<VTYPE>& x) {
vector<VTYPE> z(DIM);
rep(c, COL) { // 重ね合わせ
rep(i, DIM) {
int j = nxts[c][i];
z[j] += x[i];
}
}
return z;
};
vector<VTYPE> res(n + 1);
res[0] = (int)ac[0];
rep(p, n) {
dp = apply(dp);
rep(i, DIM) if (ac[i]) res[p + 1] += dp[i];
}
return res;
}
//【線形漸化式の発見】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,22,29,37 };
vm seq2 = { 1,4,14,41,109,276,682,1665,4041,9780,23638,57097,137877 };
vm seq3 = { 1,7,41,219,1127,5727,28993,146643,741557,3749817,18961451,95880895,484833213,451616851,396892233,686360043,981035163,852304263,13310738,963770472,287207713,160261394,773383719 };
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,284152724,990192911,985602945,184628569,143013865,120357459,135871980,693625982,923420526,935325710,232157438,179845337,642659778,928044618,599227642,429003718,808616661,796217954,104253039 };
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,632065513,233414551,425723448,668541543,395252600,948108329,415936461,936971287,807826612,208563369,385680592,915191639,982414084,119125505,245116289,652724548,553342193,353630601,164609786,388450583,428700038,12346035,723785522,759402483,991725166,966973770,273572835,930570813,280051754,519978289,374543183,92200419,226676645,296219849,527096604,207631412,18999862,632196698,361843573,810227422,529426991 };
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, 21490101, 639637731, 572881708, 766595873, 767939847, 800732318, 706345605, 549051522, 625193563, 16831163, 641408132, 715352262, 252575416, 849525237, 451254834, 154836313, 875072125, 857138290, 85504825, 43664163, 328113173, 469628779, 738455979, 301383171, 227452744, 643952737, 421179754, 838409908, 630538123, 568667002, 265423707, 249151165, 60716613, 217355206, 116129714, 63635093, 905389533, 184685402, 515736985, 227392079, 31713056, 76862195, 112672383, 534885465, 262104900, 168571937, 67257990, 313819795, 905116519, 665071483, 636607860, 194818406, 121405682, 853051069, 300594873, 952805076, 156961260, 590791198, 898252278, 730986405, 417045335, 142841961, 334902240, 897086206, 428277445, 186801201, 159105880, 854064184, 316796677, 153650552, 722350825, 139658675, 787552276, 23075458, 317870904, 596331290, 850629199, 180028751, 959548985, 481460603, 135651036, 780640327, 43173942, 489236080, 213063589, 262789237, 801410913, 945945961, 269667789, 768761768, 897810837, 109609952, 3184352, 172901738, 491772780, 398013072, 542678293, 496479689, 311637388, 954554171, 180126699, 568225985, 865389846, 572540859, 444632655, 139079422, 665137472, 566475370, 970181806, 381669268, 65317181, 471595677, 911372398, 929514139, 613572182, 297207994, 959547646 };
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,575567486,286763333,606725160,18008541,758299732,373138923,527449399,277338661,951314382,136928878,517354156,958264646,476381297,517661700,418951514,594925090,766767570,632423322,158924454,216993746,87677437,460735107,213378656,75798722,810498704,498131596,804233142,46616600,126236001,75726098,12494567,137140336,462013349,514605592,36371763,900304398,353370159,159178737,385565941,202256035,749707905,585244420,368607384,161372044,902321329,332777237,497271621,892689965,417308140,992400014,112355401,862835117,840275499,926482021,145476287,503687100,819367241,94465357,29534742,404125776,994606266,702779053,727169225,488931845,908250587,965893045,454596516,504943447,536580798,887270976,336238695,42825017,61715601,721194360,926269328,455233125,176379458,401022099,997694806,736660306,28764248,43601270,915483948,251386638,547146661,209214261,767872659,198009595,304348328,535645795,590354801,641872540,676928197,892980838,934433857,794932753,437963682,60438780,881980373,633986343,717718531,792975553,84059054,729878949,704864626,410844748,108887833,457337850,414985018,131963859,741566199,699925322,907788358,534135779,84813474,574894622,637795122,591882869,317003938,959093968,509688014,976315901,181502121,69921533,496704608,258795002,74876815,934998101,851342701,873185907,86019016,341788147,252606683,176203833,796840691,743454463,952296568,275524870,138772298,457478922,534369147,945961725,986258992,319610564,126934163,68976768,676525792,959155513,778798209,527550757,391339110,777608613,408659454,197973085,590324844,215758575,825267334,550942261,207265894,133310616,96765771,841921875,121474802,688884325,243800158,296204657,53920606,749844765,100785752,351608645,279695985,387923476,164409176,213725721,685932076,6810363,376142993,507812608,156973118,766932193,436276494,566160279,285531488,43454497,660134679,238493590,419611906,100765248,802570425,246804154,971312844,793055082,655538242,159278173,415352286,384061013,95312478,124511538,509718349,90947188,851075111,891946863,87383646,777877286,569214874,372501964,460011179,726697785,736587897,617111795,813746799,763697404,570139798,907194078,51347645,889399680,257007806,175793822,685858696,2914139,767627150,206028019,378451681,932879321,711925782,464082753,425528942,462913995,232519317,880921158,995190158,302491849,362607870,114475880,649876878,270938603,471751106,830705803,964371062,997446178,332619703,863719107,888220680,716664089,136709302,863071346,90386037,718083692,685273532,532687723,668325165,724535148,721829609,617463684,102877557,769812043,696671632,989431435,408648174,731831222,223847061,503114921,551782254,775989974,631712860,274316251,62463578,695568512,338450513,283029850,802313071,209906971,264322,709649928,269576201,702720627,814278237,655427360,353552951,363524852,641197272,331060051,920478103,831984992,911703539,304511205,997725578,887524692,275410051 };
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,767954796,760013476,112335652,2445671,300031843,593601579,245901542,564165281,606924411,736706629,197828373,21437613,119678073,388447783,530223046,437299745,345656829,635554902,923943422,277703204,878518261,216643694,468586237,936395670,471648524,576855969,384612389,393578617,654487915,401809619,797419758,18972981,36053268,272741565,793909681,463720052,814488999,215499318,685632085,39929749,128191168,938819262,118772102,266535989,323013746,142341542,754989062,367966690,934159498,606931379,503523352,311158982,171538144,797721938,676232643,181824381,749320795,822148403,726776286,822947151,889225923,461263488,566280229,317498950,494935075,743000460,249271450,966002889,860962688,199029579,992221695,223813563,906255479,686196350,467214136,390333727,751265050,327306060,435516157,824736884,860365636,983874998,487483458,563212663,727702338,474580078,775028619,786209740,407503778,275702362,527165758,126644178,635334306,554042692,717149281,706258851,46655030,102608855,218903999,174673285,866142684,549528485,253966421,388354496,497574523,305842630,212783503,872491301,257578564,918367603,641462613,128894526,363618532,681090609,791960387,797396587,692149162,169768013,844522776,467580668,876013313,328574628,375957474,598772172,576235703,904597432,698268541,10628228,62409735,711372382,827063868,652076380,700144013,729471030,31482135,762266918,822481705,476976143,923668013,938137998,695655090,932739134,991985348,270454067,811843005,128791802,201699783,832612903,786327673,274424358,196115639,70008300,283746237,911245498,683421131,710918513,390057245,452845317,305841221,929948148,953952758,3499181,693272553,71834291,137023432,706219032,382504735,283033915,498784686,52290094,118686071,814465438,197871751,538681160,733137307,485604994,478447224,463915384,930474860,750062981,680691703,699836705,2325474,986441504,159527687,187709791,953498897,983846638,539255323,429012693,9270893,932027574,390901173,1039253,628665668,988020984,268875116,855920091,47873767,379482778,163732117,195705315,930109156,255751039,954375654,760682809,553231934,945149663,267235844,976507803,940467890,323409975,474060098,626627330,49676120,284598403,170448765,644604220,422849720,643756492,585267377,333322244,340967980,142640090,233659614,495739229,90966216,971221659,567992294,236444470,950311140,77430927,879245592,312953270,474292575,210268849,732371190,7154557,625301413,120195181,213859178,994903601,618779904,798486766,728965318,708936949,401212160,424619136,79784377,910529763,718783912,767712277,105578011,947040388,133354033,885939257,382243341,810631060,281930108,986654888,668646081,467249914,689036697,462431318,476469532,495816518,46083624,744296257,172169219,54219994,12056426,384285927,746849868,802165038,965117714,2630914,201118047,48795590,509721354,980727863,672319046,498147049,358340045,474937789,576200276,641830419,465576381,528031159,980570104,688178430,892777467,292523612,530002816,867454716,165559085,521918901,819844833,13159154,661208658,464726028,791377096,509146498,734695375,445520107,550292018,852822297,255697730,882279308,152726016,250472602,343775150,590767862,534169163,740934610,968136116,55190994,237394864,80090324,922630468,105843209,399998422,994688143,668343658,595201847,210743496,980663233,357327506,290987434,25339917,671790222,995943476,983697319,933471410,225950872,755501333,980351227,831636704,421859457,537372271,734485020,898893991,858775434,529401591,578347357,42605442,338631767,616969142,55689082,822221917,27983060,696392227,670630004,926493454,166075001,40393886,74615779,864408853,487256912,107383231,861899143,715943604,432075794,579684351,7373166,774719823,550647237,156538468,941512865,678434696,36504802,610751617,637410720,403690416,755404173,730967089,482998455,633763188,425479706,826533913,81162305,396798544,570572821,293761502,766590177,110894899,180648224,734094839,647780493,140290529,589786173,280183999,641813682,984422349,799624381,786334358,810329475,802257500,742037559,196190432,811017728,754995733,623547568,459853709,371816356,423756226,547736617,727215837,764202466,93624314,683127726,261795326,326103303,25044446,559713459,738805422,882691131,13444530,11327419,391529318,769704800,887138832,898878748,505181332,756770887,656290914,331709988,597258271,53245284,151770192,772973428,796914762,306963277,917922798,887974291,995141005,380311919,435048327,125733716,678455136,728560279,737824089,341797055,287902028,14621396,236203275,780751233,917926845,64551906,66582820,681915041,327440045,255384087,426044318,974969165,77529968,891522597,528591657,108629212,383773839,24470685,327327456,222813689,642962587,360350860,438721716,317125846,646966,263343706,138736334,647697402,287797304,220330414,966691062,188770760,6724124,338606548,110561607,174278223,920597146,871096964,439172453,922990693,591222581,611344935,97957696,196288979,909829745,168584473,950300008,448321156,407258244,768721945,30903496,669358699,637015997,555813578,557571587,69664777,983143030,289578765,235207116,410045524,903871683,504205721,217687013,587026638,902660815,186467565,463461625,925752055,796723557,457161446,51191719,563249779,833645973,411391765,538256034,111574415,675299674,54526119,338206087,776595030,331318393,932625152,844658730,392585075,540136627,506378697,176322801,111797222,533040687,164897102,392211615,718752600,627601437,496397114,838922278,426767010,406895495,92231324,185297198,620691297,497594210,700452008,213238182,424196443,387250418,817502638,335354826,800708600,493493391,352978820,366043116,453167039,716733073,226602614,108425180,575171339,12300909,462865588,704880927,676001985,719134634,326955376,116718416,879220489,349369132,600088955,515124871,917498677,825874431,446335762,910612660,447836421,700444902,866609319,109581507,902654857,230991388,639396617,221802981,388171181,271807604,405634654,738714650,298645607,726181577,42755107,486882307,334896907,472314413,871712753,147346878,716595864,634158023,808479924,262500737,868655470,958568881,960314700,82156315,963543832,720546123,421216334,322348697,426401391,561507416,909923251,726398494,484189931,786972421,421217226,700322226,917619087,600353018,3641870,801144738,196609802,308562514,807651580,443750008,994404107,617225136,933854598,499109688,705743842,41670188,335728527,178344302,809886628,706697083,450173249,717857777,170688947,911532042,23598281,812306190,352097700,894181673,397171080,727462603,217622785,645669609,724922592,771203326,893492326,39609503,895245261,232211821,587628493,646078534,173906665,847468649,406402015,601112252,384867933,116262736,903400483,356903815,730231564,239240844,674802521,723944332,173016331,471037476,489020227,978916100,958947391,333123617,193430324,842022324,578210309,665731269,396294964,638609499,557834884,234868378,468226503,736056313,588384818,681051845,830262381,914120033,355873823,184633332,93750081,932327277,506568163,123092059,167763924,30651799,243965624,930627896,367260371,695707963,289148127,607854772,369041054,780079539,569536532,686843750,81837842,895019928,271129740,132454960,76103872,675258833,900706614,61113661,368575815,844208663,598541999,237680884,625767854,636267840,442359810,946482597,550095526,772600088,457572483,728497717,60830631,951528679,909599513,421217258,757003367,234313995,348314601,540495769,611975044,790108080,437314975,717068676,884011838,864335938,815674695,234469791,712775900,309059260,127738914,459708399,254956586,953197889,188617304,569096931,942499138,897407120,470351006,637545423,481387462,267608397,318231948,446523265,855721112,747662277,934323048,730264504,205769538,984194894,200801773,331578513,69990791,870141669,877466067,927975775,410416021,820807965,649529557,231229321,732896955,801458514,284902160,179129072,694310223,14513585,685481177,717630929,837394485,533171913,981854146,741588458,420284190,158342555,483947995,168432738,363883436,983959506,651288811,707253636,511419779,377136431,456961321,214346418,426156955,377202390,568607792,26506485,9465493,233427679,578270619,271633770,473199276,55893077 };
//loop: 0 LT: 837 LB: 276
vvi ssB_int = { {},{208,95,232,87,221,139,217,119},{209,190,161,255},{210,94,181,239},{212},{213,89,79,184,231,189},{213,101,173,233,155,246},{213,127,201},{213,181,215,117},{213,191,104,223},{214,85,247},{214,125,197,191},{215},{215,117},{215,149,253},{215,169,191,201,123},{216,111,178,220,118,219},{217,111,154,247,173},{217,119},{218,117,207,169,251},{218,166,253,167},{219},{219,78,245,159},{219,82,223,129,158,242,175},{219,182,229,93,169,255},{220,118,219},{221,131,222,105,171,238,179,133,255},{221,139,217,119},{221,147,238,181,87,241,175},{222,105,171,238,179,133,255},{222,105,173,243,158},{223},{223,177,175,233},{225,141,59,234,155,181,143,248,131,254},{227,149,255},{227,154,171,189,213,91,210,94,181,239},{229,93,169,255},{229,189,171,213,191,104,223},{230,57,215,149,253},{231},{231,189},{232,87,221,139,217,119},{233},{233,47,218,117,207,169,251},{233,155,246},{233,157,163,253,167,144,255},{234,142,243,157,231},{234,155,181,143,248,131,254},{235,157,213,101,173,233,155,246},{235,174,41,231,181,198,125,215},{235,190,212},{237},{237,91,234,142,243,157,231},{237,171,157,231,57,213,181,215,117},{237,187},{238,59,197,127},{238,181,87,241,175},{239},{239,53,227,149,255},{241,91,206,163,189,213,89,79,184,231,189},{241,175},{242,159},{242,175},{243,141,251,86},{243,158},{245,27,234,171,154,239,53,227,149,255},{245,141,251},{245,151,216,111,178,220,118,219},{245,159},{246},{246,92},{247},{247,164,223,97,223,177,175,233},{248,131,254},{249,13,245,141,251},{250,143,241,29,229,189,171,213,191,104,223},{251},{251,86,237,91,234,142,243,157,231},{253},{253,167},{254},{255},{255,171,42,207,148,155,46,112,207},{2,7,13,27,54,107,217,111,154,247,173},{7,13,27,54,107,217,111,154,247,173},{13,245,141,251},{25,247,173,209,190,161,255},{27,234,171,154,239,53,227,149,255},{27,54,107,217,111,154,247,173},{29,229,189,171,213,191,104,223},{29,235,190,212},{37,237,171,157,231,57,213,181,215,117},{41,231,181,198,125,215},{41,253,129,255},{43,122,215,169,191,201,123},{47,218,117,207,169,251},{53,227,149,255},{54,107,217,111,154,247,173},{57,213,181,215,117},{57,215,149,253},{59,233,157,163,253,167,144,255},{59,197,127},{63,97,223,176,199,125,192,157,231,178,223},{64,255},{75,218,182,155,237,187},{76,216,180,222,105,173,243,158},{78,245,159},{79,184,231,189},{80,207,185,167,237},{82,223,129,158,242,175},{83,221,131,222,105,171,238,179,133,255},{85,214,187,214,85,247},{85,247},{85,205,187,138,251},{86},{86,237,91,234,142,243,157,231},{87,221,139,217,119},{87,241,175},{87,89,231,157,197,125,139,242,159},{89,231,157,197,125,139,242,159},{89,79,184,231,189},{91,210,94,181,239},{91,234,142,243,157,231},{92},{93,231,173,219,182,229,93,169,255},{93,169,255},{93,194,127,80,207,185,167,237},{94,243,141,251,86},{94,181,239},{95,232,87,221,139,217,119},{97,223,176,199,125,192,157,231,178,223},{97,223,177,175,233},{101,173,233,155,246},{103,76,247,129,119,218,166,253,167},{104,223},{105,220,183,173,139,246,92},{105,171,238,179,133,255},{105,173,243,158},{107,217,111,154,247,173},{108,199,41,253,129,255},{109,43,122,215,169,191,201,123},{109,75,218,182,155,237,187},{111,154,247,173},{117},{117,207,169,251},{118,219},{119},{119,218,166,253,167},{121,207,185,163,222,105,179,214,125,197,191},{122,215,169,191,201,123},{122,134,253,147,238,59,197,127},{123},{125,215},{125,139,242,159},{127},{128,191,169,229,29,235,190,212},{129,255},{129,158,242,175},{131,254},{132,181,219,78,245,159},{133,255},{134,253,147,238,59,197,127},{138,251},{139,217,119},{139,242,159},{141,251},{141,59,234,155,181,143,248,131,254},{142,243,157,230,57,215,149,253},{142,243,157,231},{143,241,29,229,189,171,213,191,104,223},{143,248,131,254},{144,255},{145,238,153,213,127,201},{147,238,59,197,127},{147,238,181,87,241,175},{147,246,76,216,180,222,105,173,243,158},{149,253},{149,255},{151,216,111,178,220,118,219},{153,213,127,201},{153,167,249,13,245,141,251},{154,239,53,227,149,255},{154,247,173},{154,171,189,213,91,210,94,181,239},{155,246},{155,181,143,248,131,254},{157,230,57,215,149,253},{157,231},{157,231,178,223},{157,161,255,64,255},{157,197,125,139,242,159},{158},{158,242,175},{159},{161,255},{163,222,105,179,214,125,197,191},{163,253,167,144,255},{163,189,213,89,79,184,231,189},{164,223,97,223,177,175,233},{166,253,167},{167},{167,237},{169,229,29,235,190,212},{169,251},{169,255},{169,191,145,238,153,213,127,201},{170,219,82,223,129,158,242,175},{171,213,191,104,223},{171,238,179,133,255},{171,154,239,53,227,149,255},{171,157,231,57,213,181,215,117},{171,189,213,91,210,94,181,239},{173},{173,219,182,229,93,169,255},{173,233,155,246},{173,243,158},{173,139,246,92},{173,183,85,214,187,214,85,247},{174,41,231,181,198,125,215},{174,163,190,201,119,157,161,255,64,255},{175},{175,233},{175,245,27,234,171,154,239,53,227,149,255},{175,105,220,183,173,139,246,92},{176,199,125,192,157,231,178,223},{177,173,183,85,214,187,214,85,247},{177,175,233},{178,220,118,219},{178,223},{179,214,125,197,191},{179,221,85,205,187,138,251},{179,133,255},{180,222,105,173,243,158},{181,219,78,245,159},{181,221,147,238,181,87,241,175},{181,239},{181,87,241,175},{181,143,248,131,254},{181,198,125,215},{182,155,237,187},{183,220,87,89,231,157,197,125,139,242,159},{183,85,214,187,214,85,247},{183,173,139,246,92},{184,231,189},{185,239,153,167,249,13,245,141,251},{185,163,222,105,179,214,125,197,191},{185,167,237},{186,199,93,194,127,80,207,185,167,237},{187},{187,237,183,208,95,232,87,221,139,217,119},{187,138,251},{188,230,187,108,199,41,253,129,255},{189},{189,213,89,79,184,231,189},{189,235,174,41,231,181,198,125,215},{190,212},{190,161,255},{191},{191,201,123},{192,157,231,178,223},{193,94,243,141,251,86},{194,127,80,207,185,167,237},{197,125,139,242,159},{197,127},{197,191},{198,125,215},{199,41,253,129,255},{199,125,192,157,231,178,223},{201},{201,119,157,161,255,64,255},{201,123},{203,122,134,253,147,238,59,197,127},{205,187,138,251},{206,163,189,213,89,79,184,231,189},{207,169,251},{207,185,163,222,105,179,214,125,197,191} };
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 してくれる．
W = 8;
// dump("naive:", naive("010")); dump("=====");
vector<string> ssB;
// 途中から再開
repe(a, ssB_int) {
string s;
repe(x, a) s += '0' + x;
ssB.push_back(s);
}
// --------------------- 埋め込み用 ---------------------
// (文字の種類数，長さの最大値，1回で追加する文字列の量，反復回数, 検証用文字列集合)
//auto [nxts, ac] = embed_DFA(1 << W, 9, 1, 20, 1, ssB);
//int DIM = sz(ac);
//auto dp = solve<mint>(2 * DIM, nxts, ac);
//dump_math(dp);
//return 0;
// ------------------------------------------------------
vvm seqs{ vm(), seq1, seq2, seq3, seq4, seq5, seq6, seq7, seq8 };
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); // N=8 は WA
}