結果
| 問題 | No.2995 The Ruler Sequence Concatenation |
| ユーザー |
 ecottea
|
| 提出日時 | 2024-12-20 06:27:35 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 63,424 bytes |
| コンパイル時間 | 8,688 ms |
| コンパイル使用メモリ | 357,968 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-12-20 06:27:47 |
| 合計ジャッジ時間 | 10,529 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,820 KB |
| testcase_02 | AC | 2 ms
6,820 KB |
| testcase_03 | AC | 2 ms
6,816 KB |
| testcase_04 | AC | 15 ms
6,820 KB |
| testcase_05 | AC | 419 ms
6,816 KB |
| testcase_06 | AC | 350 ms
6,820 KB |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
ソースコード
// QCFium 法
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#ifndef HIDDEN_IN_VS // 折りたたみ用
// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS
// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;
// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
// 定数の定義
const double PI = acos(-1);
int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;
// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;
// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x)))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x)))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定
// 汎用関数の定義
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline T getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod
// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }
#endif // 折りたたみ用
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#ifdef _MSC_VER
#include "localACL.hpp"
#endif
using mint = modint998244353;
//using mint = static_modint<449>;
//using mint = modint; // mint::set_mod(m);
namespace atcoder {
inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif
#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(...)
#define dump_list(v)
#define dump_mat(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す
#endif
struct MFPS {
using SMFPS = vector<pim>;
int n; // 係数の個数（次数 + 1）
vm c; // 係数列
inline static vm(*CONV)(const vm&, const vm&) = convolution; // 畳込み用の関数
MFPS() : n(0) {}
MFPS(mint c0) : n(1), c({ c0 }) {}
MFPS(int c0) : n(1), c({ mint(c0) }) {}
MFPS(mint c0, int d) : n(d), c(n) { c[0] = c0; }
MFPS(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; }
void push_back(mint cn) { c.emplace_back(cn); ++n; }
void pop_back() { c.pop_back(); --n; }
[[nodiscard]] mint back() { return c.back(); }
// 比較
[[nodiscard]] bool operator==(const MFPS& g) const { return c == g.c; }
[[nodiscard]] bool operator!=(const MFPS& g) const { return c != g.c; }
// アクセス
inline mint const& operator[](int i) const { return c[i]; }
inline mint& operator[](int i) { return c[i]; }
// 次数
[[nodiscard]] int deg() const { return n - 1; }
[[nodiscard]] int size() const { return n; }
static void set_conv(vm(*CONV_)(const vm&, const vm&)) {
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;
}
[[nodiscard]] 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;
}
[[nodiscard]] MFPS operator+(const mint& sc) const { return MFPS(*this) += sc; }
[[nodiscard]] friend MFPS operator+(const mint& sc, const MFPS& f) { return f + sc; }
MFPS& operator+=(const int& sc) { *this += mint(sc); return *this; }
[[nodiscard]] MFPS operator+(const int& sc) const { return MFPS(*this) += sc; }
[[nodiscard]] 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;
}
[[nodiscard]] MFPS operator-(const MFPS& g) const { return MFPS(*this) -= g; }
// 定数減算
MFPS& operator-=(const mint& sc) { *this += -sc; return *this; }
[[nodiscard]] MFPS operator-(const mint& sc) const { return MFPS(*this) -= sc; }
[[nodiscard]] friend MFPS operator-(const mint& sc, const MFPS& f) { return -(f - sc); }
MFPS& operator-=(const int& sc) { *this += -sc; return *this; }
[[nodiscard]] MFPS operator-(const int& sc) const { return MFPS(*this) -= sc; }
[[nodiscard]] friend MFPS operator-(const int& sc, const MFPS& f) { return -(f - sc); }
// 加法逆元
[[nodiscard]] MFPS operator-() const { return MFPS(*this) *= -1; }
// 定数倍
MFPS& operator*=(const mint& sc) { rep(i, n) c[i] *= sc; return *this; }
[[nodiscard]] MFPS operator*(const mint& sc) const { return MFPS(*this) *= sc; }
[[nodiscard]] friend MFPS operator*(const mint& sc, const MFPS& f) { return f * sc; }
MFPS& operator*=(const int& sc) { *this *= mint(sc); return *this; }
[[nodiscard]] MFPS operator*(const int& sc) const { return MFPS(*this) *= sc; }
[[nodiscard]] friend MFPS operator*(const int& sc, const MFPS& f) { return f * sc; }
// 右からの定数除算
MFPS& operator/=(const mint& sc) { *this *= sc.inv(); return *this; }
[[nodiscard]] MFPS operator/(const mint& sc) const { return MFPS(*this) /= sc; }
MFPS& operator/=(const int& sc) { *this /= mint(sc); return *this; }
[[nodiscard]] 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; }
[[nodiscard]] MFPS operator*(const MFPS& g) const { return MFPS(*this) *= g; }
// 除算
[[nodiscard]] MFPS inv(int d) const {
Assert(!c.empty());
Assert(c[0] != 0);
MFPS g(c[0].inv());
for (int k = 1; k < d; k <<= 1) {
int len = max(min(2 * k, d), 1);
MFPS tmp(0, len);
rep(i, min(len, n)) tmp[i] = -c[i]; // -f
tmp *= g; // -f h
tmp.resize(len);
tmp[0] += 2; // 2 - f h
g *= tmp; // (2 - f h) h
g.resize(len);
}
return g;
}
MFPS& operator/=(const MFPS& g) { return *this *= g.inv(max(n, g.n)); }
[[nodiscard]] MFPS operator/(const MFPS& g) const { return MFPS(*this) /= g; }
// 余り付き除算
[[nodiscard]] MFPS quotient(const MFPS& g) const {
if (n < g.n) return MFPS();
return ((this->rev() / g.rev()).resize(n - g.n + 1)).rev();
}
[[nodiscard]] MFPS reminder(const MFPS& g) const {
return (*this - this->quotient(g) * g).resize();
}
[[nodiscard]] pair<MFPS, MFPS> quotient_remainder(const MFPS& g) const {
pair<MFPS, MFPS> res;
res.first = this->quotient(g);
res.second = (*this - res.first * g).resize();
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++) {
auto [j, gj] = *it;
if (i + j >= n) break;
c[i + j] += c[i] * gj;
}
// 定数項は最後に配るか消去しないといけない．
c[i] *= g0;
}
return *this;
}
[[nodiscard]] 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++) {
auto [j, gj] = *it;
if (i + j >= n) break;
c[i + j] -= c[i] * gj;
}
}
return *this;
}
[[nodiscard]] MFPS operator/(const SMFPS& g) const { return MFPS(*this) /= g; }
// 係数反転
[[nodiscard]] MFPS rev() const { MFPS h = *this; reverse(all(h.c)); return h; }
// 単項式
[[nodiscard]] static MFPS monomial(int d, mint coef = 1) {
MFPS mono(0, d + 1);
mono[d] = coef;
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;
}
// 不定元への代入
[[nodiscard]] 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;
}
[[nodiscard]] MFPS operator>>(int d) const { return MFPS(*this) >>= d; }
[[nodiscard]] MFPS operator<<(int d) const { return MFPS(*this) <<= d; }
#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] << "z^" << i;
if (i < f.n - 1) os << " + ";
}
}
return os;
}
#endif
};
mint bostan_mori(MFPS f, MFPS g, ll N) {
Assert(g.n >= 1 && g[0] != 0);
if (f.n == 0) return 0;
while (N > 0) {
MFPS f2, g2 = g;
rep(i, g2.n) if (i & 1) g2[i] *= -1;
f2 = f * g2;
g2 *= g;
f.c.clear(); g.c.clear();
if (N & 1) rep(i, min<ll>(f2.n / 2, N / 2 + 1)) f.c.push_back(f2[2 * i + 1]);
else rep(i, min<ll>((f2.n + 1) / 2, N / 2 + 1)) f.c.push_back(f2[2 * i]);
f.n = sz(f.c);
rep(i, min<ll>((g2.n + 1) / 2, N / 2 + 1)) g.c.push_back(g2[2 * i]);
g.n = sz(g.c);
N /= 2;
}
return f[0] / g[0];
}
mint linearly_recurrent_sequence(const vm& a, const vm& c, ll N) {
int n = sz(c);
if (n == 0) return 0;
MFPS A(a), C(c);
MFPS Dnm = 1 - (C >> 1);
MFPS Num = (Dnm * A).resize(n);
return bostan_mori(Num, Dnm, N);
}
vm berlekamp_massey(const vm& a) {
vm S(a), C{ 1 }, B{ 1 };
int N = sz(a), m = 1; mint b = 1;
rep(n, N) {
mint d = 0;
rep(i, sz(C)) d += C[i] * S[n - i];
if (d == 0) {
m++;
}
else if (2 * (sz(C) - 1) <= n) {
vm T(C);
mint coef = d * b.inv();
C.resize(max(sz(C), sz(B) + m));
rep(j, sz(B)) C[j + m] -= coef * B[j];
B = T;
b = d;
m = 1;
}
else {
mint coef = d * b.inv();
C.resize(max(sz(C), sz(B) + m));
rep(j, sz(B)) C[j + m] -= coef * B[j];
m++;
}
}
C.erase(C.begin());
rep(i, sz(C)) C[i] *= -1;
return C;
}
constexpr ll MOD = mint::mod();
template <class T>
T ceil_mod(T x, T m, T k) {
Assert(m > 0);
return x + smod(k - x, m);
}
constexpr int W = 25000000;
vector<tuple<ll, int, int>> ume = { {0,0,1},{1,764543027,454585878},{2,777013155,146959755},{3,768752844,291612233},{4,17726935,552881368},{5,551954533,832965},{6,831721102,388606335},{7,308264413,105230497},{8,246537908,832965},{9,799405076,388606335},{10,447337383,105230497},{11,939365636,832965},{12,767089050,388606335},{13,586410353,105230497},{14,633949011,832965},{15,734773024,388606335},{16,725483323,105230497},{17,328532386,832965},{18,702456998,388606335},{19,864556293,105230497},{20,23115761,832965},{21,670140972,388606335},{22,5384910,105230497},{23,715943489,832965},{24,637824946,388606335},{25,144457880,105230497},{26,410526864,832965},{27,605508920,388606335},{28,283530850,105230497},{29,105110239,832965},{30,573192894,388606335},{31,422603820,105230497},{32,797937967,832965},{33,540876868,388606335},{34,561676790,105230497},{35,492521342,832965},{36,508560842,388606335},{37,700749760,105230497},{38,187104717,832965},{39,476244816,388606335},{40,959515685,54060617},{41,363208465,554300453},{42,425196529,272484286},{43,198578853,625022133},{44,52531933,554300453},{45,237380508,272484286},{46,713567476,625022133},{47,740099754,554300453},{48,49564487,272484286},{49,230311746,625022133},{50,429423222,554300453},{51,859992819,272484286},{52,745300369,625022133},{53,118746690,554300453},{54,672176798,272484286},{55,262044639,625022133},{56,806314511,554300453},{57,484360777,272484286},{58,777033262,625022133},{59,495637979,554300453},{60,296544756,272484286},{61,293777532,625022133},{62,184961447,554300453},{63,108728735,272484286},{64,808766155,625022133},{65,872529268,554300453},{66,919157067,272484286},{67,325510425,625022133},{68,561852736,554300453},{69,731341046,272484286},{70,840499048,625022133},{71,251176204,554300453},{72,543525025,272484286},{73,357243318,625022133},{74,938744025,554300453},{75,355709004,272484286},{76,872231941,625022133},{77,628067493,554300453},{78,167892983,272484286},{79,388976211,625022133},{80,317390961,554300453},{81,978321315,272484286},{82,903964834,625022133},{83,6714429,554300453},{84,790505294,272484286},{85,420709104,625022133},{86,694282250,554300453},{87,602689273,272484286},{88,935697727,625022133},{89,383605718,554300453},{90,414873252,272484286},{91,452441997,625022133},{92,72929186,554300453},{93,227057231,272484286},{94,967430620,625022133},{95,760497007,554300453},{96,39241210,272484286},{97,484174890,625022133},{98,449820475,554300453},{99,849669542,272484286},{100,919160,625022133},{101,139143943,554300453},{102,661853521,272484286},{103,515907783,625022133},{104,826711764,554300453},{105,474037500,272484286},{106,32652053,625022133},{107,516035232,554300453},{108,286221479,272484286},{109,547640676,625022133},{110,205358700,554300453},{111,98405458,272484286},{112,64384946,625022133},{113,892926521,554300453},{114,908833790,272484286},{115,579373569,625022133},{116,582249989,554300453},{117,721017769,272484286},{118,96117839,625022133},{119,271573457,554300453},{120,533201748,272484286},{121,611106462,625022133},{122,959141278,554300453},{123,345385727,272484286},{124,127850732,625022133},{125,648464746,554300453},{126,157569706,272484286},{127,642839355,625022133},{128,337788214,554300453},{129,967998038,272484286},{130,159583625,625022133},{131,27111682,554300453},{132,780182017,272484286},{133,674572248,625022133},{134,714679503,554300453},{135,592365996,272484286},{136,191316518,625022133},{137,404002971,554300453},{138,404549975,272484286},{139,706305141,625022133},{140,93326439,554300453},{141,216733954,272484286},{142,223049411,625022133},{143,780894260,554300453},{144,28917933,272484286},{145,738038034,625022133},{146,470217728,554300453},{147,839346265,272484286},{148,254782304,625022133},{149,159541196,554300453},{150,651530244,272484286},{151,769770927,625022133},{152,847109017,554300453},{153,463714223,272484286},{154,286515197,625022133},{155,536432485,554300453},{156,275898202,272484286},{157,801503820,625022133},{158,225755953,554300453},{159,88082181,272484286},{160,318248090,625022133},{161,913323774,554300453},{162,898510513,272484286},{163,833236713,625022133},{164,602647242,554300453},{165,710694492,272484286},{166,349980983,625022133},{167,291970710,554300453},{168,522878471,272484286},{169,864969606,625022133},{170,979538531,554300453},{171,335062450,272484286},{172,381713876,625022133},{173,668861999,554300453},{174,147246429,272484286},{175,896702499,625022133},{176,358185467,554300453},{177,957674761,272484286},{178,413446769,625022133},{179,47508935,554300453},{180,769858740,272484286},{181,928435392,625022133},{182,735076756,554300453},{183,582042719,272484286},{184,445179662,625022133},{185,424400224,554300453},{186,394226698,272484286},{187,960168285,625022133},{188,113723692,554300453},{189,206410677,272484286},{190,476912555,625022133},{191,801291513,554300453},{192,18594656,272484286},{193,991901178,625022133},{194,490614981,554300453},{195,829022988,272484286},{196,508645448,625022133},{197,179938449,554300453},{198,641206967,272484286},{199,25389718,625022133},{200,867506270,554300453},{201,453390946,272484286},{202,540378341,625022133},{203,556829738,554300453},{204,265574925,272484286},{205,57122611,625022133},{206,246153206,554300453},{207,77758904,272484286},{208,572111234,625022133},{209,933721027,554300453},{210,888187236,272484286},{211,88855504,625022133},{212,623044495,554300453},{213,700371215,272484286},{214,603844127,625022133},{215,312367963,554300453},{216,512555194,272484286},{217,120588397,625022133},{218,1691431,554300453},{219,324739173,272484286},{220,635577020,625022133},{221,689259252,554300453},{222,136923152,272484286},{223,152321290,625022133},{224,378582720,554300453},{225,947351484,272484286},{226,667309913,625022133},{227,67906188,554300453},{228,759535463,272484286},{229,184054183,625022133},{230,755474009,554300453},{231,571719442,272484286},{232,699042806,625022133},{233,444797477,554300453},{234,383903421,272484286},{235,215787076,625022133},{236,134120945,554300453},{237,196087400,272484286},{238,730775699,625022133},{239,821688766,554300453},{240,8271379,272484286},{241,247519969,625022133},{242,511012234,554300453},{243,818699711,272484286},{244,762508592,625022133},{245,200335702,554300453},{246,630883690,272484286},{247,279252862,625022133},{248,887903523,554300453},{249,443067669,272484286},{250,794241485,625022133},{251,577226991,554300453},{252,255251648,272484286},{253,310985755,625022133},{254,266550459,554300453},{255,67435627,272484286},{256,825974378,625022133},{257,954118280,554300453},{258,877863959,272484286},{259,342718648,625022133},{260,643441748,554300453},{261,690047938,272484286},{262,857707271,625022133},{263,332765216,554300453},{264,502231917,272484286},{265,374451541,625022133},{266,22088684,554300453},{267,314415896,272484286},{268,889440164,625022133},{269,709656505,554300453},{270,126599875,272484286},{271,406184434,625022133},{272,398979973,554300453},{273,937028207,272484286},{274,921173057,625022133},{275,88303441,554300453},{276,749212186,272484286},{277,437917327,625022133},{278,775871262,554300453},{279,561396165,272484286},{280,952905950,625022133},{281,465194730,554300453},{282,373580144,272484286},{283,469650220,625022133},{284,154518198,554300453},{285,185764123,272484286},{286,984638843,625022133},{287,842086019,554300453},{288,996192455,272484286},{289,501383113,625022133},{290,531409487,554300453},{291,808376434,272484286},{292,18127383,625022133},{293,220732955,554300453},{294,620560413,272484286},{295,533116006,625022133},{296,908300776,554300453},{297,432744392,272484286},{298,49860276,625022133},{299,597624244,554300453},{300,244928371,272484286},{301,564848899,625022133},{302,286947712,554300453},{303,57112350,272484286},{304,81593169,625022133},{305,974515533,554300453},{306,867540682,272484286},{307,596581792,625022133},{308,663839001,554300453},{309,679724661,272484286},{310,113326062,625022133},{311,353162469,554300453},{312,491908640,272484286},{313,628314685,625022133},{314,42485937,554300453},{315,304092619,272484286},{316,145058955,625022133},{317,730053758,554300453},{318,116276598,272484286},{319,660047578,625022133},{320,419377226,554300453},{321,926704930,272484286},{322,176791848,625022133},{323,108700694,554300453},{324,738888909,272484286},{325,691780471,625022133},{326,796268515,554300453},{327,551072888,272484286},{328,208524741,625022133},{329,485591983,554300453},{330,363256867,272484286},{331,723513364,625022133},{332,174915451,554300453},{333,175440846,272484286},{334,240257634,625022133},{335,862483272,554300453},{336,985869178,272484286},{337,755246257,625022133},{338,551806740,554300453},{339,798053157,272484286},{340,271990527,625022133},{341,241130208,554300453},{342,610237136,272484286},{343,786979150,625022133},{344,928698029,554300453},{345,422421115,272484286},{346,303723420,625022133},{347,618021497,554300453},{348,234605094,272484286},{349,818712043,625022133},{350,307344965,554300453},{351,46789073,272484286},{352,335456313,625022133},{353,994912786,554300453},{354,857217405,272484286},{355,850444936,625022133},{356,684236254,554300453},{357,669401384,272484286},{358,367189206,625022133},{359,373559722,554300453},{360,481585363,272484286},{361,882177829,625022133},{362,62883190,554300453},{363,293769342,272484286},{364,398922099,625022133},{365,750451011,554300453},{366,105953321,272484286},{367,913910722,625022133},{368,439774479,554300453},{369,916381653,272484286},{370,430654992,625022133},{371,129097947,554300453},{372,728565632,272484286},{373,945643615,625022133},{374,816665768,554300453},{375,540749611,272484286},{376,462387885,625022133},{377,505989236,554300453},{378,352933590,272484286},{379,977376508,625022133},{380,195312704,554300453},{381,165117569,272484286},{382,494120778,625022133},{383,882880525,554300453},{384,975545901,272484286},{385,10865048,625022133},{386,572203993,554300453},{387,787729880,272484286},{388,525853671,625022133},{389,261527461,554300453},{390,599913859,272484286},{391,42597941,625022133},{392,949095282,554300453},{393,412097838,272484286},{394,557586564,625022133},{395,638418750,554300453},{396,224281817,272484286},{397,74330834,625022133},{398,327742218,554300453},{399,36465796,272484286},{400,452808495,260755212},{401,604495730,918128181},{402,273793190,742073240},{403,80167818,786664565},{404,810089271,918128181},{405,780026145,742073240},{406,241368233,786664565},{407,17438459,918128181},{408,288014747,742073240},{409,402568648,786664565},{410,223032000,918128181},{411,794247702,742073240},{412,563769063,786664565},{413,428625541,918128181},{414,302236304,742073240},{415,724969478,786664565},{416,634219082,918128181},{417,808469259,742073240},{418,886169893,786664565},{419,839812623,918128181},{420,316457861,742073240},{421,49125955,786664565},{422,47161811,918128181},{423,822690816,742073240},{424,210326370,786664565},{425,252755352,918128181},{426,330679418,742073240},{427,371526785,786664565},{428,458348893,918128181},{429,836912373,742073240},{430,532727200,786664565},{431,663942434,918128181},{432,344900975,742073240},{433,693927615,786664565},{434,869535975,918128181},{435,851133930,742073240},{436,855128030,786664565},{437,76885163,918128181},{438,359122532,742073240},{439,18084092,786664565},{440,282478704,918128181},{441,865355487,742073240},{442,179284507,786664565},{443,488072245,918128181},{444,373344089,742073240},{445,340484922,786664565},{446,693665786,918128181},{447,879577044,742073240},{448,501685337,786664565},{449,899259327,918128181},{450,387565646,742073240},{451,662885752,786664565},{452,106608515,918128181},{453,893798601,742073240},{454,824086167,786664565},{455,312202056,918128181},{456,401787203,742073240},{457,985286582,786664565},{458,517795597,918128181},{459,908020158,742073240},{460,148242644,786664565},{461,723389138,918128181},{462,416008760,742073240},{463,309443059,786664565},{464,928982679,918128181},{465,922241715,742073240},{466,470643474,786664565},{467,136331867,918128181},{468,430230317,742073240},{469,631843889,786664565},{470,341925408,918128181},{471,936463272,742073240},{472,793044304,786664565},{473,547518949,918128181},{474,444451874,742073240},{475,954244719,786664565},{476,753112490,918128181},{477,950684829,742073240},{478,117200781,786664565},{479,958706031,918128181},{480,458673431,742073240},{481,278401196,786664565},{482,166055219,918128181},{483,964906386,742073240},{484,439601611,786664565},{485,371648760,918128181},{486,472894988,742073240},{487,600802026,786664565},{488,577242301,918128181},{489,979127943,742073240},{490,762002441,786664565},{491,782835842,918128181},{492,487116545,742073240},{493,923202856,786664565},{494,988429383,918128181},{495,993349500,742073240},{496,86158918,786664565},{497,195778571,918128181},{498,501338102,742073240},{499,247359333,786664565},{500,401372112,918128181},{501,9326704,742073240},{502,408559748,786664565},{503,606965653,918128181},{504,515559659,742073240},{505,569760163,786664565},{506,812559194,918128181},{507,23548261,742073240},{508,730960578,786664565},{509,19908382,918128181},{510,529781216,742073240},{511,892160993,786664565},{512,225501923,918128181},{513,37769818,742073240},{514,55117055,786664565},{515,431095464,918128181},{516,544002773,742073240},{517,216317470,786664565},{518,636689005,918128181},{519,51991375,742073240},{520,377517885,786664565},{521,842282546,918128181},{522,558224330,742073240},{523,538718300,786664565},{524,49631734,918128181},{525,66212932,742073240},{526,699918715,786664565},{527,255225275,918128181},{528,572445887,742073240},{529,861119130,786664565},{530,460818816,918128181},{531,80434489,742073240},{532,24075192,786664565},{533,666412357,918128181},{534,586667444,742073240},{535,185275607,786664565},{536,872005898,918128181},{537,94656046,742073240},{538,346476022,786664565},{539,79355086,918128181},{540,600889001,742073240},{541,507676437,786664565},{542,284948627,918128181},{543,108877603,742073240},{544,668876852,786664565},{545,490542168,918128181},{546,615110558,742073240},{547,830077267,786664565},{548,696135709,918128181},{549,123099160,742073240},{550,991277682,786664565},{551,901729250,918128181},{552,629332115,742073240},{553,154233744,786664565},{554,109078438,918128181},{555,137320717,742073240},{556,315434159,786664565},{557,314671979,918128181},{558,643553672,742073240},{559,476634574,786664565},{4000,289239342,172110981},{4001,963083125,829189135},{4002,152582383,230676405},{4003,46165237,608061349},{4004,235995305,829189135},{4005,691423322,230676405},{4006,661285143,608061349},{4007,507151838,829189135},{4008,232019908,230676405},{4009,278160696,608061349},{4010,778308371,829189135},{4011,770860847,230676405},{4012,893280602,608061349},{4013,51220551,829189135},{4014,311457433,230676405},{4015,510156155,608061349},{4016,322377084,829189135},{4017,850298372,230676405},{4018,127031708,608061349},{4019,593533617,829189135},{4020,390894958,230676405},{4021,742151614,608061349},{4022,864690150,829189135},{4023,929735897,230676405},{4024,359027167,608061349},{4025,137602330,829189135},{4026,470332483,230676405},{4027,974147073,608061349},{4028,408758863,829189135},{4029,10929069,230676405},{4030,591022626,608061349},{4031,679915396,829189135},{4032,549770008,230676405},{4033,207898179,608061349},{4034,951071929,829189135},{4035,90366594,230676405},{4036,823018085,608061349},{4037,223984109,829189135},{4038,629207533,230676405},{4039,439893638,608061349},{4040,495140642,829189135},{4041,169804119,230676405},{4042,56769191,608061349},{4043,766297175,829189135},{4044,708645058,230676405},{4045,671889097,608061349},{4046,39209355,829189135},{4047,249241644,230676405},{4048,288764650,608061349},{4049,310365888,829189135},{4050,788082583,230676405},{4051,903884556,608061349},{4052,581522421,829189135},{4053,328679169,230676405},{4054,520760109,608061349},{4055,852678954,829189135},{4056,867520108,230676405},{4057,137635662,608061349},{4058,125591134,829189135},{4059,408116694,230676405},{4060,752755568,608061349},{4061,396747667,829189135},{4062,946957633,230676405},{4063,369631121,608061349},{4064,667904200,829189135},{4065,487554219,230676405},{4066,984751027,608061349},{4067,939060733,829189135},{4068,28150805,230676405},{4069,601626580,608061349},{4070,211972913,829189135},{4071,566991744,230676405},{4072,218502133,608061349},{4073,483129446,829189135},{4074,107588330,230676405},{4075,833622039,608061349},{4076,754285979,829189135},{4077,646429269,230676405},{4078,450497592,608061349},{4079,27198159,829189135},{4080,187025855,230676405},{4081,67373145,608061349},{4082,298354692,829189135},{4083,725866794,230676405},{4084,682493051,608061349},{4085,569511225,829189135},{4086,266463380,230676405},{4087,299368604,608061349},{4088,840667758,829189135},{4089,805304319,230676405},{4090,914488510,608061349},{4091,113579938,829189135},{4092,345900905,230676405},{4093,531364063,608061349},{4094,384736471,829189135},{4095,884741844,230676405},{4096,148239616,608061349},{4097,655893004,829189135},{4098,425338430,230676405},{4099,763359522,608061349},{4100,927049537,829189135},{4101,964179369,230676405},{4102,380235075,608061349},{4103,199961717,829189135},{4104,504775955,230676405},{4105,995354981,608061349},{4106,471118250,829189135},{4107,45372541,230676405},{4108,612230534,608061349},{4109,742274783,829189135},{4110,584213480,230676405},{4111,229106087,608061349},{4112,15186963,829189135},{4113,124810066,230676405},{4114,844225993,608061349},{4115,286343496,829189135},{4116,663651005,230676405},{4117,461101546,608061349},{4118,557500029,829189135},{4119,204247591,230676405},{4120,77977099,608061349},{4121,828656562,829189135},{4122,743088530,230676405},{4123,693097005,608061349},{4124,101568742,829189135},{4125,283685116,230676405},{4126,309972558,608061349},{4127,372725275,829189135},{4128,822526055,230676405},{4129,925092464,608061349},{4130,643881808,829189135},{4131,363122641,230676405},{4132,541968017,608061349},{4133,915038341,829189135},{4134,901963580,230676405},{4135,158843570,608061349},{4136,187950521,829189135},{4137,442560166,230676405},{4138,773963476,608061349},{4139,459107054,829189135},{4140,981401105,230676405},{4141,390839029,608061349},{4142,730263587,829189135},{4143,521997691,230676405},{4144,7714582,608061349},{4145,3175767,829189135},{4146,62594277,230676405},{4147,622834488,608061349},{4148,274332300,829189135},{4149,601435216,230676405},{4150,239710041,608061349},{4151,545488833,829189135},{4152,142031802,230676405},{4153,854829947,608061349},{4154,816645366,829189135},{4155,680872741,230676405},{4156,471705500,608061349},{4157,89557546,829189135},{4158,221469327,230676405},{4159,88581053,608061349},{40000,921571010,259947456},{40001,933178416,830139174},{40002,889482658,319624688},{40003,141179162,28630196},{40004,281884077,830139174},{40005,399279338,319624688},{40006,765653643,28630196},{40007,628834091,830139174},{40008,907320371,319624688},{40009,391883771,28630196},{40010,975784105,830139174},{40011,417117051,319624688},{40012,18113899,28630196},{40013,324489766,830139174},{40014,925158084,319624688},{40015,642588380,28630196},{40016,671439780,830139174},{40017,434954764,319624688},{40018,268818508,28630196},{40019,20145441,830139174},{40020,942995797,319624688},{40021,893292989,28630196},{40022,367095455,830139174},{40023,452792477,319624688},{40024,519523117,28630196},{40025,714045469,830139174},{40026,960833510,319624688},{40027,145753245,28630196},{40028,62751130,830139174},{40029,470630190,319624688},{40030,770227726,28630196},{40031,409701144,830139174},{40032,978671223,319624688},{40033,396457854,28630196},{40034,756651158,830139174},{40035,488467903,319624688},{40036,22687982,28630196},{40037,105356819,830139174},{40038,996508936,319624688},{40039,647162463,28630196},{40040,452306833,830139174},{40041,506305616,319624688},{40042,273392591,28630196},{40043,799256847,830139174},{40044,16102296,319624688},{40045,897867072,28630196},{40046,147962508,830139174},{40047,524143329,319624688},{40048,524097200,28630196},{40049,494912522,830139174},{40050,33940009,319624688},{40051,150327328,28630196},{40052,841862536,830139174},{40053,541981042,319624688},{40054,774801809,28630196},{40055,190568197,830139174},{40056,51777722,319624688},{40057,401031937,28630196},{40058,537518211,830139174},{40059,559818755,319624688},{40060,27262065,28630196},{40061,884468225,830139174},{40062,69615435,319624688},{40063,651736546,28630196},{40064,233173886,830139174},{40065,577656468,319624688},{40066,277966674,28630196},{40067,580123900,830139174},{40068,87453148,319624688},{40069,902441155,28630196},{40070,927073914,830139174},{40071,595494181,319624688},{40072,528671283,28630196},{40073,275779575,830139174},{40074,105290861,319624688},{40075,154901411,28630196},{40076,622729589,830139174},{40077,613331894,319624688},{40078,779375892,28630196},{40079,969679603,830139174},{40080,123128574,319624688},{40081,405606020,28630196},{40082,318385264,830139174},{40083,631169607,319624688},{40084,31836148,28630196},{40085,665335278,830139174},{40086,140966287,319624688},{40087,656310629,28630196},{40088,14040939,830139174},{40089,649007320,319624688},{40090,282540757,28630196},{40091,360990953,830139174},{40092,158804000,319624688},{40093,907015238,28630196},{40094,707940967,830139174},{40095,666845033,319624688},{40096,533245366,28630196},{40097,56646628,830139174},{40098,176641713,319624688},{40099,159475494,28630196},{40100,403596642,830139174},{40101,684682746,319624688},{40102,783949975,28630196},{40103,750546656,830139174},{40104,194479426,319624688},{40105,410180103,28630196},{40106,99252317,830139174},{40107,702520459,319624688},{40108,36410231,28630196},{40109,446202331,830139174},{40110,212317139,319624688},{40111,660884712,28630196},{40112,793152345,830139174},{40113,720358172,319624688},{40114,287114840,28630196},{40115,141858006,830139174},{40116,230154852,319624688},{40117,911589321,28630196},{40118,488808020,830139174},{40119,738195885,319624688},{40120,537819449,28630196},{40121,835758034,830139174},{40122,247992565,319624688},{40123,164049577,28630196},{40124,184463695,830139174},{40125,756033598,319624688},{40126,788524058,28630196},{40127,531413709,830139174},{40128,265830278,319624688},{40129,414754186,28630196},{40130,878363723,830139174},{40131,773871311,319624688},{40132,40984314,28630196},{40133,227069384,830139174},{40134,283667991,319624688},{40135,665458795,28630196},{40136,574019398,830139174},{40137,791709024,319624688},{40138,291688923,28630196},{40139,920969412,830139174},{40140,301505704,319624688},{40141,916163404,28630196},{40142,269675073,830139174},{40143,809546737,319624688},{40144,542393532,28630196},{40145,616625087,830139174},{40146,319343417,319624688},{40147,168623660,28630196},{40148,963575101,830139174},{40149,827384450,319624688},{40150,793098141,28630196},{40151,312280762,830139174},{40152,337181130,319624688},{40153,419328269,28630196},{40154,659230776,830139174},{40155,845222163,319624688},{40156,45558397,28630196},{40157,7936437,830139174},{40158,355018843,319624688},{40159,670032878,28630196},{400000,993975902,201513821},{400001,188516766,433194245},{400002,828306434,764883719},{400003,157733196,855975806},{400004,883050501,433194245},{400005,458175473,764883719},{400006,157469850,855975806},{400007,579339883,433194245},{400008,88044512,764883719},{400009,157206504,855975806},{400010,275629265,433194245},{400011,716157904,764883719},{400012,156943158,855975806},{400013,970163000,433194245},{400014,346026943,764883719},{400015,156679812,855975806},{400016,666452382,433194245},{400017,974140335,764883719},{400018,156416466,855975806},{400019,362741764,433194245},{400020,604009374,764883719},{400021,156153120,855975806},{400022,59031146,433194245},{400023,233878413,764883719},{400024,155889774,855975806},{400025,753564881,433194245},{400026,861991805,764883719},{400027,155626428,855975806},{400028,449854263,433194245},{400029,491860844,764883719},{400030,155363082,855975806},{400031,146143645,433194245},{400032,121729883,764883719},{400033,155099736,855975806},{400034,840677380,433194245},{400035,749843275,764883719},{400036,154836390,855975806},{400037,536966762,433194245},{400038,379712314,764883719},{400039,154573044,855975806},{400040,233256144,433194245},{400041,9581353,764883719},{400042,154309698,855975806},{400043,927789879,433194245},{400044,637694745,764883719},{400045,154046352,855975806},{400046,624079261,433194245},{400047,267563784,764883719},{400048,153783006,855975806},{400049,320368643,433194245},{400050,895677176,764883719},{400051,153519660,855975806},{400052,16658025,433194245},{400053,525546215,764883719},{400054,153256314,855975806},{400055,711191760,433194245},{400056,155415254,764883719},{400057,152992968,855975806},{400058,407481142,433194245},{400059,783528646,764883719},{400060,152729622,855975806},{400061,103770524,433194245},{400062,413397685,764883719},{400063,152466276,855975806},{400064,798304259,433194245},{400065,43266724,764883719},{400066,152202930,855975806},{400067,494593641,433194245},{400068,671380116,764883719},{400069,151939584,855975806},{400070,190883023,433194245},{400071,301249155,764883719},{400072,151676238,855975806},{400073,885416758,433194245},{400074,929362547,764883719},{400075,151412892,855975806},{400076,581706140,433194245},{400077,559231586,764883719},{400078,151149546,855975806},{400079,277995522,433194245},{400080,189100625,764883719},{400081,150886200,855975806},{400082,972529257,433194245},{400083,817214017,764883719},{400084,150622854,855975806},{400085,668818639,433194245},{400086,447083056,764883719},{400087,150359508,855975806},{400088,365108021,433194245},{400089,76952095,764883719},{400090,150096162,855975806},{400091,61397403,433194245},{400092,705065487,764883719},{400093,149832816,855975806},{400094,755931138,433194245},{400095,334934526,764883719},{400096,149569470,855975806},{400097,452220520,433194245},{400098,963047918,764883719},{400099,149306124,855975806},{400100,148509902,433194245},{400101,592916957,764883719},{400102,149042778,855975806},{400103,843043637,433194245},{400104,222785996,764883719},{400105,148779432,855975806},{400106,539333019,433194245},{400107,850899388,764883719},{400108,148516086,855975806},{400109,235622401,433194245},{400110,480768427,764883719},{400111,148252740,855975806},{400112,930156136,433194245},{400113,110637466,764883719},{400114,147989394,855975806},{400115,626445518,433194245},{400116,738750858,764883719},{400117,147726048,855975806},{400118,322734900,433194245},{400119,368619897,764883719},{400120,147462702,855975806},{400121,19024282,433194245},{400122,996733289,764883719},{400123,147199356,855975806},{400124,713558017,433194245},{400125,626602328,764883719},{400126,146936010,855975806},{400127,409847399,433194245},{400128,256471367,764883719},{400129,146672664,855975806},{400130,106136781,433194245},{400131,884584759,764883719},{400132,146409318,855975806},{400133,800670516,433194245},{400134,514453798,764883719},{400135,146145972,855975806},{400136,496959898,433194245},{400137,144322837,764883719},{400138,145882626,855975806},{400139,193249280,433194245},{400140,772436229,764883719},{400141,145619280,855975806},{400142,887783015,433194245},{400143,402305268,764883719},{400144,145355934,855975806},{400145,584072397,433194245},{400146,32174307,764883719},{400147,145092588,855975806},{400148,280361779,433194245},{400149,660287699,764883719},{400150,144829242,855975806},{400151,974895514,433194245},{400152,290156738,764883719},{400153,144565896,855975806},{400154,671184896,433194245},{400155,918270130,764883719},{400156,144302550,855975806},{400157,367474278,433194245},{400158,548139169,764883719},{400159,144039204,855975806},{4000000,68566775,962513783},{4000001,644681423,212653925},{4000002,52489718,212653925},{4000003,458542366,212653925},{4000004,864595014,212653925},{4000005,272403309,212653925},{4000006,678455957,212653925},{4000007,86264252,212653925},{4000008,492316900,212653925},{4000009,898369548,212653925},{4000010,306177843,212653925},{4000011,712230491,212653925},{4000012,120038786,212653925},{4000013,526091434,212653925},{4000014,932144082,212653925},{4000015,339952377,212653925},{4000016,746005025,212653925},{4000017,153813320,212653925},{4000018,559865968,212653925},{4000019,965918616,212653925},{4000020,373726911,212653925},{4000021,779779559,212653925},{4000022,187587854,212653925},{4000023,593640502,212653925},{4000024,1448797,212653925},{4000025,407501445,212653925},{4000026,813554093,212653925},{4000027,221362388,212653925},{4000028,627415036,212653925},{4000029,35223331,212653925},{4000030,441275979,212653925},{4000031,847328627,212653925},{4000032,255136922,212653925},{4000033,661189570,212653925},{4000034,68997865,212653925},{4000035,475050513,212653925},{4000036,881103161,212653925},{4000037,288911456,212653925},{4000038,694964104,212653925},{4000039,102772399,212653925},{4000040,508825047,212653925},{4000041,914877695,212653925},{4000042,322685990,212653925},{4000043,728738638,212653925},{4000044,136546933,212653925},{4000045,542599581,212653925},{4000046,948652229,212653925},{4000047,356460524,212653925},{4000048,762513172,212653925},{4000049,170321467,212653925},{4000050,576374115,212653925},{4000051,982426763,212653925},{4000052,390235058,212653925},{4000053,796287706,212653925},{4000054,204096001,212653925},{4000055,610148649,212653925},{4000056,17956944,212653925},{4000057,424009592,212653925},{4000058,830062240,212653925},{4000059,237870535,212653925},{4000060,643923183,212653925},{4000061,51731478,212653925},{4000062,457784126,212653925},{4000063,863836774,212653925},{4000064,271645069,212653925},{4000065,677697717,212653925},{4000066,85506012,212653925},{4000067,491558660,212653925},{4000068,897611308,212653925},{4000069,305419603,212653925},{4000070,711472251,212653925},{4000071,119280546,212653925},{4000072,525333194,212653925},{4000073,931385842,212653925},{4000074,339194137,212653925},{4000075,745246785,212653925},{4000076,153055080,212653925},{4000077,559107728,212653925},{4000078,965160376,212653925},{4000079,372968671,212653925},{4000080,779021319,212653925},{4000081,186829614,212653925},{4000082,592882262,212653925},{4000083,690557,212653925},{4000084,406743205,212653925},{4000085,812795853,212653925},{4000086,220604148,212653925},{4000087,626656796,212653925},{4000088,34465091,212653925},{4000089,440517739,212653925},{4000090,846570387,212653925},{4000091,254378682,212653925},{4000092,660431330,212653925},{4000093,68239625,212653925},{4000094,474292273,212653925},{4000095,880344921,212653925},{4000096,288153216,212653925},{4000097,694205864,212653925},{4000098,102014159,212653925},{4000099,508066807,212653925},{4000100,914119455,212653925},{4000101,321927750,212653925},{4000102,727980398,212653925},{4000103,135788693,212653925},{4000104,541841341,212653925},{4000105,947893989,212653925},{4000106,355702284,212653925},{4000107,761754932,212653925},{4000108,169563227,212653925},{4000109,575615875,212653925},{4000110,981668523,212653925},{4000111,389476818,212653925},{4000112,795529466,212653925},{4000113,203337761,212653925},{4000114,609390409,212653925},{4000115,17198704,212653925},{4000116,423251352,212653925},{4000117,829304000,212653925},{4000118,237112295,212653925},{4000119,643164943,212653925},{4000120,50973238,212653925},{4000121,457025886,212653925},{4000122,863078534,212653925},{4000123,270886829,212653925},{4000124,676939477,212653925},{4000125,84747772,212653925},{4000126,490800420,212653925},{4000127,896853068,212653925},{4000128,304661363,212653925},{4000129,710714011,212653925},{4000130,118522306,212653925},{4000131,524574954,212653925},{4000132,930627602,212653925},{4000133,338435897,212653925},{4000134,744488545,212653925},{4000135,152296840,212653925},{4000136,558349488,212653925},{4000137,964402136,212653925},{4000138,372210431,212653925},{4000139,778263079,212653925},{4000140,186071374,212653925},{4000141,592124022,212653925},{4000142,998176670,212653925},{4000143,405984965,212653925},{4000144,812037613,212653925},{4000145,219845908,212653925},{4000146,625898556,212653925},{4000147,33706851,212653925},{4000148,439759499,212653925},{4000149,845812147,212653925},{4000150,253620442,212653925},{4000151,659673090,212653925},{4000152,67481385,212653925},{4000153,473534033,212653925},{4000154,879586681,212653925},{4000155,287394976,212653925},{4000156,693447624,212653925},{4000157,101255919,212653925},{4000158,507308567,212653925},{4000159,913361215,212653925},{40000000,495190683,674533918},{40000001,280931537,682072758},{40000002,305168847,566739441},{40000003,705973450,872965089},{40000004,921113492,682072758},{40000005,386710747,566739441},{40000006,380252719,872965089},{40000007,563051094,682072758},{40000008,468252647,566739441},{40000009,54531988,872965089},{40000010,204988696,682072758},{40000011,549794547,566739441},{40000012,727055610,872965089},{40000013,845170651,682072758},{40000014,631336447,566739441},{40000015,401334879,872965089},{40000016,487108253,682072758},{40000017,712878347,566739441},{40000018,75614148,872965089},{40000019,129045855,682072758},{40000020,794420247,566739441},{40000021,748137770,872965089},{40000022,769227810,682072758},{40000023,875962147,566739441},{40000024,422417039,872965089},{40000025,411165412,682072758},{40000026,957504047,566739441},{40000027,96696308,872965089},{40000028,53103014,682072758},{40000029,40801594,566739441},{40000030,769219930,872965089},{40000031,693284969,682072758},{40000032,122343494,566739441},{40000033,443499199,872965089},{40000034,335222571,682072758},{40000035,203885394,566739441},{40000036,117778468,872965089},{40000037,975404526,682072758},{40000038,285427294,566739441},{40000039,790302090,872965089},{40000040,617342128,682072758},{40000041,366969194,566739441},{40000042,464581359,872965089},{40000043,259279730,682072758},{40000044,448511094,566739441},{40000045,138860628,872965089},{40000046,899461685,682072758},{40000047,530052994,566739441},{40000048,811384250,872965089},{40000049,541399287,682072758},{40000050,611594894,566739441},{40000051,485663519,872965089},{40000052,183336889,682072758},{40000053,693136794,566739441},{40000054,159942788,872965089},{40000055,823518844,682072758},{40000056,774678694,566739441},{40000057,832466410,872965089},{40000058,465456446,682072758},{40000059,856220594,566739441},{40000060,506745679,872965089},{40000061,107394048,682072758},{40000062,937762494,566739441},{40000063,181024948,872965089},{40000064,747576003,682072758},{40000065,21060041,566739441},{40000066,853548570,872965089},{40000067,389513605,682072758},{40000068,102601941,566739441},{40000069,527827839,872965089},{40000070,31451207,682072758},{40000071,184143841,566739441},{40000072,202107108,872965089},{40000073,671633162,682072758},{40000074,265685741,566739441},{40000075,874630730,872965089},{40000076,313570764,682072758},{40000077,347227641,566739441},{40000078,548909999,872965089},{40000079,953752719,682072758},{40000080,428769541,566739441},{40000081,223189268,872965089},{40000082,595690321,682072758},{40000083,510311441,566739441},{40000084,895712890,872965089},{40000085,237627923,682072758},{40000086,591853341,566739441},{40000087,569992159,872965089},{40000088,877809878,682072758},{40000089,673395241,566739441},{40000090,244271428,872965089},{40000091,519747480,682072758},{40000092,754937141,566739441},{40000093,916795050,872965089},{40000094,161685082,682072758},{40000095,836479041,566739441},{40000096,591074319,872965089},{40000097,801867037,682072758},{40000098,918020941,566739441},{40000099,265353588,872965089},{40000100,443804639,682072758},{40000101,1318488,566739441},{40000102,937877210,872965089},{40000103,85742241,682072758},{40000104,82860388,566739441},{40000105,612156479,872965089},{40000106,725924196,682072758},{40000107,164402288,566739441},{40000108,286435748,872965089},{40000109,367861798,682072758},{40000110,245944188,566739441},{40000111,958959370,872965089},{40000112,9799400,682072758},{40000113,327486088,566739441},{40000114,633238639,872965089},{40000115,649981355,682072758},{40000116,409027988,566739441},{40000117,307517908,872965089},{40000118,291918957,682072758},{40000119,490569888,566739441},{40000120,980041530,872965089},{40000121,932100912,682072758},{40000122,572111788,566739441},{40000123,654320799,872965089},{40000124,574038514,682072758},{40000125,653653688,566739441},{40000126,328600068,872965089},{40000127,215976116,682072758},{40000128,735195588,566739441},{40000129,2879337,872965089},{40000130,856158071,682072758},{40000131,816737488,566739441},{40000132,675402959,872965089},{40000133,498095673,682072758},{40000134,898279388,566739441},{40000135,349682228,872965089},{40000136,140033275,682072758},{40000137,979821288,566739441},{40000138,23961497,872965089},{40000139,780215230,682072758},{40000140,63118835,566739441},{40000141,696485119,872965089},{40000142,422152832,682072758},{40000143,144660735,566739441},{40000144,370764388,872965089},{40000145,64090434,682072758},{40000146,226202635,566739441},{40000147,45043657,872965089},{40000148,704272389,682072758},{40000149,307744535,566739441},{40000150,717567279,872965089},{40000151,346209991,682072758},{40000152,389286435,566739441},{40000153,391846548,872965089},{40000154,986391946,682072758},{40000155,470828335,566739441},{40000156,66125817,872965089},{40000157,628329548,682072758},{40000158,552370235,566739441},{40000159,738649439,872965089},{400000000,486061618,676172645},{400000001,966120183,893958233},{400000002,195684939,749797754},{400000003,259999880,58647338},{400000004,757665084,893958233},{400000005,742008032,749797754},{400000006,784884197,58647338},{400000007,549209985,893958233},{400000008,290086772,749797754},{400000009,311524161,58647338},{400000010,340754886,893958233},{400000011,836409865,749797754},{400000012,836408478,58647338},{400000013,132299787,893958233},{400000014,384488605,749797754},{400000015,363048442,58647338},{400000016,922089041,893958233},{400000017,930811698,749797754},{400000018,887932759,58647338},{400000019,713633942,893958233},{400000020,478890438,749797754},{400000021,414572723,58647338},{400000022,505178843,893958233},{400000023,26969178,749797754},{400000024,939457040,58647338},{400000025,296723744,893958233},{400000026,573292271,749797754},{400000027,466097004,58647338},{400000028,88268645,893958233},{400000029,121371011,749797754},{400000030,990981321,58647338},{400000031,878057899,893958233},{400000032,667694104,749797754},{400000033,517621285,58647338},{400000034,669602800,893958233},{400000035,215772844,749797754},{400000036,44261249,58647338},{400000037,461147701,893958233},{400000038,762095937,749797754},{400000039,569145566,58647338},{400000040,252692602,893958233},{400000041,310174677,749797754},{400000042,95785530,58647338},{400000043,44237503,893958233},{400000044,856497770,749797754},{400000045,620669847,58647338},{400000046,834026757,893958233},{400000047,404576510,749797754},{400000048,147309811,58647338},{400000049,625571658,893958233},{400000050,950899603,749797754},{400000051,672194128,58647338},{400000052,417116559,893958233},{400000053,498978343,749797754},{400000054,198834092,58647338},{400000055,208661460,893958233},{400000056,47057083,749797754},{400000057,723718409,58647338},{400000058,206361,893958233},{400000059,593380176,749797754},{400000060,250358373,58647338},{400000061,789995615,893958233},{400000062,141458916,749797754},{400000063,775242690,58647338},{400000064,581540516,893958233},{400000065,687782009,749797754},{400000066,301882654,58647338},{400000067,373085417,893958233},{400000068,235860749,749797754},{400000069,826766971,58647338},{400000070,164630318,893958233},{400000071,782183842,749797754},{400000072,353406935,58647338},{400000073,954419572,893958233},{400000074,330262582,749797754},{400000075,878291252,58647338},{400000076,745964473,893958233},{400000077,876585675,749797754},{400000078,404931216,58647338},{400000079,537509374,893958233},{400000080,424664415,749797754},{400000081,929815533,58647338},{400000082,329054275,893958233},{400000083,970987508,749797754},{400000084,456455497,58647338},{400000085,120599176,893958233},{400000086,519066248,749797754},{400000087,981339814,58647338},{400000088,910388430,893958233},{400000089,67144988,749797754},{400000090,507979778,58647338},{400000091,701933331,893958233},{400000092,613468081,749797754},{400000093,34619742,58647338},{400000094,493478232,893958233},{400000095,161546821,749797754},{400000096,559504059,58647338},{400000097,285023133,893958233},{400000098,707869914,749797754},{400000099,86144023,58647338},{400000100,76568034,893958233},{400000101,255948654,749797754},{400000102,611028340,58647338},{400000103,866357288,893958233},{400000104,802271747,749797754},{400000105,137668304,58647338},{400000106,657902189,893958233},{400000107,350350487,749797754},{400000108,662552621,58647338},{400000109,449447090,893958233},{400000110,896673580,749797754},{400000111,189192585,58647338},{400000112,240991991,893958233},{400000113,444752320,749797754},{400000114,714076902,58647338},{400000115,32536892,893958233},{400000116,991075413,749797754},{400000117,240716866,58647338},{400000118,822326146,893958233},{400000119,539154153,749797754},{400000120,765601183,58647338},{400000121,613871047,893958233},{400000122,87232893,749797754},{400000123,292241147,58647338},{400000124,405415948,893958233},{400000125,633555986,749797754},{400000126,817125464,58647338},{400000127,196960849,893958233},{400000128,181634726,749797754},{400000129,343765428,58647338},{400000130,986750103,893958233},{400000131,727957819,749797754},{400000132,868649745,58647338},{400000133,778295004,893958233},{400000134,276036559,749797754},{400000135,395289709,58647338},{400000136,569839905,893958233},{400000137,822359652,749797754},{400000138,920174026,58647338},{400000139,361384806,893958233},{400000140,370438392,749797754},{400000141,446813990,58647338},{400000142,152929707,893958233},{400000143,916761485,749797754},{400000144,971698307,58647338},{400000145,942718961,893958233},{400000146,464840225,749797754},{400000147,498338271,58647338},{400000148,734263862,893958233},{400000149,12918965,749797754},{400000150,24978235,58647338},{400000151,525808763,893958233},{400000152,559242058,749797754},{400000153,549862552,58647338},{400000154,317353664,893958233},{400000155,107320798,749797754},{400000156,76502516,58647338},{400000157,108898565,893958233},{400000158,653643891,749797754},{400000159,601386833,58647338},{4000000000,563731795,101991780},{4000000001,521128628,80081571},{4000000002,189714572,80081571},{4000000003,856544869,80081571},{4000000004,525130813,80081571},{4000000005,193716757,80081571},{4000000006,860547054,80081571},{4000000007,529132998,80081571},{4000000008,197718942,80081571},{4000000009,864549239,80081571},{4000000010,533135183,80081571},{4000000011,201721127,80081571},{4000000012,868551424,80081571},{4000000013,537137368,80081571},{4000000014,205723312,80081571},{4000000015,872553609,80081571},{4000000016,541139553,80081571},{4000000017,209725497,80081571},{4000000018,876555794,80081571},{4000000019,545141738,80081571},{4000000020,213727682,80081571},{4000000021,880557979,80081571},{4000000022,549143923,80081571},{4000000023,217729867,80081571},{4000000024,884560164,80081571},{4000000025,553146108,80081571},{4000000026,221732052,80081571},{4000000027,888562349,80081571},{4000000028,557148293,80081571},{4000000029,225734237,80081571},{4000000030,892564534,80081571},{4000000031,561150478,80081571},{4000000032,229736422,80081571},{4000000033,896566719,80081571},{4000000034,565152663,80081571},{4000000035,233738607,80081571},{4000000036,900568904,80081571},{4000000037,569154848,80081571},{4000000038,237740792,80081571},{4000000039,904571089,80081571},{4000000040,573157033,80081571},{4000000041,241742977,80081571},{4000000042,908573274,80081571},{4000000043,577159218,80081571},{4000000044,245745162,80081571},{4000000045,912575459,80081571},{4000000046,581161403,80081571},{4000000047,249747347,80081571},{4000000048,916577644,80081571},{4000000049,585163588,80081571},{4000000050,253749532,80081571},{4000000051,920579829,80081571},{4000000052,589165773,80081571},{4000000053,257751717,80081571},{4000000054,924582014,80081571},{4000000055,593167958,80081571},{4000000056,261753902,80081571},{4000000057,928584199,80081571},{4000000058,597170143,80081571},{4000000059,265756087,80081571},{4000000060,932586384,80081571},{4000000061,601172328,80081571},{4000000062,269758272,80081571},{4000000063,936588569,80081571},{4000000064,605174513,80081571},{4000000065,273760457,80081571},{4000000066,940590754,80081571},{4000000067,609176698,80081571},{4000000068,277762642,80081571},{4000000069,944592939,80081571},{4000000070,613178883,80081571},{4000000071,281764827,80081571},{4000000072,948595124,80081571},{4000000073,617181068,80081571},{4000000074,285767012,80081571},{4000000075,952597309,80081571},{4000000076,621183253,80081571},{4000000077,289769197,80081571},{4000000078,956599494,80081571},{4000000079,625185438,80081571},{4000000080,293771382,80081571},{4000000081,960601679,80081571},{4000000082,629187623,80081571},{4000000083,297773567,80081571},{4000000084,964603864,80081571},{4000000085,633189808,80081571},{4000000086,301775752,80081571},{4000000087,968606049,80081571},{4000000088,637191993,80081571},{4000000089,305777937,80081571},{4000000090,972608234,80081571},{4000000091,641194178,80081571},{4000000092,309780122,80081571},{4000000093,976610419,80081571},{4000000094,645196363,80081571},{4000000095,313782307,80081571},{4000000096,980612604,80081571},{4000000097,649198548,80081571},{4000000098,317784492,80081571},{4000000099,984614789,80081571},{4000000100,653200733,80081571},{4000000101,321786677,80081571},{4000000102,988616974,80081571},{4000000103,657202918,80081571},{4000000104,325788862,80081571},{4000000105,992619159,80081571},{4000000106,661205103,80081571},{4000000107,329791047,80081571},{4000000108,996621344,80081571},{4000000109,665207288,80081571},{4000000110,333793232,80081571},{4000000111,2379176,80081571},{4000000112,669209473,80081571},{4000000113,337795417,80081571},{4000000114,6381361,80081571},{4000000115,673211658,80081571},{4000000116,341797602,80081571},{4000000117,10383546,80081571},{4000000118,677213843,80081571},{4000000119,345799787,80081571},{4000000120,14385731,80081571},{4000000121,681216028,80081571},{4000000122,349801972,80081571},{4000000123,18387916,80081571},{4000000124,685218213,80081571},{4000000125,353804157,80081571},{4000000126,22390101,80081571},{4000000127,689220398,80081571},{4000000128,357806342,80081571},{4000000129,26392286,80081571},{4000000130,693222583,80081571},{4000000131,361808527,80081571},{4000000132,30394471,80081571},{4000000133,697224768,80081571},{4000000134,365810712,80081571},{4000000135,34396656,80081571},{4000000136,701226953,80081571},{4000000137,369812897,80081571},{4000000138,38398841,80081571},{4000000139,705229138,80081571},{4000000140,373815082,80081571},{4000000141,42401026,80081571},{4000000142,709231323,80081571},{4000000143,377817267,80081571},{4000000144,46403211,80081571},{4000000145,713233508,80081571},{4000000146,381819452,80081571},{4000000147,50405396,80081571},{4000000148,717235693,80081571},{4000000149,385821637,80081571},{4000000150,54407581,80081571},{4000000151,721237878,80081571},{4000000152,389823822,80081571},{4000000153,58409766,80081571},{4000000154,725240063,80081571},{4000000155,393826007,80081571},{4000000156,62411951,80081571},{4000000157,729242248,80081571},{4000000158,397828192,80081571},{4000000159,66414136,80081571},{40000000000,531807397,256551991} };
mint solve(ll N) {
vl p10(18 + 1);
repi(i, 0, 18) p10[i] = powi(10, i);
int i = ubpos(ume, make_tuple(N / W, INF, INF)) - 1;
auto [N0, r_, pow10_] = ume[i];
N0 *= W;
if (N - N0 <= W) {
mint r = r_;
mint pow10 = pow10_;
for (ll n = N0 + 1; n <= N; n++) {
string s = to_string(n);
int l = sz(s);
ll p = p10[l];
r = r * (pow10 * p + 1) + n * pow10;
pow10 = pow10 * pow10 * p;
}
return r;
}
else {
string s = to_string(N);
int l = sz(s);
ll N00 = ceil_mod<ll>(p10[l - 1] + W, MOD, N);
dump("N00:", N00);
vm a;
rep(k, 4) {
ll N2 = N00 + MOD * k;
int i = ubpos(ume, make_tuple(N2 / W, INF, INF)) - 1;
auto [N0, r_, pow10_] = ume[i];
N0 *= W;
dump(N0, N2);
mint r = r_;
mint pow10 = pow10_;
for (ll n = N0 + 1; n <= N2; n++) {
string s = to_string(n);
int l = sz(s);
ll p = p10[l];
r = r * (pow10 * p + 1) + n * pow10;
pow10 = pow10 * pow10 * p;
}
a.push_back(r);
}
dump("a:", a);
auto c = berlekamp_massey(a);
a.resize(sz(c));
dump("a:", a); dump("c:", c);
ll D = N - N00;
ll Q = D / MOD;
dump("D:", D, "Q:", Q);
mint res = linearly_recurrent_sequence(a, c, Q);
return res;
}
return 0;
}
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
// zikken10();
// umekomi();
ll n;
cin >> n;
assert(n <= 9876543210);
cout << solve(n) << endl;
}