結果
| 問題 | No.1062 素敵なスコア |
| コンテスト | |
| ユーザー |
 ecottea
|
| 提出日時 | 2025-12-25 03:46:36 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 50,194 bytes |
| 記録 | |
| コンパイル時間 | 11,476 ms |
| コンパイル使用メモリ | 368,496 KB |
| 実行使用メモリ | 7,852 KB |
| 最終ジャッジ日時 | 2025-12-25 03:46:51 |
| 合計ジャッジ時間 | 13,849 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 1 |
| other | AC * 19 WA * 13 |
ソースコード
#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
pair<vm, int> slice_1D(const vvm& tbl, int i2) {
// seq : tbl[..][i2] を抜き出した列
vm seq;
// offset : seq[0] が tbl[offset][i2] に対応することを表す．
int offset = INF;
rep(i1, sz(tbl)) {
if (i2 < sz(tbl[i1])) {
chmin(offset, i1);
seq.push_back(tbl[i1][i2]);
}
}
return { seq, offset };
}
tuple<vvm, int, int> slice_2D(const vvvm& box, int i3) {
// tbl : box[..][..][i3] を抜き出したテーブル
vvm tbl;
// offset : tbl[0][0] が box[offset1][offset2][i3] に対応することを表す．
int offset1 = INF, offset2 = INF;
rep(i1, sz(box)) {
tbl.push_back(vm());
rep(i2, sz(box[i1])) {
if (i2 < sz(box[i1]) && i3 < sz(box[i1][i2])) {
chmin(offset1, i1);
chmin(offset2, i2);
tbl.back().push_back(box[i1][i2][i3]);
}
}
if (tbl.back().empty()) tbl.pop_back();
}
return { tbl, offset1, offset2 };
}
// 数列 seq を延長して seq[0..N] にする．
void solve_1D(vm& seq, int N, vvm coefs) {
// static int call_cnt = 0;
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 i1 =", i);
Assert(dnm != 0);
}
seq[i] = -num / dnm;
// 除算回避用
//mint dnm_inv;
//if (call_cnt == 0) {
// dnm_inv = fm.inv_neg(1 + i);
//}
//else {
// dnm_inv = fm.inv_neg(-1 + 2 * i) * 2 * fm.inv_neg(2 + i);
//}
//seq[i] = -num * dnm_inv;
}
// call_cnt++;
}
// 2 次元数列 tbl を元に seq = tbl[N][0..M] を計算する．
vm solve_2D(const vvm& tbl, int N, int M, vvvm coefs1, vvvm coefs) {
// static int call_cnt = 0;
int TRM1 = 1;
int DEG1 = sz(coefs);
int TRM2 = sz(coefs[0]);
int DEG2 = sz(coefs[0][0]);
vm res(TRM2 - 1);
// i1 方向に tbl[..][0], ..., tbl[..][TRM2-2] を延長する．
dump("------- solve_1D -------");
rep(i2, TRM2 - 1) {
dump("--- i2:", i2, "---");
auto [seq, offset] = slice_1D(tbl, i2);
if (N - offset < 0) continue;
solve_1D(seq, N - offset, coefs1[i2]);
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) {
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 N1 =", N, "i2 =", i2);
Assert(dnm != 0);
}
res[i2] = -num / dnm;
}
// call_cnt++;
return res;
}
// 3 次元数列 box を元に seq = tbl[N1][N2][0..N3] を計算する．
vm solve_3D(const vvvm& box, int N1, int N2, int N3, vvvvm coefs1, vvvvm coefs2, vvvvm coefs3) {
int TRM1 = 1;
int DEG1 = sz(coefs3);
int TRM2 = 1;
int DEG2 = sz(coefs3[0]);
int TRM3 = sz(coefs3[0][0]);
int DEG3 = sz(coefs3[0][0][0]);
vm res(TRM3 - 1);
// (i1,i2) 平面における延長
dump("------- solve_2D -------");
rep(i3, TRM3 - 1) {
dump("--- i3:", i3, "---");
auto [tbl, offset1, offset2] = slice_2D(box, i3);
if (N1 - offset1 < 0 || N2 - offset2 < 0) continue;
auto seq = solve_2D(tbl, N1 - offset1, N2 - offset2, coefs1[i3], coefs2[i3]);
dump("seq:", seq);
res[i3] = seq[N2 - offset2];
}
vm pow_i1s(DEG1);
pow_i1s[0] = 1;
repi(d1, 1, DEG1 - 1) pow_i1s[d1] = pow_i1s[d1 - 1] * (N1 - TRM1 + 1);
vm pow_i2s(DEG2);
pow_i2s[0] = 1;
repi(d2, 1, DEG2 - 1) pow_i2s[d2] = pow_i2s[d2 - 1] * (N2 - TRM2 + 1);
// i3 方向に tbl[N1][N2][..] を延長する．
res.resize(N3 + 1);
repi(i3, TRM3 - 1, N3) {
mint dnm = 0;
mint pow_i3 = 1;
rep(d3, DEG3) {
rep(d2, DEG2) {
rep(d1, DEG1) {
dnm += coefs3[d1][d2][0][d3] * pow_i1s[d1] * pow_i2s[d2] * pow_i3;
}
}
pow_i3 *= i3 - TRM3 + 1;
}
mint num = 0;
repi(t3, 1, TRM3 - 1) {
mint pow_i3 = 1;
rep(d3, DEG3) {
rep(d2, DEG2) {
rep(d1, DEG1) {
num += coefs3[d1][d2][t3][d3] * pow_i1s[d1] * pow_i2s[d2] * pow_i3 * res[i3 - t3];
}
}
pow_i3 *= i3 - TRM3 + 1 + t3;
}
}
// dnm * tbl[N1][N2][i3] + num = 0 を解く．分母 0 に注意！
if (dnm == 0) {
dump("DIVISION BY ZERO at N1 =", N1, "N2 =", N2, "i3 =", i3);
Assert(dnm != 0);
}
res[i3] = -num / dnm;
}
return res;
}
// 3 次元数列 box を元に seq = tbl[N1][N2][0..N3] を計算する．
vm solve_3D(const vvvm& box, int N1, int N2, int N3) {
// --------------- embed_coefs() からの出力を貼る ----------------
constexpr int TRM1 = 1;
constexpr int DEG1 = 3;
constexpr int TRM2 = 1;
constexpr int DEG2 = 4;
constexpr int TRM3 = 4;
constexpr int DEG3 = 3;
vvvm coefs1[TRM3 - 1] = { {
{{-499122176,0},{499122173,499122176},{1,1}},
{{-14538994,-242366534,0},{-164725306,228127310,242366534},{-4,0,1}},
{{-45548726,-67621358,0},{420273123,451276873,67621358},{-9,0,1}},
{{-315253223,-345455770,0},{425477732,-261289447,345455770},{-16,0,1}}},{
{{330301441,-491782144,0},{-477102081,132120572,491782144},{-4,0,1}},
{{247784853,-471146467,0},{243344266,-415639111,471146467},{-9,0,1}},
{{300171379,195460433,0},{202441166,328094295,-195460433},{-16,0,1}},
{{39657729,-299903811,0},{203474899,363084052,299903811},{-25,0,1}}},{
{{187170817,-436731904,0},{249561087,436731900,436731904},{-9,0,1}},
{{223368088,-488208426,0},{-300491920,199357834,488208426},{-16,0,1}},
{{171469142,-24848328,0},{-482857099,27317481,24848328},{-25,0,1}},
{{-213892211,20318458,0},{-134425600,31026088,-20318458},{-36,0,1}}} };
vvvm coefs2[TRM3 - 1] = { {
{{81338487,-115845635,-104754044,277290097,0},{310563910,236620145,-382660490,251409685,-277290097},{401763985,157749454,-176232079,280987552,-257571676},{0,-138028968,-215670342,-239702094,-162060710},{4,-8,17,-19,6}},
{{332748086,55458008,277290097,0,0},{443664194,-48063560,-358628498,-110916035,0},{-41901084,412854799,-370952286,66549645,-443664159},{0,-207043433,-408541000,158979526,83803213},{4,-4,-13,5,1}},
{{0,0,0,0,0},{443664178,-499122167,-277290097,0,0},{305635325,-85035621,-257571695,-443664159,0},{0,430107709,237237024,83803213,0},{-8,0,0,1,0}}},{
{{-86328095,-53605269,472941496,-137297626,0},{-373599025,-161546618,198210719,-5302790,137297626},{197576408,-363332895,167793537,387564803,218849424},{0,-97679729,-482443014,-378697303,355784044},{0,-16,4,-10,6}},
{{-125951368,486214820,-137297626,0,0},{-56696680,216517406,257946204,-449053849,0},{-265753145,211846628,127624917,52343875,-274595252},{0,334535391,-410453906,-216186422,-189650244},{-16,-4,-10,6,1}},
{{0,0,0,0,0},{-248780539,237434281,137297626,0,0},{250874242,-286464500,-256019138,-274595252,0},{0,66907082,-192669977,-189650244,0},{-8,0,0,1,0}}},{
{{-384753161,-355086487,-188121135,-157294821,0},{346494156,278852121,270905621,-188572406,157294821},{273768855,-357028580,462005424,125453383,322218114},{0,-121847802,-294778760,-246056517,205025569},{-36,-24,3,-3,6}},
{{272377135,266245675,-157294821,0,0},{238852452,-241086428,-303654720,-369065069,0},{-176167301,498854536,-116298192,-210160206,-314589642},{0,428044313,48138832,-339891286,443318858},{-44,4,-9,7,1}},
{{0,0,0,0,0},{151163361,417409036,157294821,0,0},{20615939,-255655555,485644395,-314589642,0},{0,-453818135,121615278,443318858,0},{-8,0,0,1,0}}} };
mint coefs3[DEG1][DEG2][TRM3][DEG3] = { {
{{-1,0,0},{12,3,0},{-16,-16,-2},{0,0,4}},
{{499122176,0,0},{9,-499122175,0},{499122156,499122162,-1},{0,-499122172,-499122172}},
{{0,0,0},{-499122175,0,0},{499122168,-3,0},{-499122176,5,1}},
{{0,0,0},{0,0,0},{-1,0,0},{-499122176,1,0}}},{
{{0,0,0},{3,0,0},{-14,-5,0},{0,6,1}},
{{0,0,0},{-499122175,0,0},{499122164,-3,0},{-499122174,8,1}},
{{0,0,0},{0,0,0},{-3,0,0},{3,3,0}},
{{0,0,0},{0,0,0},{0,0,0},{1,0,0}}},{
{{0,0,0},{0,0,0},{-2,0,0},{2,1,0}},
{{0,0,0},{0,0,0},{-1,0,0},{-499122174,1,0}},
{{0,0,0},{0,0,0},{0,0,0},{1,0,0}},
{{0,0,0},{0,0,0},{0,0,0},{0,0,0}}} };
// --------------------------------------------------------------
vm res(TRM3 - 1);
// (i1,i2) 平面における延長
dump("------- solve_2D -------");
rep(i3, TRM3 - 1) {
dump("--- i3:", i3, "---");
auto [tbl, offset1, offset2] = slice_2D(box, i3);
if (N1 - offset1 < 0 || N2 - offset2 < 0) continue;
auto seq = solve_2D(tbl, N1 - offset1, N2 - offset2, coefs1[i3], coefs2[i3]);
dump("seq:", seq);
res[i3] = seq[N2 - offset2];
}
vm pow_i1s(DEG1);
pow_i1s[0] = 1;
repi(d1, 1, DEG1 - 1) pow_i1s[d1] = pow_i1s[d1 - 1] * (N1 - TRM1 + 1);
vm pow_i2s(DEG2);
pow_i2s[0] = 1;
repi(d2, 1, DEG2 - 1) pow_i2s[d2] = pow_i2s[d2 - 1] * (N2 - TRM2 + 1);
// i3 方向に tbl[N1][N2][..] を延長する．
res.resize(N3 + 1);
repi(i3, TRM3 - 1, N3) {
mint dnm = 0;
mint pow_i3 = 1;
rep(d3, DEG3) {
rep(d2, DEG2) {
rep(d1, DEG1) {
dnm += coefs3[d1][d2][0][d3] * pow_i1s[d1] * pow_i2s[d2] * pow_i3;
}
}
pow_i3 *= i3 - TRM3 + 1;
}
mint num = 0;
repi(t3, 1, TRM3 - 1) {
mint pow_i3 = 1;
rep(d3, DEG3) {
rep(d2, DEG2) {
rep(d1, DEG1) {
num += coefs3[d1][d2][t3][d3] * pow_i1s[d1] * pow_i2s[d2] * pow_i3 * res[i3 - t3];
}
}
pow_i3 *= i3 - TRM3 + 1 + t3;
}
}
// dnm * tbl[N1][N2][i3] + num = 0 を解く．分母 0 に注意！
if (dnm == 0) {
dump("DIVISION BY ZERO at N1 =", N1, "N2 =", N2, "i3 =", i3);
Assert(dnm != 0);
}
res[i3] = -num / dnm;
}
return res;
}
vvvm box = {
{{8,48,336,2640,23040,221760,2338560,26853120,333849600,477704188,298575808,598598695,17072443,533766958,180722340},{40,248,1920,17040,168000,1814400,21288960,269740800,677612541,581561291,728382657,63394417,623147336,907819853,101655699},{276,1800,14760,141120,1512000,17781120,226800000,118777341,823656915,366190899,764061040,873712965,485026941,427126902,289106224},{2208,15696,137088,1395072,15966720,201035520,749787134,402160600,776637831,125157049,328394580,610564453,290617021,883023368,786922801},{19680,154560,1451520,15724800,191116800,558186494,107749339,52024766,476777082,331909681,186765417,897251973,671245000,890971481,982669978},{192960,1676160,17003520,196473600,535376894,849710045,939924956,108012740,462321415,26658156,909631924,197527452,617137181,340426208,564456191},{2066400,19776960,216820800,677936894,587075292,821147615,659020706,9539179,37634655,657301310,731993243,411761456,656199464,260302143,484560073},{24030720,252000000,983965694,293379033,347991496,933594392,797388978,279162056,212424334,651029171,744643915,815093652,887968561,612007847,413019093},{301916160,454078461,952039381,311133592,812956457,925433356,387622903,17597259,378009409,100824488,946766598,308705852,140561957,310974891,765471016},{85793788,557132750,578485583,312270807,636294809,494622216,445221739,854912,238722275,44733988,337723580,890268255,149607171,441060926,679239940},{100613573,63744236,107142948,757217903,687896675,79824955,576424003,334127970,765487456,521420866,414261348,100563328,300992993,142528971,713953306},{702434417,281359633,632301980,797822977,859409218,993475177,123587239,571219047,929706468,320442670,820192364,782082619,701529048,575096662,335166436},{181736862,791290923,845847956,175284481,600870838,559769104,501335516,471664524,473856220,67794608,770277444,343476342,610407583,40890120,844975401},{557869603,315302302,706335400,385201800,411358432,652572248,277229151,908633511,659015078,779598208,453977857,297989763,431477845,360472494,105078951},{316050562,468748055,587288997,501796491,348797517,445167672,901689913,213487949,197316113,75750140,743787502,529550715,246587726,711850678,994453187}},
{{48,312,2400,20880,201600,2136960,24675840,308448000,158369788,978783173,219540581,368692476,842580118,542262015,858810272},{248,1760,15120,147840,1599360,18869760,240710400,305055741,463432656,872459532,640849662,667837525,508123462,310600175,7296509},{1800,13680,126000,1330560,15603840,199584000,757770494,785361880,510267774,787222027,261485062,291205990,644107704,527254451,138633671},{15696,129024,1266048,14224896,177811200,430452734,794967005,911109581,280216343,698970372,210868062,702424898,257481872,888370264,386002164},{154560,1384320,14515200,172972800,292074494,109046751,671211005,607708789,9539179,373562499,99915770,656248958,489394942,600547908,255425026},{1676160,16381440,184032000,330090494,559860704,472411665,838690887,771134575,254486594,525190124,494646276,637805614,65377944,296574303,522880278},{19776960,210470400,538228094,68805598,156509194,507658398,279750694,90361170,826064156,655585639,684284705,662244824,852543278,790593574,598802555},{252000000,913002494,586750939,79277545,908822405,582475310,345445913,29687635,742245296,822680425,220001495,18691888,712499108,670876552,806504939},{454078461,89836501,853478831,223274240,112476899,100403411,746732352,716181067,171057347,31395043,245915766,18583970,517417827,143521234,701529048},{557132750,237317466,742007061,322916994,131443065,464058516,8431554,73923055,556084758,189892197,715009442,8009920,545265884,7602317,628950746},{63744236,997616581,518829362,956037809,168224541,568925982,762119703,769517696,618146626,811735202,386700995,268370319,523312493,791416077,364960095},{281359633,219083534,552009294,81504243,292154131,936488574,115964027,756646361,390013543,748630541,870256045,131565204,471508585,549509331,570550403},{791290923,897496481,933089978,98487844,809909845,765387923,337723580,363519834,875288630,611240272,29670571,819410580,26013304,726460100,185799488},{315302302,129890501,596316849,937793387,382668655,429531394,537137573,340236154,877540562,962556769,16604148,559402080,637996934,172520715,453788116},{468748055,245444736,488891162,959882000,585379195,265407207,820132488,213209204,244625782,193056089,977762326,475382144,417866693,923295028,722952181}},
{{336,2400,20160,191520,2016000,23224320,290304000,917113341,620505032,315591831,384133134,101680065,80299930,5219787,138280973},{1920,15120,141120,1491840,17418240,221356800,38943741,624397268,651771206,104569505,976650685,341417195,487399347,484256282,190254987},{14760,126000,1270080,14515200,183254400,518269694,187582939,368764342,805236128,570298222,858621105,824925039,114460272,475985833,305547510},{137088,1266048,13644288,166199040,238852094,724089824,8916478,895632990,987195988,490057561,676360669,734441645,974210425,262389698,47546300},{1451520,14515200,166924800,159018494,708771810,85757478,843837773,266883479,851597236,260642290,916227929,321121885,891518066,296574303,175486760},{17003520,184032000,261661694,914058210,391552561,993061534,421290059,924480099,669843992,333043594,926964610,168919175,991361339,227615141,291313659},{216820800,538228094,228797151,323312160,17543272,459891704,698448311,453514114,817989581,503005563,576441541,514207263,588816835,799510965,385244984},{983965694,586750939,987950581,397314235,54229368,389635151,469586766,61974125,217879253,941820993,850206792,297119649,44395334,375997243,658496810},{952039381,853478831,26713501,205120847,327369457,234578061,672519579,972415256,761347899,794630309,372531232,689453607,692288414,784990876,391950729},{578485583,742007061,551205840,448975666,76062841,678978884,526634671,440475659,851324507,375153521,73656597,632103349,898266075,481557442,921842434},{107142948,518829362,47173834,212424334,764076040,49203172,915002775,690690946,677217376,415962258,60180067,507883977,549809390,145505935,606988593},{632301980,552009294,487698820,939737961,425985022,145208798,775638335,691752786,27475110,341848174,118978583,884307364,730876396,121023725,652470011},{845847956,933089978,929271199,435858039,524521626,581177735,569920802,981786970,598460733,377572566,264417139,346364075,11873705,84757132,863231746},{706335400,596316849,447775470,746839035,920210481,622221732,540355931,451875151,359873792,789740009,210319930,536519183,229586823,324917490,966103211},{587288997,488891162,830828710,156362780,83286454,891814063,367167748,870404690,541121709,737385003,390329117,6505980,325568088,836798853,836338841}},
{{2640,20880,191520,1975680,22498560,279417600,757446141,221985738,886752445,63394417,307555505,791324791,125764677,528581089,773110668},{17040,147840,1491840,16934400,211680000,877520894,66210774,66317679,451042652,551342463,407701052,632053215,382600583,760910631,649457373},{141120,1330560,14515200,177811200,398519294,28564445,939924956,818103343,801908092,190783580,969578907,48968040,424364517,168122911,422154475},{1395072,14224896,166199040,174985214,189529057,66547228,973162637,194827075,449888597,212424334,317413981,46198931,824875545,163617212,158110633},{15724800,172972800,159018494,908680163,292152891,186919681,105698228,622625275,381187180,452937560,386152310,857336099,497239426,838956454,926771901},{196473600,330090494,914058210,697347644,571124681,411032220,40149965,345349175,710963759,486369816,651049901,652328593,147934919,471541619,409821524},{677936894,68805598,323312160,186919681,549962209,863651725,537895537,220960716,866168383,398789615,243538451,877474209,301271738,807852592,891920809},{293379033,79277545,397314235,210895505,411729770,533877374,606704364,926729105,984063440,387780214,364113823,530064145,682737065,109642738,431310640},{311133592,223274240,205120847,70276688,477623092,247024945,508409509,141892107,956605128,204159390,827082231,415283850,189046164,717383708,427729584},{312270807,322916994,448975666,279479067,16008196,598612770,696151044,325531804,868944845,346547202,701573321,356498155,25981571,268591219,222877049},{757217903,956037809,212424334,163629824,191867083,203698340,739053826,10707870,188347117,674666590,96243423,987377598,295375586,631049820,534809689},{797822977,81504243,939737961,588565289,658953360,986682390,227416046,653214777,195103359,663769185,815248646,879267631,744662513,182362547,83724782},{175284481,98487844,435858039,776980978,203782636,94814771,387289628,731938827,388937974,941915966,3698080,697704922,666051404,81055662,195482158},{385201800,937793387,746839035,751022059,165641635,261130056,500846328,642417632,620908640,382475748,56039241,276277275,883021537,132388589,708627984},{501796491,959882000,156362780,355327654,428532674,659191745,954842511,789740009,806663099,989672998,476012892,199516720,598922962,848360043,276234283}},
{{23040,201600,2016000,22498560,275788800,677612541,781469644,934778070,404720678,461962085,678847892,222200589,484919601,73200222,143941471},{168000,1599360,17418240,211680000,824298494,785361880,114343304,682024750,390157212,706975033,744561779,700573765,320315837,951821520,173126472},{1512000,15603840,183254400,398519294,308306398,227260910,825823672,956314672,284182121,79824955,330777755,982014076,237183576,702577521,903969772},{15966720,177811200,238852094,189529057,85757478,512805284,318352339,90361170,308860246,4643233,100824488,76970999,712331755,483040167,498448350},{191116800,292074494,708771810,292152891,633443219,524227779,684890969,461550440,264622204,684486217,498002007,857420395,20552995,642400133,64548357},{535376894,559860704,391552561,571124681,740361058,596229251,549950026,630162418,314265585,513525769,277720418,283839612,619000859,349090512,940635751},{587075292,156509194,17543272,549962209,585971412,80964072,860987750,775528812,129289046,40536842,658321343,102329227,427626560,423446156,890444380},{347991496,908822405,54229368,411729770,222559459,379947307,952741275,346728836,627900860,913481630,131394279,728480052,23578262,163324340,817976558},{812956457,112476899,327369457,477623092,437941518,775528812,169516373,731840223,511712797,930303699,310751895,910183618,348400648,338925667,989672998},{636294809,131443065,76062841,16008196,289857352,324866560,609002794,199894708,826681735,753675800,378787263,260467486,278609872,201820358,233948544},{687896675,168224541,764076040,191867083,632093097,763235266,808695390,702099925,115341182,286635184,107631995,814569048,15489872,443155235,254409929},{859409218,292154131,425985022,658953360,391534173,993492029,629360836,430021600,767692657,264332431,994683036,444978061,886723007,602786663,14486499},{600870838,809909845,524521626,203782636,934690447,90040957,13430201,63766795,855418355,994504025,787465045,931437951,802335711,748960145,420224600},{411358432,382668655,920210481,165641635,500802882,26209740,811943936,508354394,77625181,194801461,312592071,131611551,630001770,322226693,612827939},{348797517,585379195,83286454,428532674,91036842,497939245,938910989,187352261,276925081,828143076,545140924,9324508,585947112,636870343,683031554}},
{{221760,2136960,23224320,279417600,677612541,302468044,459668706,409867564,564899805,741113586,294527523,7296509,112218477,522730032,673314819},{1814400,18869760,221356800,877520894,785361880,795848081,797515799,493094932,240994785,824925039,439931475,864959311,994063967,796762650,761920944},{17781120,199584000,518269694,28564445,227260910,828397115,35273609,140572375,152151889,959889417,152445804,512729505,327969346,866177706,982351262},{201035520,430452734,724089824,66547228,512805284,359527427,409719633,965668405,794373754,139842743,15164766,695445576,343686053,636076974,77327896},{558186494,109046751,85757478,186919681,524227779,40149965,501732070,351281861,217879253,811760143,378872857,715009442,215253848,510530898,701529048},{849710045,472411665,993061534,411032220,596229251,285402192,90639571,410651917,754591132,865781167,635329220,733691379,500154573,572432334,426046953},{821147615,507658398,459891704,863651725,80964072,741581977,231086850,766184187,903446789,929602590,202683432,242811241,847261916,309878771,503516287},{933594392,582475310,389635151,533877374,379947307,295915763,28061534,572324377,946978717,844874442,513226204,400303382,947179653,295375586,75121297},{925433356,100403411,234578061,247024945,775528812,844220697,120335594,296947100,873658,378692549,951914532,283245902,467531404,548654125,710766348},{494622216,464058516,678978884,598612770,324866560,703493124,364491816,515815843,788410786,965133399,186770834,951898393,783921617,383139956,934568961},{79824955,568925982,49203172,203698340,763235266,76446877,958976329,378692549,80814907,905305640,704841968,756797455,769129413,774472730,231742713},{993475177,936488574,145208798,986682390,993492029,954157640,48358544,430748999,229803072,78878258,220214722,769062685,419089556,221418731,446969373},{559769104,765387923,581177735,94814771,90040957,439423561,400303382,4924306,324048851,281154074,880916773,32338834,992093664,188832107,751531575},{652572248,429531394,622221732,261130056,26209740,868452704,452077271,294012582,952805843,338531211,67176238,462454048,612052272,17573044,156174765},{445167672,265407207,891814063,659191745,497939245,988634649,875941195,248574072,64652179,364196347,66247844,49100048,925379191,737807107,740822578}},
{{2338560,24675840,290304000,757446141,781469644,459668706,78835075,616368665,978121873,342745479,93956166,890165433,706427318,90827918,768000568},{21288960,240710400,38943741,66210774,114343304,797515799,860155623,8004661,873142995,598918066,398352347,776184714,949064893,313044398,666952332},{226800000,757770494,187582939,939924956,825823672,35273609,758198695,188315356,938058673,930392760,994760698,296574303,393119720,98797429,905720614},{749787134,794967005,8916478,973162637,318352339,409719633,186360105,690116838,163253696,639456846,112958675,738292644,77625224,18672149,787593524},{107749339,671211005,843837773,105698228,684890969,501732070,712916531,982820124,800366154,59841165,925837089,643577399,524658090,962556769,792254111},{939924956,838690887,421290059,40149965,549950026,90639571,775528812,376001637,420022134,204159390,815613179,863013707,507883977,789740009,124582772},{659020706,279750694,698448311,537895537,860987750,231086850,312986332,835779586,693073597,602334353,253406635,166879383,967488134,545362613,717671879},{797388978,345445913,469586766,606704364,952741275,28061534,221050765,464605084,674015928,36975521,241573745,786387873,221656281,710836596,136635412},{387622903,746732352,672519579,508409509,169516373,120335594,558106652,35280814,619105812,314238906,521919470,813546795,205639446,322967727,309303138},{445221739,8431554,526634671,696151044,609002794,364491816,412193879,805778279,119047857,803135968,291968076,970936473,55513564,254532967,767785881},{576424003,762119703,915002775,739053826,808695390,958976329,466476338,477026945,385665474,964438699,858483863,514487870,846217902,919689294,757820313},{123587239,115964027,775638335,227416046,629360836,48358544,651182564,711660569,128342003,70372496,827625934,530877814,604198101,898155828,986942368},{501335516,337723580,569920802,387289628,13430201,400303382,386922525,987065617,177016362,514487870,765798090,924882715,8860168,951728918,761249312},{277229151,537137573,540355931,500846328,811943936,452077271,33393598,333563681,354094695,689715598,627989776,579860368,774673446,911059678,545423322},{901689913,820132488,367167748,954842511,938910989,875941195,904619971,182028907,654927342,769692970,236063204,143516474,336746158,670294266,438036180}},
{{26853120,308448000,917113341,221985738,934778070,409867564,616368665,391628400,366854457,744898572,410552384,695033329,402646007,785376695,407132763},{269740800,305055741,624397268,66317679,682024750,493094932,8004661,889215647,179289185,916983651,298183761,630033201,475509165,867072109,289886438},{118777341,785361880,368764342,818103343,956314672,140572375,188315356,265285523,321121885,685032802,608392392,483040167,184815319,319488475,428326121},{402160600,911109581,895632990,194827075,90361170,965668405,690116838,171057347,951602886,961359758,668615587,819581806,224241427,128401779,953883925},{52024766,607708789,266883479,622625275,461550440,351281861,982820124,463820040,898569672,653035936,929126433,106929933,409644295,990729734,82736446},{108012740,771134575,924480099,345349175,630162418,410651917,376001637,936932025,986818828,864766259,439423561,746990680,64265448,730876396,162969008},{9539179,90361170,453514114,220960716,775528812,766184187,835779586,946978717,303037637,459412742,378787263,866783763,77625181,744662513,260713791},{279162056,29687635,61974125,926729105,346728836,572324377,464605084,617063090,297972356,545633704,679193353,596818643,938061982,171220932,859229862},{17597259,716181067,972415256,141892107,731840223,296947100,35280814,33747331,993645446,66176999,378727487,958873314,780802026,361593955,712769634},{854912,73923055,440475659,325531804,199894708,515815843,805778279,835263696,113074182,295307627,762864926,249313721,243628148,539768986,221453594},{334127970,769517696,690690946,10707870,702099925,378692549,477026945,545200203,595114888,320549096,677474959,469645445,686965965,55437521,713612201},{571219047,756646361,691752786,653214777,430021600,430748999,711660569,144829918,993695736,64168401,938151437,164580256,986984581,912994123,736968872},{471664524,363519834,981786970,731938827,63766795,4924306,987065617,475051909,830395595,7980420,547327298,878553136,852315837,478093060,627370191},{908633511,340236154,451875151,642417632,508354394,294012582,333563681,359282523,2740925,128364601,225650981,887640439,728540098,80250943,351770085},{213487949,213209204,870404690,789740009,187352261,248574072,182028907,419089556,123171180,148592227,287770898,478093060,617398032,212883058,108203126}},
{{333849600,158369788,620505032,886752445,404720678,564899805,978121873,366854457,961879374,669868036,488548065,610524733,512575542,464478023,434504326},{677612541,463432656,651771206,451042652,390157212,240994785,873142995,179289185,424364517,558305461,837911927,251070892,154376790,128446052,155123194},{823656915,510267774,805236128,801908092,284182121,152151889,938058673,321121885,581790170,265179260,137694694,242160579,43357569,130353765,837061243},{776637831,280216343,987195988,449888597,308860246,794373754,163253696,951602886,245915766,134654882,865458014,694035730,85369541,809171323,302190606},{476777082,9539179,851597236,381187180,264622204,217879253,800366154,898569672,894850336,73656597,255590780,41035979,989891700,255233015,475382144},{462321415,254486594,669843992,710963759,314265585,754591132,420022134,986818828,881150619,227628488,291508090,246111976,878730598,738595042,266520025},{37634655,826064156,817989581,866168383,129289046,903446789,693073597,303037637,860829562,484741203,7765658,98548344,478728865,789017500,315809118},{212424334,742245296,217879253,984063440,627900860,946978717,674015928,297972356,314238906,625596093,422618319,756797455,338531211,892933788,748960145},{378009409,171057347,761347899,956605128,511712797,873658,619105812,993645446,912507195,161317833,811867023,87780539,826763547,248328973,49100048},{238722275,556084758,851324507,868944845,826681735,788410786,119047857,113074182,961917046,159706976,964540427,901854504,91687103,384561029,194923845},{765487456,618146626,677217376,188347117,115341182,80814907,385665474,595114888,141237507,259846327,642999712,531817079,837192552,525887615,729684740},{929706468,390013543,27475110,195103359,767692657,229803072,128342003,993695736,475178792,642666072,899053902,713455632,860173948,578394438,293803267},{473856220,875288630,598460733,388937974,855418355,324048851,177016362,830395595,753618883,857671766,801422305,453292332,988870275,118637455,527235007},{659015078,877540562,359873792,620908640,77625181,952805843,354094695,2740925,960067229,547668464,356474023,606860378,746229311,971544828,442255426},{197316113,244625782,541121709,806663099,276925081,64652179,654927342,123171180,784931470,359898110,163603460,582133876,622484744,525768501,892890600}},
{{477704188,978783173,315591831,63394417,461962085,741113586,342745479,744898572,669868036,86971526,714464096,947841462,835456314,583165173,563929455},{581561291,872459532,104569505,551342463,706975033,824925039,598918066,916983651,558305461,574456718,637973932,525355081,20819128,784759231,602158828},{366190899,787222027,570298222,190783580,79824955,959889417,930392760,685032802,265179260,355327654,270833209,77327896,597201763,37711530,631371846},{125157049,698970372,490057561,212424334,4643233,139842743,639456846,961359758,134654882,215253848,429810705,658496810,712696255,40890120,379554550},{331909681,373562499,260642290,452937560,684486217,811760143,59841165,653035936,73656597,970640631,854976174,789740009,37482610,840072793,456992269},{26658156,525190124,333043594,486369816,513525769,865781167,204159390,864766259,227628488,139680560,337035240,568145378,456849496,534809689,105414076},{657301310,655585639,503005563,398789615,40536842,929602590,602334353,459412742,484741203,386922525,608132102,918115288,808471855,546225254,402390144},{651029171,822680425,941820993,387780214,913481630,844874442,36975521,545633704,625596093,697299662,167043015,638566249,915403072,621400547,881154929},{100824488,31395043,794630309,204159390,930303699,378692549,314238906,66176999,161317833,762864926,240391972,706567561,604198101,308444226,997506403},{44733988,189892197,375153521,346547202,753675800,965133399,803135968,295307627,159706976,204704976,232723329,421784585,493299319,188278719,259542746},{521420866,811735202,415962258,674666590,286635184,905305640,964438699,320549096,259846327,368036350,454242636,108352347,400737891,402043235,617398032},{320442670,748630541,341848174,663769185,264332431,78878258,70372496,64168401,642666072,811130333,77568981,828481843,139930031,327189256,116060408},{67794608,611240272,377572566,941915966,994504025,281154074,514487870,7980420,857671766,775712028,752902756,297092251,444978533,238918222,104888034},{779598208,962556769,789740009,382475748,194801461,338531211,689715598,128364601,547668464,179418551,546020518,546869720,386483637,86211785,829075079},{75750140,193056089,737385003,989672998,828143076,364196347,769692970,148592227,359898110,391521711,564501798,668596885,471397300,805869435,253739672}},
{{298575808,219540581,384133134,307555505,678847892,294527523,93956166,410552384,488548065,714464096,94685749,521823283,273063940,542413336,730294969},{728382657,640849662,976650685,407701052,744561779,439931475,398352347,298183761,837911927,637973932,981762629,965250019,763243112,521762938,51112650},{764061040,261485062,858621105,969578907,330777755,152445804,994760698,608392392,137694694,270833209,421399456,830625762,157048314,934518658,319505811},{328394580,210868062,676360669,317413981,100824488,15164766,112958675,668615587,865458014,429810705,849539233,664458721,83758699,316240911,379174849},{186765417,99915770,916227929,386152310,498002007,378872857,925837089,929126433,255590780,854976174,390274661,427729584,260291700,332913890,276096529},{909631924,494646276,926964610,651049901,277720418,635329220,815613179,439423561,291508090,337035240,797365089,315976723,895432358,554899894,924742627},{731993243,684284705,576441541,243538451,658321343,202683432,253406635,378787263,7765658,608132102,66333076,319076856,484826065,526541940,683478059},{744643915,220001495,850206792,364113823,131394279,513226204,241573745,679193353,422618319,167043015,73081693,926637714,145567047,211064538,725794932},{946766598,245915766,372531232,827082231,310751895,951914532,521919470,378727487,811867023,240391972,1005997,782132665,863348474,457184490,651235758},{337723580,715009442,73656597,701573321,378787263,186770834,291968076,762864926,964540427,232723329,531817079,547668464,383940514,478093060,973655587},{414261348,386700995,60180067,96243423,107631995,704841968,858483863,677474959,642999712,454242636,863649965,338163029,205458332,427635069,649070512},{820192364,870256045,118978583,815248646,994683036,220214722,827625934,938151437,899053902,77568981,817917808,419820004,546869720,678279150,715948334},{770277444,29670571,264417139,3698080,787465045,880916773,765798090,547327298,801422305,752902756,399247694,608149072,65928151,554910375,7936971},{453977857,16604148,210319930,56039241,312592071,67176238,627989776,225650981,356474023,546020518,480416523,593075218,72234471,786387405,331041287},{743787502,977762326,390329117,476012892,545140924,66247844,236063204,287770898,163603460,564501798,351219481,943333876,753656736,533412383,985624963}},
{{598598695,368692476,101680065,791324791,222200589,7296509,890165433,695033329,610524733,947841462,521823283,502444980,32533100,809852825,495132235},{63394417,667837525,341417195,632053215,700573765,864959311,776184714,630033201,251070892,525355081,965250019,90574837,481564993,918706760,665785390},{873712965,291205990,824925039,48968040,982014076,512729505,296574303,483040167,242160579,77327896,830625762,196827242,87847711,696122745,125400770},{610564453,702424898,734441645,46198931,76970999,695445576,738292644,819581806,694035730,658496810,664458721,430796343,783706268,249908642,115754222},{897251973,656248958,321121885,857336099,857420395,715009442,643577399,106929933,41035979,789740009,427729584,732527571,769996877,978188237,76430391},{197527452,637805614,168919175,652328593,283839612,733691379,863013707,746990680,246111976,568145378,315976723,350143679,779642803,893722189,252540856},{411761456,662244824,514207263,877474209,102329227,242811241,166879383,866783763,98548344,918115288,319076856,131611551,588617838,668388104,278541606},{815093652,18691888,297119649,530064145,728480052,400303382,786387873,596818643,756797455,638566249,926637714,319703998,375141519,362528491,934392010},{308705852,18583970,689453607,415283850,910183618,283245902,813546795,958873314,87780539,706567561,782132665,715568439,686145710,349325742,687926344},{890268255,8009920,632103349,356498155,260467486,951898393,970936473,249313721,901854504,421784585,547668464,781909230,587368217,222013035,765272405},{100563328,268370319,507883977,987377598,814569048,756797455,514487870,469645445,531817079,108352347,338163029,139930031,831875764,516692276,442255426},{782082619,131565204,884307364,879267631,444978061,769062685,530877814,164580256,713455632,828481843,419820004,952844659,959388521,844730953,657285340},{343476342,819410580,346364075,697704922,931437951,32338834,924882715,878553136,453292332,297092251,608149072,8264794,280799369,355519277,27961546},{297989763,559402080,536519183,276277275,131611551,462454048,579860368,887640439,606860378,546869720,593075218,400323484,765043568,579793352,908065505},{529550715,475382144,6505980,199516720,9324508,49100048,143516474,478093060,582133876,668596885,943333876,736252503,174126562,391607116,572143969}},
{{17072443,842580118,80299930,125764677,484919601,112218477,706427318,402646007,512575542,835456314,273063940,32533100,170875875,928929290,533552970},{623147336,508123462,487399347,382600583,320315837,994063967,949064893,475509165,154376790,20819128,763243112,481564993,875156679,223469560,243861828},{485026941,644107704,114460272,424364517,237183576,327969346,393119720,184815319,43357569,597201763,157048314,87847711,821661723,418951023,196671351},{290617021,257481872,974210425,824875545,712331755,343686053,77625224,224241427,85369541,712696255,83758699,783706268,539568024,525163141,614258071},{671245000,489394942,891518066,497239426,20552995,215253848,524658090,409644295,989891700,37482610,260291700,769996877,546722571,278156630,250299448},{617137181,65377944,991361339,147934919,619000859,500154573,507883977,64265448,878730598,456849496,895432358,779642803,883382043,589015865,212433253},{656199464,852543278,588816835,301271738,427626560,847261916,967488134,77625181,478728865,808471855,484826065,588617838,663358119,944806949,651698206},{887968561,712499108,44395334,682737065,23578262,947179653,221656281,938061982,338531211,915403072,145567047,375141519,574187795,353559387,449457042},{140561957,517417827,692288414,189046164,348400648,467531404,205639446,780802026,826763547,604198101,863348474,686145710,248689070,631069775,755413584},{149607171,545265884,898266075,25981571,278609872,783921617,55513564,243628148,91687103,493299319,383940514,587368217,636961753,694249511,686245099},{300992993,523312493,549809390,295375586,15489872,769129413,846217902,686965965,837192552,400737891,205458332,831875764,805314315,837154899,90814271},{701529048,471508585,730876396,744662513,886723007,419089556,604198101,986984581,860173948,139930031,546869720,959388521,554910375,592297178,581180249},{610407583,26013304,11873705,666051404,802335711,992093664,8860168,852315837,988870275,444978533,65928151,280799369,138631928,80902325,847494278},{431477845,637996934,229586823,883021537,630001770,612052272,774673446,728540098,746229311,386483637,72234471,765043568,662710707,553743434,204118762},{246587726,417866693,325568088,598922962,585947112,925379191,336746158,617398032,622484744,471397300,753656736,174126562,193601167,307565799,848907509}},
{{533766958,542262015,5219787,528581089,73200222,522730032,90827918,785376695,464478023,583165173,542413336,809852825,928929290,617245622,382644705},{907819853,310600175,484256282,760910631,951821520,796762650,313044398,867072109,128446052,784759231,521762938,918706760,223469560,817992764,523185236},{427126902,527254451,475985833,168122911,702577521,866177706,98797429,319488475,130353765,37711530,934518658,696122745,418951023,606947734,65880113},{883023368,888370264,262389698,163617212,483040167,636076974,18672149,128401779,809171323,40890120,316240911,249908642,525163141,471508021,71435030},{890971481,600547908,296574303,838956454,642400133,510530898,962556769,990729734,255233015,840072793,332913890,978188237,278156630,483186213,457036900},{340426208,296574303,227615141,471541619,349090512,572432334,789740009,730876396,738595042,534809689,554899894,893722189,589015865,273926960,510582528},{260302143,790593574,799510965,807852592,423446156,309878771,545362613,744662513,789017500,546225254,526541940,668388104,944806949,997521154,792995613},{612007847,670876552,375997243,109642738,163324340,295375586,710836596,171220932,892933788,621400547,211064538,362528491,353559387,766451846,152134342},{310974891,143521234,784990876,717383708,338925667,548654125,322967727,361593955,248328973,308444226,457184490,349325742,631069775,730239695,216945528},{441060926,7602317,481557442,268591219,201820358,383139956,254532967,539768986,384561029,188278719,478093060,222013035,694249511,370565913,997843399},{142528971,791416077,145505935,631049820,443155235,774472730,919689294,55437521,525887615,402043235,427635069,516692276,837154899,606193787,644870737},{575096662,549509331,121023725,182362547,602786663,221418731,898155828,912994123,578394438,327189256,678279150,844730953,592297178,312155443,418557288},{40890120,726460100,84757132,81055662,748960145,188832107,951728918,478093060,118637455,238918222,554910375,355519277,80902325,908065505,153587359},{360472494,172520715,324917490,132388589,322226693,17573044,911059678,80250943,971544828,86211785,786387405,579793352,553743434,427348954,673008438},{711850678,923295028,836798853,848360043,636870343,737807107,670294266,212883058,525768501,805869435,533412383,391607116,307565799,283987704,314488675}},
{{180722340,858810272,138280973,773110668,143941471,673314819,768000568,407132763,434504326,563929455,730294969,495132235,533552970,382644705,110063484},{101655699,7296509,190254987,649457373,173126472,761920944,666952332,289886438,155123194,602158828,51112650,665785390,243861828,523185236,981193166},{289106224,138633671,305547510,422154475,903969772,982351262,905720614,428326121,837061243,631371846,319505811,125400770,196671351,65880113,501798698},{786922801,386002164,47546300,158110633,498448350,77327896,787593524,953883925,302190606,379554550,379174849,115754222,614258071,71435030,685924325},{982669978,255425026,175486760,926771901,64548357,701529048,792254111,82736446,475382144,456992269,276096529,76430391,250299448,457036900,691847593},{564456191,522880278,291313659,409821524,940635751,426046953,124582772,162969008,266520025,105414076,924742627,252540856,212433253,510582528,704977866},{484560073,598802555,385244984,891920809,890444380,503516287,717671879,260713791,315809118,402390144,683478059,278541606,651698206,792995613,750006001},{413019093,806504939,658496810,431310640,817976558,75121297,136635412,859229862,748960145,881154929,725794932,934392010,449457042,152134342,694683515},{765471016,701529048,391950729,427729584,989672998,710766348,309303138,712769634,49100048,997506403,651235758,687926344,755413584,216945528,155709742},{679239940,628950746,921842434,222877049,233948544,934568961,767785881,221453594,194923845,259542746,973655587,765272405,686245099,997843399,289554058},{713953306,364960095,606988593,534809689,254409929,231742713,757820313,713612201,729684740,617398032,649070512,442255426,90814271,644870737,771189798},{335166436,570550403,652470011,83724782,14486499,446969373,986942368,736968872,293803267,116060408,715948334,657285340,581180249,418557288,44750491},{844975401,185799488,863231746,195482158,420224600,751531575,761249312,627370191,527235007,104888034,7936971,27961546,847494278,153587359,907588180},{105078951,453788116,966103211,708627984,612827939,156174765,545423322,351770085,442255426,829075079,331041287,908065505,204118762,673008438,981862961},{994453187,722952181,836338841,276234283,683031554,740822578,438036180,108203126,892890600,253739672,985624963,572143969,848907509,314488675,520252705}} };
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
//【方法】
// 愚直を書いて集めたデータをもとに変数係数線形漸化式を復元する．
//【使い方】
// 1. vvm tbl = naive() を実装する．
// 2. embed_coefs() を実行する．
// 3. 出力を solve() 内に貼る．
// 4. solve(tbl, n, m) で勝手に tbl[n][0..m] を求めてくれる．
// 愚直解を用意する．再計算がイヤなら埋め込む．
// auto box = naive();
// 愚直解を渡して変数係数線形漸化式の係数を得る．再計算がイヤなら埋め込む．
// 引数：tbl, DEG1_ini, DEG2_ini, TRM3_ini, DEG3_ini, LLL
// auto [coefs1, coefs2, coefs3] = embed_coefs_3D(box, 1, 1, 1, 1, 0);
int n, a1, a2;
cin >> n >> a1 >> a2;
int n0 = a1 - 1, n1 = a2 - a1 - 1, n2 = n - a2 - 1;
// 3 次元数列 box を元に seq = box[n1][n2][0..n3] を計算する．
// 整理すると綺麗な式になるなら FullSimplify[] すると速くなる．
// auto seq = solve_3D(box, n0, n1, n2, coefs1, coefs2, coefs3);
auto seq = solve_3D(box, n0, n1, n2);
//dump(seq);
mint res = seq[n2];
EXIT(res);
}