結果
| 問題 | No.1685 One by One |
| コンテスト | |
| ユーザー |
 ecottea
|
| 提出日時 | 2025-12-21 18:17:40 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 55,908 bytes |
| 記録 | |
| コンパイル時間 | 7,859 ms |
| コンパイル使用メモリ | 361,152 KB |
| 実行使用メモリ | 814,600 KB |
| 最終ジャッジ日時 | 2025-12-21 18:17:50 |
| 合計ジャッジ時間 | 9,640 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 WA * 1 |
| other | AC * 11 WA * 4 MLE * 1 -- * 30 |
ソースコード
// QCFium 法
//#pragma GCC target("avx2") // yukicoder と codechef では消す
#pragma GCC optimize("O3") // たまにバグる
#pragma GCC optimize("unroll-loops")
#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); rep(i,9)cout<<MLE[i]; exit(0); } } // RE の代わりに MLE を出す
#endif
// 数列 seq を延長して seq[0..N] にする．
void solve_1D(vm& seq, int N, vvm coefs) {
int TRM = sz(coefs);
int DEG = sz(coefs[0]);
int n = sz(seq);
seq.resize(N + 1);
// TRM 項間の，係数多項式の次数 DEG 未満の変数係数線形漸化式
// Σt∈[0..TRM) Σd∈[0..DEG) coefs[t][f] (i-TRM+1+t)^d a[i-t] = 0
// を用いて数列 a を延長する．
repi(i, n, N) {
mint dnm = 0;
mint pow_i = 1;
rep(d, DEG) {
dnm += coefs[0][d] * pow_i;
pow_i *= i - TRM + 1;
}
mint num = 0;
repi(t, 1, TRM - 1) {
mint pow_i = 1;
rep(d, DEG) {
num += coefs[t][d] * pow_i * seq[i - t];
pow_i *= i - TRM + 1 + t;
}
}
// dnm * a[i] + num = 0 を解く．分母 0 に注意！
if (dnm == 0) {
dump("DIVISION BY ZERO at i =", i);
Assert(dnm != 0);
}
seq[i] = -num / dnm;
}
}
mint ngs[] = {0,2,27,284,2875,29112,297381,3066968,31898043,334088600,519333016,249880213,834895512,469745464,809678609,770302353,566062593,812058088,218212551,901440335,898199270,477774349,202661371,832970536,129226607,576996613,333676942,968684808,533096993,418662272,824300530,407648070,678363484,168129458,968388076,778604702,175906262,829390085,57583480,213326768,930656681,307994764,935585620,771902300,8214665,833552892,122899009,573662991,669762934,972508139,239197954,929070642,598465873,466857028,182677385,286609113,980668603,119017508,317728152,633319098,796617334,981960963,763883294,892819483,504557679,430746140,314112981,831961745,840491760,943976362,383732769,168108950,824533270,417158303,581453857,214937937,373812501,987051848,176484937,17776393,455008459,327203911,22491854,680703281,948624917,798131508,632863714,474027332,81346599,722045463,278382364,26412783,328330455,256778497,573490358,453296189,372798647,393985851,711491187,631805997,736143097,28801525,291592418,553073929,116980939,415440033,991854044,619590232,727521284,725405505,837155208,168310239,245627313,524469948,611389628,166239957,296451349,34215041,957824642,732770067,337010,36565790,952163391,946826444,197160106,735814387,80476298,770501059,28314478,740702095,765533920,952753253,99591455,683211347,180052435,756092689,814359966,694794428,535359993,610944279,221997832,231481985,384895216,558284925,914648413,144418595,317379228,661354970,927619708,931201341,153078584,231261298,628804578,396284576,878420735,949310967,834870602,396469638,700273746,189343188,610716849,385562944,847421095,998207736,437819293,779534734,450555262,145083152,572621692,77365263,126196101,126833428,899432402,855384120,733616606,595714104,123146355,664583082,339262830,326129136,270871157,774564965,391437845,732984554,487301684,631580689,349439252,594858239,932533765,814280584,930357680,560119032,771030330,709380423,868004497,251769568,407547467,682676414,460429519,229019866,713578015,901854180,946759007,285266828,604230254,556563235,832098216,29741968,897588913,837113099,418281847,666712006,263788438,114906200,676450582,646309571,166849587,290666419,756356243,207017590,538993276,718554721,813553248,409015110,5633319,280669595,795354938,585201470,357972509,261594804,9183159,305269971,531410883,902991337,174637046,62235770,510573210,562174139,29541238,55782965,398908878,144956895,126667109,928699307,91951059,923518254,451118346,841888675,868842281,363332202,753699100,298693504,968893785,939488041,198277313,952276997,378793722,925358592,376950874,264028664,477860527,122338756,875394978,882966759,91965657,13579175,415065694,18805223,586778699,529987087,955274197,400763484,491760607,14961564,90446861,330916621,958828658,149274765,879072073,170459641,926125176,877873002,502439787,858434758,33222760,530536442,478480834,892086685,942844927,236014077,742970729,33667953,303351763,507620378,395087386,344462824,152434052,401943879,668488270,47018306,517758182,891950903,18230282,166401385,930817927,66111817,78510970,316687925,554061445,399179332,64926019,925341709,790690290,610449144,986160759,147614226,699477251,411019248,892230335,206098958,453562168,383793963,417686455,527862566,601217537,501826766,705360159,158612143,685232503,700259253,399245816,381438081,791541631,617172508,797593686,876640315,280141378,825291238,514888532,533430339,439544574,960615166,478485847,438883819,154125277,769356171,118314203,583718244,122986641,235592016,599375026,708426401,60602606,116368673,490293903,243635785,897380750,468434686,614000300,561310842,805434986,896468331,815929950,561654262,463600744,744837572,412896160,913791116,488044954,784841417,931952004,964609645,638011392,632976697,1563151,365798716,298110382,990807654,375460121,253251479,609695803,783338137,431169324,648702238,452272833,101181571,579103523,626729172,507101563,184042518,960435637,878927062,297867566,772905847,701645019,425750759,480784592,386926732,394159535,878000783,212070662,255707587,417038463,1432761,793156638,428173744,675277876,221834837,107896270,140187679,998369068,878308644,343694514,521012958,568496173,785332660,307278559,179604998,288144838,346754535,2040279,857340981,137413383,44402036,914966294,252934037,478078783,989788759,712874708,172986382,668079784,427240615,462415866,571852333,268809031,565725023,16223896,804697200,795735328,228866852,653611685,276601331,500194679,827487885,752344796,861132030,312580377,829957033,343556421,413429919,540617892,981199655,883689024,432889372,476308367,673644255,665595053,925927218,456853938,823956085,251027569,294483488,82084273,11861618,50098301,426676757,255208901,884604138,569934524,828846661,622465581,843341192,707714031,513576358,410376213,581144333,550783291,291083973,608491890,783905399,973246028,771473254,291682521,24121315,861735725,500945937,615862502,161239688,665160723,521353516,876939404,529881158,757945962,398427675,58137073,405958413,104851094,33194944,716860185,381366544,820655320,652743752,841057591,958072975,556147857,478820194,40836202,838210097,798838850,442335650,43418396,208018525,688119145,994213139,391863458,590599579,345220409,621385176,117962521,857037007,774305762,684113311,867371756,762146736,921042241,722692743,524624273,770683542,50657654,357805243,132917738,549631515,443684828,31128303,222411871,891446934,431095758,159924193,722535855,85212781,155734077,913944935,307763849,799507068,430926195,366461264,410688431,815359750,491341509,729253568,136845195,293373813,725462159,818148921,828580027,725370228,796598324,20246387,500426102,569115202,908966123,36167458,49066617,107432155,626550962,944960687,214635711,223651615,433914343,765247906,542701299,423035627,665298397,939643808,871955363,661073242,157985240,328082703,280749548,808031455,48150598,693152159,497733949,418010590,878165395,585124023,20743502,894533918,459192713,427909459,650616470,728083579,712365848,338114242,774077540,924782246,900676159,265759127,721627655,413718202,944221177,727846305,21533497,82235401,202597969,257071699,438889965,327696327,3522623,417780372,504721752,477116178,380554886,787569389,891256429,606211917,689576354,221330805,137775193,665109161,968084447,252214001,662617354,871937258,390862637,544633591,37659095,440322862,74078958,80728157,60970743,481779897,541353463,520503976,466623678,943376244,431306038,147306736,421166744,957983521,789100121,635013588,600866883,686417304,943917798,898388389,181386496,698016897,492299165,912195138,713751842,560737796,812332782,29231021,464405044,515232388,994053447,428730815,754715152,228742983,545760259,819789108,583983591,756727029,679472233,342905574,933852028,428003691,372672631,132156982,215698665,131082517,698106752,794861650,285786366,772900273,630856890,181790771,965553357,828033751,511102172,435477571,345746736,679799776,773812838,174236701,682217775,640240044,671904798,155819289,514392399,108818571,616539368,444217686,211315505,983057517,222703304,708144113,335418153,338976050,276349703,92983500,996169155,777532182,847435497,864327856,958528855,222261693,257713830,730347826,980923771,203262124,998250398,218725559,885836692,943711928,796539844,829905066,802449646,463304406,826228428,989402423,529471988,999870771,906202967,897658009,14893877,515209144,71691216,524954594,76559369,830132939,702707721,643908149,824946973,438986041,735544,822166675,411768673,825190589,853164741,114253746,837895735,375205004,704933136,826824163,630713979,246344550,934505533,567059453,893691891,759449706,607729914,839098639,153409536,720944594,465644235,897915238,739000685,173731986,356073614,583189056,437414134,707200601,981254628,14484988,613826646,247368764,421801424,276548805,453362706,387126202,869390274,467667884,133438194,3621608,264707007,833855137,645605302,101976867,713621014,96647975,815899398,27758519,992235471,672412109,170816167,198102108,874704334,166023726,215959954,946950886,849651424,389762817,915607592,78575950,551518515,537245572,448073268,968060173,910861600,600085130,318194167,363376774,430092765,203277387,983510485,234205471,912359759,5408723,269902194,359555756,621235898,411088323,599431647,730708758,729919400,864367180,362836469,200364659,65482526,333236525,629193441,509875930,393356841,64654943,327487996,49737990,227587098,755208987,942199506,1669565,302059208,185122519,957613723,644720604,845631165,317347844,717380287,891599973,695182510,560326929,954943378,551060142,713475282,231697942,855978190,784811638,430639907,491500872,832996402,563229873,318308409,491918016,355046884,578380975,485600905,677403245,685225571,113861798,849966065,714133435,243370583,337433383,76999289,736119864,326209798,431367229,454387568,79284614,169591644,387206165,619673963,828222892,174700418,559127635,496963943,39167932,49529331,149836564,209560289,436176040,346015617,206263224,111012293,394669724,587911006,614562482,73519843,145074652,198297010,81325255,650403008,180611188,23005314,675540536,218940407,95747974,979625795,118461341,868860741,860939192,664874830,748074610,126104067,901003285,151545566,217172776,911257563,231022296,850530098,289124182,609362158,425819506,141969114,324733444,12352718,330123582,328272712,377494312,532238623,158142140,439620709,909173803,322796879,625285533,188048438,330298944,237397071,806937006,910136151,240036708,40751534,942491480,845046337,721883521,198729093,939822666,945426734,994952089,3675951,615124015,996526111,256459665,401124275,71314512,870017390,706294488,391604609,705890374,953515917,78613119,462428029,412713312,37888828,638754236,915130771,503753767,313249590,578431057,158854602,18127886,909154789,891595350,784200090,544634171,58311916,705992324,649169461,425294143,68654961,513403313,127790419,913124229,116185680,229530652,311979539,325965485,734766117,915323527,816649217,617027403,882463576,524276932,757715382,93536219,897163353,850079363,136031932,451113832,521635749,978472285,704784172,574816041,632057462,734098137,655394556,705275866,56914795,865255172,66219859,880164482,501410921,374201601,242572992,365585482,359567668,192338287,610286655,337531572,773889839,210893760,875476144,293951663,600605057,701518495,751432605,938490650,369506725,581724276,436365546,262132359,335764000,605100774,782519849,286686718,575312182,421431367,680201302,379581535,283531906,93175761,256761199,431854779,220796250,913471146,104250222,292766160,721671599,768572503,399764295,112330183,991778444,704638182,358467438,861376583,608656159,483605118,715254558,363841349,259826549,469357500,917329779,826090471,369399776,159032683,606953177,980351600,236036580,527621754,554595688,712444980,150176510,167333708,350882714,254757180,427426133,852481491,374283723,909487550,102030583,901998014,421804382,908597286,438480416,483505094,217600734,314277779,575729083,734693498,390765617,864127656,210104700,443179616,711112146,56729476,815577789,187628519,886714412,962405250,44484403,698729780,481336707,108938648,286219299,255762876,468245802,202466423,945501128,650041769,155575711,870996805,563371725,290673876,689603987,570673797,633553532,319313848,680362499,962280103,108293592,560971247,885737118,72132545,467538938,781310189,237551217,550082493,168180164,719709487,666576059,628531153,371994329,455588936,480884614,44377481,596585344,653047305,514003475,988641841,983068738,271479836,641730914,27093638,200699116,654360548,309351582,71320940,536393732,416641804,14399071,566838205,905863719,769056474,699911392,431440042,255470684,150287373,813796500,852479780,963073204,564028101,200531808,69640605,923555620,3110942,90365716,339361236,181805852,177083326,742668442,984176400,813607367,88677052,482557095,800818399,625761940,383634176,569135357,490614952,539615295,566763831,65152064,633498653,692674060,38321505,77759649,594573654,770784772,449265450,302665373,496686082,530178793,202970355,280928010,691808866,890042722,959345442,529573288,452914333,775985746,846827614,130305661,106278147,611469544,551847076,412852640,66072696,516752474,509338915,529457802,915670417,619781165,487922730,775462177,395765814,33019084,169561384,634205692,224290063,135221350,618354409,249701249,174706147,80600434,480138101,271449795,904023495,95407018,373314322,791368482,459256888,151720835,757743537,236774874,353636700,5850823,657484303,489777653,898365428,157592727,43217052,992436701,624239655,35002675,571733619,82007801,572004138,125245087,210296478,543404125,296901038,11058078,981533216,106632339,639425501,669828529,702111799,695129451,940860414,555407670,578950841,620273227,778274156,596418952,935082844,592053050,103136115,461144191,389632934,835263219,203654689,14122881,516921748,702867398,973565421,465118470,203111441,526837333,821123162,310851114,366616674,627781486,530655481,726202118,66383467,818685949,665021803,953899965,273227170,328257063,181089773,180739483,883940136,362594082,396455476,283928768,847197902,778235782,761422468,681559672,800586632,848714606,357735511,745049209,371295270,503658254,875278829,376208174,362740283,919811027,69658543,541853450,942288738,507237184,753029514,69443548,536364982,705180900,332173886,369155603,883084309,416716068,240194726,29336470,401300875,820501637,244306633,152052950,940310014,323307352,107076825,457403640,418105606,320801614,760842019,275293735,387067684,635044727,950036403,844613490,320286048,843604160,791874480,919364033,349827112,511253756,72369433,68586711,907650380,390027342,933596467,96439004,796412355,306269915,998750928,221987387,982730412,603717622,570364288,14297040,101690918,455452600,670312063,542691919,826255931,723087792,793130992,98710753,38326471,18714111,822016186,819427441,565768288,916362881,697846708,934503566,538334787,479868543,504547108,234299388,294959134,478838722,442752546,219849957,644298358,946419149,216199551,760478599,828218914,529097950,247544356,356344597,34751100,515894893,52809574,988170420,285228964,765841560,850754581,321996361,113523338,735303069,373487273,957518161,452551962,265584769,851007790,913704279,595293294,130562436,489299417,929580221,416428619,910320264,147093237,23003770,901891182,643287358,547624023,238118274,43167414,107059053,171691664,495411834,759119450,288719555,826550870,460521869,81918613,168272473,499889457,769751851,998143031,250005534,412779672,785202104,300496648,17688226,547650129,539372183,287387047,596312061,867752193,885095023,835949272,763870234,491595173,927388727,625629425,119371424,863605590,943853292,720266317,181123865,915304953,684564988,189037363,270725559,770467601,642664302,767716658,767785668,488554685,794562279,220784964,523695790,981218704,314155122,499398989,90627670,819843356,709766873,537896863,784912925,575588590,605849875,725912072,356657478,544961649,915001395,294722636,443710815,703123231,113158726,421447805,556033545,949056812,374654626,638284146,382019880,644772202,221313911,535932655,779759878,189392210,796350984,968365050,389586795,531317465,664818008,43036922,739937725,866529676,861237906,215992737,951010527,210588815,589936636,96628264,471754398,422851791,592381025,691099304,719073477,869551816,457384524,204523898,573102816,642825746,888555638,431895034,463015220,427576509,991914051,911278029,457156305,631252996,573468616,845576191,238632831,96414521,508929789,86257651,194038286,60577306,986953943,858932411,904252043,263363638,7954273,663029456,260827549,445842736,743897608,979526406,987886671,318104854,43942519,775019667,280895842,665934858,137739998,663670991,800201502,454887093,3294683,528023712,487588993,729689828,585375961,624692940,623270684,908537547,968533832,349827837,306292186,127124684,425881558,268887765,715036198,697237674,810420520,973509201,929470868,316443489,717299543,24748505,986435505,77653908,406156241,645924119,663853414,912007735,545596604,282639740,318402316,991142403,946249655,610690001,155359836,932642151,114884926,163597,489470602,785791826,960294025,631667059,316231567,491258676,160613894,553743565,996512545,719225777,226223247,414622024,380229447,605943729,265069907,782301616,233802131,53829689,813627140,717956147,778385982,899678137,400503961,331975850,832557430,19005337,670966924,422713535,642695867,188550881,628498282,882063936,473736559,27455500,115634894,385363266,664769275,649631832,819026324,525065785,495835101,443878103,892770205,317418477,922556021,510958559,420844454,479057980,902097464,852234560,936567745,621416353,608397882,379038666,470008140,518111923,63685735,748796405,933251309,40200458,424924712,635121538,302692243,400674118,325157618,850169446,451851477,481913978,193324909,892723448,327088327,847720287,538007517,593461742,439125124,147716914,829459121,280323749,39280755,224763447,522048819,324817522,560674427,482584342,537012763,853898701,344209684,671079800,852289475,550536535,419134753,556708643,394589186,54390325,381124436,880399843,669728492,830334168,210057382,185906674,184259031,8406430,223125594,807402273,391023673,472112982,989395935,877623558,757920453,666250962,873807043,890704993,537008916,816589682,914536015,454939068,1036586,918313323,728821064,248963810,455088376,435652399,86124347,939387425,75830818,895906693,443128865,941465867,647013822,150057248,302173314,166730130,938222003,332288396,193397932,639228092,302245589,47038863,329852966,193708802,420545271,970642471,421212299,587490203,949791523,666379734,147847414,423642365,914117012,425939456,173686506,564391710,358300966,315733441,141744358,578875146,339662498,2581508,193234479,707155290,150981687,417473837,284714427,166299572,652207350,573997894,569012023,117850869,992030139,17105473,444362070,28614599,191337378,258838580,497895959,781624744,755979262,628419752,857539505,335016797,78368553,65350758,981588744,834020928,180628052,194912803,882363243,898974622,151486705,573054954,17741642,927724354,654837160,252864711,406062895,819692706,501244270,865168952,733633017,139444969,221193504,579232315,410298575,816346202,204849069,501793445,298445606,739234364,408334420,668127452,75171097,536342189,416518709,875169986,330090561,531615756,295971685,358120666,841846399,170936327,339827083,427577468,698325074,827318968,117016978,413088075,246718962,558023850,960473976,332029595,250328458,809769944,88031029,166985015,203690828,91225255,564621205,999085278,105558757,557929280,719901190,391666074,866184613,591793151,125042594,580182552,971658941,204254312,659711114,315638612,561295467,576194920,822383671,209026397,186693068,689737592,512677074,836992872,352796614,510718089,995508518,753446806,574078612,309575750,124631264,597907242,659253518,142256372,516889126,18037930,786321483,845822925,712738002,919017778,723622463,109597041,701143887,287345606,982719595,371682663,254967708,699883943,97435246,37482491,855051569,328621191,230222449,304527035,94794374,767770652,298571878,177262442,217274830,131187854,812216373,828266637,156610835,550279265,392800807,297596857,320216786,427066466,246236517,787344307,932884097,944488577,955167656,563019628,608518836,48399434,628377079,571867914,293486749,747129527,126762656,899395224,275690999,228443639,584987639,857060757,385430643,404605916,555969644,87232588,486224116,464368903,513311516,686778300,701423420,998564251,291717197,533539458,318284199,180081066,121769921,36982259,174983436,280202453,433805281,155077052,956163824,857107868,889646377,886241887,447964292,156539464,292938789,32786012,62341103,586219610,65235002,439017808,331178506,723183821,567114140,529660223,741414779,230520718,549442745,703332201,281690482,569405783,476095633,69252483,573137777,906837076,665460889,599310740,888979784,914525153,937946955,259507732,714739633,824391498,562233675,146718933,89945145,589226505,428972227,671895694,625623512,55370109,936502143,715857637,861490800,497420405,956032800,34793468,145766580,256608969,643555645,376154369,854574868,852903700,640383368,333788970,734824490,650643804,803021175,935760955,906289853,322507789,351777535,182834985,172059409,439234937,757507045,1583212,821571847,804190647,51612391,163772997,138371920,448699911,419269521,67647410,598507651 };
// 2 次元数列 tbl を元に seq = tbl[N][0..M] を計算する．
vm solve_2D(const vvm& tbl, int N, int M) {
// --------------- embed_coefs() からの出力を貼る ----------------
constexpr int TRM1 = 1;
constexpr int DEG1 = 40;
constexpr int TRM2 = 4;
constexpr int DEG2 = 3;
vvm coefs1[TRM2 - 1] = {
{{0,-1},{-1,1}},
{{0,2,-1},{0,-3,1}},
{{333333329,266666674,400000005,-1},{-399999950,-333333375,-266666662,0},{399999970,66666701,-133333345,1}} };
mint coefs[DEG1][TRM2][DEG2] = {
{{228988823,485992551,-419001245},{419001245,-161997517,419001245},{419001245,-161997517,419001245},{-419001245,-161997517,-419001245}},
{{-499359902,-375740556,485793141},{-100287549,-424083173,-485793141},{-195293760,480910623,-485793141},{195293760,318913106,485793141}},
{{-372346530,494665554,-127072981},{22002619,-460336887,127072981},{450968310,-31371196,127072981},{130030452,-2957471,-127072981}},
{{465930912,-252915886,197257939},{360363613,423166578,-197257939},{-275001292,-212198327,-197257939},{-239205574,41947635,197257939}},
{{392185890,-139913774,243119201},{242147103,-479383246,-243119201},{228436791,-493093558,-243119201},{-355509772,112390571,243119201}},
{{-16144117,-55869812,94281632},{-491060094,-296361263,-94281632},{-275464096,-80765265,-94281632},{472722035,432996340,94281632}},
{{-442278669,-247711630,-33428469},{-147719674,-168847142,33428469},{323688486,302561018,33428469},{-80569285,113997754,-33428469}},
{{125876680,233870220,286192666},{458517080,11185844,-286192666},{291374735,-155956501,-286192666},{-197093103,-89099563,286192666}},
{{-427840125,-142130417,160986},{-321456445,284196370,-160986},{109506878,-284840314,-160986},{-142935347,142774361,160986}},
{{-143055632,-428623264,-238090463},{-476441315,475778461,238090463},{-475636385,476583391,238090463},{-238170956,476261419,-238090463}},
{{304500839,-82711340,-283626097},{-144805844,-337521659,283626097},{-335258152,472026040,283626097},{335419138,-51793041,-283626097}},
{{-338596120,465789544,-362670587},{-99102450,-65593594,362670587},{482767079,-483724072,362670587},{279142465,83528122,-362670587}},
{{-177090942,200604082,-246788537},{95180071,-99746469,246788537},{281827150,86900610,246788537},{434546760,-187758223,-246788537}},
{{297553198,241641198,-396958848},{-355163333,-89110972,396958848},{410893996,-323053650,396958848},{226435424,170523424,-396958848}},
{{456429461,439140219,-459889871},{-583864,-87823152,459889871},{14621910,-72617378,459889871},{-261410447,-278699689,-459889871}},
{{123284538,352244760,103716638},{68828923,442291398,-103716638},{-230620418,142842057,-103716638},{-166338430,62621792,103716638}},
{{-23260422,36351371,14701615},{58683650,-288694825,-14701615},{-422733167,229888365,-14701615},{-37156704,22455089,14701615}},
{{-55669433,136904520,-392624115},{-69816518,248494189,392624115},{3691557,322002264,392624115},{100025081,292599034,-392624115}},
{{122337820,51913157,-440733153},{-277756732,363026583,440733153},{-240877293,399906022,440733153},{255578908,185154245,-440733153}},
{{-462378253,304714594,-69275331},{159950394,-259616466,69275331},{-43715357,-463282217,69275331},{-348908758,418184089,-69275331}},
{{435543005,89057670,-240930001},{-388064166,155048326,240930001},{265559186,-191328329,240930001},{293707668,-52777667,-240930001}},
{{-450614403,79125401,-256889935},{-228200402,-383895138,256889935},{-432850400,411454871,256889935},{363575069,-106685134,-256889935}},
{{267482771,-116789788,-290872461},{-294052843,-276030251,290872461},{421497496,439520088,290872461},{337572510,-46700049,-290872461}},
{{165840610,131790844,-85607565},{-362356306,398396279,85607565},{183281403,-55966019,85607565},{-440171338,-474221104,-85607565}},
{{-127570239,372149395,471557605},{122803980,-229096294,-471557605},{-305233845,342865888,-471557605},{14361384,-485918989,471557605}},
{{186462536,193420492,-178466786},{470850016,-321960437,178466786},{-171361980,35827574,178466786},{85754415,92712371,-178466786}},
{{-291381941,383178651,382324212},{-107666077,-318481459,-382324212},{0,-210815382,-382324212},{471557605,146118190,382324212}},
{{-459228438,-114990186,12695320},{88378954,18798837,-12695320},{0,-69580117,-12695320},{-178466786,165771466,12695320}},
{{479003847,325683558,388671872},{-63476600,190917963,-388671872},{0,254394563,-388671872},{382324212,229003923,388671872}},
{{280273489,47851593,207031256},{56640654,-385742185,-207031256},{0,-442382839,-207031256},{12695320,-219726576,207031256}},
{{119140588,-150390649,492187500},{-35156273,498046874,-492187500},{0,-466796860,-492187500},{388671872,119140635,492187500}},
{{339843783,472656272,453125006},{-460937486,-136718748,-453125006},{0,324218738,-453125006},{207031256,339843745,453125006}},
{{-210937524,85937487,-281250004},{-265625016,429687500,281250004},{0,-304687491,281250004},{492187500,-210937496,-281250004}},
{{234375021,15625012,312500004},{406250013,78125002,-312500004},{0,-328125011,-312500004},{453125006,234374997,312500004}},
{{406249990,93749993,-125000002},{437499994,468750001,125000002},{0,31250007,125000002},{-281250004,406250006,-125000002}},
{{437500016,-437499995,250000003},{-374999997,-187500001,-250000003},{0,187499996,-250000003},{312500004,437500000,250000003}},
{{-375000009,374999999,500000003},{-250000008,-125000003,-500000003},{0,125000005,-500000003},{-125000002,-375000001,500000003}},
{{-249999992,250000008,1},{-500000001,250000001,-1},{0,-250000005,-1},{250000003,-250000004,1}},
{{500000002,500000003,0},{-5,500000001,0},{0,-500000001,0},{500000003,-500000003,0}},
{{0,0,0},{1,0,0},{1,0,0},{0,0,0}} };
// --------------------------------------------------------------
vm res(TRM2 - 1);
// i1 方向に tbl[..][0], ..., tbl[..][TRM2-2] を延長する．
dump("------- solve_1D -------");
rep(i2, TRM2 - 1) {
dump("--- i2:", i2, "---");
vm seq; int offset = 0;
rep(i1, sz(tbl)) {
if (sz(tbl[i1]) <= i2) {
if (offset == i1) {
offset = i1 + 1;
continue;
}
else {
break;
}
}
seq.emplace_back(tbl[i1][i2]);
}
if (N - offset < 0) continue;
solve_1D(seq, N - offset, coefs1[i2]);
//dump("seq:", seq);
res[i2] = seq[N - offset];
}
vm pow_i1s(DEG1);
pow_i1s[0] = 1;
repi(d1, 1, DEG1 - 1) pow_i1s[d1] = pow_i1s[d1 - 1] * (N - TRM1 + 1);
// i2 方向に tbl[N][..] を延長する．
res.resize(M + 1);
repi(i2, TRM2 - 1, M) {
// 0 除算回避
if (i2 * 2 == N) {
res[i2] = ngs[i2];
continue;
}
mint dnm = 0;
mint pow_i2 = 1;
rep(d2, DEG2) {
rep(d1, DEG1) {
dnm += coefs[d1][0][d2] * pow_i1s[d1] * pow_i2;
}
pow_i2 *= i2 - TRM2 + 1;
}
mint num = 0;
repi(t2, 1, TRM2 - 1) {
mint pow_i2 = 1;
rep(d2, DEG2) {
rep(d1, DEG1) {
num += coefs[d1][t2][d2] * pow_i1s[d1] * pow_i2 * res[i2 - t2];
}
pow_i2 *= i2 - TRM2 + 1 + t2;
}
}
// dnm * tbl[N][i2] + num = 0 を解く．分母 0 に注意！
if (dnm == 0) {
dump("DIVISION BY ZERO at i1 =", N, "i2 =", i2);
Assert(dnm != 0);
}
res[i2] = -num / dnm;
}
return res;
}
vvm tbl = {
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50},
{1,6,19,37,61,91,127,169,217,271,331,397,469,547,631,721,817,919,1027,1141,1261,1387,1519,1657,1801,1951,2107,2269,2437,2611,2791,2977,3169,3367,3571,3781,3997,4219,4447,4681,4921,5167,5419,5677,5941,6211,6487,6769,7057,7351},
{1,8,27,64,125,216,343,512,729,1000,1331,1728,2197,2744,3375,4096,4913,5832,6859,8000,9261,10648,12167,13824,15625,17576,19683,21952,24389,27000,29791,32768,35937,39304,42875,46656,50653,54872,59319,64000,68921,74088,79507,85184,91125,97336,103823,110592,117649,125000},
{1,10,51,180,501,1131,2221,3951,6531,10201,15231,21921,30601,41631,55401,72331,92871,117501,146731,181101,221181,267571,320901,381831,451051,529281,617271,715801,825681,947751,1082881,1231971,1395951,1575781,1772451,1986981,2220421,2473851,2748381,3045151,3365331,3710121,4080751,4478481,4904601,5360431,5847321,6366651,6919831,7508301},
{1,12,73,284,835,2036,4347,8408,15069,25420,40821,62932,93743,135604,191255,263856,357017,474828,621889,803340,1024891,1292852,1614163,1996424,2447925,2977676,3595437,4311748,5137959,6086260,7169711,8402272,9798833,11375244,13148345,15135996,17357107,19831668,22580779,25626680,28992781,32703692,36785253,41264564,46170015,51531316,57379527,63747088,70667849,78177100},
{1,14,99,476,1765,5418,14407,33839,71835,140505,257069,445117,736009,1170415,1799995,2689219,3917327,5580429,7793745,10693985,14441869,19224787,25259599,32795575,42117475,53548769,67454997,84247269,104385905,128384215,156812419,190301707,229548439,275318485,328451705,389866569,460564917,541636859,634265815,739733695,859426219,994838377,147580022,319381638,512100178,727725112,968384580,236351685,534050961,864064911},
{1,16,129,704,2875,9456,26411,65024,144909,298000,573661,1045056,1816919,3034864,4896375,7663616,11678201,17378064,25316569,36184000,50831571,70298096,95839459,128961024,171453125,225429776,293370741,378167104,483170479,612246000,769829231,960987136,191483242,467847177,797448618,188575922,650519517,193660123,829562118,571071972,432422106,429340134,579163740,900961288,415658305,146170012,117539973,357085072,894546923,762249853},
{1,18,163,996,4645,17718,57799,166344,432073,1027351,2262853,4665259,9083725,16831423,29869081,51038083,84351319,135350605,211540123,322905961,482532463,707326729,18863228,444361166,17807727,781241229,786208468,95411580,784560031,944444115,683247096,129113494,432991862,771770905,351728534,412313980,230283716,124212698,459402898,653211837,180824442,581492160,465263843,520233723,520332181,333685854,931574142,398009800,939972077,898321200},
{1,20,201,1360,7001,29112,101941,310472,843471,2084752,4760723,10167312,20505043,39357332,72354003,128069584,219214133,364183164,589042693,930035504,436705438,175747890,235706564,732649276,816968713,681467993,570905284,793186930,732414240,864005518,772131845,169722862,921317010,69049527,862091291,789871282,619436821,437326618,696354075,267720788,498903621,277782497,103500852,164575667,424799984,717507202,848793553,710322878,402366173,367757355},
{1,22,243,1804,10165,46530,180775,614680,1871145,5188590,13286043,31735023,71282113,151590693,307025643,595289971,109940848,998067142,484703752,905893322,752684748,728784814,825055209,414576419,372584327,226227954,339800519,141863245,401515367,561966889,140546045,205323454,939662701,307215269,831169051,502936676,836936208,89673724,662989354,713076623,988733824,924256778,14438993,501309564,404514457,929636067,291251002,990151052,586898493,16758654},
{1,24,289,2336,14305,71000,297381,1081088,3486591,10154440,27100491,67081312,155545403,340670344,709621235,413986297,708384583,7534229,968656869,608015415,462684087,811376715,971363711,692240880,671630650,222856333,130293757,734535523,296768196,699930913,553367144,777875225,759384263,172011712,585079502,983863555,350515533,469816803,144297520,24875525,286639558,404822563,313488242,259095921,693026089,581455222,547780258,302229290,855478101,58146251},
{1,26,339,2964,19605,104910,474215,1866280,6539625,20758530,60511803,163786428,415382397,994338281,260193819,903157973,195605819,399138699,403813892,705357736,863671220,633366671,16287203,559023634,307650625,939789755,723458153,106029393,918344566,392182541,437844858,916760194,976319702,895505269,325505958,305030994,991390344,681980966,413338598,223550663,56155486,277687928,885228657,703586333,223470369,222058397,946081727,435802485,537413362,303358507},
{1,28,393,3696,26265,150780,729905,3066968,11422251,38322580,117380131,331910448,874684707,165706790,73073960,309535267,117884549,416342677,656230766,755419258,620617087,969546997,422293003,163526185,900131210,370719570,326163510,718205500,834308502,332742703,597902961,591693243,466728279,680205092,257942893,266230559,520678348,168521279,102792133,289658714,107768603,812442511,358238781,159923898,72754663,66598330,903531012,764766170,381052676,983928102},
{1,30,451,4540,34501,211546,1092231,4892536,19439241,69690006,228509259,692897076,960751942,217709231,141557428,499036480,184622865,785948861,427820047,642206371,460229836,984744981,581901786,780936648,306603433,770632620,880009099,135379683,552385284,721432419,441574823,287688769,32766536,274060523,538455658,437084050,226858985,824708055,625857587,456151283,64912074,565857066,421716103,678489063,433252413,761399197,924506423,655426390,383412002,862553514},
{1,32,513,5504,44545,290592,1594369,7579136,31898043,120811360,417094139,326538361,921273686,856112666,336172519,136000022,453001994,658085485,36735776,747039001,939887522,939021568,421651894,790896050,825419098,54998744,438499099,670459841,339545599,519490681,426984301,842407793,615134774,757145310,4872255,816564853,224479689,850536911,522574564,166065010,301060066,694177165,925135618,507445,118030545,498553924,509851262,800286523,260896724,222383715},
{1,34,579,6596,56645,391782,2276743,11450248,50940297,203891370,744170955,504056126,838996636,6047309,710825814,417252479,472487324,347092189,180947277,197257496,631772355,778000569,334472808,690270877,882531830,367288119,631801515,684086783,55844214,256655053,677174812,650261992,2668506,849793813,168041696,25918845,49036888,134883668,872928398,222882599,816321379,793742651,622630055,472201265,548578911,216816339,91367407,510217861,351265692,704116425},
{1,36,649,7824,71065,519492,3188017,16915008,79305553,334088600,281236862,520425036,800941863,306193541,479494415,512154267,916329807,848171189,654862203,375827748,297771211,666146092,455337711,180219143,686246227,540361713,995877841,355665929,862594983,144011323,481006499,490502125,843961657,214490632,91514151,686520858,422035139,764408534,291106955,681655152,999800508,902973638,921008780,913016915,890313746,898343783,522610036,607145274,757874815,36309588},
{1,38,723,9196,88085,678642,4386151,24489176,120709737,534152510,150489261,963115411,367021376,959024041,112943753,111814874,128504077,869647520,186648829,113948318,87825311,628396651,253622684,157377664,762052576,212120117,409584493,429252267,394573144,809886106,918372836,911924458,720065884,760019842,420565346,855681509,549337043,63876022,212496130,181335179,385211880,799587973,996363231,282243617,822062982,594175931,407487730,190494831,241615189,395007958},
{1,40,801,10720,108001,874728,5939521,34814848,180013761,834876008,519333016,629091397,917305361,925012307,105901665,972170766,86148956,979288338,55582009,837772846,398876864,777839176,966068819,85614347,145635957,265541953,81917602,323675242,417003473,756465875,908892618,388403464,400943526,194288379,163743376,636510563,419868208,643938944,720410824,14852745,95939462,307784869,892642738,104892567,423297645,968311508,973464082,918246988,531640873,776954969},
{1,42,883,12404,131125,1113854,7928103,48682472,263511081,278400843,632794616,785434818,381816458,634380288,284957308,232260742,644641754,295493300,792778,191982598,3956231,94544338,326027200,884967917,21999170,802890825,461962906,284292047,937865001,994948702,123260479,127613361,66332297,297948121,291516179,58507577,678636828,524804817,514661979,524099445,407623041,997954810,887859698,110156287,729037846,975548400,58783134,373621030,406843462,431102842},
{1,44,969,14256,157785,1402764,10444721,67055296,379248849,921160773,832356225,249880213,401024118,225406661,559035196,854519088,6682481,815098836,895996641,996327102,891163767,920734317,734463270,700175710,860317853,795613016,717381165,462912233,111175378,186507629,650863758,554438350,523706928,621908261,257007259,157587811,138793906,992173726,107404262,357327563,10603040,561131203,200797018,681433555,572484254,691139667,85660207,442826930,335331872,505214865},
{1,46,1059,16284,188325,1748874,13596359,91096376,537400521,837810136,591327120,674268983,342691535,194562095,981966990,205927510,824008576,259127171,930666898,91268065,640583444,589688936,691751211,459963291,613797793,604619152,476089912,759363092,91791365,932115288,170303029,40776841,763318464,351094732,898879243,41844296,69554864,731345122,853757112,385705003,968337150,275331642,566315464,800231269,802186303,49028194,935116348,418104952,866555650,627668592},
{1,48,1153,18496,223105,2160304,17505537,122198272,750695169,125905812,555043061,820639157,834895512,304961259,613693996,44137590,152653661,759077468,158077476,976907134,296919518,752562105,671638569,170481719,99659308,833266097,347009389,967466805,737023396,733573333,139330773,699775600,767695590,951793998,563309640,973748137,385121983,517231826,957019103,96096871,576424481,461015524,652144091,911255771,545501081,583881921,281236643,596582702,627678775,886352511},
{1,50,1251,20900,262501,2645910,22311751,162015560,34908994,911509975,592458841,968141052,626379863,838832815,765068468,55727685,564217481,185779089,80270499,186490927,46497813,868628581,202471848,482697810,708092282,722046640,164758037,960696241,323674434,710306979,839130719,284095248,930347629,334775585,940425722,617485636,79101125,690629397,611035375,602650399,747664920,857403459,375038645,504947694,450254,789768209,846727963,345816808,700877355,51051407},
{1,52,1353,23504,306905,3215316,28172977,212500288,409424842,355843804,859812613,420412492,14933393,469745464,794316340,726179594,970603149,87998888,562454825,209796560,608841319,661476196,677723496,929166733,118756655,29249457,350082331,251752820,132224199,34451936,208705352,989603137,200541338,476172051,372665451,93859216,140536348,313183931,453689324,68326578,61637361,73802008,815609715,145859009,532312429,414561919,639854303,99953084,662694953,207884596},
{1,54,1459,26316,356725,3878946,35267239,275940504,897865634,663134273,878790683,159015774,594361659,89441109,653634506,642525318,72157435,871731288,687351285,35782289,883963466,880259763,862782869,601576048,216328963,628846605,60856517,680408420,615439574,497351151,668399214,282408228,350913096,19712966,123400879,18554252,386881591,533785549,373885911,24564170,912160058,283081767,373628484,220066990,555770700,875585487,71513590,239151724,165525437,185860052},
{1,56,1569,29344,412385,4648056,43794241,355001984,528808115,89808008,631732957,669539407,422916833,106719594,809678609,947805913,375577228,583382180,648136094,899710093,663841893,68811845,612633922,955218147,470452416,694945240,101122433,811288900,368127076,181571011,443084222,626293292,99540782,468213454,663108288,770253931,519652632,587388377,136160051,523150216,657124865,593475905,106283084,647913309,602241289,996123912,822858123,986818907,584097342,58564371},
{1,58,1683,32596,474325,5534766,53977063,452773288,336583380,955199503,676740461,978012818,70469044,600105471,556620267,552370488,558963272,224127518,392263046,842614707,935845683,713045622,997511401,489378701,263509915,700721701,672812163,146021889,903857504,278149373,442163315,357400663,356464217,293563732,985728217,402388996,180253630,347080161,496421533,125352845,20516613,705352511,124864663,630565094,12669395,810827265,283735427,347875265,835891018,375007714},
{1,60,1801,36080,543001,6552092,66063921,572814272,362170933,653953809,285893759,940647031,989128886,659703394,816429125,770302353,92382704,570200456,507306035,744161108,954532109,362823729,255217608,676920353,728186562,931389383,418879847,223533408,831160564,159111388,512791401,705241694,554747425,468621341,442903950,379202448,60099951,271271630,846351797,313594289,81694938,203217063,301527868,111725779,816344972,873486434,464729704,78731285,839210116,398547090},
{1,62,1923,39804,618885,7713978,80329991,719208184,654193382,670318117,610165678,836706461,766482364,415314630,891447142,633296126,595469611,452067632,708147000,815494671,936180464,484217924,391703691,496636562,841348137,903179930,302777182,894742343,355420928,723573286,317472375,766038487,229071225,274339588,937374599,562756822,441777149,778982933,864063505,484402550,98959738,66158931,795827720,696941354,577171785,13025754,525847531,385689622,141405586,353495662},
{1,64,2049,43776,702465,9035328,97079297,896617472,270019024,594530516,875014304,321886429,925075247,106872227,413633992,938377253,566062593,848662439,254245732,397676616,871610825,913594801,301265434,511704298,210319090,462247905,319044346,118183380,605639260,253919181,837557707,766961731,172515187,800980978,159004696,897586637,533116731,912616623,767693359,375707842,165753052,731143656,283527226,155629179,172495140,787361160,69173886,981815323,672446959,164219337},
{1,66,2179,48004,794245,10532038,116646663,110343425,276979914,141529447,611074260,807974986,54936648,86884115,607390334,959401572,64921787,446744975,36320017,309751348,858499464,579321075,596462675,377866129,385594521,475835658,516561953,960764871,852650564,73693721,414776746,472895822,265124371,767074750,465033260,696640252,606732467,690336941,171597358,742470114,868483035,490552251,626078088,169483409,745836337,226040889,350273075,193829131,545832666,312451571},
{1,68,2313,52496,894745,12221028,139399729,366389817,753713156,172222510,924826217,343875449,206787076,348607839,42882281,609674180,633997532,812058088,878195527,564192052,740398448,467898549,259068576,423347880,305856984,64008428,948332183,345462153,374834906,351624614,735279272,546141104,298931207,147090427,536365159,804410785,558345541,661427068,483898886,697070429,102786164,324067433,322333676,892731242,658264467,562512674,979645439,697288883,237625856,587566902},
{1,70,2451,57260,1004501,14120274,165741031,671530577,791633543,717569202,814617922,83319574,633982099,189377007,580867127,233423581,477095286,256757098,31150657,634680573,752532652,476456061,813983745,301623962,527053626,377374105,81522360,255395036,720009950,924384563,543573914,538906293,159931419,787245666,310143074,15284168,257130666,177625731,834919621,123122249,847936743,67007508,125867742,927772247,940134024,919222559,462755271,465095272,361724585,618036294},
{1,72,2593,62304,1124065,16248840,196110145,33381746,496545859,5748590,537935707,435873196,153174862,976533968,746778095,561068796,271587656,5440033,218212551,59317419,595694518,666680132,638009749,291742254,631492183,351592435,433205645,931973640,888912417,957905532,963623374,394664222,134593791,724205195,556787609,735167317,23469814,321236177,796219510,627794147,948741600,454198160,375002942,125870572,461902892,782756213,11682229,64489346,848709243,542150448},
{1,74,2739,67636,1254005,18626910,230985895,460477786,990405391,492699833,36384123,10193019,599241077,728949900,452261949,760108833,592765278,869792967,168580781,421107580,726678820,648451977,89653632,936902793,728437228,253076968,141040897,824818687,820918845,436818481,165071086,443762361,503771541,209795504,960385285,526038666,375020309,648438851,116188968,719014523,917365877,95516813,459918839,21909280,819830739,168612247,372381767,806888323,584601849,219265986},
{1,76,2889,73264,1394905,21275820,270888625,962352306,413235469,896340686,425424635,472001777,81435866,409626836,590838678,803209453,156083550,618641788,657015529,901440335,118474526,93750191,584425600,896224695,236669306,537387540,520994296,16829165,828857812,489127582,958181360,87127326,933883914,602914197,733302034,420250541,165095921,402466567,422249787,504171421,981103258,127890024,995667135,366757610,117555244,406182902,571052386,695402047,501673890,150985731},
{1,78,3043,79196,1547365,24218090,316382535,549623459,925211227,234787368,556552682,453979087,7416723,498479425,498944932,892993056,852286052,627011383,902668693,806388098,447582250,611693585,889041312,931051059,664957231,45717599,802110028,918479892,646446851,277888647,768957329,470749011,728908035,648167992,451175769,910788272,757883680,157137635,606745138,411834579,557520062,148626225,638414710,722310499,974226992,589955076,827972476,546604527,902969399,463978746},
{1,80,3201,85440,1712001,27477456,368078081,234084068,708918747,868917335,660257378,670789140,132184943,638081091,635505441,27443415,772722516,252019937,781700006,490756783,898199270,378073784,952248329,525219034,367482826,482897240,875434697,740527028,23805475,433732037,992847104,112147703,634567960,870282303,118024778,441019318,892095032,296358467,188459266,154039421,897783296,445867961,600606157,525504954,481904553,86358319,560681933,742204793,28348683,995997323},
{1,82,3363,92004,1889445,31078902,426634439,28796581,971799396,549635464,78810163,409856674,212830750,983096784,256683302,919632158,719798082,744540528,778260464,50717239,286201139,834931208,943671988,373240008,218908668,371260434,82114643,361386385,926174769,980225373,5457430,317241796,68389527,396270317,200570874,466179219,762423536,642361099,201202736,501300181,78868099,97747849,634977872,278950147,723880767,349390636,628419579,799623734,103569893,837160368},
{1,84,3529,98896,2080345,35048692,492762033,948193053,948789023,470223869,98669489,587336326,210023743,405951270,645731349,822046802,461477028,925815631,448616609,277594305,614512683,477774349,100472323,670736013,613763625,322706685,411613254,28752013,780573985,444340589,773589540,4256516,908471396,351601917,447142360,63343293,542453477,329134163,111427875,652397203,785197552,306356510,925184653,797803082,767105443,977778294,567999557,509636300,771132175,819130555},
{1,86,3699,106124,2285365,39414402,567225127,8180199,905162268,324175146,893068504,579074312,376434374,992409387,44091992,511870136,795393959,182686604,557118837,283329744,175436725,525594424,775487645,120896030,375365080,812151901,292482887,669689978,777959237,80189764,274503222,777198702,988224724,49541899,172360109,558769596,840531917,755681607,919179753,628744637,620980711,931289536,289811650,525790458,225213252,752314821,428945657,163285282,586445754,777109207},
{1,88,3873,113696,2505185,44204952,650844481,226249800,139592260,368929667,586173310,58316112,13824791,382668545,419169917,975132045,282396126,260476682,282116,840730697,299497159,528301,202661371,611466433,315161999,680631182,972284457,605874791,778883465,10711055,44152030,103089513,902188004,676430487,996145213,894090321,712586243,186172735,401729961,952754438,698083383,550859329,672182317,728191699,451666059,596264674,45441364,961585850,953233850,511621787},
{1,90,4051,121620,2740501,49450638,744500071,621594345,987436405,495958325,451061295,95550710,167691613,564184949,366023404,760325359,17853516,560726324,821485122,662497928,802725777,102751230,404889894,904494288,796743453,372770695,240949692,175936328,520745030,171351927,34800804,304644584,391613693,281772830,431600591,534460058,767750729,996556416,496436959,219103231,739419227,61730790,157413772,274922405,310664143,604858863,395132840,735126573,32388164,710137765},
{1,92,4233,129904,2992025,55183164,849133873,215228275,824259018,307653734,254673347,801285352,64527668,796404230,726612576,852961332,631140200,209720033,591931472,75914508,541138206,446615206,954256330,832970536,411942358,959023832,191648635,408959862,77016249,546765978,360269471,149588792,892096540,967240809,308640030,123881554,930947456,557109758,951558238,400009707,398703977,338498606,730435096,542457754,288511456,929777685,40572789,201407725,695249338,338439765},
{1,94,4419,138556,3260485,61435674,965752711,30114845,69602131,201514876,763841957,819800649,685613662,546545553,69562345,649136246,133237764,974097997,775749495,443595468,60648175,48401580,449273109,667169930,895688653,994959244,877464356,790575868,817254751,232711935,546418807,405723791,300732433,565385868,216799233,547646661,146765504,812402265,735339518,866810322,672343760,237549659,823050137,60031340,314935268,362340564,664065983,928788161,237994599,498167929},
{1,96,4609,147584,3546625,68242784,95431162,91298711,191015687,462132694,427489520,11132112,516546416,748705624,364813515,83512099,865886109,973221863,723069341,942414297,446657933,555707688,53382370,169825402,129226607,258740109,777623935,677501812,961095328,880060977,234403984,373348689,270084919,202207494,44490626,26152530,494905704,576880817,936924063,229823189,408441460,697007325,409499225,221634403,805055677,833981240,266534443,779509261,261775399,250403725},
{1,98,4803,156996,3851205,75640614,239314560,426044433,708358831,361507205,251129412,689751044,217429565,482681598,596200730,44526337,993924545,833032503,529323693,194807317,583879540,586245154,195335205,418542977,321052350,677068182,796155483,455706580,391128499,984347709,406664326,560254276,372443034,757206310,790272974,369970619,408526316,100661933,299707088,648643845,138884496,78172634,987953980,841416578,952927254,116680356,984115837,232496343,83795861,862923360} };
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
//【方法】
// 愚直を書いて集めたデータをもとに変数係数線形漸化式を復元する．
//【使い方】
// 1. vm tbl = naive() を実装する．
// 2. coefs = embed_coefs(tbl, TRM1_ini, DEG1_ini, TRM2_ini, DEG2_ini, LLL); を実行する．
// 3. 出力を solve() 内に貼る．
// 4. solve(tbl, n, m, [coefs]) で勝手に tbl[n][0..m] を求めてくれる．
// 愚直解を用意する．再計算がイヤなら埋め込む．
// auto tbl = naive();
// return 0;
// 愚直解を渡して変数係数線形漸化式の係数を得る．再計算がイヤなら埋め込む．
// 引数：tbl, DEG1_ini, TRM2_ini, DEG2_ini, LLL?
// auto [coefs1, coefs] = embed_coefs_2D(tbl, 40, 4, 1, 0);
int n, m;
cin >> n >> m;
// n = 998, m = 2443;
// 2 次元数列 tbl を元に seq = tbl[n][0..m] を計算する．
// 整理すると綺麗な式になるなら FullSimplify[] すると速くなる．
// auto seq = solve_2D(tbl, n, m, coefs1, coefs);
auto seq = solve_2D(tbl, n, m);
//dump(seq);
mint res = seq[m];
EXIT(res); // サンプル 4 は合うが 3 がだめ
}