結果
| 問題 |
No.1561 connect x connect
|
| コンテスト | |
| ユーザー |
 ecottea
|
| 提出日時 | 2025-09-09 01:17:13 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 49,543 bytes |
| コンパイル時間 | 7,413 ms |
| コンパイル使用メモリ | 338,252 KB |
| 実行使用メモリ | 7,720 KB |
| 最終ジャッジ日時 | 2025-09-09 01:17:24 |
| 合計ジャッジ時間 | 9,102 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 18 WA * 3 RE * 14 |
ソースコード
#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, vi> 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 = 9;
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 が受理状態か
vi 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> solve1(int n) {
// --------------- embed_DFA() からの出力を貼る ----------------
constexpr int DIM = 4;
constexpr int COL = 2;
int nxts[COL][DIM] = {
{0,2,2,3},
{1,1,3,3} };
bool ac[DIM] = { 1,1,1,0 };
// --------------------------------------------------------------
// 数え上げ DP
array<VTYPE, DIM> dp;
dp.fill(0);
dp[0] = 1;
auto apply = [&](const array<VTYPE, DIM>& x) {
array<VTYPE, DIM> z;
z.fill(INF);
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] += dp[i];
}
return res;
}
template <class VTYPE>
vector<VTYPE> solve2(int n) {
// --------------- embed_DFA() からの出力を貼る ----------------
constexpr int DIM = 6;
constexpr int COL = 4;
int nxts[COL][DIM] = {
{0,4,4,4,4,5},
{1,1,5,1,5,5},
{2,5,2,2,5,5},
{3,3,3,3,5,5} };
bool ac[DIM] = { 1,1,1,1,1,0 };
// --------------------------------------------------------------
// 数え上げ DP
array<VTYPE, DIM> dp;
dp.fill(0);
dp[0] = 1;
auto apply = [&](const array<VTYPE, DIM>& x) {
array<VTYPE, DIM> z;
z.fill(0);
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;
}
template <class VTYPE>
vector<VTYPE> solve3(int n) {
// --------------- embed_DFA() からの出力を貼る ----------------
constexpr int DIM = 11;
constexpr int COL = 8;
int nxts[COL][DIM] = {
{0,5,5,5,4,5,4,5,5,5,5},
{3,4,3,3,4,4,4,3,4,4,3},
{1,1,1,4,4,4,4,1,1,4,4},
{2,2,2,2,4,4,4,2,2,4,2},
{9,4,4,4,4,4,4,9,9,9,9},
{6,4,6,6,4,4,6,10,6,6,10},
{8,8,8,4,4,4,4,8,8,8,8},
{7,7,7,7,4,4,7,7,7,7,7} };
bool ac[DIM] = { 1,1,1,1,0,1,0,1,1,1,1 };
// --------------------------------------------------------------
// 数え上げ DP
array<VTYPE, DIM> dp;
dp.fill(0);
dp[0] = 1;
auto apply = [&](const array<VTYPE, DIM>& x) {
array<VTYPE, DIM> z;
z.fill(0);
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;
}
template <class VTYPE>
vector<VTYPE> solve4(int n) {
// --------------- embed_DFA() からの出力を貼る ----------------
constexpr int DIM = 23;
constexpr int COL = 16;
int nxts[COL][DIM] = {
{0,1,14,14,14,1,1,1,14,14,1,14,14,14,14,14,14,14,1,14,14,14,14},
{12,1,1,12,12,1,1,1,1,1,1,12,12,1,1,12,12,1,1,1,1,12,12},
{2,1,2,2,1,1,1,1,1,1,1,2,1,2,1,2,1,2,1,2,1,2,1},
{15,1,15,15,15,1,1,1,1,1,1,15,15,15,1,15,15,15,1,15,1,15,15},
{9,1,1,9,9,1,1,1,9,9,1,9,1,9,1,1,1,9,1,1,1,1,9},
{18,1,1,22,22,1,1,1,18,18,18,22,18,18,1,18,18,18,18,1,1,18,22},
{13,1,13,13,13,1,1,1,13,13,1,13,1,13,1,13,1,13,1,13,1,13,13},
{3,1,3,3,3,1,1,1,3,3,3,3,3,3,1,3,3,3,3,3,1,3,3},
{20,1,1,1,20,1,1,1,20,1,1,20,1,1,1,1,20,20,1,20,20,20,1},
{5,1,1,5,16,5,1,5,5,1,5,16,5,1,1,5,16,5,1,5,5,16,5},
{6,1,6,6,6,1,6,6,6,1,1,19,1,6,1,6,6,19,1,19,6,19,1},
{7,1,7,7,21,7,7,7,7,1,7,21,7,7,1,7,21,21,1,21,7,21,7},
{8,1,1,8,8,1,1,1,8,8,1,8,1,8,1,1,8,8,1,8,8,8,8},
{10,1,1,4,4,10,1,10,10,10,10,4,10,10,1,10,4,10,10,10,10,4,4},
{17,1,17,17,17,1,17,17,17,17,1,17,1,17,1,17,17,17,1,17,17,17,17},
{11,1,11,11,11,11,11,11,11,11,11,11,11,11,1,11,11,11,11,11,11,11,11} };
bool ac[DIM] = { 1,0,1,1,1,0,0,0,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1 };
// --------------------------------------------------------------
// 数え上げ DP
array<VTYPE, DIM> dp;
dp.fill(0);
dp[0] = 1;
auto apply = [&](const array<VTYPE, DIM>& x) {
array<VTYPE, DIM> z;
z.fill(0);
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;
}
template <class VTYPE>
vector<VTYPE> solve5(int n) {
// --------------- embed_DFA() からの出力を貼る ----------------
constexpr int DIM = 53;
constexpr int COL = 32;
int nxts[COL][DIM] = {
{0,32,32,32,32,33,32,32,32,33,33,33,32,33,32,32,32,33,33,33,33,33,33,33,32,33,33,33,32,33,32,32,32,33,32,32,33,32,32,32,32,32,32,32,32,33,32,32,32,32,32,32,33},
{1,1,33,1,33,33,33,1,33,33,33,33,33,33,33,1,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,1,33,33,1,1,33,1,33,1,33,1,1,1,33,33,33,1,33,1,1,1,33},
{2,33,2,2,33,33,2,2,33,33,33,33,33,33,2,2,33,33,33,33,33,33,33,33,33,33,33,33,33,33,2,2,33,33,33,33,33,33,2,2,2,2,33,33,33,33,2,2,2,2,33,33,33},
{3,3,3,3,33,33,3,3,33,33,33,33,33,33,3,3,33,33,33,33,33,33,33,33,33,33,33,33,33,33,3,3,33,33,3,3,33,3,3,3,3,3,3,3,33,33,3,3,3,3,3,3,33},
{4,33,33,33,4,33,4,4,33,33,33,33,4,33,4,4,33,33,33,33,33,33,33,33,33,33,33,33,4,33,4,4,33,33,4,4,33,4,33,33,33,33,33,33,4,33,4,4,33,33,33,4,33},
{5,5,33,5,5,5,5,34,33,33,33,33,5,5,5,34,33,33,33,33,33,33,33,33,33,33,33,33,5,5,5,34,33,33,34,34,33,34,33,5,33,5,5,5,5,5,5,34,33,5,5,34,5},
{6,33,6,6,6,33,6,6,33,33,33,33,6,33,6,6,33,33,33,33,33,33,33,33,33,33,33,33,6,33,6,6,33,33,6,6,33,6,6,6,6,6,33,33,6,33,6,6,6,6,33,6,33},
{7,7,7,7,7,7,7,7,33,33,33,33,7,7,7,7,33,33,33,33,33,33,33,33,33,33,33,33,7,7,7,7,33,33,7,7,33,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7},
{8,33,33,33,33,33,33,33,8,33,33,33,8,33,8,8,33,33,33,33,33,33,33,33,8,33,33,33,8,33,8,8,33,33,33,8,33,8,8,8,8,8,8,8,33,33,33,33,33,33,33,33,33},
{9,9,33,9,33,33,33,9,9,9,33,9,9,9,9,42,33,33,33,33,33,33,33,33,9,9,33,9,9,9,9,42,33,33,9,42,33,42,9,42,9,42,42,42,33,33,33,9,33,9,9,9,33},
{10,33,10,10,33,33,10,10,10,33,10,10,10,33,38,38,33,33,33,33,33,33,33,33,10,33,10,10,10,33,38,38,33,33,33,10,33,10,38,38,38,38,10,10,33,33,10,10,10,10,33,33,33},
{11,11,11,11,33,33,11,11,11,11,11,11,11,11,39,39,33,33,33,33,33,33,33,33,11,11,11,11,11,11,39,39,33,33,11,39,33,39,39,39,39,39,39,39,33,33,11,11,11,11,11,11,33},
{12,33,33,33,12,33,12,12,12,33,33,33,12,33,12,12,33,33,33,33,33,33,33,33,12,33,33,33,12,33,12,12,33,33,12,12,33,12,12,12,12,12,12,12,12,33,12,12,33,33,33,12,33},
{13,13,33,13,13,13,13,35,13,13,33,13,13,13,13,35,33,33,33,33,33,33,33,33,13,13,33,13,13,13,13,35,33,33,35,35,33,35,13,35,13,35,35,35,13,13,13,35,33,13,13,35,13},
{14,33,14,14,14,33,14,14,14,33,14,14,14,33,14,14,33,33,33,33,33,33,33,33,14,33,14,14,14,33,14,14,33,33,14,14,33,14,14,14,14,14,14,14,14,33,14,14,14,14,33,14,33},
{15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,33,33,33,33,33,33,33,33,15,15,15,15,15,15,15,15,33,33,15,15,33,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15},
{16,33,33,33,33,33,33,33,33,33,33,33,33,33,33,33,16,33,33,33,33,33,33,33,16,33,33,33,16,33,16,16,33,33,33,33,33,16,33,33,16,16,33,16,16,33,16,16,16,16,16,16,33},
{17,17,33,17,33,33,33,17,33,33,33,33,33,33,33,17,17,17,33,17,33,33,33,17,17,17,33,17,17,17,17,50,33,33,17,17,17,50,33,17,17,50,17,50,17,17,17,50,17,50,50,50,33},
{18,33,18,18,33,33,18,18,33,33,33,33,33,33,18,18,18,33,18,18,33,33,18,18,18,33,18,18,18,33,48,48,33,33,33,33,33,18,18,18,48,48,33,18,18,33,48,48,48,48,18,18,33},
{19,19,19,19,33,33,19,19,33,33,33,33,33,33,19,19,19,19,19,19,33,33,19,19,19,19,19,19,19,19,49,49,33,33,19,19,19,49,19,19,49,49,19,49,19,19,49,49,49,49,49,49,33},
{20,33,33,33,20,33,20,20,33,33,33,33,20,33,20,20,20,33,33,33,20,33,20,20,20,33,33,33,44,33,44,44,33,33,20,20,20,44,33,33,20,20,33,20,44,33,44,44,20,20,20,44,20},
{21,21,33,21,21,21,21,36,33,33,33,33,21,21,21,36,21,21,33,21,21,21,21,36,21,21,33,21,45,45,45,51,33,33,36,36,36,51,33,21,21,52,21,52,45,45,45,51,21,52,52,51,52},
{22,33,22,22,22,33,22,22,33,33,33,33,22,33,22,22,22,33,22,22,22,33,22,22,22,33,22,22,46,33,46,46,33,33,22,22,22,46,22,22,46,46,33,22,46,33,46,46,46,46,22,46,22},
{23,23,23,23,23,23,23,23,33,33,33,33,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,47,47,47,47,33,33,23,23,23,47,23,23,47,47,23,47,47,47,47,47,47,47,47,47,47},
{24,33,33,33,33,33,33,33,24,33,33,33,24,33,24,24,24,33,33,33,33,33,33,33,24,33,33,33,24,33,24,24,33,33,33,24,33,24,24,24,24,24,24,24,24,33,24,24,24,24,24,24,33},
{25,25,33,25,33,33,33,25,25,25,33,25,25,25,25,43,25,25,33,25,33,33,33,25,25,25,33,25,25,25,25,43,33,33,25,43,25,43,25,43,25,43,43,43,25,25,25,43,25,43,43,43,33},
{26,33,26,26,33,33,26,26,26,33,26,26,26,33,40,40,26,33,26,26,33,33,26,26,26,33,26,26,26,33,40,40,33,33,33,26,33,26,40,40,40,40,26,26,26,33,40,40,40,40,26,26,33},
{27,27,27,27,33,33,27,27,27,27,27,27,27,27,41,41,27,27,27,27,33,33,27,27,27,27,27,27,27,27,41,41,33,33,27,41,27,41,41,41,41,41,41,41,27,27,41,41,41,41,41,41,33},
{28,33,33,33,28,33,28,28,28,33,33,33,28,33,28,28,28,33,33,33,28,33,28,28,28,33,33,33,28,33,28,28,33,33,28,28,28,28,28,28,28,28,28,28,28,33,28,28,28,28,28,28,28},
{29,29,33,29,29,29,29,37,29,29,33,29,29,29,29,37,29,29,33,29,29,29,29,37,29,29,33,29,29,29,29,37,33,33,37,37,37,37,29,37,29,37,37,37,29,29,29,37,29,37,37,37,37},
{30,33,30,30,30,33,30,30,30,33,30,30,30,33,30,30,30,33,30,30,30,33,30,30,30,33,30,30,30,33,30,30,33,33,30,30,30,30,30,30,30,30,30,30,30,33,30,30,30,30,30,30,30},
{31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,33,33,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31} };
bool ac[DIM] = { 1,1,1,1,1,0,1,1,1,0,0,0,1,0,1,1,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0 };
// --------------------------------------------------------------
// 数え上げ DP
array<VTYPE, DIM> dp;
dp.fill(0);
dp[0] = 1;
auto apply = [&](const array<VTYPE, DIM>& x) {
array<VTYPE, DIM> z;
z.fill(0);
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 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 };
//loop: 0 LT: 325 LB: 207
vvi ssB_int = { {},{1,127,82},{3,126,65,127},{4,119,89,111},{5,125,86,107,61},{5,127},{6,124},{7,61,106,95},{10,119,93,97,47,106,45,119},{11,126},{13,123,70,91,106,95},{19,110,57,99,94,115},{21,119,76,107,77,59,110},{21,127},{23},{23,122,79},{26,73,125,87},{26,111,66,111,89,113,11,126},{27,85,119,45,123},{29,81,87,69,125,1,127,82},{33,61,102,75,124,71,58,111},{33,111,57,23},{35,117,85,55,36,111},{36,111},{37,59,109,70,107,41,111},{37,117,95},{38,121,77,39,122,79},{39,41,105,95,81,102,60},{39,122,79},{41,103,93,113,47},{41,109,71,105,63},{41,111},{41,118,91,105,93,99,94,116},{42,107,93,55},{43,45,119},{43,74,122,87,73,125},{43,125,66,127},{45},{45,119},{45,123},{46,85,127},{46,106,91,77,123,6,124},{47},{47,105,91,86,117,79},{49,107,94,107,57,7,61,106,95},{50,47,64,58},{51,46,106,91,77,123,6,124},{53,107,78,123},{53,108,91,86,60},{53,109,69,102,58,75,121,79},{53,111,73,119,82,63,101},{54,99,85,95,105,45,117,93},{55},{55,109,59,65,123,78},{56,103,74,127},{57,23},{57,99,94,115},{58,111},{59,109},{59,110},{60},{61},{61,69,127},{62,107},{63},{64,127,65,125,4,119,89,111},{65,125,4,119,89,111},{65,127},{66,127},{67,93,69,119},{67,94,115},{69,77,123},{69,119},{69,123},{69,127},{70,91,106,95},{71,58,111},{71,125},{73,118,93,75,118,92},{73,119,45,123},{73,125},{73,125,87},{74,122,87,73,125},{74,127},{75,118,26,73,125,87},{75,118,92},{75,121,79},{75,124,67,94,115},{76,107,77,59,110},{77,59,110},{77,113,95},{77,123},{78},{78,123},{79},{79,121,75,118,26,73,125,87},{81,71,125},{81,95},{81,102,60},{81,123,46,107,70,109,43,45,119},{82},{82,63,101},{82,125,33,111,57,23},{83,94,115},{83,109,59,110},{83,117,79,97,62,107},{84,59,110,91},{84,95,69,123},{85,55,36,111},{85,95,84,59,110,91},{85,123,73,119,45,123},{85,127},{86,60},{86,107,61},{86,117,79},{86,123,78,114,91,101,93,81,95},{87},{87,69,125,1,127,82},{87,84,95,69,123},{87,89,111,56,103,74,127},{88,83,94,115},{89,39,125,67,93,69,119},{89,103,69,77,123},{89,111},{89,111,56,103,74,127},{89,113,11,126},{90,55,109,59,65,123,78},{90,83,109,59,110},{90,109,21,127},{91},{91,86,60},{91,105,93,99,94,116},{91,110,53,111,73,119,82,63,101},{91,118},{92},{93},{93,55},{93,71,121,79,114,93,37,117,95},{93,75,118,92},{93,113,47},{94,53,107,78,123},{94,115},{95},{95,105,45,117,93},{97,47,105,91,86,117,79},{97,62,107},{99,61,67,125,65,127},{99,94,115},{100,59,110},{101},{101,67,102,61,69,127},{101,93,81,95},{101,93,115,46,85,127},{102,60},{102,93,81,71,125},{103,74,127},{103,82,125,33,111,57,23},{105,42,107,93,55},{105,45,117,93},{105,47,101,59,109},{105,63},{105,93,99,94,116},{106,45,119},{106,91,77,123,6,124},{106,95},{107},{107,41,111},{107,61},{107,78,123},{107,90,83,109,59,110},{108,91,86,60},{109},{109,21,127},{109,59,110},{109,91,118},{110},{110,57,99,94,115},{111},{111,57,23},{112,95,100,59,110},{113,47},{113,95},{114,79,121,75,118,26,73,125,87},{114,93,37,117,95},{115},{115,78,123,45},{116},{116,94,99,61,75,124,67,94,115},{117,37,59,109,70,107,41,111},{117,79},{117,93},{117,95},{118},{118,92},{119},{119,45,123},{121,78,115},{121,79},{122,79},{122,87,73,125},{123},{123,78},{124},{125},{125,87},{126},{127} };
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 = 6;
// 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回で追加する文字列の量，反復回数, 検証用文字列集合)
// embed_DFA(1 << W, 9, 1, 20, 1, ssB);
int n; ll m;
cin >> n >> m;
vm seq;
if (n == 1) seq = solve1<mint>(300);
else if (n == 2) seq = solve2<mint>(300);
else if (n == 3) seq = solve3<mint>(300);
else if (n == 4) seq = solve4<mint>(300);
else if (n == 5) seq = solve5<mint>(300);
else if (n == 6) {
// seq = solve6<mint>(129 * 2); // 提出時には solve6() を消す
seq = seq6;
}
else if (n == 7) {
// seq = solve7<mint>(324 * 2); // 提出時には solve7() を消す
seq = seq7;
}
else exit(-1);
dump_math(seq);
auto coef = berlekamp_massey(seq);
dump(sz(coef));
MFPS::set_conv(naive_convolution);
EXIT(linearly_recurrent_sequence(seq, coef, m) - 1);
}