結果
| 問題 | No.1561 connect x connect |
| ユーザー |
 ecottea
|
| 提出日時 | 2023-04-03 00:23:57 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 59,782 bytes |
| コンパイル時間 | 10,054 ms |
| コンパイル使用メモリ | 503,648 KB |
| 実行使用メモリ | 5,640 KB |
| 最終ジャッジ日時 | 2023-10-25 05:16:35 |
| 合計ジャッジ時間 | 13,706 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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 | 6 ms
4,348 KB |
| testcase_15 | AC | 8 ms
4,348 KB |
| testcase_16 | AC | 10 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 | 2 ms
4,348 KB |
| testcase_22 | AC | 3 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 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| 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 | WA | - |
| testcase_37 | WA | - |
ソースコード
#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, 3750183, 187865261, 191584864, 879856061, 812783194, 805278012, 234689380, 88287120, 142717819, 470647052, 294257676, 752852398, 498225649, 319347307, 995589000, 685893099, 667526674, 311322184, 701120108, 401990479, 879427849, 803470940, 5453945, 779997482, 786419495, 629438261, 274037462, 406495198, 255714746, 358726055, 310986424, 873073368, 432576121, 13028531, 117059318, 57663180, 730812399, 84410228, 309016493, 61056206, 597233487, 514019571, 827491922, 549016896, 945849928, 464710185, 752556322, 110042443, 624664469, 294912710, 989649786, 992051625, 950964007, 568290221, 430408067, 606168911, 780514302, 584977, 673255107, 135354119, 641178117, 51048518, 868339339, 281745607, 786028550, 159530069, 411488639, 664665569, 567185155, 470338296, 681047048, 366836537, 802993740, 54658846, 951924983, 228781897, 592750761, 310214667, 674925049, 652070324, 689747705, 179767722, 401147982, 906794745, 887737438, 248999751, 941170361, 675152367, 389356379, 412319048, 776992612, 961688322, 833761766, 187728057, 555399651, 111546950, 278234093, 95135126, 737056657, 279509469, 417171852, 867209370, 734065024, 511004149, 562157644, 668942158, 612009944, 529478745, 767671372, 750126520, 437690213, 125699155, 666296730, 12378268, 22785875, 505483052, 442690689, 809519545, 425980587, 820992399, 743721366, 408827368, 608847955, 580930997, 652720592, 657337319, 287655611, 4784280, 96462627, 690778041, 794912812, 930397710, 647718358, 662839111, 2946431, 435527317, 728799124, 99683342, 69965573, 219775128, 724771601, 672827722, 201889209, 458393454, 761302150, 867382042, 57145060, 349834343, 775220354, 269178191, 818660308, 566964970, 280499176, 694631895, 298648954, 278966320, 910600703, 331500293, 607535547, 297470038, 282697284, 391239292, 192184481, 148727449, 900497954, 382179879, 159528355, 269471405, 543913581, 362946735, 750586466, 35275298, 831672222, 296878796, 68474675, 465522762, 311128399, 683741268, 296137889, 866654350, 746552335, 939293992, 720894361, 732494679, 597160394, 808326401, 982137950, 944681707, 339092607, 710742724, 276220755, 89315781, 561785650, 356719900, 611924671, 358675639, 291175176, 284555045, 862224229, 196109244, 481584079, 391895830, 296534035, 558305391, 451193169, 677312424, 257910187, 316150495, 110897398, 360259927, 826075546, 519273471, 598713519, 181790059, 297553794, 626205571, 772072076, 960696949, 776924186, 632814211, 599033091, 576607044, 227728133, 407956469, 555041463, 702044504, 466711609, 726321190, 262472031, 954628673, 435484197, 618496840, 286774327, 800390364, 594197369, 879533899, 385408449, 781461237, 747595082, 347593763, 57248441, 315183367, 682058776, 793564921, 793705147, 520062764, 911202552, 206457311, 346494462, 461330007, 190010932, 860479415, 600245998, 874524842, 427144694, 661290554, 782497105, 626195828, 324186845, 499154172, 564783585, 5790873, 205964932, 766122043, 142292391, 938369312, 983024000, 524142781, 296678069, 813325719, 905433409, 649915213, 772491676, 924643700, 530819902, 260774657, 287514382, 862888265, 885161345, 997645497, 26787692, 306059171, 389425639, 792228751, 54936584, 50632442, 638874800, 606936567, 557130594, 266040368, 108955864, 930540936, 313569616, 219524050, 11699212, 668444280, 494021450, 172099866, 654221133, 140118875, 633996503, 479522648, 806668959, 784925922, 497814762, 408118899, 342751646, 673642276, 434245681, 661046335, 873249315, 656866458, 968060474, 76096802, 721903238, 938109965, 869879072, 917786999, 608656645, 149459547, 481339210, 761737733, 151526476, 967094536, 869941453, 502823118, 202524110, 154809493, 383184718, 973564112, 40058783, 284933672, 711783060, 187757746, 935739359, 42730836, 841165202, 88445318, 631136507, 567671414, 743708027, 217588194, 907956607, 427347602, 397730169, 98193630, 431776051, 269843369, 580627565, 320085081, 366595572, 642378923, 289320947, 541838429, 856408290, 614053971, 537681173, 590751098, 625538324, 167367480, 979909493, 130257042, 943518504, 397803665, 470017941, 611665407, 939294127, 171766259, 898663354, 176654361, 410506069, 781394294, 347200500, 928567458, 551779725, 352454613, 380900858, 222236357, 863832173, 881647180, 962205604, 583943439, 575313885, 29627013, 307367981, 315906986, 538555269, 612534688, 455826028, 405559812, 194686460, 60027178, 359729995, 484653341, 894898610, 427817750, 372291581, 215852419, 704860232, 27529118, 480685215, 358483072, 81988880, 177604018, 904306319, 627728978, 585327977, 134541200, 411361122, 426460452, 741081503, 839426274, 100880993, 517938247, 533688099, 30441041, 269489292, 18181034, 484370892, 670970529, 388214728, 73299124, 413171501, 661154816, 129543320, 312174404, 825189660, 598835814, 8304351, 761479635, 523453432, 794801409, 727156231, 681086090, 362103330, 744005327, 183180596, 24278140, 988631041, 511087334, 393728348, 550781451, 921308976, 790414283, 630495925, 535748564, 864970160, 333235288, 24944422, 92727528, 384709977, 825056143, 98723335, 317567619, 459322824, 246838953, 411640233, 365406521, 270814260, 141253513, 191402524, 907454086, 570817503, 184361697, 386854960, 482877198, 367615430, 257388104, 545716891, 685403594, 419175356, 178079042, 978671436, 48865080, 158482106, 376313343, 546454688, 151211976, 646935283, 332292717, 745295864, 719256378, 324660381, 849240460, 299728774, 398996578, 984015249, 389859775, 802559572, 709474309, 850699164, 385501407, 573158647, 34740270, 942354716, 865007782, 935756662, 438675981, 374514094, 267380011, 815896053, 263203133, 489681795, 336192229, 996296213, 841960684, 19066753, 422473820, 474365997, 247182975, 718863169, 52313996, 19960100, 602755128, 52072768, 454367872, 915332721, 592251105, 190385564, 435953237, 447348376, 803137506, 191731077, 6472058, 643032651, 335872214, 152778712, 284976934, 1565556, 450248228, 58371842, 32554594, 834070759, 342390232, 476139266, 4497133, 797736197, 549163218, 218007254, 426511884, 852253925, 763697496, 749323230, 446308026, 557841843, 59684778, 90096758, 32771818, 156184788, 246547779, 822642346, 457941668, 568282121, 70302825, 7698573, 676395514, 326315500, 614780248, 184773432, 235968671, 358941505, 733780484, 291689974, 821158977, 897399508, 346276321, 530432419, 216985060, 919754188, 542721504, 477084691, 994078662, 613332656, 45548982, 441563736, 167248618, 268492727, 13742238, 932546157, 55773957, 934192942, 632026241, 384160579, 231633371, 109880163, 460463766, 790859292, 586953707, 201268543, 648453289, 897926800, 370604998, 324752835, 193049175, 837714542, 176110904, 799095357, 226291537, 921312155, 722054565, 190113071, 571247287, 755784147, 584978500, 840265152, 191663217, 474797795, 817145297, 216732657, 461731683, 541944003, 977738905, 72321569, 878780485, 195131847, 7228288, 138596509, 187279732, 196816956, 535601385, 754786237, 487495634, 672568624, 557483010, 504388800, 102369393, 300505052, 625937877, 551893174, 606794240, 393213535, 260537136, 643968027, 240404902, 542660157, 446114262, 729632104, 694934886, 795405284, 919202130, 537705403, 141762695, 86248184, 100441363, 377212661, 763747480, 874897600, 347074876, 308806842, 836847004, 718195486, 196982586, 291530951, 272726055, 95268528, 675527095, 493525927, 209356865, 229824602, 633912883, 663032543, 495200766, 408130884, 238713455, 146408810, 973445347, 461980107, 797584115, 384158806, 858360776, 705935531, 197567171, 549954566, 488028789, 838354789, 352447207, 941745481, 835474761, 491439068, 894385495, 982544666, 101902927, 22862370, 249488585, 291033314, 122258598, 740924040, 860171769, 76141102, 674626502, 268319372, 873562443, 487030731, 678215763, 192766753, 244241257, 68550185, 293020360, 1750275, 671841309, 848018123, 308727524, 358614210, 585368766, 483511356, 727340576, 142523025, 340437703, 835322511, 763271597, 918486069, 100022587, 750339561, 897364522, 975223650, 777216060, 571043257, 516457389, 982913942, 79799674, 197802548, 541484625, 407148999, 580639057, 513880774, 414476277, 311235126, 391772284, 511887364, 408237952, 565814426, 484559881, 166667829, 195261343, 479009789, 74231133, 518235296, 331078984, 290070923, 144642993, 783946104, 474687851, 239631285, 261915328, 599205284, 771645060, 65841012, 627194398, 858550100, 600885502, 330162916, 946156797, 487833545, 657586540, 252669876, 581824701, 699396721, 758634715, 177554463, 93254443, 806449418, 477078573, 339307340, 427482676, 788296434, 3583881, 296591989, 67779371, 354307026, 536375014, 683939724, 521631807, 11240898, 430732489, 423518299, 764954900, 979777625, 279078336, 485981597, 294268688, 549145936, 828312034, 196369202, 694865630, 458063712, 685504659, 581396488, 298047317, 237096822, 600600621, 535064805, 699122499, 406227644, 788023797, 343249694, 587955514, 668217466, 906300532, 655522270, 27797587, 598368156, 551623153, 557273018, 212970175, 247035371, 407981915, 649421448, 377182023, 786056194, 422678723, 32279872, 857447571, 317734000, 376133311, 734302823, 615007351, 667155401, 538158497, 157947070, 770771687, 538630337, 421219967, 215061440, 446651715, 855157206, 377212542, 625871501, 25371594, 739362155, 19961430, 329517256, 228110036, 778143942, 215401854, 707741341, 978209497, 524659470, 345725595, 664765275, 883851636, 972887548, 386980269, 346575195, 250946161, 772670548, 147664644, 490510211, 523354270, 545049516, 538714885, 230026624, 19217391, 530804852, 37460848, 634030182, 25881004, 998093058, 852075895, 261722523, 839597491, 671400727, 335504247, 827696031, 943744758, 30244706, 919055700, 80298583, 215327017, 404157354, 531091495, 806498974, 130246152, 552767841, 21076530, 838164726, 813301071, 480454488, 328304400, 813188789, 967104180, 285043554, 856145592, 645278654, 665085680, 718249200, 864078011, 48674354, 67710341, 280412675, 958893897, 670189164, 266990503, 424900224, 692251683, 867408626, 464689179, 660484478, 255059845, 469148654, 351789248, 225721259, 460040264, 410574009, 438347694, 36357452, 75572976, 553601248, 726781871, 66339064, 940553817, 118742362, 397109798, 822220689, 703363324, 97586487, 824833196, 689919445, 360748983, 56993761, 999605922, 358577766, 254640520, 709324105, 232481122, 743300301, 804000474, 440097259, 387214678, 184570832, 96287162, 56174862, 22508993, 239197024, 572684084, 74853103, 650973670, 313733293, 520828578, 712065170, 134400409, 541037789, 636976015, 462258030, 604313047, 127476804, 858495383, 988174633, 939576671, 886244249, 357798105, 425441292, 124856812, 940814529, 194170284, 638668351, 891021347, 294283741, 589618490, 972408036, 388937284, 18229878, 849132219, 627594427, 711911486, 148933950, 748204271, 390434364, 251071826, 154293277, 718599396, 852784868, 713347824, 443516209, 137332601, 724071733, 784442917, 390067160, 784630158, 922836008, 328938732, 969469046, 744900037, 31052287, 127270831, 48650126, 4164588, 493986310, 323737042, 287721004, 120314818, 222321639, 462819908, 81331877, 160678625, 539407270, 983524616, 897881456, 359514571, 836431268, 236909643, 490634710, 542279649, 468433040, 578979175, 64035036, 775944902, 783710989, 974571998, 425490544, 620922960, 515300166, 197083329, 276104341, 907990231, 892428913, 252837712, 260595501, 387982828, 981737650, 736068531, 176522355, 73017674, 187342799, 913551900, 381590212, 808608010, 66602401, 550567347, 902030789, 774709711, 796324475, 497023082, 580398926, 397778023, 505274400, 434459951, 340427192, 944577090, 417414235, 168273361, 203195384, 228857889, 22051871, 562234023, 912983986, 423743325, 285446396, 955624963, 739984315, 227640778, 384867109, 303976682, 314187687, 566232435, 434842759, 548544725, 9475623, 944417453, 632164895, 47711297, 351095605, 23465712, 914995138, 318840142, 426799615, 57009172, 923811408, 916871180, 150405116, 135954953, 246126473, 901736125, 27145822, 99496751, 190941560, 683599851, 682388088, 252345664, 341264815, 483575497, 381822500, 730409425, 996090919, 68191347, 430856592, 939803856, 742164938, 806623703, 324657452, 456633148, 862000510, 251678212, 715865130, 593147570, 921540191, 473640604, 633453333, 623291844, 860306507, 731888641, 627061481, 54974618, 29171902, 737968056, 780481152, 844170631, 131589267, 831433729, 718282623, 543277494, 33670988, 297117590, 188452570, 747657818, 337545279, 50846290, 61076855, 560390987, 898676543, 36622700, 781850717, 304935384, 652397963, 58724587, 492122771, 454311181, 583159679, 697788095, 814913071, 289354366, 108144888, 697247100, 424313665, 754420273}
};
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},
{1367, 999120754, 357943299, 643171076, 309447493, 560332341, 388863224, 982377265, 836321648, 935927470, 699998577, 154762525, 56962294, 407330924, 855136129, 372952342, 557411176, 952881040, 338640681, 793818000, 622810351, 716581076, 830489992, 231229362, 425642938, 563950528, 56496575, 395663617, 562575738, 306817033, 606355657, 537575247, 426868282, 419893148, 388980668, 410138490, 885944831, 817075695, 193885104, 821633025, 483483621, 126217009, 459910345, 623085526, 489843693, 725271110, 123594081, 871204638, 105884154, 991651163, 198974709, 865183106, 114880440, 508565426, 164046542, 712551179, 394845188, 712696255, 173224642, 68955090, 843792777, 123682564, 828010602, 499448325, 267508012, 799801799, 930341902, 777889248, 850527579, 414464912, 497694272, 598974092, 633969825, 256718752, 562861370, 773621366, 430206610, 486190127, 818681697, 814015914, 676867263, 878795121, 610880446, 549445356, 911099873, 450987526, 983960554, 964994440, 29737071, 531836400, 693875906, 101408196, 170026375, 307272569, 606621111, 692341043, 427140358, 406444279, 279240577, 396572678, 232450090, 863215078, 501790000, 921661338, 192106577, 694837543, 492370100, 325722945, 744712323, 486316585, 245851692, 282670868, 777267722, 122231121, 192804354, 870109544, 974358247, 600770720, 258180774, 622338938, 344058798, 977309621, 749779715, 735160831, 875029487, 523185161, 256459670, 5495796, 535595341, 408449234, 352995124, 940469807, 87838259, 129193111, 794467899, 151175114, 902946735, 620122063, 251794995, 226031521, 293389451, 222165025, 884461532, 557381849, 57968489, 932763262, 672619357, 66093092, 649886240, 769561882, 282447198, 737750366, 398166255, 292768150, 36194238, 500136674, 308251928, 211954293, 505780797, 795108354, 180294568, 511515369, 576854371, 530594563, 970567870, 79953460, 229500798, 382757702, 770660149, 628462086, 755718781, 552740711, 194681956, 96496183, 218688378, 718434968, 400313198, 699936170, 997367581, 691588563, 382093112, 401371608, 89992407, 427493304, 108313057, 64746070, 661046178, 613401010, 211529801, 431659509, 438506089, 286017695, 909176143, 82470841, 540263107, 276074990, 461179450, 900719608, 23443811, 883599246, 904780234, 247377265, 890424458, 989916140, 389616865, 43620310, 383249863, 835789480, 153922981, 460095246, 848921308, 959974852, 364550274, 845552731, 740400206, 922923376, 211695855, 240716642, 308503851, 994195368, 494041945, 419108769, 820607273, 531209246, 730851633, 154809137, 930136133, 737499073, 633813795, 276671451, 228774474, 461465859, 602815320, 439870079, 813005819, 113869760, 362604063, 30568639, 907687610, 739693808, 462189483, 482070616, 309801982, 380505161, 42930421, 678182588, 944261355, 944536423, 400069018, 444803591, 271016247, 732694640, 851704095, 165918763, 518834898, 466203077, 282164619, 357922761, 195386078, 713497433, 739561870, 282228841, 603922535, 467001497, 129860685, 396240507, 968058910, 884139740, 42313206, 320827276, 500780637, 393783491, 657355467, 828380385, 366196787, 844172872, 686582419, 794017372, 363523642, 539727801, 468499527, 689472651, 938322957, 442749667, 657962571, 568347798, 465093841, 182864889, 994464949, 237601530, 434785014, 833157920, 285402143, 181081294, 847359295, 512527609, 757146038, 186531849, 251191895, 548391522, 742915116, 182757640, 584623898, 320042722, 367777681, 909604813, 182703412, 997704263, 991882472, 637038938, 762435947, 369615932, 21365846, 536245054, 718156014, 554053452, 896163780, 960297466, 589462724, 196983875, 456633957, 445429297, 461004820, 768008320, 488575723, 826969370, 634865542, 992132806, 883932885, 117937359, 19873437, 983043642, 387138520, 343160353, 912102560, 63357039, 686485207, 97120129, 177403011, 886214635, 124354009, 995989468, 939023875, 807868709, 82100289, 212571648, 452389684, 606417845, 158957347, 65080588, 177173639, 285834270, 515865911, 986068386, 154587639, 652571698, 245419965, 774345753, 375296831, 503770880, 106382033, 832901864, 583014696, 524039448, 359256534, 929790938, 624123696, 50176679, 603002829, 730227483, 259260262, 307139620, 226455038, 896919724, 632784251, 130308414, 141405261, 597672733, 884452225, 145520087, 545745889, 369907285, 772841073, 561594690, 914882754, 796826480, 967198092, 156575463, 203083423, 758173700, 617866821, 676144048, 172837327, 289096466, 862647464, 399187602, 169229884, 929499770, 694036874, 643745136, 372749486, 200340028, 123445213, 526863032, 516257380, 871283146, 816063172, 472259481, 422948366, 125815783, 323770391, 372399362, 612699823, 905869942, 874960459, 783995264, 674357440, 18901428, 973963669, 755427397, 395247654, 908168453, 557395491, 592882959, 371277735, 315771958, 441715343, 687875953, 27021757, 780593218, 115473886, 705743363, 293658886, 852209471, 244120335, 246075651, 534679547, 643884492, 572429033, 821958993, 257678291, 715042557, 694121405, 938366991, 362261470, 904670020, 912050171, 156733856, 883908972, 95889147, 822477416, 853914480, 314332195, 361645741, 5507765, 349417715, 449742698, 514857945, 579805267, 829909017, 389067426, 865658631, 32508281, 412295452, 722652714, 449571733, 508593185, 891711554, 496165165, 386293004, 463108380, 957869810, 375211771, 865718269, 849342795, 327842256, 57807671, 776652892, 15699225, 517799440, 306916306, 816401737, 723256863, 81709237, 416573846, 28005577, 715626745, 517383761, 32154400, 179445353, 603194098, 488908285, 744733676, 416978376, 408900849, 141610061, 664637699, 113147190, 978558879, 211800204, 491588310, 874043040, 72599150, 79106465, 119500907, 277552489, 882269692, 542231696, 113191985, 530943505, 388581636, 494504559, 15445364, 504589532, 540633692, 728389563, 347398182, 29733222, 922088824, 638878198, 329517532, 252867568, 779080129, 951018267, 307781349, 135173292, 858058687, 536670200, 470538033, 178671779, 114264150, 641831795, 435870867, 896683614, 281039506, 306090338, 812540861, 453181711, 587560433, 240011200, 22675412, 515244621, 108684049, 341250813, 169965149, 372954213, 248702918, 991455425, 598254462, 201313346, 219980900, 321334645, 224301415, 163767615, 674303404, 247467706, 493523033, 958504859, 112851287, 800294934, 979632454, 365789224, 52898112, 474413601, 375376257, 803282002, 964935190, 711373637, 101191218, 780586041, 821924814, 232347383, 300721405, 344326377, 909344268, 649256373, 537510696, 953614330, 947553695, 901209659, 456109289, 477740908, 629642748, 183362585, 575853690, 110313324, 951570172, 844456275, 255857330, 353213789, 65611480, 18950509, 580255566, 108877595, 867490602, 937517879, 304515308, 199574420, 738884063, 747388474, 866499001, 741166473, 992801930, 419843354, 929575168, 537246451, 730345489, 42618769, 162358437, 14231022, 887568880, 217282986, 117926525, 980285627, 462276356, 752985094, 976957076, 875278607, 207235024, 698845374, 256080068, 100902152, 648919106, 910998056, 508041327, 838734905, 85669799, 817782325, 14697663, 434703698, 99740081, 656345461, 770606116, 672614206, 764334373, 27645656, 449868400, 119703500, 713238690, 152816507, 540106906, 954942959, 656053866, 261333678, 612541232, 827992693, 384813560, 253064647, 483708564, 497223340, 266942418, 902394201, 778316272, 46124736, 246580231, 356639602, 882153173, 618803558, 745941336, 436420948, 123173547, 282189421, 193304685, 145835209, 191948416, 880149274, 106913694, 850017568, 733393278, 445097788, 919755359, 705413837, 918944632, 275225079, 714452259, 57388337, 543499295, 895351744, 245367252, 330991210, 961717969, 853739490, 479444001, 532888697, 49115607, 43462091, 512017944, 131534242, 647052419, 310325703, 35189928, 206912822, 714223304, 439807396, 714925175, 937917835, 806090482, 150880540, 633518270, 582358011, 47302421, 155745670, 955545715, 602177043, 111441139, 128545682, 746755799, 729736375, 153575093, 653045865, 644512501, 533205634, 597422422, 132946172, 759019193, 340823199, 825893029, 185335909, 745455541, 887246999, 68439706, 632527822, 783402066, 509494685, 527814262, 951159523, 460359713, 303069471, 637350991, 988240418, 719579613, 847369900, 114697919, 703560652, 449069922, 806142265, 999905392, 589903703, 634577039, 472506920, 356891495, 928468173, 622684037, 795175352, 239192340, 574256987, 850134736, 580955408, 879508179, 480009866, 568553320, 283825626, 168626739, 985724537, 469320273, 461161256, 534191535, 248369664, 934663014, 934113838, 755273624, 239389249, 432198281, 941030364, 816498760, 325474547, 955704629, 301308523, 610041416, 162433703, 199021220, 296977724, 160947526, 687364092, 771995871, 644883534, 494381803, 150138443, 298668609, 150472508, 472504939, 401018854, 185248713, 169535915, 909916265, 837118890, 900540166, 578288768, 28978085, 678163855, 289603260, 535780865, 529181290, 115276307, 322637536, 25849032, 301296061, 641718623, 680807362, 579191137, 250662213, 719636492, 977811636, 487853839, 922723568, 661974933, 336824036, 961072665, 446602947, 732422040, 186268386, 478133106, 218553149, 45936683, 245099176, 353693505, 890679821, 175181743, 643487906, 678086242, 585309945, 802357570, 315875417, 993178032, 686514761, 380295161, 939923826, 310687543, 747744929, 240558178, 619204813, 907292639, 376447121, 127269313, 17422874, 12709115, 548403458, 86977403, 703540117, 815792689, 650381886, 431243561, 879026471, 120440834, 136073658, 760604891, 642593738, 936532908, 517314307, 92983480, 16384874, 669378599, 891005543, 530596840, 918123598, 824737494, 913176458, 354938627, 943178765, 283525818, 774829674, 29140036, 590168987, 512578141, 405551989, 310543243, 964713731, 76429937, 172683036, 365419991, 100938306, 167280327, 757986326, 728375913, 483768489, 951485772, 925280452, 172048144, 790871299, 315358910, 266463010, 842436054, 9976654, 373527546, 472107895, 446957250, 304004775, 402734819, 377322628, 577077102, 775811262, 902004344, 949806826, 384423233, 143215026, 810614979, 714127100, 940446914, 894564778, 861396409, 937639781, 26518729, 345490767, 266252029, 741768429, 117584945, 599093251, 210056163, 249127856, 971783839, 888738228, 661736500, 866617476, 437737753, 139017796, 954757054, 474654509, 67958734, 756440226, 252419985, 123814748, 377816092, 220327372, 509569190, 577660460, 687664791, 169628621, 942787270, 435149621, 901697388, 945172063, 248157203, 123280035, 309201619, 930235860, 668990886, 58565620, 597675920, 341523091, 47061561, 410088754, 855894034, 218187615, 135015388, 597981182, 889973578, 384467160, 172813736, 850067164, 61199528, 23273592, 184987979, 338907748, 930362811, 368047262, 739832639, 818782963, 280230472, 257419445, 801324023, 171458297, 677535041, 80814669, 573198144, 76950556, 871673887, 124751482, 154802360, 568726975, 515868906, 150619396, 124790093, 520625406, 112586838, 729899491, 458186593, 486343321, 452646553, 303447635, 505374464, 877292876, 648939084, 229883984, 239684326, 115972954, 551526649, 206224792, 927822663, 731259639, 511377607, 895704828, 634894226, 271130482, 362427771, 984986564, 462860223, 552876364, 787501729, 222761241, 301822527, 246929194, 774820669, 52621498, 652859353, 735141242, 868740258, 841728480, 862038229, 10559019, 742294464, 750766945, 295628994, 657417238, 666118810, 173308451, 707381154, 824554515, 15790364, 623524399, 127178057, 98741397, 481411949, 575071568, 53216138, 953198987, 812817752, 242842615, 624340674, 659219254, 864376724, 355934741, 707001196, 826124700, 693045669, 795493219, 30712857, 967503347, 83141469, 217785269, 205298805, 327861289, 899314384, 611738986, 344069220, 242070789, 455738335, 866085649, 128828507, 464180119, 666532767, 192605985, 56441768, 325507373, 555273034, 152405461, 29857598, 12442332, 274762880, 138321326, 792356567, 40085334, 719329932, 878683071, 771231405, 195702325, 7788990, 310583451, 116662942, 397569117, 705154919, 77860394, 449859226, 426554754, 323818628, 361536955, 280566503, 762011713, 487261075, 298933836, 150429474, 239140824, 150976406, 216034971, 762526124, 801474607, 660226986, 784085939, 731460384, 142710290, 291471761, 127224671, 541478383, 284567298, 811913780, 177945757, 5251580, 546021653, 326334935, 291926446, 744518331, 165364937, 415487358, 128721803, 937833347, 11142442, 339479120, 94857641, 813432036, 375926893, 138180026, 34156920, 638323727, 138884031, 429421923, 104581067, 850616137, 678177746, 447877062, 405899841, 604180146, 426021746, 468458635, 655816356, 707298699, 502043204, 533468824, 57476799, 535481076, 826216158, 241124803, 56340849, 657905217, 713181282, 130517587, 895086556, 273904, 999999867}
};
//【展開係数】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;
}