結果
| 問題 |
No.1684 Find Brackets
|
| ユーザー |
 ecottea
|
| 提出日時 | 2025-05-09 20:14:11 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,047 ms / 2,000 ms |
| コード長 | 24,999 bytes |
| コンパイル時間 | 5,379 ms |
| コンパイル使用メモリ | 287,956 KB |
| 実行使用メモリ | 61,880 KB |
| 最終ジャッジ日時 | 2025-05-09 20:14:31 |
| 合計ジャッジ時間 | 20,438 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 21 |
ソースコード
#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 T 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);
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; }
}
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）
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す
#endif
//【階乗など（法が大きな素数）】
/*
* Factorial_mint(int N) : O(n)
* N まで計算可能として初期化する．
*
* mint fact(int n) : O(1)
* n! を返す．
*
* mint fact_inv(int n) : O(1)
* 1/n! を返す（n が負なら 0 を返す）
*
* mint inv(int n) : O(1)
* 1/n を返す．
*
* mint perm(int n, int r) : O(1)
* 順列の数 nPr を返す．
*
* mint perm_inv(int n, int r) : O(1)
* 順列の数の逆数 1/nPr を返す．
*
* mint bin(int n, int r) : O(1)
* 二項係数 nCr を返す．
*
* mint bin_inv(int n, int r) : O(1)
* 二項係数の逆数 1/nCr を返す．
*
* mint mul(vi rs) : O(|rs|)
* 多項係数 nC[rs] を返す．（n = Σrs）
*
* mint hom(int n, int r) : O(1)
* 重複組合せの数 nHr = n+r-1Cr を返す（0H0 = 1 とする）
*
* mint neg_bin(int n, int r) : O(1)
* 負の二項係数 nCr = (-1)^r -n+r-1Cr を返す（n ≦ 0, r ≧ 0）
*
* mint pochhammer(int x, int n) : O(1)
* ポッホハマー記号 x^(n) を返す（n ≧ 0）
*
* mint pochhammer_inv(int x, int n) : O(1)
* ポッホハマー記号の逆数 1/x^(n) を返す（n ≧ 0）
*/
class Factorial_mint {
int n_max;
// 階乗と階乗の逆数の値を保持するテーブル
vm fac, fac_inv;
public:
// n! までの階乗とその逆数を前計算しておく．O(n)
Factorial_mint(int n) : n_max(n), fac(n + 1), fac_inv(n + 1) {
// verify : https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b
fac[0] = 1;
repi(i, 1, n) fac[i] = fac[i - 1] * i;
fac_inv[n] = fac[n].inv();
repir(i, n - 1, 0) fac_inv[i] = fac_inv[i + 1] * (i + 1);
}
Factorial_mint() : n_max(0) {} // ダミー
// n! を返す．
mint fact(int n) const {
// verify : https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b
Assert(0 <= n && n <= n_max);
return fac[n];
}
// 1/n! を返す（n が負なら 0 を返す）
mint fact_inv(int n) const {
// verify : https://atcoder.jp/contests/abc289/tasks/abc289_h
Assert(n <= n_max);
if (n < 0) return 0;
return fac_inv[n];
}
// 1/n を返す．
mint inv(int n) const {
// verify : https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d
Assert(n > 0);
Assert(n <= n_max);
return fac[n - 1] * fac_inv[n];
}
// 順列の数 nPr を返す．
mint perm(int n, int r) const {
// verify : https://atcoder.jp/contests/abc172/tasks/abc172_e
Assert(n <= n_max);
if (r < 0 || n - r < 0) return 0;
return fac[n] * fac_inv[n - r];
}
// 順列の数 nPr の逆数を返す．
mint perm_inv(int n, int r) const {
// verify : https://yukicoder.me/problems/no/3139
Assert(n <= n_max);
Assert(0 <= r); Assert(r <= n);
return fac_inv[n] * fac[n - r];
}
// 二項係数 nCr を返す．
mint bin(int n, int r) const {
// verify : https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod
Assert(n <= n_max);
if (r < 0 || n - r < 0) return 0;
return fac[n] * fac_inv[r] * fac_inv[n - r];
}
// 二項係数の逆数 1/nCr を返す．
mint bin_inv(int n, int r) const {
// verify : https://www.codechef.com/problems/RANDCOLORING
Assert(n <= n_max);
Assert(r >= 0);
Assert(n - r >= 0);
return fac_inv[n] * fac[r] * fac[n - r];
}
// 多項係数 nC[rs] を返す．
mint mul(const vi& rs) const {
// verify : https://yukicoder.me/problems/no/2141
if (*min_element(all(rs)) < 0) return 0;
int n = accumulate(all(rs), 0);
Assert(n <= n_max);
mint res = fac[n];
repe(r, rs) res *= fac_inv[r];
return res;
}
// 重複組合せの数 nHr = n+r-1Cr を返す（0H0 = 1 とする）
mint hom(int n, int r) {
// verify : https://mojacoder.app/users/riantkb/problems/toj_ex_2
if (n == 0) return (int)(r == 0);
if (r < 0 || n - 1 < 0) return 0;
Assert(n + r - 1 <= n_max);
return fac[n + r - 1] * fac_inv[r] * fac_inv[n - 1];
}
// 負の二項係数 nCr を返す（n ≦ 0, r ≧ 0）
mint neg_bin(int n, int r) {
// verify : https://atcoder.jp/contests/abc345/tasks/abc345_g
if (n == 0) return (int)(r == 0);
Assert(-n + r - 1 <= n_max);
if (r < 0 || -n - 1 < 0) return 0;
return (r & 1 ? -1 : 1) * fac[-n + r - 1] * fac_inv[r] * fac_inv[-n - 1];
}
// ポッホハマー記号 x^(n) を返す（n ≧ 0）
mint pochhammer(int x, int n) {
// verify : https://atcoder.jp/contests/agc070/tasks/agc070_c
int x2 = x + n - 1;
if (x <= 0 && 0 <= x2) return 0;
if (x > 0) {
Assert(x2 <= n_max);
return fac[x2] * fac_inv[x - 1];
}
else {
Assert(-x <= n_max);
return (n & 1 ? -1 : 1) * fac[-x] * fac_inv[-x2 - 1];
}
}
// ポッホハマー記号の逆数 1/x^(n) を返す（n ≧ 0）
mint pochhammer_inv(int x, int n) {
// verify : https://atcoder.jp/contests/agc070/tasks/agc070_c
int x2 = x + n - 1;
Assert(!(x <= 0 && 0 <= x2));
if (x > 0) {
Assert(x2 <= n_max);
return fac_inv[x2] * fac[x - 1];
}
else {
Assert(-x <= n_max);
return (n & 1 ? -1 : 1) * fac_inv[-x] * fac[-x2 - 1];
}
}
};
//【部分集合の全探索（大きさ固定）】O(nCr)
/*
* 大きさ n の全体集合 Ω のうち，大きさ r の部分集合 set⊂Ω を昇順に全探索する．
*
* 制約：r > 0
*/
// verify : https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_11_D
#define repbc(set, n, r) for(int set = (1 << int(r)) - 1, lb, nx; set < (1 << int(n)); lb = set & -set, nx = set + lb, set = (((set & ~nx) / lb) >> 1) | nx)
ll naive(int n, int m) {
if (m == 0) return 2 * n;
ll res = 0;
repbc(set, n, m) {
vi acc(n + 1);
rep(i, n) acc[i + 1] = acc[i] + (getb(set, i) ? 1 : -1);
int acc_min = *min_element(all(acc));
res += (acc[0] - acc_min) + n + (acc[n] - acc_min);
}
return res;
}
void zikken() {
int N = 28;
vvl tbl(N, vl(N));
repi(n, 1, N) repi(m, 1, n) {
tbl[n - 1][m - 1] = naive(n, m);
}
dump_math(tbl);
exit(0);
}
/*
{{2,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},{6,4,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},{14,14,6,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},{26,34,26,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{42,72,72,42,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{62,134,164,134,62,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{86,226,338,338,226,86,14,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{114,354,634,746,634,354,114,16,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{146,524,1100,1520,1520,1100,524,146,18,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{182,742,1792,2872,3292,2872,1792,742,182,20,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{222,1014,2774,5084,6668,6668,5084,2774,1014,222,22,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{266,1346,4118,8518,12676,14260,12676,8518,4118,1346,266,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{314,1744,5904,13626,22778,28784,28784,22778,13626,5904,1744,314,26,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{366,2214,8220,20960,38978,54994,61000,54994,38978,20960,8220,2214,366,28,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{422,2762,11162,31182,63942,99978,122858,122858,99978,63942,31182,11162,2762,422,30,0,0,0,0,0,0,0,0,0,0,0,0,0},{482,3394,14834,45074,101130,173930,235706,258586,235706,173930,101130,45074,14834,3394,482,32,0,0,0,0,0,0,0,0,0,0,0,0},{546,4116,19348,63548,154940,291076,432516,520032,520032,432516,291076,154940,63548,19348,4116,546,34,0,0,0,0,0,0,0,0,0,0,0},{614,4934,24824,87656,230864,470768,762488,1001168,1088684,1001168,762488,470768,230864,87656,24824,4934,614,36,0,0,0,0,0,0,0,0,0,0},{686,5854,31390,118600,335656,738760,1296904,1851172,2187092,2187092,1851172,1296904,738760,335656,118600,31390,5854,686,38,0,0,0,0,0,0,0,0,0},{762,6882,39182,157742,477512,1128680,2136440,3299240,4223020,4558940,4223020,3299240,2136440,1128680,477512,157742,39182,6882,762,40,0,0,0,0,0,0,0,0},{842,8024,48344,206614,666262,1683712,3420160,5687620,7858180,9151472,9151472,7858180,5687620,3420160,1683712,666262,206614,48344,8024,842,42,0,0,0,0,0,0,0},{926,9286,59028,266928,913574,2458502,5336432,9514760,14133660,17715084,19008376,17715084,14133660,9514760,5336432,2458502,913574,266928,59028,9286,926,44,0,0,0,0,0,0},{1014,10674,71394,340586,1233170,3521302,8136022,15490732,24643260,33142036,38134324,38134324,33142036,24643260,15490732,8136022,3521302,1233170,340586,71394,10674,1014,46,0,0,0,0,0},{1106,12194,85610,429690,1641054,4956366,12147638,24607382,41768372,60073428,73980516,78972804,73980516,60073428,41768372,24607382,12147638,4956366,1641054,429690,85610,12194,1106,48,0,0,0,0},{1202,13852,101852,536552,2155752,6866612,17796212,38225962,68990762,105764312,139046232,158361632,158361632,139046232,105764312,68990762,38225962,17796212,6866612,2155752,536552,101852,13852,1202,50,0,0,0},{1302,15654,120304,663704,2798564,9376564,25624224,58185324,111302674,181292594,253725344,307808464,327123864,307808464,253725344,181292594,111302674,58185324,25624224,9376564,2798564,663704,120304,15654,1302,52,0,0},{1406,17606,141158,813908,3593828,12635588,36316388,86934098,175737098,303218738,450470258,580849208,655733528,655733528,580849208,450470258,303218738,175737098,86934098,36316388,12635588,3593828,813908,141158,17606,1406,54,0},{1514,19714,164614,990166,4569196,16821436,50728036,127690636,272044846,495828406,779764786,1066087186,1276699336,1351583656,1276699336,1066087186,779764786,495828406,272044846,127690636,50728036,16821436,4569196,990166,164614,19714,1514,56}};
*/
vvm dp = { {2,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},{6,4,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},{14,14,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{26,34,26,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{42,72,72,42,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{62,134,164,134,62,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{86,226,338,338,226,86,14,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{114,354,634,746,634,354,114,16,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{146,524,1100,1520,1520,1100,524,146,18,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{182,742,1792,2872,3292,2872,1792,742,182,20,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{222,1014,2774,5084,6668,6668,5084,2774,1014,222,22,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{266,1346,4118,8518,12676,14260,12676,8518,4118,1346,266,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{314,1744,5904,13626,22778,28784,28784,22778,13626,5904,1744,314,26,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{366,2214,8220,20960,38978,54994,61000,54994,38978,20960,8220,2214,366,28,0,0,0,0,0,0,0,0,0,0,0,0,0},{422,2762,11162,31182,63942,99978,122858,122858,99978,63942,31182,11162,2762,422,30,0,0,0,0,0,0,0,0,0,0,0,0},{482,3394,14834,45074,101130,173930,235706,258586,235706,173930,101130,45074,14834,3394,482,32,0,0,0,0,0,0,0,0,0,0,0},{546,4116,19348,63548,154940,291076,432516,520032,520032,432516,291076,154940,63548,19348,4116,546,34,0,0,0,0,0,0,0,0,0,0},{614,4934,24824,87656,230864,470768,762488,1001168,1088684,1001168,762488,470768,230864,87656,24824,4934,614,36,0,0,0,0,0,0,0,0,0},{686,5854,31390,118600,335656,738760,1296904,1851172,2187092,2187092,1851172,1296904,738760,335656,118600,31390,5854,686,38,0,0,0,0,0,0,0,0},{762,6882,39182,157742,477512,1128680,2136440,3299240,4223020,4558940,4223020,3299240,2136440,1128680,477512,157742,39182,6882,762,40,0,0,0,0,0,0,0},{842,8024,48344,206614,666262,1683712,3420160,5687620,7858180,9151472,9151472,7858180,5687620,3420160,1683712,666262,206614,48344,8024,842,42,0,0,0,0,0,0},{926,9286,59028,266928,913574,2458502,5336432,9514760,14133660,17715084,19008376,17715084,14133660,9514760,5336432,2458502,913574,266928,59028,9286,926,44,0,0,0,0,0},{1014,10674,71394,340586,1233170,3521302,8136022,15490732,24643260,33142036,38134324,38134324,33142036,24643260,15490732,8136022,3521302,1233170,340586,71394,10674,1014,46,0,0,0,0},{1106,12194,85610,429690,1641054,4956366,12147638,24607382,41768372,60073428,73980516,78972804,73980516,60073428,41768372,24607382,12147638,4956366,1641054,429690,85610,12194,1106,48,0,0,0},{1202,13852,101852,536552,2155752,6866612,17796212,38225962,68990762,105764312,139046232,158361632,158361632,139046232,105764312,68990762,38225962,17796212,6866612,2155752,536552,101852,13852,1202,50,0,0},{1302,15654,120304,663704,2798564,9376564,25624224,58185324,111302674,181292594,253725344,307808464,327123864,307808464,253725344,181292594,111302674,58185324,25624224,9376564,2798564,663704,120304,15654,1302,52,0},{1406,17606,141158,813908,3593828,12635588,36316388,86934098,175737098,303218738,450470258,580849208,655733528,655733528,580849208,450470258,303218738,175737098,86934098,36316388,12635588,3593828,813908,141158,17606,1406,54} };
void zikken2() {
int N = 25;
vvl tbl(N, vl(N));
repi(n, 1, N) repi(m, 1, n) {
tbl[n - 1][m - 1] = naive(n, m);
}
repi(n, 1, N) {
repir(m, n - 1, 1) {
tbl[n - 1][m - 1] += tbl[n - 1][m - 1 + 1];
}
reverse(tbl[n - 1].begin(), tbl[n - 1].begin() + n);
}
dump_math(tbl);
exit(0);
}
/*
{{2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{4,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{6,20,34,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{8,34,68,94,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{10,52,124,196,238,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{12,74,208,372,506,568,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{14,100,326,664,1002,1228,1314,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{16,130,484,1118,1864,2498,2852,2966,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{18,164,688,1788,3308,4828,5928,6452,6598,0,0,0,0,0,0,0,0,0,0,0,0,0},{20,202,944,2736,5608,8900,11772,13564,14306,14488,0,0,0,0,0,0,0,0,0,0,0,0},{22,244,1258,4032,9116,15784,22452,27536,30310,31324,31546,0,0,0,0,0,0,0,0,0,0,0},{24,290,1636,5754,14272,26948,41208,53884,62402,66520,67866,68132,0,0,0,0,0,0,0,0,0,0},{26,340,2084,7988,21614,44392,73176,101960,124738,138364,144268,146012,146326,0,0,0,0,0,0,0,0,0},{28,394,2608,10828,31788,70766,125760,186760,241754,280732,301692,309912,312126,312492,0,0,0,0,0,0,0,0},{30,452,3214,14376,45558,109500,209478,332336,455194,555172,619114,650296,661458,664220,664642,0,0,0,0,0,0,0},{32,514,3908,18742,63816,164946,338876,574582,833168,1068874,1242804,1343934,1389008,1403842,1407236,1407718,0,0,0,0,0,0},{34,580,4696,24044,87592,242532,533608,966124,1486156,2006188,2438704,2729780,2884720,2948268,2967616,2971732,2972278,0,0,0,0,0},{36,650,5584,30408,118064,348928,819696,1582184,2583352,3672036,4673204,5435692,5906460,6137324,6224980,6249804,6254738,6255352,0,0,0,0},{38,724,6578,37968,156568,492224,1230984,2527888,4379060,6566152,8753244,10604416,11901320,12640080,12975736,13094336,13125726,13131580,13132266,0,0,0},{40,802,7684,46866,204608,682120,1810800,3947240,7246480,11469500,16028440,20251460,23550700,25687140,26815820,27293332,27451074,27490256,27497138,27497900,0,0},{42,884,8908,57252,263866,930128,2613840,6034000,11721620,19579800,28731272,37882744,45740924,51428544,54848704,56532416,57198678,57405292,57453636,57461660,57462502,0},{44,970,10256,69284,336212,1249786,3708288,9044720,18559480,32693140,50408224,69416600,87131684,101265344,110780104,116116536,118575038,119488612,119755540,119814568,119823854,119824780}};
*/
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
// zikken();
int n, m;
cin >> n >> m;
// dump(naive(n, m)); dump("=======");
repea(a, dp) a.insert(a.begin(), 0);
dp.insert(dp.begin(), vm());
dumpel(dp);
dp.resize(n + 1);
repi(i, 0, n) dp[i].resize(6);
dp[n][0] = 2 * n;
repi(i, 4, n) {
auto dpsub = [&](const mint& x) { return dp[x.val()][1]; };
auto Power = [&](const mint& x, int n) { mint res = 1; rep(hoge, n) res *= x; return res; };
mint nn = i;
dp[i][1] = ((19 - 14 * nn) * dpsub(-2 + nn) + (-52 + 23 * nn) * dpsub(-1 + nn)) / (-23 + 9 * nn);
}
repi(i, 5, n) {
auto dpsub = [&](const mint& x) { return dp[x.val()][2]; };
auto Power = [&](const mint& x, int n) { mint res = 1; rep(hoge, n) res *= x; return res; };
mint nn = i;
dp[i][2] = (59 * (-5 + nn) * dpsub(-3 + nn) + (1066 - 237 * nn) * dpsub(-2 + nn) + (-1367 + 204 * nn) * dpsub(-1 + nn)) / (-317 + 26 * nn);
}
repi(i, 5, n) {
auto dpsub = [&](const mint& x) { return dp[x.val()][3]; };
auto Power = [&](const mint& x, int n) { mint res = 1; rep(hoge, n) res *= x; return res; };
mint nn = i;
dp[i][3] = (-11 * (-7 + nn) * (-386 + 183 * nn) * dpsub(-3 + nn) + (90470 + 7 * nn * (-4105 + 263 * nn)) * dpsub(-2 + nn) +
(-16366 + nn * (-615 + 421 * nn)) * dpsub(-1 + nn)) / (6302 + nn * (-3269 + 249 * nn));
}
repi(i, 6, n) {
auto dpsub = [&](const mint& x) { return dp[x.val()][4]; };
auto Power = [&](const mint& x, int n) { mint res = 1; rep(hoge, n) res *= x; return res; };
mint nn = i;
dp[i][4] = (-2 * (-10 + nn) * (-979053261 + 330339752 * nn) * dpsub(-4 + nn) +
(63971784060 + nn * (-19509017357 + 1279424125 * nn)) * dpsub(-3 + nn) +
(-47071401348 + 19 * (849814103 - 62751785 * nn) * nn) * dpsub(-2 + nn) +
(26976884064 + nn * (-9995504359 + 753200471 * nn)) * dpsub(-1 + nn)) / (9 * (864944624 + nn * (-290454133 + 19962353 * nn)));
}
repi(i, 7, n) {
auto dpsub = [&](const mint& x) { return dp[x.val()][5]; };
auto Power = [&](const mint& x, int n) { mint res = 1; rep(hoge, n) res *= x; return res; };
mint nn = i;
dp[i][5] = (-2 * (-13 + nn) * (-353690007684 + 87414970319 * nn) * dpsub(-5 + nn) +
(27617778043260 + nn * (-5868151762601 + 277908920579 * nn)) * dpsub(-4 + nn) - 15867104901852 * dpsub(-3 + nn) +
6353608541790 * dpsub(-2 + nn) + 978165705066 * dpsub(-1 + nn) +
nn * ((3257009971893 - 156263571147 * nn) * dpsub(-3 + nn) + (-840460825417 + 15791106145 * nn) * dpsub(-2 + nn) +
(-762378106525 + 61366150597 * nn) * dpsub(-1 + nn))) / (36 * (37092403474 + nn * (-11213145845 + 665907376 * nn)));
}
dp[n].resize(n + 1);
repi(j, 6, n / 2) {
auto dpsub = [&](const mint& x, const mint& y) { return dp[x.val()][y.val()]; };
auto Power = [&](const mint& x, int n) { mint res = 1; rep(hoge, n) res *= x; return res; };
mint nn1 = n;
mint nn2 = j;
dp[n][j] = ((7 + nn1 - 2 * nn2) * (8 + nn1 - 2 * nn2) * (4 + nn1 - nn2) * (5 + nn1 - nn2) * dpsub(nn1, -5 + nn2) -
(4 + nn1 - nn2) * (-62 + nn1 * (107 + 3 * nn1 * (12 + nn1)) + 16 * nn2 - nn1 * (79 + 13 * nn1) * nn2 +
2 * (7 + 8 * nn1) * Power(nn2, 2) - 4 * Power(nn2, 3)) * dpsub(nn1, -4 + nn2) - 1260 * dpsub(nn1, -3 + nn2) -
720 * nn1 * dpsub(nn1, -3 + nn2) - 41 * Power(nn1, 2) * dpsub(nn1, -3 + nn2) + 22 * Power(nn1, 3) * dpsub(nn1, -3 + nn2) +
3 * Power(nn1, 4) * dpsub(nn1, -3 + nn2) + 1380 * nn2 * dpsub(nn1, -3 + nn2) + 560 * nn1 * nn2 * dpsub(nn1, -3 + nn2) -
4 * Power(nn1, 2) * nn2 * dpsub(nn1, -3 + nn2) - 12 * Power(nn1, 3) * nn2 * dpsub(nn1, -3 + nn2) -
596 * Power(nn2, 2) * dpsub(nn1, -3 + nn2) - 138 * nn1 * Power(nn2, 2) * dpsub(nn1, -3 + nn2) +
10 * Power(nn1, 2) * Power(nn2, 2) * dpsub(nn1, -3 + nn2) + 116 * Power(nn2, 3) * dpsub(nn1, -3 + nn2) +
8 * nn1 * Power(nn2, 3) * dpsub(nn1, -3 + nn2) - 8 * Power(nn2, 4) * dpsub(nn1, -3 + nn2) - 240 * dpsub(nn1, -2 + nn2) +
250 * nn1 * dpsub(nn1, -2 + nn2) + 87 * Power(nn1, 2) * dpsub(nn1, -2 + nn2) + 4 * Power(nn1, 3) * dpsub(nn1, -2 + nn2) -
Power(nn1, 4) * dpsub(nn1, -2 + nn2) + 120 * nn2 * dpsub(nn1, -2 + nn2) - 332 * nn1 * nn2 * dpsub(nn1, -2 + nn2) -
72 * Power(nn1, 2) * nn2 * dpsub(nn1, -2 + nn2) + 56 * Power(nn2, 2) * dpsub(nn1, -2 + nn2) +
150 * nn1 * Power(nn2, 2) * dpsub(nn1, -2 + nn2) + 14 * Power(nn1, 2) * Power(nn2, 2) * dpsub(nn1, -2 + nn2) -
44 * Power(nn2, 3) * dpsub(nn1, -2 + nn2) - 24 * nn1 * Power(nn2, 3) * dpsub(nn1, -2 + nn2) +
8 * Power(nn2, 4) * dpsub(nn1, -2 + nn2) + (-1 + nn2) *
(-132 + 2 * nn1 * (-16 + nn1 * (3 + nn1)) + 144 * nn2 + (11 - 7 * nn1) * nn1 * nn2 + 2 * (-23 + 2 * nn1) * Power(nn2, 2) +
4 * Power(nn2, 3)) * dpsub(nn1, -1 + nn2)) / ((2 + nn1 - 2 * nn2) * (3 + nn1 - 2 * nn2) * (-1 + nn2) * nn2);
}
repi(j, n / 2 + 1, n) dp[n][j] = dp[n][n - j];
// dumpel(dp);
mint res = 0;
repi(j, m, n) res += dp[n][j];
// 割り算ちゃんとしてないからさすがにTLEしそう．
EXIT(res);
}