結果
| 問題 | No.1561 connect x connect |
| ユーザー |
 ecottea
|
| 提出日時 | 2023-04-03 00:36:12 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 329 ms / 2,000 ms |
| コード長 | 59,909 bytes |
| コンパイル時間 | 10,627 ms |
| コンパイル使用メモリ | 504,972 KB |
| 実行使用メモリ | 5,536 KB |
| 最終ジャッジ日時 | 2023-10-25 05:16:51 |
| 合計ジャッジ時間 | 14,196 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,348 KB |
| testcase_01 | AC | 2 ms
4,348 KB |
| testcase_02 | AC | 3 ms
4,348 KB |
| testcase_03 | AC | 2 ms
4,348 KB |
| testcase_04 | AC | 2 ms
4,348 KB |
| testcase_05 | AC | 2 ms
4,348 KB |
| testcase_06 | AC | 2 ms
4,348 KB |
| testcase_07 | AC | 2 ms
4,348 KB |
| testcase_08 | AC | 2 ms
4,348 KB |
| testcase_09 | AC | 2 ms
4,348 KB |
| testcase_10 | AC | 2 ms
4,348 KB |
| testcase_11 | AC | 2 ms
4,348 KB |
| testcase_12 | AC | 3 ms
4,348 KB |
| testcase_13 | AC | 3 ms
4,348 KB |
| testcase_14 | AC | 7 ms
4,348 KB |
| testcase_15 | AC | 8 ms
4,348 KB |
| testcase_16 | AC | 11 ms
4,348 KB |
| testcase_17 | AC | 2 ms
4,348 KB |
| testcase_18 | AC | 2 ms
4,348 KB |
| testcase_19 | AC | 50 ms
4,348 KB |
| testcase_20 | AC | 3 ms
4,348 KB |
| testcase_21 | AC | 3 ms
4,348 KB |
| testcase_22 | AC | 4 ms
4,348 KB |
| testcase_23 | AC | 2 ms
4,348 KB |
| testcase_24 | AC | 49 ms
4,348 KB |
| testcase_25 | AC | 2 ms
4,348 KB |
| testcase_26 | AC | 329 ms
5,536 KB |
| testcase_27 | AC | 328 ms
5,536 KB |
| testcase_28 | AC | 317 ms
5,468 KB |
| testcase_29 | AC | 327 ms
5,536 KB |
| testcase_30 | AC | 322 ms
5,500 KB |
| testcase_31 | AC | 2 ms
4,348 KB |
| testcase_32 | AC | 3 ms
4,348 KB |
| testcase_33 | AC | 8 ms
4,348 KB |
| testcase_34 | AC | 50 ms
4,348 KB |
| testcase_35 | AC | 10 ms
4,348 KB |
| testcase_36 | AC | 52 ms
4,348 KB |
| testcase_37 | AC | 317 ms
5,500 KB |
ソースコード
#ifndef HIDDEN_IN_VS // 折りたたみ用
// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS
// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;
// 型名の短縮
using ll = long long; // -2^63 ～ 2^63 = 9 * 10^18（int は -2^31 ～ 2^31 = 2 * 10^9）
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 vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>;
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);
const vi DX = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
const vi DY = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004004004004004LL;
double EPS = 1e-15;
// 入出力高速化
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 < (1 << int(d)); ++set) // d ビット全探索（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define smod(n, m) ((((n) % (m)) + (m)) % (m)) // 非負mod
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
// 汎用関数の定義
template <class T> inline ll pow(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 get(T set, int i) { return (set >> i) & T(1); }
// 演算子オーバーロード
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; }
// 手元環境（Visual Studio）
#ifdef _MSC_VER
#include "local.hpp"
// 提出用（gcc）
#else
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) : -1; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; }
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 gcd __gcd
#define dump(...)
#define dumpel(v)
#define dump_list(v)
#define dump_list2D(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) while (1) cout << "OLE"; }
#endif
#endif // 折りたたみ用
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
using mint = modint1000000007;
//using mint = modint998244353;
//using mint = modint; // mint::set_mod(m);
istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>;
#endif
//【形式的冪級数】
/*
* MFPS() : O(1)
* 零多項式 f = 0 で初期化する．
*
* MFPS(mint c0) : O(1)
* 定数多項式 f = c0 で初期化する．
*
* MFPS(mint c0, int n) : O(n)
* n 次未満の項をもつ定数多項式 f = c0 で初期化する．
*
* MFPS(vm c) : O(n)
* f(z) = c[0] + c[1] z + ... + c[n - 1] z^(n-1) で初期化する．
*
* set_conv(vm(*CONV)(const vm&, const vm&)) : O(1)
* 畳込み用の関数を CONV に設定する．
*
* c + f, f + c : O(1) f + g : O(n)
* f - c : O(1) c - f, f - g, -f : O(n)
* c * f, f * c : O(n) f * g : O(n log n) f * g_sp : O(n k)（k : g の項数）
* f / c : O(n) f / g : O(n log n) f / g_sp : O(n k)（k : g の項数）
* 形式的冪級数としての和，差，積，商の結果を返す．
* g_sp はスパース多項式であり，{次数, 係数} の次数昇順の組の vector で表す．
* 制約 : 商では g(0) != 0
*
* MFPS f.inv(int d) : O(n log n)
* 1 / f mod z^d を返す．
* 制約 : f(0) != 0
*
* MFPS f.quotient(MFPS g) : O(n log n)
* MFPS f.reminder(MFPS g) : O(n log n)
* pair<MFPS, MFPS> f.quotient_remainder(MFPS g) : O(n log n)
* 多項式としての f を g で割った商，余り，商と余りの組を返す．
* 制約 : g の最高次の係数は 0 でない
*
* int f.deg(), int f.size() : O(1)
* 多項式 f の次数[項数]を返す．
*
* MFPS::monomial(int d) : O(d)
* 単項式 z^d を返す．
*
* mint f.assign(mint c) : O(n)
* 多項式 f の不定元 z に c を代入した値を返す．
*
* f.resize(int d) : O(1)
* mod z^d をとる．
*
* f.resize() : O(n)
* 不要な高次の項を削る．
*
* f >> d, f << d : O(n)
* 係数列を d だけ右[左]シフトした多項式を返す．
* （右シフトは z^d の乗算，左シフトは z^d で割った商と等価）
*
* MFPS power_mod(MFPS f, ll d, MFPS g) : O(m log m log d) （m = deg g）
* f(z)^d mod g(z) を返す．
*/
struct MFPS {
using SMFPS = vector<pair<int, mint>>;
int n; // 係数の個数（次数 + 1）
vm c; // 係数列
inline static vm(*CONV)(const vm&, const vm&) = convolution; // 畳込み用の関数
// コンストラクタ（0，定数，係数列で初期化）
MFPS() : n(0) {}
MFPS(const mint& c0) : n(1), c({ c0 }) {}
MFPS(const int& c0) : n(1), c({ mint(c0) }) {}
MFPS(const mint& c0, int d) : n(d), c(n) { c[0] = c0; }
MFPS(const int& c0, int d) : n(d), c(n) { c[0] = c0; }
MFPS(const vm& c_) : n(sz(c_)), c(c_) {}
MFPS(const vi& c_) : n(sz(c_)), c(n) { rep(i, n) c[i] = c_[i]; }
// 代入
MFPS(const MFPS& f) = default;
MFPS& operator=(const MFPS& f) = default;
MFPS& operator=(const mint& c0) { n = 1; c = { c0 }; return *this; }
// 比較
bool operator==(const MFPS& g) const { return c == g.c; }
bool operator!=(const MFPS& g) const { return c != g.c; }
// アクセス
mint const& operator[](int i) const { return c[i]; }
mint& operator[](int i) { return c[i]; }
// 次数
int deg() const { return n - 1; }
int size() const { return n; }
static void set_conv(vm(*CONV_)(const vm&, const vm&)) {
// verify : https://atcoder.jp/contests/tdpc/tasks/tdpc_fibonacci
CONV = CONV_;
}
// 加算
MFPS& operator+=(const MFPS& g) {
if (n >= g.n) rep(i, g.n) c[i] += g.c[i];
else {
rep(i, n) c[i] += g.c[i];
repi(i, n, g.n - 1) c.push_back(g.c[i]);
n = g.n;
}
return *this;
}
MFPS operator+(const MFPS& g) const { return MFPS(*this) += g; }
// 定数加算
MFPS& operator+=(const mint& sc) {
if (n == 0) { n = 1; c = { sc }; }
else { c[0] += sc; }
return *this;
}
MFPS operator+(const mint& sc) const { return MFPS(*this) += sc; }
friend MFPS operator+(const mint& sc, const MFPS& f) { return f + sc; }
MFPS& operator+=(const int& sc) { *this += mint(sc); return *this; }
MFPS operator+(const int& sc) const { return MFPS(*this) += sc; }
friend MFPS operator+(const int& sc, const MFPS& f) { return f + sc; }
// 減算
MFPS& operator-=(const MFPS& g) {
if (n >= g.n) rep(i, g.n) c[i] -= g.c[i];
else {
rep(i, n) c[i] -= g.c[i];
repi(i, n, g.n - 1) c.push_back(-g.c[i]);
n = g.n;
}
return *this;
}
MFPS operator-(const MFPS& g) const { return MFPS(*this) -= g; }
// 定数減算
MFPS& operator-=(const mint& sc) { *this += -sc; return *this; }
MFPS operator-(const mint& sc) const { return MFPS(*this) -= sc; }
friend MFPS operator-(const mint& sc, const MFPS& f) { return -(f - sc); }
MFPS& operator-=(const int& sc) { *this += -sc; return *this; }
MFPS operator-(const int& sc) const { return MFPS(*this) -= sc; }
friend MFPS operator-(const int& sc, const MFPS& f) { return -(f - sc); }
// 加法逆元
MFPS operator-() const { return MFPS(*this) *= -1; }
// 定数倍
MFPS& operator*=(const mint& sc) { rep(i, n) c[i] *= sc; return *this; }
MFPS operator*(const mint& sc) const { return MFPS(*this) *= sc; }
friend MFPS operator*(const mint& sc, const MFPS& f) { return f * sc; }
MFPS& operator*=(const int& sc) { *this *= mint(sc); return *this; }
MFPS operator*(const int& sc) const { return MFPS(*this) *= sc; }
friend MFPS operator*(const int& sc, const MFPS& f) { return f * sc; }
// 右からの定数除算
MFPS& operator/=(const mint& sc) { *this *= sc.inv(); return *this; }
MFPS operator/(const mint& sc) const { return MFPS(*this) /= sc; }
MFPS& operator/=(const int& sc) { *this /= mint(sc); return *this; }
MFPS operator/(const int& sc) const { return MFPS(*this) /= sc; }
// 積
MFPS& operator*=(const MFPS& g) { c = CONV(c, g.c); n = sz(c); return *this; }
MFPS operator*(const MFPS& g) const { return MFPS(*this) *= g; }
// 除算
MFPS inv(int d) const {
// 参考：https://nyaannyaan.github.io/library/fps/formal-power-series.hpp
// verify : https://judge.yosupo.jp/problem/inv_of_formal_power_series
//【方法】
// 1 / f mod x^d を求めることは，
// f g = 1 (mod x^d)
// なる g を求めることである．
// この d の部分を 1, 2, 4, ..., 2^i と倍々にして求めていく．
//
// d = 1 のときについては
// g = 1 / f[0] (mod x^1)
// である．
//
// 次に，
// g = h (mod x^k)
// が求まっているとして
// g mod x^(2 k)
// を求める．最初の式を変形していくことで
// g - h = 0 (mod x^k)
// ⇒ (g - h)^2 = 0 (mod x^(2 k))
// ⇔ g^2 - 2 g h + h^2 = 0 (mod x^(2 k))
// ⇒ f g^2 - 2 f g h + f h^2 = 0 (mod x^(2 k))
// ⇔ g - 2 h + f h^2 = 0 (mod x^(2 k)) (f g = 1 (mod x^d) より)
// ⇔ g = (2 - f h) h (mod x^(2 k))
// を得る．
//
// この手順を d <= 2^i となる i まで繰り返し，d 次以上の項を削除すればよい．
Assert(c[0] != 0);
MFPS g(c[0].inv());
for (int k = 1; k < d; k *= 2) {
g = (2 - *this * g) * g;
g.resize(2 * k);
}
return g.resize(d);
}
MFPS& operator/=(const MFPS& g) { return *this *= g.inv(max(n, g.n)); }
MFPS operator/(const MFPS& g) const { return MFPS(*this) /= g; }
// 余り付き除算
MFPS quotient(const MFPS& g) const {
// 参考 : https://nyaannyaan.github.io/library/fps/formal-power-series.hpp
// verify : https://judge.yosupo.jp/problem/division_of_polynomials
//【方法】
// f(x) = g(x) q(x) + r(x) となる q(x) を求める．
// f の次数は n - 1, g の次数は m - 1 とする．(n >= m)
// 従って q の次数は n - m，r の次数は m - 2 となる．
//
// f^R で f の係数列を逆順にした多項式を表す．すなわち
// f^R(x) := f(1/x) x^(n-1)
// である．他の多項式も同様とする．
//
// 最初の式で x → 1/x と置き換えると，
// f(1/x) = g(1/x) q(1/x) + r(1/x)
// ⇔ f(1/x) x^(n-1) = g(1/x) q(1/x) x^(n-1) + r(1/x) x^(n-1)
// ⇔ f(1/x) x^(n-1) = g(1/x) x^(m-1) q(1/x) x^(n-m) + r(1/x) x^(m-2) x^(n-m+1)
// ⇔ f^R(x) = g^R(x) q^R(x) + r^R(x) x^(n-m+1)
// ⇒ f^R(x) = g^R(x) q^R(x) (mod x^(n-m+1))
// ⇒ q^R(x) = f^R(x) / g^R(x) (mod x^(n-m+1))
// を得る．
//
// これで q を mod x^(n-m+1) で正しく求めることができることになるが，
// q の次数は n - m であったから，q 自身を正しく求めることができた．
if (n < g.n) return MFPS();
return ((this->rev() / g.rev()).resize(n - g.n + 1)).rev();
}
MFPS reminder(const MFPS& g) const {
// verify : https://judge.yosupo.jp/problem/division_of_polynomials
return (*this - this->quotient(g) * g).resize(g.n - 1);
}
pair<MFPS, MFPS> quotient_remainder(const MFPS& g) const {
// verify : https://judge.yosupo.jp/problem/division_of_polynomials
pair<MFPS, MFPS> res;
res.first = this->quotient(g);
res.second = (*this - res.first * g).resize(g.n - 1);
return res;
}
// スパース積
MFPS& operator*=(const SMFPS& g) {
// g の定数項だけ例外処理
auto it0 = g.begin();
mint g0 = 0;
if (it0->first == 0) {
g0 = it0->second;
it0++;
}
// 後ろからインライン配る DP
repir(i, n - 1, 0) {
// 上位項に係数倍して配っていく．
for (auto it = it0; it != g.end(); it++) {
int j; mint gj;
tie(j, gj) = *it;
if (i + j >= n) break;
c[i + j] += c[i] * gj;
}
// 定数項は最後に配るか消去しないといけない．
c[i] *= g0;
}
return *this;
}
MFPS operator*(const SMFPS& g) const { return MFPS(*this) *= g; }
// スパース商
MFPS& operator/=(const SMFPS& g) {
// g の定数項だけ例外処理
auto it0 = g.begin();
Assert(it0->first == 0 && it0->second != 0);
mint g0_inv = it0->second.inv();
it0++;
// 前からインライン配る DP（後ろに累積効果あり）
rep(i, n) {
// 定数項は最初に配らないといけない．
c[i] *= g0_inv;
// 上位項に係数倍して配っていく．
for (auto it = it0; it != g.end(); it++) {
int j; mint gj;
tie(j, gj) = *it;
if (i + j >= n) break;
c[i + j] -= c[i] * gj;
}
}
return *this;
}
MFPS operator/(const SMFPS& g) const { return MFPS(*this) /= g; }
// 係数反転
MFPS rev() const { MFPS h = *this; reverse(all(h.c)); return h; }
// 単項式
static MFPS monomial(int d) {
MFPS mono(0, d + 1);
mono[d] = 1;
return mono;
}
// 不要な高次項の除去
MFPS& resize() {
// 最高次の係数が非 0 になるまで削る．
while (n > 0 && c[n - 1] == 0) {
c.pop_back();
n--;
}
return *this;
}
// x^d 以上の項を除去する．
MFPS& resize(int d) {
n = d;
c.resize(d);
return *this;
}
// 不定元への代入
mint assign(const mint& x) const {
mint val = 0;
repir(i, n - 1, 0) val = val * x + c[i];
return val;
}
// 係数のシフト
MFPS& operator>>=(int d) {
n += d;
c.insert(c.begin(), d, 0);
return *this;
}
MFPS& operator<<=(int d) {
n -= d;
if (n <= 0) { c.clear(); n = 0; }
else c.erase(c.begin(), c.begin() + d);
return *this;
}
MFPS operator>>(int d) const { return MFPS(*this) >>= d; }
MFPS operator<<(int d) const { return MFPS(*this) <<= d; }
// 累乗の剰余
friend MFPS power_mod(const MFPS& f, ll d, const MFPS& g) {
MFPS res(1), pow2(f);
while (d > 0) {
if (d & 1LL) res = (res * pow2).reminder(g);
pow2 = (pow2 * pow2).reminder(g);
d /= 2;
}
return res;
}
#ifdef _MSC_VER
friend ostream& operator<<(ostream& os, const MFPS& f) {
if (f.n == 0) os << 0;
else {
rep(i, f.n) {
os << f[i].val() << "z^" << i;
if (i < f.n - 1) os << " + ";
}
}
return os;
}
#endif
};
//【畳込み（素朴）】O(n m)
/*
* a[0..n) と b[0..m) を畳み込んだ数列 c[0..n+m-1) を返す．
* すなわち c[k] = Σ_(i+j=k) a[i] b[j] である．
*/
template <class T>
vector<T> naive_convolution(const vector<T>& a, const vector<T>& b) {
// verify : https://atcoder.jp/contests/abc214/tasks/abc214_g
int n = sz(a), m = sz(b);
if (n == 0 || m == 0) return vector<T>();
// c[k] = Σ_(i+j=k) a[i] b[j]
vector<T> c(n + m - 1);
rep(i, n) rep(j, m) c[i + j] += a[i] * b[j];
return c;
}
vvm as{
{},
{0, 1, 3},
{0, 3, 13, 40},
{0, 6, 40, 218, 1126, 5726, 28992, 146642},
{0, 10, 108, 1126, 11506, 116166, 1168586, 11749134, 118127408, 187692415, 941503421, 64334502, 171422003, 349404639},
{0, 15, 275, 5726, 116166, 2301877, 45280509, 889477656, 470102989, 131617800, 543346538, 672693081, 528691884, 433100319, 259856352, 631703746, 121492784, 65000963, 67868821, 431503520, 556143263, 898859209, 822402657, 746831347, 942022314, 42461886, 245383965, 159194955, 442319965, 719053964, 735342087, 986228635, 385914410},
{0, 21, 681, 28992, 1168586, 45280509, 732082734, 37461992, 885687205, 403247903, 630794366, 96311199, 188560385, 132214957, 81864959, 656832813, 129969437, 337127917, 885747691, 994734031, 901081506, 113735510, 330166803, 692897482, 221245902, 823578678, 149151767, 513212823, 565413378, 343413792, 552163984, 401017125, 775469314, 768705741, 822998669, 524634565, 141276343, 644398112, 617812249, 791340223, 983870515, 203398182, 625614815, 683890375, 368195928, 142285464, 986226417, 160965035, 405204827, 206471233, 652493150, 587867820, 808610901, 707659600, 22802536, 445444835, 187616183, 160982744, 457176050, 436730256, 169883893, 240716120, 405440669, 340484060, 656210817, 36771327, 96126498, 306426249, 814430155, 444930212, 988328253},
{0, 28, 1664, 146642, 11749134, 889477656, 37461992, 949940562, 34890374, 408395779, 465431123, 169444072, 476095424, 659247954, 873440607, 926228358, 615656154, 946323264, 52968124, 753942504, 466886220, 131497623, 574943442, 651491966, 558045773, 251030380, 281770571, 626734327, 538734009, 338782739, 544266404, 882070771, 638524752, 866251039, 377115307, 677270990, 923683803, 407681394, 135644897, 799433050, 734586418, 252356851, 562319011, 202766611, 459305661, 237631148, 937873188, 999735041, 471421437, 196454674, 548587822, 155433694, 513218158, 425727801, 201766011, 618282733, 853358524, 794224019, 317787454, 420202005, 208101995, 561508157, 165138107, 680690785, 440574802, 642204069, 1519935, 740668820, 993620892, 358321040, 609591537, 544950607, 452208170, 885834624, 821590676, 398458087, 516061104, 713420418, 988022777, 345184826, 285034175, 821685364, 13669476, 704448103, 129864472, 272789356, 791468167, 22642555, 191074948, 725893030, 621310461, 91319075, 716141215, 100651620, 124026881, 366140815, 685675711, 544588613, 31892809, 733368799, 814661720, 416829950, 25354705, 920576064, 404858750, 224503153, 408647840, 32879424, 449601451, 954308700, 384324116, 674296838, 792515237, 188224955, 323348585, 972509240, 558237931, 478379644, 769454589, 5532215, 665030504, 378063244, 50177022, 152536855, 592606999, 936002695, 561844587, 98320627, 393845743, 234288387, 975460550, 94761064, 230083310, 437478027, 493404365, 809166706, 952865395, 30537948, 269093029, 454344596, 528546169, 743583991, 647074729, 593751773, 863574928, 753557944, 354148307, 464934709, 275033859, 450276861, 375178856, 24286587, 880771043, 120621725, 710396662, 135056587, 742687865, 845401042, 8181486, 277891374, 585736419, 570298110, 955283694, 601817563, 141857657, 613931527, 134904117, 127307580, 914760872, 56527073, 515151064, 85256390, 867641311, 644658123, 516456196, 546485053, 695768127, 950249035, 737354235, 328196921},
{0, 36, 4040, 741556, 118127408, 470102989, 885687205, 34890374, 247777016, 233426110, 328755371, 705627253, 787442872, 382905968, 14599213, 54410761, 601006292, 612557411, 15449456, 990194963, 286282085, 699722725, 781620769, 840139026, 489073872, 334785849, 435236311, 109774734, 741619354, 198733961, 979223831, 316303898, 39151097, 758722723, 846456337, 302710767, 751509519, 910422866, 269441528, 739223079, 47041872, 144990978, 835832181, 94144832, 432122371, 718847361, 143249505, 202420879, 524474077, 175432350, 259981775, 949834434, 650788361, 314338901, 308488393, 925015945, 735629952, 55340122, 870087004, 914406437, 652461932, 824517283, 13384791, 734924498, 195917202, 347913012, 345009223, 72962601, 728865665, 529666843, 443583543, 797807890, 499559112, 582526183, 750449603, 794171249, 339435367, 795879914, 610395113, 651525515, 665256279, 771083632, 124044838, 103256298, 555278857, 168723782, 37135886, 926137424, 193565944, 44104251, 848927128, 311714530, 740363205, 103826476, 426742610, 675142274, 731839743, 444416323, 663478468, 724122696, 351972777, 394976529, 438819547, 910482232, 104665901, 409225876, 167205682, 514913255, 760105145, 29299318, 710711305, 114816263, 854763814, 393789740, 110116602, 971095517, 965304627, 656067527, 345333181, 54369787, 393350947, 645767328, 278297447, 584309442, 643959646, 760481447, 306899117, 556007296, 90782544, 501999191, 487093902, 851119019, 214855164, 290938704, 483935411, 931413698, 87706720, 543982301, 557974404, 993894344, 617966931, 450284946, 530064541, 635450110, 955879320, 855098870, 534537883, 745899211, 102957101, 662330955, 760521286, 880202513, 410332359, 896841550, 21942388, 327590993, 607470931, 510274101, 755158989, 271684724, 681115728, 979634385, 116288824, 441075062, 869557219, 498624604, 668265455, 563569496, 411144207, 372553915, 26571455, 299681786, 483501145, 332251237, 514296631, 262088005, 767350800, 242709545, 312245270, 625558060, 630739736, 166453361, 987400268, 534085288, 177342293, 635886216, 360697926, 830064107, 142999667, 796390630, 541632626, 524331979, 832128250, 56784302, 599770934, 420185002, 36118708, 960687380, 886180310, 494123322, 256629996, 167297430, 422622751, 387880447, 805197257, 990906673, 197392117, 409215677, 751867399, 114891717, 20016317, 539423303, 506437722, 420323843, 17970683, 326175155, 607163024, 810675077, 843118080, 586603097, 332437402, 683685949, 604167445, 591515392, 281318475, 78155302, 77262870, 295568742, 84378564, 642943804, 12418388, 229594263, 734305604, 17384828, 186823879, 593406287, 961690928, 25278271, 599757507, 378599083, 885999372, 931931154, 847818732, 310703306, 179718037, 657210250, 145528035, 460498835, 941558183, 335135033, 141616629, 159440568, 260876848, 890714211, 188331960, 684788951, 962770200, 647749365, 692000110, 84789890, 537064226, 34450693, 41361159, 550194872, 245249510, 900342927, 708273455, 11582750, 128969774, 512056024, 55621840, 349004103, 637116327, 221258619, 579454604, 113893155, 576214565, 70474670, 23918406, 481813326, 650352628, 246808992, 284149773, 322921320, 932867440, 994253316, 940618752, 728504628, 428989277, 122474883, 119546567, 24132989, 106306057, 431011676, 611024275, 216092722, 58878209, 120907053, 721629563, 912245906, 362994491, 77928369, 598179975, 862251408, 302060801, 740845851, 459478020, 470575531, 272055896, 271404799, 997912850, 546477555, 102801686, 821058456, 253389281, 766070116, 630671870, 387593406, 363890599, 503970373, 198459011, 993364983, 210948547, 542855600, 819226189, 105570790, 913838629, 104902492, 762607730, 954174415, 72362182, 262189042, 660554698, 644882931, 306650491, 22189921, 453123535, 325669077, 343206525, 974951457, 351413353, 739439727, 691749300, 370158155, 944047087, 188614448, 382554560, 385741341, 62378861, 740868823, 256532720, 721260792, 546722312, 476298563, 606762613, 98776597, 898445055, 605244416, 333859175, 433695415, 401161555, 572855900, 243667256, 85343275, 675159111, 922771403, 996753883, 954048792, 469148681, 19943310, 296231983, 99393046, 204271242, 312577414, 956614050, 159362747, 723539464, 111719269, 894138283, 588450712, 602782641, 981925081, 900433722, 180543976, 267328359, 522848269, 4196876, 67000221, 107779275, 321728788, 528597009, 269434052, 964941752, 949825535, 975030569, 458728260, 549511657, 418171228, 245570031, 648210002, 972434486, 581872841, 635344873, 319802131, 678265430, 806155028, 954458488, 526854316, 847377932, 635338258, 992797405, 996032138, 354562941, 45336905, 183006406, 369367986, 247817599, 491651791, 494803388, 962480389, 263666033, 589248787, 333002562, 984917436, 533517314, 834849849, 760791455, 813814450, 264438765, 491534108, 918145304, 179243081, 160538845, 82373668, 881806227, 278695929},
{0, 45, 9779, 3749816, 187692415, 131617800, 403247903, 408395779, 233426110, 197302784, 177620321, 206888828, 835061252, 770003207, 167817536, 517820843, 580617827, 469175694, 251779825, 370582103, 72645164, 713328911, 277616510, 902795788, 659852725, 220506451, 987735057, 337008278, 326694483, 929531709, 623473947, 796684890, 777051644, 795130911, 868689620, 888962474, 15266105, 133906102, 896971307, 432781360, 609904712, 139195228, 582320632, 810000435, 144947710, 694533822, 353828777, 974567746, 545012102, 655590198, 684583110, 709008352, 516538184, 177659042, 730381723, 46966182, 70580724, 546296538, 649380101, 839329069, 521579662, 795443379, 918648017, 416884199, 467381920, 180180330, 922394205, 388926319, 338398209, 519862997, 15436054, 832899909, 25205988, 638023458, 397967187, 958525485, 625245409, 761065828, 308642848, 984865575, 166574801, 351074508, 483949359, 826042702, 587151802, 332893090, 23588721, 198575871, 217064634, 935342647, 875830166, 870762060, 431430866, 714037905, 451514552, 118685251, 876908840, 648215587, 848279668, 60298648, 631459253, 423970402, 946540283, 520092027, 98956341, 792001638, 336970096, 931916670, 592163792, 698538791, 255778677, 599081543, 736931826, 498542055, 487642144, 167722474, 425497074, 479036070, 196741185, 39983686, 490171826, 41410688, 950392180, 499418290, 916512858, 995578975, 364239372, 287759310, 305160181, 776807436, 795631950, 394372202, 993536736, 574952319, 609892554, 374430406, 859025147, 436507546, 532241817, 70196027, 667557733, 86629981, 53437441, 215255354, 775586987, 386301783, 329730035, 202594580, 163573385, 90440286, 830055244, 592282175, 146234819, 713607860, 431108208, 391672172, 89707230, 227887893, 635772628, 670074546, 823064293, 429723599, 720075550, 708101376, 728992627, 35839866, 649628048, 777233024, 769395244, 273231976, 452388241, 103609465, 50984607, 571111271, 37433616, 645071594, 241717405, 852257157, 792730997, 762093846, 260970344, 710690387, 581362111, 325183396, 887018246, 894572200, 248056865, 450822007, 28780679, 485097554, 610718927, 844021940, 806875641, 356112859, 159635847, 788536148, 115844061, 32006334, 343606685, 949709181, 501111333, 368083991, 85114366, 231716730, 758617505, 42613424, 792424028, 406591750, 7556235, 372313392, 875852936, 303229657, 493990389, 413068577, 970321428, 914931582, 883280547, 348694252, 48829705, 693879473, 956820845, 494398843, 524838672, 55642290, 291803820, 838072276, 937627886, 352806075, 872719356, 645619108, 203657091, 833772501, 188791198, 15808272, 336497713, 294256664, 801099446, 152749995, 41154832, 192492036, 312034558, 714016971, 939095632, 362217612, 344871905, 183574935, 889188174, 138994256, 960429161, 296389559, 883734447, 484177868, 83759713, 357767259, 405799384, 404997964, 179592455, 903922102, 309177362, 762328559, 846181321, 186860329, 535482051, 303516149, 218656364, 107450950, 239712834, 878534309, 957325925, 369018716, 743188094, 890784475, 179418699, 403243176, 82350077, 760467414, 628649939, 536068242, 546840675, 460160401, 131727617, 556807821, 103868149, 100658424, 320228785, 310512098, 723638547, 644759206, 54096166, 438468025, 280923557, 715718353, 545633130, 123399383, 171267284, 991718619, 983352761, 402614189, 319762846, 922715169, 183148106, 404824713, 482568353, 237420087, 669034731, 275370689, 906758281, 912995718, 736734514, 669078916, 551700747, 844999682, 490707946, 397056376, 72201274, 440950741, 308110319, 99342341, 252577468, 439457763, 862615164, 97430404, 650977533, 227567872, 732837766, 486412310, 424158571, 314727501, 706889056, 657623511, 936876993, 355562470, 9669720, 793140369, 959968300, 899351234, 219020216, 880286167, 595856391, 493610283, 799709671, 824990610, 720595839, 329639104, 976749337, 936889221, 809494863, 315709609, 237042146, 110330913, 567862810, 101728268, 746956576, 529866255, 586725298, 648040801, 779748452, 153236583, 914584631, 749408847, 513718701, 14088744, 993137657, 564190068, 564615128, 218058108, 134675641, 474742395, 687879968, 690548088, 277156362, 833518401, 580665444, 577772528, 19376544, 299323127, 895099027, 299338547, 839803398, 687138570, 578794727, 71021961, 41918341, 510329763, 609712540, 451003507, 709704951, 186996194, 578245109, 487769767, 658075788, 864769755, 506366568, 233278984, 86797707, 695583509, 153704084, 307322932, 831266923, 199868472, 103620682, 993020713, 659107946, 396528525, 448813397, 73914984, 907386095, 831778457, 594736347, 150616395, 988883526, 366215643, 167086401, 868932945, 313717943, 593312471, 235565012, 521329248, 311252446, 123949902, 964499849, 144982401, 326364967, 391588166, 501164095, 279706676, 683502822, 592927881, 202357005, 297878695, 111559939, 437962853, 837545570, 371947446, 187758155, 101943565, 305769633, 487510260, 916387514, 682044268, 61059324, 657929288, 460684128, 163896142, 161536407, 538311886, 723564214, 36418739, 327436336, 989827281, 124248645, 832708688, 882308790, 710452531, 77716353, 875129876, 836074411, 531835865, 56875321, 833407105, 423331035, 393581722, 167353704, 46338145, 795984501, 429448793, 921170554, 895713357, 399606530, 448677100, 376663936, 565811400, 301582936, 103096130, 89229646, 456280484, 935984940, 257863967, 62176804, 520077003, 989724020, 230216016, 198426323, 232816551, 723398169, 947598119, 145563483, 543560195, 769283254, 687695853, 412141785, 458246892, 322562821, 870174788, 792046447, 992281653, 261650102, 321433331, 28258915, 361339155, 916537223, 304030644, 26483722, 311683688, 962388783, 635976431, 109322303, 111089464, 562711339, 932659823, 884184806, 961770497, 482763443, 787907009, 283606372, 844167426, 96801505, 102993913, 616787769, 332259272, 90020691, 33473958, 108789187, 901500422, 168357636, 853210301, 871337077, 376008840, 609311701, 33409148, 458480523, 530786778, 390698056, 481382022, 680007463, 849208790, 270019810, 368593263, 287960378, 683678741, 840373286, 472091096, 256821798, 909688373, 636672904, 857109891, 992260814, 638259714, 682582093, 715207690, 600484323, 181860536, 177868141, 849248564, 743213709, 255749170, 601589780, 577202203, 715681221, 735331176, 522995960, 337047396, 380280967, 562020808, 449068543, 963757501, 321956499, 151307217, 161277903, 285233282, 762020021, 339297753, 69679348, 52568303, 535629098, 658030018, 319086680, 600634301, 532594728, 293331051, 603165887, 881090116, 441710021, 197876329, 311209998, 65489057, 438038471, 846586492, 841740111, 900892505, 272268279, 272662986, 89882804, 789135775, 548746487, 93712454, 214835785, 687205843, 809953436, 716639879, 931867150, 5763196, 404820388, 529438877, 222826259, 393767310, 372063277, 755012934, 553961581, 34305285, 137826363, 970617902, 758748623, 22630688, 297099624, 233382191, 919549105, 715661682, 204181124, 621028315, 733111353, 820512193, 577134999, 902996456, 829943695, 846032894, 905693877, 542196551, 252622955, 523732069, 530997965, 533006837, 460888302, 533952669, 844001205, 812367056, 483211338, 158530789, 288773918, 681553155, 968699783, 254686618, 449601998, 599196037, 225007854, 290070160, 539848030, 608861062, 188322344, 747926660, 538066172, 847178687, 798739308, 292443380, 645523492, 583709863, 519984309, 947227788, 785996221, 849492107, 217296632, 379082083, 328454321, 948218307, 458921548, 733036260, 335345610, 773876458, 744463437, 69765238, 106787889, 312188870, 578318834, 7590839, 644251670, 957688430, 335704885, 472634567, 890314526, 887231598, 869685716, 675313178, 908538033, 362098899, 320019526, 244292819, 322269049, 505039770, 483852205, 866472202, 694039567, 823738103, 892325140, 758360001, 346368562, 815348254, 412182503, 471602176, 990001493, 666290216, 161636116, 879511684, 412410210, 446019037, 337121630, 658855385, 784637957, 536675583, 404218240, 960104489, 897138435, 48992282, 548012990, 560174715, 792156454, 160189169, 705905872, 573054279, 928960434, 598430005, 723118328, 3133966, 709956394, 400173006, 843883821, 846982537, 379029168, 361068204, 661888589, 887835679, 493479920, 976133608, 354917572, 765784969, 49078976, 364396665, 502948009, 205972104, 807960031, 802286021, 744327814, 245246294, 420470862, 538828146, 696329703, 411129575, 588274570, 6230560, 547505555, 473360733, 576825268, 869928171, 485124875, 32250130, 382711654, 49947367, 690021132, 761491956, 113839876, 634613886, 973389949, 360297061, 350465803, 385111971, 501526753, 394165342, 117902532, 47188185, 669058037, 586179392, 803534253, 9867730, 117081149, 270343570, 869732012, 535560128, 74135321, 913166862, 745264069, 367865464, 623137053, 135895289, 799585395, 704614475, 888437551, 472048245, 210649737, 887519734, 367380507, 467654308, 310951744, 120246371, 1570185, 489874614, 177001364, 639465634, 752300677, 618186089, 125694494, 282846280, 736316609, 953882934, 653497932, 841032400, 979929908, 640731760, 744566282, 956866912, 308789171, 978715397, 648405630, 702106874, 252210450, 37223998, 173800106, 569247455, 870763443, 145425498, 15568087, 948078131, 543632996, 464071584, 555186162, 273468192, 844935944, 319095366, 541561522, 462755462, 976898547, 38432185, 745007341, 431518992, 996017081, 641720868, 979768983, 850953140, 572191500, 305562385, 828023713, 101969831, 319513329, 411569368, 498489858, 687104004, 861506575, 386766011, 47630047, 485950686, 906252626, 435904945, 523398217, 237981274, 184197706, 269135307, 723734629, 996762583, 961708129, 184077468, 987996423, 232884778, 412092659, 38185479, 920544354, 863648751, 226193943, 388570440, 67028234, 139276129, 987378193, 100903448, 903580344, 405505214, 867338867, 333622878, 921218665, 511487222, 463201346, 414182967, 124574190, 125984615, 331268678, 712901251, 926814813, 792501262, 571854656, 980486453, 67546855, 150063837, 986275190, 522883996, 773384884, 81195741, 381162217, 512867735, 787522767, 774407258, 380624609, 500979859, 425339121, 963880441, 911568272, 792258594, 350130673, 602869571, 264295247, 559699881, 354311181, 316717483, 974583423, 385148768, 775793636, 276045306, 192338240, 677282938, 975826894, 376504882, 438875821, 650005503, 18308145, 573861618, 505201938, 646594656, 659950897, 130894025, 249286645, 298317355, 654311532, 836465450, 865286055, 895177950, 246676014, 195480007, 816931196, 479506395, 881134448, 708030910, 402627578, 94318479, 239737460, 50326524, 124781860, 692461839, 182412976, 588599601, 905280444, 671991486, 149716817, 47905658, 64714287, 716724851, 557647216, 28241812, 713896117, 846376494, 206401418, 428739231, 942397989, 324941900, 306688147, 258918808, 206428157, 459115203, 714606128, 901629112, 466484868, 310408763, 294905148, 749311051, 394101771, 403806550, 498739596, 248404900, 190125924, 522025988, 356210447, 962389205, 814535861, 3980315, 250331408, 790031419, 402340345, 314834487, 602818980, 373056826, 513025448, 514106359, 330630795, 280415656, 110664532, 260357566, 438075255, 589257527, 858090853, 422891205, 620257075, 790506377, 952563016, 765975974, 960893637, 543352842, 365161673, 624020379, 800469365, 251809505, 622790780, 765922253, 402911760, 997555042, 559439272, 29544238, 878217449, 228591540, 899811201, 871109199, 546784719, 253989180, 599758115, 684560325, 694533607, 280703340, 236096123, 66961640, 589317182, 148043719, 775804319, 268637104, 330635805, 56702421, 125110763, 721113904, 467948371, 559561215, 304843404, 297100892, 617590242, 296473496, 369817637, 718004636, 526124218, 325406214, 131642557, 869709758, 216629105, 687991036, 573256824, 311737341, 758758392, 234589476, 806451920, 213768729, 631008009, 285161193, 822185858, 233315562, 217016673, 677480896, 804760339, 303459984, 221413383, 399022533, 365958714, 40799195, 381705662, 789465567, 637528335, 343565435, 451970239, 746068672, 166867880, 819274545, 76504657, 397541090, 634573222, 532288800, 461447953, 593079116, 206340568, 73124197, 802335966, 905865702, 467513529, 84938694, 290540136, 695515463, 3667894, 705686513, 717484972, 407798786, 866250512, 73759857, 988625790, 225509686, 921183249, 230949763, 381533094, 278804584, 32480390, 574582357, 123789423, 768169179, 487732014, 297765428, 731832401, 432860256, 598148966, 289492130, 97013575, 442023507, 762069525, 931825284, 458140597, 189544522, 921471521, 275855481, 956391146, 193634695, 84677511, 113885808, 830941679, 431684736, 119795183, 940323412, 300483044, 11521577, 885580158, 695593645, 494983307, 139383566, 821276667, 477452984, 683243183, 361935517, 273621685, 4025495, 476432519, 678629225, 920228510, 134283532, 278793091, 224178916, 869681152, 174441945, 438098978}
};
vvm cs{
{},
{3, 1000000004, 1},
{4, 1000000003, 0, 1},
{9, 999999981, 35, 999999985, 1000000004, 16, 999999998, 1},
{17, 999999917, 230, 999999735, 999999932, 623, 999999375, 65, 255, 999999809, 162, 999999911, 11, 1},
{41, 999999381, 5212, 999973375, 83965, 999864370, 999942070, 800268, 998379872, 906816, 1514014, 997448417, 2622787, 992845888, 8542237, 6980821, 978012096, 16003845, 993847324, 963869, 9768918, 986300473, 2595314, 5478389, 996644365, 223797, 402417, 999810824, 43282, 999995793, 999999809, 51, 1000000006},
{89, 999996897, 60466, 999257343, 6041799, 968004573, 93346877, 20132019, 549856378, 942059966, 948280892, 670341682, 294959301, 961520636, 275891884, 189284953, 515408927, 922413135, 986504724, 979485868, 720816875, 486024197, 821502095, 228407485, 704805532, 223667986, 776018349, 941916815, 982949299, 983769096, 505535302, 523480614, 810844222, 62008594, 945798937, 936686122, 979848061, 881424398, 223307320, 389288711, 115243176, 871832255, 154797729, 264630700, 793731894, 474147171, 173708838, 77027412, 306695658, 223643742, 451868870, 858041020, 847477522, 201612744, 12688266, 441316887, 595366047, 761957547, 79015122, 324684919, 658083892, 323926634, 778759299, 788104398, 970651995, 999423842, 555056, 57842, 1472, 999999900, 1000000006},
{226, 999977874, 1292003, 948734189, 482639899, 453154095, 850171195, 53766434, 788348805, 767594257, 188714740, 598871713, 883399554, 709615713, 322699082, 986376596, 844270261, 888811106, 547589032, 882157610, 667161026, 29154215, 905430460, 179972353, 799086382, 109931487, 932091627, 923631714, 538216708, 225769134, 190218477, 933240728, 980414754, 650176206, 495743686, 173877261, 915747648, 421940793, 658876396, 676358445, 378352488, 366586232, 364288897, 67047170, 964904564, 18433516, 462351050, 435241358, 293201017, 899999622, 871078999, 282273016, 616150786, 249104930, 529489817, 445485824, 524709217, 920747536, 73969011, 692790848, 477920513, 967224422, 898584731, 728294606, 733541559, 393937587, 739879036, 876592518, 162264859, 754971238, 178494008, 670965860, 955488408, 56370837, 861488538, 854209867, 653207784, 604011435, 74519735, 90858378, 426116702, 694762825, 65727321, 275031861, 637412043, 384920506, 178612041, 692100536, 388085824, 780020976, 842937545, 807785140, 469838013, 723950318, 890629929, 667156054, 562691692, 247463473, 774737263, 232253314, 881179515, 340084998, 851043661, 657673978, 67173776, 878742507, 809564593, 317067145, 906198878, 320688075, 608672151, 825278395, 628738192, 341889953, 176997673, 706383980, 649591907, 968658812, 837313372, 619565648, 485531550, 535882597, 434994403, 943784930, 887421946, 742622147, 97058866, 81772232, 434770011, 242913036, 172224260, 670937179, 519092571, 842638307, 929977582, 121377445, 479173601, 812021656, 716911716, 406838412, 882414802, 672491101, 336543495, 907983776, 300278697, 790478625, 192285044, 868324775, 738918870, 422561190, 957681166, 76178749, 619069795, 800082505, 418269063, 273758032, 187778239, 707484059, 151480839, 454492864, 761261839, 783939986, 120122643, 288503168, 82972688, 717825556, 814732925, 356971908, 142949576, 836855049, 453924327, 806848365, 106140317, 731677741, 622171930, 128702022, 998922178, 999981690, 368, 1000000006},
{520, 999878386, 17390127, 271941042, 12221018, 825170939, 946272379, 992795005, 570014743, 761196060, 274525434, 258708087, 157923496, 919433882, 369952284, 756726770, 295080098, 532249251, 101354107, 715984295, 879333867, 474923844, 497951360, 958714294, 763845687, 55498233, 511499519, 289563782, 70609024, 53801475, 639525339, 650235010, 453658842, 52803150, 357011056, 631033789, 831284225, 530329205, 768602119, 931770997, 316728669, 335109643, 860119414, 254806040, 142226513, 3642639, 703014308, 612199562, 464250, 652135305, 336807315, 58770255, 347804990, 25195250, 382787019, 696217027, 362201400, 493515955, 759702994, 974599336, 163896570, 734017600, 310415048, 3895313, 99583804, 81703211, 477713927, 812387920, 637066917, 135467700, 697018383, 887795039, 945599102, 215293422, 973526783, 331287367, 624742631, 958596321, 266700105, 709527794, 582295502, 31836043, 793694988, 357882085, 547802684, 471498993, 241295347, 276210057, 138511124, 813557138, 88530163, 810414085, 614468673, 116360042, 659554150, 196969246, 93941602, 716270904, 443161549, 792794552, 763417404, 667752393, 487248816, 21968021, 66651664, 560416809, 740444824, 332888483, 865576740, 372734637, 998781460, 347690554, 225913591, 180557278, 696274267, 637675248, 191920692, 333508237, 829923261, 932544081, 18216137, 37872862, 691444028, 936349601, 328714110, 607898327, 503005008, 643100335, 886570237, 469673910, 200369247, 11353469, 161412416, 844974377, 807977643, 665002514, 775561800, 849842816, 73797450, 491098680, 615612655, 798399024, 77500997, 65514307, 788585661, 679161941, 55580523, 29717803, 240730013, 620789750, 633160256, 150339838, 630435844, 602121197, 157808383, 85486157, 918737053, 487182149, 300427234, 926015159, 347604857, 725358733, 980432356, 686545141, 482266210, 267165275, 316169148, 148612508, 958537399, 244257288, 672613114, 853577354, 719280422, 754137626, 924150639, 599594107, 376573383, 676099505, 4315306, 350162057, 287209355, 310615140, 287931377, 748503128, 396291528, 347807126, 169893621, 565166813, 437508295, 992906817, 205628385, 769443194, 653379891, 136898561, 416192789, 650909420, 650565558, 419319168, 835142620, 141592637, 579173543, 888956411, 293744771, 171247934, 513178221, 54578338, 665724116, 992250337, 530195388, 468001520, 422543464, 562669569, 807197643, 660838797, 920548969, 302437097, 237323356, 621285833, 863722737, 387510340, 773183236, 981552276, 185968856, 697584375, 104688499, 173362357, 519878977, 927355474, 895746100, 473371241, 214220488, 787805746, 837823022, 770828149, 339700826, 594481902, 524341112, 728106337, 846397660, 772955503, 506769646, 779631621, 997543168, 721997180, 490136004, 420763648, 855279913, 930569505, 646004005, 97309351, 261633959, 981508374, 97498485, 450600498, 477454241, 442839157, 705666698, 55705259, 266964991, 478546407, 345369871, 644836050, 916554452, 553937218, 397116491, 941835283, 92110671, 31720885, 513039162, 993907029, 511948790, 760812141, 499649183, 553586981, 635132037, 706429510, 562438375, 453485355, 646852987, 815300275, 657940637, 909091973, 796293298, 580555824, 504753339, 409763779, 470173802, 216496387, 456922572, 610657511, 699531783, 262654525, 406896931, 37727766, 731949674, 299791403, 369761224, 622809363, 336414753, 468918100, 437792409, 439944526, 537726509, 659902622, 422156772, 561456689, 457304600, 759539501, 914303810, 147039258, 291756152, 642525591, 964766818, 113595187, 216226312, 419336070, 20003916, 945111425, 846959060, 194095888, 439686521, 883612510, 205173735, 103712934, 232125716, 569938836, 245408923, 358452800, 400073015, 17980197, 915188806, 454086133, 326239270, 434280888, 112841642, 457939375, 115692310, 190319116, 355580248, 250427019, 105171277, 354371490, 210318962, 602519050, 309307880, 74891220, 368560209, 778594288, 579007269, 176463779, 149815841, 313061425, 438587013, 305068306, 409527286, 142236637, 452204899, 91975976, 836323438, 906775198, 47575767, 396297608, 222103616, 384010750, 612067600, 52369871, 403015989, 155624823, 591992744, 472403755, 873292889, 95306287, 362031149, 818145231, 11302535, 783781320, 115964034, 198638619, 128966905, 200535180, 580748761, 139819119, 329483773, 986361128, 825297899, 956474219, 619409338, 849360143, 844683719, 526080233, 786489218, 147162504, 741527500, 630052818, 281389488, 342788330, 49592688, 690272250, 511505185, 886235137, 47682286, 676144060, 17943766, 880004794, 96693084, 426141415, 664084148, 334046812, 270567479, 578529189, 555958330, 559568908, 171351303, 478209884, 269999304, 390658098, 560425597, 147723557, 923053036, 941751864, 564566673, 196903145, 222159471, 39627068, 910277885, 671278496, 694126350, 942780260, 433867918, 644656057, 410175215, 775147581, 22691715, 999961164, 999999157, 1000000006},
{1373, 999112539, 363234030, 487044577, 474461697, 736811294, 276396212, 336657236, 573970133, 534082066, 626827671, 528295550, 625583652, 909279400, 36408031, 616610190, 7132279, 612032950, 609058435, 824112264, 472362569, 92495648, 4965734, 24442386, 229205123, 681001833, 581723000, 75799334, 919203262, 553393619, 960986363, 912090722, 846561018, 924576857, 966861803, 163950453, 916483745, 729277841, 703239176, 393727716, 421239709, 250955109, 67425251, 467214041, 361904102, 351734304, 200705515, 795230510, 44728247, 247969785, 691160446, 118461776, 838243257, 851653435, 990928860, 982762964, 815547726, 435917752, 669307579, 260787714, 292363503, 46730087, 782078189, 685881258, 479849773, 937350474, 172640051, 168280429, 681019654, 773527080, 192283832, 894728427, 686808904, 406528255, 3743037, 206407963, 843460439, 885287590, 606343844, 571843157, 100786457, 194315162, 185836566, 35566838, 212615396, 182872810, 527040895, 298481966, 639314360, 378292155, 508633965, 43501006, 265622117, 6181897, 397856606, 75580028, 127948073, 858336552, 921396800, 468434741, 89372209, 146311060, 980705971, 79756239, 969726186, 718446013, 392065416, 957542649, 417440614, 985342618, 465089046, 844186449, 974589567, 864373942, 692235234, 233500497, 879858195, 500378564, 689153253, 857990387, 849973669, 371946935, 866616280, 676132013, 87223496, 375006758, 22417025, 26429844, 387361422, 220263905, 278060295, 819232075, 862777044, 588383320, 874037138, 986621843, 606114438, 933438992, 336883041, 535158361, 513863961, 810436081, 130117806, 697945319, 364925247, 951385954, 478594784, 510699943, 253706620, 36766679, 469747230, 574954812, 688547380, 139659150, 819400531, 842434642, 546131633, 602894226, 190080722, 411536968, 984685739, 339089395, 195437554, 164783176, 231676684, 629814994, 308684140, 619414856, 921325876, 760321486, 844313540, 905322254, 940401847, 779159922, 315720449, 782709985, 890108823, 462466013, 211449547, 506181324, 601673943, 899345361, 908181133, 251054122, 986032901, 415013, 882850647, 844205537, 428585123, 157252748, 972380579, 291756877, 444545025, 867289978, 640741374, 350745175, 903926437, 835376151, 304184895, 566214306, 855297710, 712991148, 791513698, 417537036, 181191483, 375805622, 170635157, 232674776, 625807710, 616148791, 261642303, 220867908, 501693025, 671804528, 522686064, 441590606, 628790771, 43680825, 691403900, 882666383, 706124787, 229685576, 982214178, 785726393, 795415888, 998114655, 219082955, 388567789, 363428578, 911017492, 779038626, 863258340, 811568333, 636003704, 434978177, 251376838, 32948255, 494772807, 23495604, 516666830, 691664929, 747996214, 257424620, 882433049, 683837046, 673937246, 63891186, 208127144, 249226065, 888008896, 883036223, 779291719, 303874151, 66140233, 353491162, 763514288, 979143511, 20105688, 39955309, 861367478, 456499233, 115941481, 762570557, 941778559, 954242433, 230328535, 552828043, 668447955, 77165130, 747035484, 335773832, 816977675, 393734840, 660696318, 740176904, 613111714, 543575273, 735280570, 457594191, 938985793, 420442433, 429166682, 326276720, 76634144, 536259551, 535675944, 755298928, 491517534, 244841317, 691961899, 131223874, 114826667, 785710365, 88751557, 778277464, 172866047, 499014682, 774578808, 752694299, 478539595, 607876533, 911606091, 78075009, 329720970, 490624769, 434961208, 79715447, 24695651, 801365067, 480270454, 831922281, 320857997, 640370096, 645434223, 537481426, 361689635, 879701971, 286487315, 254952187, 552193376, 770894605, 306312372, 32261280, 11833150, 521349341, 65070839, 743978423, 500438933, 861096878, 163039996, 283185542, 365511419, 4954198, 996420415, 625164445, 255724358, 909619496, 742226851, 359391562, 323120420, 569983954, 87808947, 595695080, 689806378, 881067230, 33050782, 456717468, 110720700, 318344195, 904247742, 267661435, 201042497, 611886089, 131154703, 936566040, 878950902, 614882653, 150088545, 930088996, 878777455, 564144702, 322673544, 103317270, 327224873, 864286440, 812002048, 241919085, 145389011, 753143429, 388909435, 695554090, 876611554, 926777682, 121689809, 591340728, 484254062, 713466529, 683401520, 953041599, 146395920, 567125738, 988967741, 409018854, 205634967, 451246043, 369141919, 410366532, 963224553, 975509411, 304587474, 575872263, 146865713, 208418860, 727333779, 428234655, 450562135, 946241343, 346004116, 472905020, 107484882, 491920069, 777484375, 449491845, 613093731, 279115721, 399511751, 638141694, 825256622, 608027733, 481490178, 689545240, 814013063, 821208531, 415185334, 357859148, 187216549, 306195372, 76438381, 574628019, 169865211, 512877992, 118171172, 129859986, 186831158, 711673916, 757182008, 374272871, 772529225, 205233673, 685624410, 86926035, 375589662, 109182833, 759190463, 943592978, 268176601, 498084897, 972523792, 451754997, 283650879, 475831968, 582230354, 991413125, 968833137, 367050828, 111438697, 870445064, 380603441, 960374761, 765139327, 708613696, 259336875, 664163117, 213257451, 894842210, 35402879, 310807881, 904264073, 525445091, 459833081, 879943567, 426203964, 473697228, 620647886, 664749651, 908067535, 975543492, 344642305, 822174349, 726368697, 296849851, 320613543, 139052731, 31216065, 488715013, 360509094, 421511852, 322158747, 833999598, 397692982, 14980331, 76271004, 270523697, 863890303, 715250736, 477162541, 602483974, 926943299, 998920667, 374622157, 277317320, 231178115, 418427027, 49235085, 253129041, 555665252, 334125156, 338622350, 59004595, 36918332, 922721728, 422768891, 757463617, 325080890, 484088747, 140571557, 41446360, 428587248, 286992979, 771928655, 672724819, 556781080, 86445195, 392258996, 207848678, 486149604, 467123152, 860373968, 747110908, 324833347, 436958738, 629151854, 402732726, 78931861, 446699127, 278919716, 100566464, 218566106, 664032120, 789305794, 494961151, 335717950, 7236424, 661974300, 806502174, 123537496, 523034982, 832428797, 185075432, 678826539, 699322020, 537285748, 291876780, 778131759, 551298946, 836352924, 83644047, 218488486, 900706043, 726688593, 836582369, 854365026, 91220959, 190363391, 162234408, 579167612, 760904660, 198681981, 146105825, 399354733, 92372467, 237815553, 206706839, 114350550, 844577350, 355256562, 989793273, 856098692, 694079756, 824315188, 999161335, 133055685, 516683338, 55895763, 757996822, 753560918, 660891568, 717326867, 556273817, 536457050, 364279278, 568208239, 549990319, 444357405, 761908778, 538782523, 229671017, 8127403, 477249779, 177718552, 612259526, 112388546, 888464349, 488821659, 340551058, 402753580, 293041334, 999485174, 890756318, 165786504, 862914412, 901148362, 898311896, 891300698, 112858367, 670529433, 691306227, 671538507, 574400193, 473774359, 551735476, 111889310, 520511517, 136783298, 682932199, 240564673, 407782364, 739719249, 958480479, 839917237, 139673980, 503550606, 504331298, 765668705, 550426804, 823095534, 906787208, 41898550, 454984571, 179032373, 436703536, 663314897, 576419988, 12910271, 215888490, 121254150, 464579053, 583603822, 514567288, 902805791, 169725521, 475093194, 938053557, 563265485, 822443456, 85083402, 867831644, 111310514, 673399191, 165690377, 211384514, 283766253, 109033451, 310852344, 36254487, 705218987, 755512431, 351697842, 301562506, 43939543, 937350889, 877547174, 768316279, 820815612, 129524904, 907933309, 247978623, 137283191, 864547605, 690157179, 503237577, 718924217, 941924656, 476187236, 398869819, 405134890, 478474246, 76355146, 731228204, 812215696, 896182432, 581173512, 655351049, 170318880, 651905378, 436610238, 862335426, 980794966, 190339452, 113563060, 50355775, 134392006, 29926729, 180433797, 919515640, 643718324, 426153875, 607690834, 821644724, 478036928, 699159958, 175968852, 876053188, 471334551, 637316176, 600844968, 546563709, 340276970, 242114808, 892118077, 6479853, 257766520, 302472546, 932636171, 897145276, 449734141, 470780779, 387816709, 336929400, 394001600, 265352410, 572188769, 821684206, 123335994, 746452480, 39411297, 350606536, 835177890, 926763555, 373609036, 668043505, 352021924, 506995194, 101282065, 485159331, 37122329, 277564511, 339935752, 258853931, 986080842, 592139593, 255927745, 198264631, 112200355, 809615945, 13382701, 906100119, 317596899, 31706760, 851576786, 671421865, 950159077, 451051960, 355130395, 338516851, 700105368, 171941283, 916395278, 984388748, 665003299, 743132541, 205927141, 610525411, 634998871, 81613114, 555094671, 978814371, 312436959, 238285653, 261567873, 238993858, 247252247, 135342762, 661342217, 841840577, 279097948, 258280312, 187831537, 203407493, 277733303, 72760622, 562059091, 506070511, 509519077, 294314094, 851232594, 514016563, 910873137, 67633679, 605688733, 125722720, 523832772, 493915455, 437553668, 923236042, 909092340, 148360251, 32687305, 276680120, 248303960, 47151665, 899183233, 421578802, 138064107, 961910789, 678041497, 982617730, 988475552, 407608456, 494036034, 537746049, 891296982, 392625446, 360866289, 113918492, 277005797, 938165613, 592517616, 543307666, 538239896, 869041371, 488915081, 945937316, 929224143, 710035264, 635199808, 11027019, 976128342, 914854913, 181790898, 82363799, 497135348, 964649823, 184548947, 10368090, 857019874, 201750536, 762375659, 393756072, 135168347, 881372959, 900963708, 957761070, 653659352, 454726215, 432984694, 279670656, 176520163, 117070520, 615604429, 202117348, 704049478, 650220053, 965845652, 572194436, 270401083, 950721076, 206109073, 70108855, 253766837, 452538849, 477182337, 18581826, 984806586, 958218838, 363864686, 422419861, 994035764, 935482642, 943231071, 619174586, 984283929, 216591282, 537516518, 367672652, 151148053, 938572456, 194332482, 823966662, 581529950, 144527920, 311376611, 544091444, 970383684, 566840147, 774660870, 259607723, 111064201, 334896996, 393755252, 497986292, 611239147, 223211479, 722731070, 762065800, 899800379, 725042799, 544785396, 260606497, 667279007, 269172633, 850895593, 491849556, 382846772, 304895322, 71158983, 485987409, 675923988, 645159736, 92715379, 318367556, 722106969, 120975884, 148208771, 162410542, 647825034, 480348996, 217437132, 797343280, 644487726, 9790715, 509319856, 491035478, 606866261, 416983817, 281348799, 499720195, 697147603, 654720117, 698899680, 499713962, 91860103, 203029320, 247716921, 794098127, 357288085, 183749922, 694782320, 810592891, 949482295, 581545407, 875911264, 211509859, 754208824, 965513330, 602467230, 889366627, 16831320, 731579972, 736876138, 199893332, 277058476, 274352225, 512420251, 231661754, 999397014, 806966131, 370571040, 833726991, 650387677, 828892011, 237764615, 732529224, 572358928, 986616293, 597898077, 601059933, 122017790, 361146428, 284913651, 879777357, 136277824, 808157757, 44920089, 801592783, 94225970, 862918862, 655328128, 625707008, 323389980, 423625417, 366389466, 103647365, 975023823, 156289439, 422448055, 702845272, 949542175, 727010238, 937046663, 289307289, 212599524, 136519547, 899538216, 365041943, 746076536, 62430827, 180186341, 483058896, 23521573, 83291903, 519318359, 676683256, 5804359, 680044442, 279972335, 360410206, 768513153, 596270311, 697764385, 727596733, 554679759, 389598903, 30851994, 611658107, 409524531, 362643820, 432141852, 183654243, 430338950, 659183865, 605708447, 523751029, 421134812, 110833422, 952886192, 479571223, 663457539, 725220998, 175792609, 676014155, 370669572, 600620970, 917338140, 530764338, 749740314, 332377433, 610416698, 676727798, 314171138, 416975856, 437567050, 404554374, 843626425, 591767698, 639099914, 484205598, 454657297, 815852772, 81189131, 67557227, 179686656, 820317869, 34459798, 870272864, 88630856, 647420253, 961453572, 904312475, 28919847, 347438399, 843937275, 389520987, 97955240, 990662712, 698010320, 756374648, 738791536, 621020108, 757373993, 248640051, 31419980, 606831498, 75678195, 352248491, 443709799, 127022932, 199173386, 800689697, 562905962, 340573521, 422090894, 339951019, 162084187, 606092764, 57478078, 744195645, 49932710, 565592991, 199736, 159920602, 882691364, 117033078, 697838160, 190495543, 157273456, 26388002, 577100270, 708794080, 360080558, 697441880, 924634280, 664129160, 160651563, 819161060, 924408316, 170512886, 692272234, 761158998, 669209225, 497381086, 522856316, 16104936, 294486527, 230063565, 423471922, 533136942, 139856322, 25243987, 732380182, 174808640, 358273345, 655759625, 99324530, 789447370, 314922165, 771851381, 874752618, 630547320, 895703772, 288638932, 750131445, 265236905, 705495750, 307600795, 138504910, 293250090, 325540387, 555833992, 921557810, 1797781, 999997177, 1}
};
//【展開係数】O(n log n log d)
/*
* 有理式 f(x)/g(x) を形式的冪級数に展開したときの x^d の係数を返す．
*
* 制約 : deg f < deg g, g[0] != 0
*/
mint bostan_mori(const MFPS& f, const MFPS& g, ll d) {
// 参考 : http://q.c.titech.ac.jp/docs/progs/polynomial_division.html
// verify : https://atcoder.jp/contests/tdpc/tasks/tdpc_fibonacci
//【方法】
// 分母分子に g(-x) を掛けることにより
// f(x) / g(x) = f(x) g(-x) / g(x) g(-x)
// を得る．ここで g(x) g(-x) は偶多項式なので
// g(x) g(-x) = e(x^2)
// と表すことができる．
//
// 分子について
// f(x) g(-x) = E(x^2) + x O(x^2)
// というように偶多項式部分と奇多項式部分に分けると，d が偶数のときは
// [x^d] f(x) g(-x) / g(x) g(-x)
// = [x^d] E(x^2) / e(x^2)
// = [x^(d/2)] E(x) / e(x)
// となり，d が奇数のときは
// [x^d] f(x) g(-x) / g(x) g(-x)
// = [x^d] x O(x^2) / e(x^2)
// = [x^((d-1)/2)] O(x) / e(x)
// となる．
//
// これを繰り返せば d を半分ずつに減らしていくことができる．
Assert(g.n >= 1 && g[0] != 0);
// d = 0 のときは定数項を返す．
if (d == 0) return f[0] / g[0];
// f2(x) = f(x) g(-x), g2(x) = g(x) g(-x) を求める．
MFPS f2, g2 = g;
rep(i, g2.n) if (i % 2 == 1) g2[i] *= -1;
f2 = f * g2;
g2 *= g;
// f3(x) = E(x) or O(x), g3(x) = e(x) を求める．
MFPS f3, g3;
if (d % 2 == 0) rep(i, (f2.n + 1) / 2) f3.c.push_back(f2[2 * i]);
else rep(i, f2.n / 2) f3.c.push_back(f2[2 * i + 1]);
f3.n = sz(f3.c);
rep(i, g.n) g3.c.push_back(g2[2 * i]);
g3.n = sz(g3.c);
// d を半分にして再帰を回す．
return bostan_mori(f3, g3, d / 2);
}
//【線形漸化式】O(d log d log n)
/*
* 初項 a[0..d) と漸化式 a[i] = Σj=[0..d) c[j]a[i-1-j] で定義される
* 数列 a について，a[n] の値を返す．
*
* 利用：【展開係数】
*/
mint linearly_recurrent_sequence(const vm& a, const vm& c, ll n) {
// verify : https://judge.yosupo.jp/problem/kth_term_of_linearly_recurrent_sequence
int d = sz(a);
if (d == 0) return 0;
MFPS A(a), C(c);
MFPS Dnm = 1 - (C >> 1);
MFPS Num = (Dnm * A).resize(d);
return bostan_mori(Num, Dnm, n);
}
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
MFPS::set_conv(naive_convolution);
// umekomi(3000, 9);
int n; ll m;
cin >> n >> m;
cout << linearly_recurrent_sequence(as[n], cs[n], m) << endl;
}