#ifndef HIDDEN_IN_VS // 折りたたみ用 #define _CRT_SECURE_NO_WARNINGS #include 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; using pll = pair; using pil = pair; using pli = pair; using vi = vector; using vvi = vector; using vvvi = vector; using vvvvi = vector; using vl = vector; using vvl = vector; using vvvl = vector; using vvvvl = vector; 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) #define repe(v, a) for(const auto& v : (a)) // 汎用関数の定義 template inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; } #endif // 折りたたみ用 #if __has_include() #include using namespace atcoder; #ifdef _MSC_VER #include "localACL.hpp" #endif using mint = modint998244353; 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; using vvm = vector; using vvvm = vector; using vvvvm = vector; using pim = pair; #endif #ifdef _MSC_VER #include "local.hpp" #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) : 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) #endif mint bostan_mori(vm f, vm g, ll N) { if (sz(f) == 0) return 0; while (N > 0) { vm f2, g2 = g; rep(i, sz(g2)) if (i & 1) g2[i] *= -1; f2 = convolution(f, g2); g2 = convolution(g2, g); f.clear(); g.clear(); if (N & 1) rep(i, min(sz(f2) / 2, N / 2 + 1)) f.push_back(f2[2 * i + 1]); else rep(i, min((sz(f2) + 1) / 2, N / 2 + 1)) f.push_back(f2[2 * i]); rep(i, min((sz(g2) + 1) / 2, N / 2 + 1)) g.push_back(g2[2 * i]); 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; vm Dnm(n + 1); Dnm[0] = 1; repi(i, 1, n) Dnm[i] = -c[i - 1]; vm Num = convolution(Dnm, a); Num.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 T ceil_mod(T x, T m, T k) { Assert(m > 0); return x + ((k - x) % m + m) % m; } vector> ume = { {0,0,1},{2,638929461,146959755},{4,328433164,454585878},{6,333903256,291612233},{8,915096849,146959755},{10,17726935,552881368},{12,46052030,388606335},{14,490871208,832965},{16,280449819,105230497},{18,619145821,388606335},{20,246537908,832965},{22,391708195,105230497},{24,193995259,388606335},{26,2204608,832965},{28,502966571,105230497},{30,767089050,388606335},{32,756115661,832965},{34,614224947,105230497},{36,341938488,388606335},{38,511782361,832965},{40,725483323,105230497},{42,915032279,388606335},{44,267449061,832965},{46,836741699,105230497},{48,489881717,388606335},{50,23115761,832965},{52,948000075,105230497},{54,64731155,388606335},{56,777026814,832965},{58,61014098,105230497},{60,637824946,388606335},{62,532693514,832965},{64,172272474,105230497},{66,212674384,388606335},{68,288360214,832965},{70,283530850,105230497},{72,785768175,388606335},{74,44026914,832965},{76,394789226,105230497},{78,360617613,388606335},{80,797937967,832965},{82,506047602,105230497},{84,933711404,388606335},{86,553604667,832965},{88,617305978,105230497},{90,508560842,388606335},{92,309271367,832965},{94,728564354,105230497},{96,83410280,388606335},{98,64938067,832965},{100,959515685,54060617},{102,699971808,272484286},{104,101424288,554300453},{106,295229999,625022133},{108,150421250,272484286},{110,52531933,554300453},{112,906869768,625022133},{114,599115045,272484286},{116,3639578,554300453},{118,520265184,625022133},{120,49564487,272484286},{122,952991576,554300453},{124,133660600,625022133},{126,498258282,272484286},{128,904099221,554300453},{130,745300369,625022133},{132,946952077,272484286},{134,855206866,554300453},{136,358695785,625022133},{138,397401519,272484286},{140,806314511,554300453},{142,970335554,625022133},{144,846095314,272484286},{146,757422156,554300453},{148,583730970,625022133},{150,296544756,272484286},{152,708529801,554300453},{154,197126386,625022133},{156,745238551,272484286},{158,659637446,554300453},{160,808766155,625022133},{162,195687993,272484286},{164,610745091,554300453},{166,422161571,625022133},{168,644381788,272484286},{170,561852736,554300453},{172,35556987,625022133},{174,94831230,272484286},{176,512960381,554300453},{178,647196756,625022133},{180,543525025,272484286},{182,464068026,554300453},{184,260592172,625022133},{186,992218820,272484286},{188,415175671,554300453},{190,872231941,625022133},{192,442668262,272484286},{194,366283316,554300453},{196,485627357,625022133},{198,891362057,272484286},{200,317390961,554300453},{202,99022773,625022133},{204,341811499,272484286},{206,268498606,554300453},{208,710662542,625022133},{210,790505294,272484286},{212,219606251,554300453},{214,324057958,625022133},{216,240954736,272484286},{218,170713896,554300453},{220,935697727,625022133},{222,689648531,272484286},{224,121821541,554300453},{226,549093143,625022133},{228,140097973,272484286},{230,72929186,554300453},{232,162488559,625022133},{234,588791768,272484286},{236,24036831,554300453},{238,774128328,625022133},{240,39241210,272484286},{242,973388829,554300453},{244,387523744,625022133},{246,487935005,272484286},{248,924496474,554300453},{250,919160,625022133},{252,936628800,272484286},{254,875604119,554300453},{256,612558929,625022133},{258,387078242,272484286},{260,826711764,554300453},{262,225954345,625022133},{264,835772037,272484286},{266,777819409,554300453},{268,837594114,625022133},{270,286221479,272484286},{272,728927054,554300453},{274,450989530,625022133},{276,734915274,272484286},{278,680034699,554300453},{280,64384946,625022133},{282,185364716,272484286},{284,631142344,554300453},{286,676024715,625022133},{288,634058511,272484286},{290,582249989,554300453},{292,289420131,625022133},{294,84507953,272484286},{296,533357634,554300453},{298,901059900,625022133},{300,533201748,272484286},{302,484465279,554300453},{304,514455316,625022133},{306,981895543,272484286},{308,435572924,554300453},{310,127850732,625022133},{312,432344985,272484286},{314,386680569,554300453},{316,739490501,625022133},{318,881038780,272484286},{320,337788214,554300453},{322,352885917,625022133},{324,331488222,272484286},{326,288895859,554300453},{328,964525686,625022133},{330,780182017,272484286},{332,240003504,554300453},{334,577921102,625022133},{336,230631459,272484286},{338,191111149,554300453},{340,191316518,625022133},{342,679325254,272484286},{344,142218794,554300453},{346,802956287,625022133},{348,129774696,272484286},{350,93326439,554300453},{352,416351703,625022133},{354,578468491,272484286},{356,44434084,554300453},{358,29747119,625022133},{360,28917933,272484286},{362,993786082,554300453},{364,641386888,625022133},{366,477611728,272484286},{368,944893727,554300453},{370,254782304,625022133},{372,926305523,272484286},{374,896001372,554300453},{376,866422073,625022133},{378,376754965,272484286},{380,847109017,554300453},{382,479817489,625022133},{384,825448760,272484286},{386,798216662,554300453},{388,93212905,625022133},{390,275898202,272484286},{392,749324307,554300453},{394,704852674,625022133},{396,724591997,272484286},{398,700431952,554300453},{400,318248090,625022133},{402,175041439,272484286},{404,651539597,554300453},{406,929887859,625022133},{408,623735234,272484286},{410,602647242,554300453},{412,543283275,625022133},{414,74184676,272484286},{416,553754887,554300453},{418,156678691,625022133},{420,522878471,272484286},{422,504862532,554300453},{424,768318460,625022133},{426,971572266,272484286},{428,455970177,554300453},{430,381713876,625022133},{432,422021708,272484286},{434,407077822,554300453},{436,993353645,625022133},{438,870715503,272484286},{440,358185467,554300453},{442,606749061,625022133},{444,321164945,272484286},{446,309293112,554300453},{448,220144477,625022133},{450,769858740,272484286},{452,260400757,554300453},{454,831784246,625022133},{456,220308182,272484286},{458,211508402,554300453},{460,445179662,625022133},{462,669001977,272484286},{464,162616047,554300453},{466,58575078,625022133},{468,119451419,272484286},{470,113723692,554300453},{472,670214847,625022133},{474,568145214,272484286},{476,64831337,554300453},{478,283610263,625022133},{480,18594656,272484286},{482,15938982,554300453},{484,895250032,625022133},{486,467288451,272484286},{488,965290980,554300453},{490,508645448,625022133},{492,915982246,272484286},{494,916398625,554300453},{496,122040864,625022133},{498,366431688,272484286},{1000,821362827,723063855},{1002,180949063,987279182},{1004,812596146,917814425},{1006,838939353,765036093},{1008,746332710,987279182},{1010,10377836,917814425},{1012,694022366,765036093},{1014,313472004,987279182},{1016,206403879,917814425},{1018,549105379,765036093},{1020,878855651,987279182},{1022,402429922,917814425},{1024,404188392,765036093},{1026,445994945,987279182},{1028,598455965,917814425},{1030,259271405,765036093},{1032,13134239,987279182},{1034,794482008,917814425},{1036,114354418,765036093},{1038,578517886,987279182},{1040,990508051,917814425},{1042,967681784,765036093},{1044,145657180,987279182},{1046,188289741,917814425},{1048,822764797,765036093},{1050,711040827,987279182},{1052,384315784,917814425},{1054,677847810,765036093},{1056,278180121,987279182},{1058,580341827,917814425},{1060,532930823,765036093},{1062,843563768,987279182},{1064,776367870,917814425},{1066,388013836,765036093},{1068,410703062,987279182},{1070,972393913,917814425},{1072,243096849,765036093},{1074,976086709,987279182},{1076,170175603,917814425},{1078,98179862,765036093},{1080,543226003,987279182},{1082,366201646,917814425},{1084,951507228,765036093},{1086,110365297,987279182},{1088,562227689,917814425},{1090,806590241,765036093},{1092,675748944,987279182},{1094,758253732,917814425},{1096,661673254,765036093},{1098,242888238,987279182},{1100,954279775,917814425},{1102,516756267,765036093},{1104,808271885,987279182},{1106,152061465,917814425},{1108,371839280,765036093},{1110,375411179,987279182},{1112,348087508,917814425},{1114,226922293,765036093},{1116,940794826,987279182},{1118,544113551,917814425},{1120,82005306,765036093},{1122,507934120,987279182},{1124,740139594,917814425},{1126,935332672,765036093},{1128,75073414,987279182},{1130,936165637,917814425},{1132,790415685,765036093},{1134,640457061,987279182},{1136,133947327,917814425},{1138,645498698,765036093},{1140,207596355,987279182},{1142,329973370,917814425},{1144,500581711,765036093},{1146,772980002,987279182},{1148,525999413,917814425},{1150,355664724,765036093},{1152,340119296,987279182},{1154,722025456,917814425},{1156,210747737,765036093},{1158,905502943,987279182},{1160,918051499,917814425},{1162,65830750,765036093},{1164,472642237,987279182},{1166,115833189,917814425},{1168,919158116,765036093},{1170,39781531,987279182},{1172,311859232,917814425},{1174,774241129,765036093},{1176,605165178,987279182},{1178,507885275,917814425},{1180,629324142,765036093},{1182,172304472,987279182},{1184,703911318,917814425},{1186,484407155,765036093},{1188,737688119,987279182},{1190,899937361,917814425},{1192,339490168,765036093},{1194,304827413,987279182},{1196,97719051,917814425},{1198,194573181,765036093},{1200,870211060,987279182},{1202,293745094,917814425},{1204,49656194,765036093},{1206,437350354,987279182},{1208,489771137,917814425},{1210,902983560,765036093},{1212,4489648,987279182},{1214,685797180,917814425},{1216,758066573,765036093},{1218,569873295,987279182},{1220,881823223,917814425},{1222,613149586,765036093},{1224,137012589,987279182},{1226,79604913,917814425},{1228,468232599,765036093},{1230,702396236,987279182},{1232,275630956,917814425},{1234,323315612,765036093},{1236,269535530,987279182},{1238,471656999,917814425},{1240,178398625,765036093},{1242,834919177,987279182},{1244,667683042,917814425},{1246,33481638,765036093},{1248,402058471,987279182},{1250,863709085,917814425},{1252,886809004,765036093},{1254,967442118,987279182},{1256,61490775,917814425},{1258,741892017,765036093},{1260,534581412,987279182},{1262,257516818,917814425},{1264,596975030,765036093},{1266,101720706,987279182},{1268,453542861,917814425},{1270,452058043,765036093},{1272,667104353,987279182},{1274,649568904,917814425},{1276,307141056,765036093},{1278,234243647,987279182},{1280,845594947,917814425},{1282,162224069,765036093},{1284,799627294,987279182},{1286,43376637,917814425},{1288,17307082,765036093},{1290,366766588,987279182},{1292,239402680,917814425},{1294,870634448,765036093},{1296,932150235,987279182},{1298,435428723,917814425},{1300,725717461,765036093},{1302,499289529,987279182},{1304,631454766,917814425},{1306,580800474,765036093},{1308,66428823,987279182},{1310,827480809,917814425},{1312,435883487,765036093},{1314,631812470,987279182},{1316,25262499,917814425},{1318,290966500,765036093},{1320,198951764,987279182},{1322,221288542,917814425},{1324,146049513,765036093},{1326,764335411,987279182},{1328,417314585,917814425},{1330,1132526,765036093},{1332,331474705,987279182},{1334,613340628,917814425},{1336,854459892,765036093},{1338,896858352,987279182},{1340,809366671,917814425},{1342,709542905,765036093},{1344,463997646,987279182},{1346,7148361,917814425},{1348,564625918,765036093},{1350,31136940,987279182},{1352,203174404,917814425},{1354,419708931,765036093},{1356,596520587,987279182},{1358,399200447,917814425},{1360,274791944,765036093},{1362,163659881,987279182},{1364,595226490,917814425},{1366,129874957,765036093},{1368,729043528,987279182},{1370,791252533,917814425},{1372,983202323,765036093},{1374,296182822,987279182},{1376,987278576,917814425},{1378,838285336,765036093},{1380,861566469,987279182},{1382,185060266,917814425},{1384,693368349,765036093},{1386,428705763,987279182},{1388,381086309,917814425},{1390,548451362,765036093},{1392,994089410,987279182},{1394,577112352,917814425},{1396,403534375,765036093},{1398,561228704,987279182},{10000,524366650,602985854},{10002,493230547,201513821},{10004,161434916,315436916},{10006,27985124,286301960},{10008,564581399,201513821},{10010,940546322,315436916},{10012,32559207,286301960},{10014,635932251,201513821},{10016,721413375,315436916},{10018,37133290,286301960},{10020,707283103,201513821},{10022,502280428,315436916},{10024,41707373,286301960},{10026,778633955,201513821},{10028,283147481,315436916},{10030,46281456,286301960},{10032,849984807,201513821},{10034,64014534,315436916},{10036,50855539,286301960},{10038,921335659,201513821},{10040,843125940,315436916},{10042,55429622,286301960},{10044,992686511,201513821},{10046,623992993,315436916},{10048,60003705,286301960},{10050,65793010,201513821},{10052,404860046,315436916},{10054,64577788,286301960},{10056,137143862,201513821},{10058,185727099,315436916},{10060,69151871,286301960},{10062,208494714,201513821},{10064,964838505,315436916},{10066,73725954,286301960},{10068,279845566,201513821},{10070,745705558,315436916},{10072,78300037,286301960},{10074,351196418,201513821},{10076,526572611,315436916},{10078,82874120,286301960},{10080,422547270,201513821},{10082,307439664,315436916},{10084,87448203,286301960},{10086,493898122,201513821},{10088,88306717,315436916},{10090,92022286,286301960},{10092,565248974,201513821},{10094,867418123,315436916},{10096,96596369,286301960},{10098,636599826,201513821},{10100,648285176,315436916},{10102,101170452,286301960},{10104,707950678,201513821},{10106,429152229,315436916},{10108,105744535,286301960},{10110,779301530,201513821},{10112,210019282,315436916},{10114,110318618,286301960},{10116,850652382,201513821},{10118,989130688,315436916},{10120,114892701,286301960},{10122,922003234,201513821},{10124,769997741,315436916},{10126,119466784,286301960},{10128,993354086,201513821},{10130,550864794,315436916},{10132,124040867,286301960},{10134,66460585,201513821},{10136,331731847,315436916},{10138,128614950,286301960},{10140,137811437,201513821},{10142,112598900,315436916},{10144,133189033,286301960},{10146,209162289,201513821},{10148,891710306,315436916},{10150,137763116,286301960},{10152,280513141,201513821},{10154,672577359,315436916},{10156,142337199,286301960},{10158,351863993,201513821},{10160,453444412,315436916},{10162,146911282,286301960},{10164,423214845,201513821},{10166,234311465,315436916},{10168,151485365,286301960},{10170,494565697,201513821},{10172,15178518,315436916},{10174,156059448,286301960},{10176,565916549,201513821},{10178,794289924,315436916},{10180,160633531,286301960},{10182,637267401,201513821},{10184,575156977,315436916},{10186,165207614,286301960},{10188,708618253,201513821},{10190,356024030,315436916},{10192,169781697,286301960},{10194,779969105,201513821},{10196,136891083,315436916},{10198,174355780,286301960},{10200,851319957,201513821},{10202,916002489,315436916},{10204,178929863,286301960},{10206,922670809,201513821},{10208,696869542,315436916},{10210,183503946,286301960},{10212,994021661,201513821},{10214,477736595,315436916},{10216,188078029,286301960},{10218,67128160,201513821},{10220,258603648,315436916},{10222,192652112,286301960},{10224,138479012,201513821},{10226,39470701,315436916},{10228,197226195,286301960},{10230,209829864,201513821},{10232,818582107,315436916},{10234,201800278,286301960},{10236,281180716,201513821},{10238,599449160,315436916},{10240,206374361,286301960},{10242,352531568,201513821},{10244,380316213,315436916},{10246,210948444,286301960},{10248,423882420,201513821},{10250,161183266,315436916},{10252,215522527,286301960},{10254,495233272,201513821},{10256,940294672,315436916},{10258,220096610,286301960},{10260,566584124,201513821},{10262,721161725,315436916},{10264,224670693,286301960},{10266,637934976,201513821},{10268,502028778,315436916},{10270,229244776,286301960},{10272,709285828,201513821},{10274,282895831,315436916},{10276,233818859,286301960},{10278,780636680,201513821},{10280,63762884,315436916},{10282,238392942,286301960},{10284,851987532,201513821},{10286,842874290,315436916},{10288,242967025,286301960},{10290,923338384,201513821},{10292,623741343,315436916},{10294,247541108,286301960},{10296,994689236,201513821},{10298,404608396,315436916},{10300,252115191,286301960},{10302,67795735,201513821},{10304,185475449,315436916},{10306,256689274,286301960},{10308,139146587,201513821},{10310,964586855,315436916},{10312,261263357,286301960},{10314,210497439,201513821},{10316,745453908,315436916},{10318,265837440,286301960},{10320,281848291,201513821},{10322,526320961,315436916},{10324,270411523,286301960},{10326,353199143,201513821},{10328,307188014,315436916},{10330,274985606,286301960},{10332,424549995,201513821}, { 10334, 88055067, 315436916 }, { 10336,279559689,286301960 }, { 10338,495900847,201513821 }, { 10340,867166473,315436916 }, { 10342,284133772,286301960 }, { 10344,567251699,201513821 }, { 10346,648033526,315436916 }, { 10348,288707855,286301960 }, { 10350,638602551,201513821 }, { 10352,428900579,315436916 }, { 10354,293281938,286301960 }, { 10356,709953403,201513821 }, { 10358,209767632,315436916 }, { 10360,297856021,286301960 }, { 10362,781304255,201513821 }, { 10364,988879038,315436916 }, { 10366,302430104,286301960 }, { 10368,852655107,201513821 }, { 10370,769746091,315436916 }, { 10372,307004187,286301960 }, { 10374,924005959,201513821 }, { 10376,550613144,315436916 }, { 10378,311578270,286301960 }, { 10380,995356811,201513821 }, { 10382,331480197,315436916 }, { 10384,316152353,286301960 }, { 10386,68463310,201513821 }, { 10388,112347250,315436916 }, { 10390,320726436,286301960 }, { 10392,139814162,201513821 }, { 10394,891458656,315436916 }, { 10396,325300519,286301960 }, { 10398,211165014,201513821 }, { 100000,822319949,866530894 }, { 100002,517763441,338965038 }, { 100004,526419412,573803236 }, { 100006,581550976,661126719 }, { 100008,84567203,338965038 }, { 100010,524312644,573803236 }, { 100012,615236347,661126719 }, { 100014,649615318,338965038 }, { 100016,522205876,573803236 }, { 100018,648921718,661126719 }, { 100020,216419080,338965038 }, { 100022,520099108,573803236 }, { 100024,682607089,661126719 }, { 100026,781467195,338965038 }, { 100028,517992340,573803236 }, { 100030,716292460,661126719 }, { 100032,348270957,338965038 }, { 100034,515885572,573803236 }, { 100036,749977831,661126719 }, { 100038,913319072,338965038 }, { 100040,513778804,573803236 }, { 100042,783663202,661126719 }, { 100044,480122834,338965038 }, { 100046,511672036,573803236 }, { 100048,817348573,661126719 }, { 100050,46926596,338965038 }, { 100052,509565268,573803236 }, { 100054,851033944,661126719 }, { 100056,611974711,338965038 }, { 100058,507458500,573803236 }, { 100060,884719315,661126719 }, { 100062,178778473,338965038 }, { 100064,505351732,573803236 }, { 100066,918404686,661126719 }, { 100068,743826588,338965038 }, { 100070,503244964,573803236 }, { 100072,952090057,661126719 }, { 100074,310630350,338965038 }, { 100076,501138196,573803236 }, { 100078,985775428,661126719 }, { 100080,875678465,338965038 }, { 100082,499031428,573803236 }, { 100084,21216446,661126719 }, { 100086,442482227,338965038 }, { 100088,496924660,573803236 }, { 100090,54901817,661126719 }, { 100092,9285989,338965038 }, { 100094,494817892,573803236 }, { 100096,88587188,661126719 }, { 100098,574334104,338965038 }, { 100100,492711124,573803236 }, { 100102,122272559,661126719 }, { 100104,141137866,338965038 }, { 100106,490604356,573803236 }, { 100108,155957930,661126719 }, { 100110,706185981,338965038 }, { 100112,488497588,573803236 }, { 100114,189643301,661126719 }, { 100116,272989743,338965038 }, { 100118,486390820,573803236 }, { 100120,223328672,661126719 }, { 100122,838037858,338965038 }, { 100124,484284052,573803236 }, { 100126,257014043,661126719 }, { 100128,404841620,338965038 }, { 100130,482177284,573803236 }, { 100132,290699414,661126719 }, { 100134,969889735,338965038 }, { 100136,480070516,573803236 }, { 100138,324384785,661126719 }, { 100140,536693497,338965038 }, { 100142,477963748,573803236 }, { 100144,358070156,661126719 }, { 100146,103497259,338965038 }, { 100148,475856980,573803236 }, { 100150,391755527,661126719 }, { 100152,668545374,338965038 }, { 100154,473750212,573803236 }, { 100156,425440898,661126719 }, { 100158,235349136,338965038 }, { 100160,471643444,573803236 }, { 100162,459126269,661126719 }, { 100164,800397251,338965038 }, { 100166,469536676,573803236 }, { 100168,492811640,661126719 }, { 100170,367201013,338965038 }, { 100172,467429908,573803236 }, { 100174,526497011,661126719 }, { 100176,932249128,338965038 }, { 100178,465323140,573803236 }, { 100180,560182382,661126719 }, { 100182,499052890,338965038 }, { 100184,463216372,573803236 }, { 100186,593867753,661126719 }, { 100188,65856652,338965038 }, { 100190,461109604,573803236 }, { 100192,627553124,661126719 }, { 100194,630904767,338965038 }, { 100196,459002836,573803236 }, { 100198,661238495,661126719 }, { 100200,197708529,338965038 }, { 100202,456896068,573803236 }, { 100204,694923866,661126719 }, { 100206,762756644,338965038 }, { 100208,454789300,573803236 }, { 100210,728609237,661126719 }, { 100212,329560406,338965038 }, { 100214,452682532,573803236 }, { 100216,762294608,661126719 }, { 100218,894608521,338965038 }, { 100220,450575764,573803236 }, { 100222,795979979,661126719 }, { 100224,461412283,338965038 }, { 100226,448468996,573803236 }, { 100228,829665350,661126719 }, { 100230,28216045,338965038 }, { 100232,446362228,573803236 }, { 100234,863350721,661126719 }, { 100236,593264160,338965038 }, { 100238,444255460,573803236 }, { 100240,897036092,661126719 }, { 100242,160067922,338965038 }, { 100244,442148692,573803236 }, { 100246,930721463,661126719 }, { 100248,725116037,338965038 }, { 100250,440041924,573803236 }, { 100252,964406834,661126719 }, { 100254,291919799,338965038 }, { 100256,437935156,573803236 }, { 100258,998092205,661126719 }, { 100260,856967914,338965038 }, { 100262,435828388,573803236 }, { 100264,33533223,661126719 }, { 100266,423771676,338965038 }, { 100268,433721620,573803236 }, { 100270,67218594,661126719 }, { 100272,988819791,338965038 }, { 100274,431614852,573803236 }, { 100276,100903965,661126719 }, { 100278,555623553,338965038 }, { 100280,429508084,573803236 }, { 100282,134589336,661126719 }, { 100284,122427315,338965038 }, { 100286,427401316,573803236 }, { 100288,168274707,661126719 }, { 100290,687475430,338965038 }, { 100292,425294548,573803236 }, { 100294,201960078,661126719 }, { 100296,254279192,338965038 }, { 100298,423187780,573803236 }, { 100300,235645449,661126719 }, { 100302,819327307,338965038 }, { 100304,421081012,573803236 }, { 100306,269330820,661126719 }, { 100308,386131069,338965038 }, { 100310,418974244,573803236 }, { 100312,303016191,661126719 }, { 100314,951179184,338965038 }, { 100316,416867476,573803236 }, { 100318,336701562,661126719 }, { 100320,517982946,338965038 }, { 100322,414760708,573803236 }, { 100324,370386933,661126719 }, { 100326,84786708,338965038 }, { 100328,412653940,573803236 }, { 100330,404072304,661126719 }, { 100332,649834823,338965038 }, { 100334,410547172,573803236 }, { 100336,437757675,661126719 }, { 100338,216638585,338965038 }, { 100340,408440404,573803236 }, { 100342,471443046,661126719 }, { 100344,781686700,338965038 }, { 100346,406333636,573803236 }, { 100348,505128417,661126719 }, { 100350,348490462,338965038 }, { 100352,404226868,573803236 }, { 100354,538813788,661126719 }, { 100356,913538577,338965038 }, { 100358,402120100,573803236 }, { 100360,572499159,661126719 }, { 100362,480342339,338965038 }, { 100364,400013332,573803236 }, { 100366,606184530,661126719 }, { 100368,47146101,338965038 }, { 100370,397906564,573803236 }, { 100372,639869901,661126719 }, { 100374,612194216,338965038 }, { 100376,395799796,573803236 }, { 100378,673555272,661126719 }, { 100380,178997978,338965038 }, { 100382,393693028,573803236 }, { 100384,707240643,661126719 }, { 100386,744046093,338965038 }, { 100388,391586260,573803236 }, { 100390,740926014,661126719 }, { 100392,310849855,338965038 }, { 100394,389479492,573803236 }, { 100396,774611385,661126719 }, { 100398,875897970,338965038 }, { 1000000,627220691,829189135 }, { 1000002,391334307,122983324 }, { 1000004,139563091,122983324 }, { 1000006,886036228,122983324 }, { 1000008,634265012,122983324 }, { 1000010,382493796,122983324 }, { 1000012,130722580,122983324 }, { 1000014,877195717,122983324 }, { 1000016,625424501,122983324 }, { 1000018,373653285,122983324 }, { 1000020,121882069,122983324 }, { 1000022,868355206,122983324 }, { 1000024,616583990,122983324 }, { 1000026,364812774,122983324 }, { 1000028,113041558,122983324 }, { 1000030,859514695,122983324 }, { 1000032,607743479,122983324 }, { 1000034,355972263,122983324 }, { 1000036,104201047,122983324 }, { 1000038,850674184,122983324 }, { 1000040,598902968,122983324 }, { 1000042,347131752,122983324 }, { 1000044,95360536,122983324 }, { 1000046,841833673,122983324 }, { 1000048,590062457,122983324 }, { 1000050,338291241,122983324 }, { 1000052,86520025,122983324 }, { 1000054,832993162,122983324 }, { 1000056,581221946,122983324 }, { 1000058,329450730,122983324 }, { 1000060,77679514,122983324 }, { 1000062,824152651,122983324 }, { 1000064,572381435,122983324 }, { 1000066,320610219,122983324 }, { 1000068,68839003,122983324 }, { 1000070,815312140,122983324 }, { 1000072,563540924,122983324 }, { 1000074,311769708,122983324 }, { 1000076,59998492,122983324 }, { 1000078,806471629,122983324 }, { 1000080,554700413,122983324 }, { 1000082,302929197,122983324 }, { 1000084,51157981,122983324 }, { 1000086,797631118,122983324 }, { 1000088,545859902,122983324 }, { 1000090,294088686,122983324 }, { 1000092,42317470,122983324 }, { 1000094,788790607,122983324 }, { 1000096,537019391,122983324 }, { 1000098,285248175,122983324 }, { 1000100,33476959,122983324 }, { 1000102,779950096,122983324 }, { 1000104,528178880,122983324 }, { 1000106,276407664,122983324 }, { 1000108,24636448,122983324 }, { 1000110,771109585,122983324 }, { 1000112,519338369,122983324 }, { 1000114,267567153,122983324 }, { 1000116,15795937,122983324 }, { 1000118,762269074,122983324 }, { 1000120,510497858,122983324 }, { 1000122,258726642,122983324 }, { 1000124,6955426,122983324 }, { 1000126,753428563,122983324 }, { 1000128,501657347,122983324 }, { 1000130,249886131,122983324 }, { 1000132,996359268,122983324 }, { 1000134,744588052,122983324 }, { 1000136,492816836,122983324 }, { 1000138,241045620,122983324 }, { 1000140,987518757,122983324 }, { 1000142,735747541,122983324 }, { 1000144,483976325,122983324 }, { 1000146,232205109,122983324 }, { 1000148,978678246,122983324 }, { 1000150,726907030,122983324 }, { 1000152,475135814,122983324 }, { 1000154,223364598,122983324 }, { 1000156,969837735,122983324 }, { 1000158,718066519,122983324 }, { 1000160,466295303,122983324 }, { 1000162,214524087,122983324 }, { 1000164,960997224,122983324 }, { 1000166,709226008,122983324 }, { 1000168,457454792,122983324 }, { 1000170,205683576,122983324 }, { 1000172,952156713,122983324 }, { 1000174,700385497,122983324 }, { 1000176,448614281,122983324 }, { 1000178,196843065,122983324 }, { 1000180,943316202,122983324 }, { 1000182,691544986,122983324 }, { 1000184,439773770,122983324 }, { 1000186,188002554,122983324 }, { 1000188,934475691,122983324 }, { 1000190,682704475,122983324 }, { 1000192,430933259,122983324 }, { 1000194,179162043,122983324 }, { 1000196,925635180,122983324 }, { 1000198,673863964,122983324 }, { 1000200,422092748,122983324 }, { 1000202,170321532,122983324 }, { 1000204,916794669,122983324 }, { 1000206,665023453,122983324 }, { 1000208,413252237,122983324 }, { 1000210,161481021,122983324 }, { 1000212,907954158,122983324 }, { 1000214,656182942,122983324 }, { 1000216,404411726,122983324 }, { 1000218,152640510,122983324 }, { 1000220,899113647,122983324 }, { 1000222,647342431,122983324 }, { 1000224,395571215,122983324 }, { 1000226,143799999,122983324 }, { 1000228,890273136,122983324 }, { 1000230,638501920,122983324 }, { 1000232,386730704,122983324 }, { 1000234,134959488,122983324 }, { 1000236,881432625,122983324 }, { 1000238,629661409,122983324 }, { 1000240,377890193,122983324 }, { 1000242,126118977,122983324 }, { 1000244,872592114,122983324 }, { 1000246,620820898,122983324 }, { 1000248,369049682,122983324 }, { 1000250,117278466,122983324 }, { 1000252,863751603,122983324 }, { 1000254,611980387,122983324 }, { 1000256,360209171,122983324 }, { 1000258,108437955,122983324 }, { 1000260,854911092,122983324 }, { 1000262,603139876,122983324 }, { 1000264,351368660,122983324 }, { 1000266,99597444,122983324 }, { 1000268,846070581,122983324 }, { 1000270,594299365,122983324 }, { 1000272,342528149,122983324 }, { 1000274,90756933,122983324 }, { 1000276,837230070,122983324 }, { 1000278,585458854,122983324 }, { 1000280,333687638,122983324 }, { 1000282,81916422,122983324 }, { 1000284,828389559,122983324 }, { 1000286,576618343,122983324 }, { 1000288,324847127,122983324 }, { 1000290,73075911,122983324 }, { 1000292,819549048,122983324 }, { 1000294,567777832,122983324 }, { 1000296,316006616,122983324 }, { 1000298,64235400,122983324 }, { 1000300,810708537,122983324 }, { 1000302,558937321,122983324 }, { 1000304,307166105,122983324 }, { 1000306,55394889,122983324 }, { 1000308,801868026,122983324 }, { 1000310,550096810,122983324 }, { 1000312,298325594,122983324 }, { 1000314,46554378,122983324 }, { 1000316,793027515,122983324 }, { 1000318,541256299,122983324 }, { 1000320,289485083,122983324 }, { 1000322,37713867,122983324 }, { 1000324,784187004,122983324 }, { 1000326,532415788,122983324 }, { 1000328,280644572,122983324 }, { 1000330,28873356,122983324 }, { 1000332,775346493,122983324 }, { 1000334,523575277,122983324 }, { 1000336,271804061,122983324 }, { 1000338,20032845,122983324 }, { 1000340,766505982,122983324 }, { 1000342,514734766,122983324 }, { 1000344,262963550,122983324 }, { 1000346,11192334,122983324 }, { 1000348,757665471,122983324 }, { 1000350,505894255,122983324 }, { 1000352,254123039,122983324 }, { 1000354,2351823,122983324 }, { 1000356,748824960,122983324 }, { 1000358,497053744,122983324 }, { 1000360,245282528,122983324 }, { 1000362,991755665,122983324 }, { 1000364,739984449,122983324 }, { 1000366,488213233,122983324 }, { 1000368,236442017,122983324 }, { 1000370,982915154,122983324 }, { 1000372,731143938,122983324 }, { 1000374,479372722,122983324 }, { 1000376,227601506,122983324 }, { 1000378,974074643,122983324 }, { 1000380,722303427,122983324 }, { 1000382,470532211,122983324 }, { 1000384,218760995,122983324 }, { 1000386,965234132,122983324 }, { 1000388,713462916,122983324 }, { 1000390,461691700,122983324 }, { 1000392,209920484,122983324 }, { 1000394,956393621,122983324 }, { 1000396,704622405,122983324 }, { 1000398,452851189,122983324 }, { 10000000,97922885,291099516 }, { 10000002,454650003,195436786 }, { 10000004,837433850,439828528 }, { 10000006,515891626,788335147 }, { 10000008,177450450,195436786 }, { 10000010,566851720,439828528 }, { 10000012,632108779,788335147 }, { 10000014,898495250,195436786 }, { 10000016,296269590,439828528 }, { 10000018,748325932,788335147 }, { 10000020,621295697,195436786 }, { 10000022,25687460,439828528 }, { 10000024,864543085,788335147 }, { 10000026,344096144,195436786 }, { 10000028,753349683,439828528 }, { 10000030,980760238,788335147 }, { 10000032,66896591,195436786 }, { 10000034,482767553,439828528 }, { 10000036,98733038,788335147 }, { 10000038,787941391,195436786 }, { 10000040,212185423,439828528 }, { 10000042,214950191,788335147 }, { 10000044,510741838,195436786 }, { 10000046,939847646,439828528 }, { 10000048,331167344,788335147 }, { 10000050,233542285,195436786 }, { 10000052,669265516,439828528 }, { 10000054,447384497,788335147 }, { 10000056,954587085,195436786 }, { 10000058,398683386,439828528 }, { 10000060,563601650,788335147 }, { 10000062,677387532,195436786 }, { 10000064,128101256,439828528 }, { 10000066,679818803,788335147 }, { 10000068,400187979,195436786 }, { 10000070,855763479,439828528 }, { 10000072,796035956,788335147 }, { 10000074,122988426,195436786 }, { 10000076,585181349,439828528 }, { 10000078,912253109,788335147 }, { 10000080,844033226,195436786 }, { 10000082,314599219,439828528 }, { 10000084,30225909,788335147 }, { 10000086,566833673,195436786 }, { 10000088,44017089,439828528 }, { 10000090,146443062,788335147 }, { 10000092,289634120,195436786 }, { 10000094,771679312,439828528 }, { 10000096,262660215,788335147 }, { 10000098,12434567,195436786 }, { 10000100,501097182,439828528 }, { 10000102,378877368,788335147 }, { 10000104,733479367,195436786 }, { 10000106,230515052,439828528 }, { 10000108,495094521,788335147 }, { 10000110,456279814,195436786 }, { 10000112,958177275,439828528 }, { 10000114,611311674,788335147 }, { 10000116,179080261,195436786 }, { 10000118,687595145,439828528 }, { 10000120,727528827,788335147 }, { 10000122,900125061,195436786 }, { 10000124,417013015,439828528 }, { 10000126,843745980,788335147 }, { 10000128,622925508,195436786 }, { 10000130,146430885,439828528 }, { 10000132,959963133,788335147 }, { 10000134,345725955,195436786 }, { 10000136,874093108,439828528 }, { 10000138,77935933,788335147 }, { 10000140,68526402,195436786 }, { 10000142,603510978,439828528 }, { 10000144,194153086,788335147 }, { 10000146,789571202,195436786 }, { 10000148,332928848,439828528 }, { 10000150,310370239,788335147 }, { 10000152,512371649,195436786 }, { 10000154,62346718,439828528 }, { 10000156,426587392,788335147 }, { 10000158,235172096,195436786 }, { 10000160,790008941,439828528 }, { 10000162,542804545,788335147 }, { 10000164,956216896,195436786 }, { 10000166,519426811,439828528 }, { 10000168,659021698,788335147 }, { 10000170,679017343,195436786 }, { 10000172,248844681,439828528 }, { 10000174,775238851,788335147 }, { 10000176,401817790,195436786 }, { 10000178,976506904,439828528 }, { 10000180,891456004,788335147 }, { 10000182,124618237,195436786 }, { 10000184,705924774,439828528 }, { 10000186,9428804,788335147 }, { 10000188,845663037,195436786 }, { 10000190,435342644,439828528 }, { 10000192,125645957,788335147 }, { 10000194,568463484,195436786 }, { 10000196,164760514,439828528 }, { 10000198,241863110,788335147 }, { 10000200,291263931,195436786 }, { 10000202,892422737,439828528 }, { 10000204,358080263,788335147 }, { 10000206,14064378,195436786 }, { 10000208,621840607,439828528 }, { 10000210,474297416,788335147 }, { 10000212,735109178,195436786 }, { 10000214,351258477,439828528 }, { 10000216,590514569,788335147 }, { 10000218,457909625,195436786 }, { 10000220,80676347,439828528 }, { 10000222,706731722,788335147 }, { 10000224,180710072,195436786 }, { 10000226,808338570,439828528 }, { 10000228,822948875,788335147 }, { 10000230,901754872,195436786 }, { 10000232,537756440,439828528 }, { 10000234,939166028,788335147 }, { 10000236,624555319,195436786 }, { 10000238,267174310,439828528 }, { 10000240,57138828,788335147 }, { 10000242,347355766,195436786 }, { 10000244,994836533,439828528 }, { 10000246,173355981,788335147 }, { 10000248,70156213,195436786 }, { 10000250,724254403,439828528 }, { 10000252,289573134,788335147 }, { 10000254,791201013,195436786 }, { 10000256,453672273,439828528 }, { 10000258,405790287,788335147 }, { 10000260,514001460,195436786 }, { 10000262,183090143,439828528 }, { 10000264,522007440,788335147 }, { 10000266,236801907,195436786 }, { 10000268,910752366,439828528 }, { 10000270,638224593,788335147 }, { 10000272,957846707,195436786 }, { 10000274,640170236,439828528 }, { 10000276,754441746,788335147 }, { 10000278,680647154,195436786 }, { 10000280,369588106,439828528 }, { 10000282,870658899,788335147 }, { 10000284,403447601,195436786 }, { 10000286,99005976,439828528 }, { 10000288,986876052,788335147 }, { 10000290,126248048,195436786 }, { 10000292,826668199,439828528 }, { 10000294,104848852,788335147 }, { 10000296,847292848,195436786 }, { 10000298,556086069,439828528 }, { 10000300,221066005,788335147 }, { 10000302,570093295,195436786 }, { 10000304,285503939,439828528 }, { 10000306,337283158,788335147 }, { 10000308,292893742,195436786 }, { 10000310,14921809,439828528 }, { 10000312,453500311,788335147 }, { 10000314,15694189,195436786 }, { 10000316,742584032,439828528 }, { 10000318,569717464,788335147 }, { 10000320,736738989,195436786 }, { 10000322,472001902,439828528 }, { 10000324,685934617,788335147 }, { 10000326,459539436,195436786 }, { 10000328,201419772,439828528 }, { 10000330,802151770,788335147 }, { 10000332,182339883,195436786 }, { 10000334,929081995,439828528 }, { 10000336,918368923,788335147 }, { 10000338,903384683,195436786 }, { 10000340,658499865,439828528 }, { 10000342,36341723,788335147 }, { 10000344,626185130,195436786 }, { 10000346,387917735,439828528 }, { 10000348,152558876,788335147 }, { 10000350,348985577,195436786 }, { 10000352,117335605,439828528 }, { 10000354,268776029,788335147 }, { 10000356,71786024,195436786 }, { 10000358,844997828,439828528 }, { 10000360,384993182,788335147 }, { 10000362,792830824,195436786 }, { 10000364,574415698,439828528 }, { 10000366,501210335,788335147 }, { 10000368,515631271,195436786 }, { 10000370,303833568,439828528 }, { 10000372,617427488,788335147 }, { 10000374,238431718,195436786 }, { 10000376,33251438,439828528 }, { 10000378,733644641,788335147 }, { 10000380,959476518,195436786 }, { 10000382,760913661,439828528 }, { 10000384,849861794,788335147 }, { 10000386,682276965,195436786 }, { 10000388,490331531,439828528 }, { 10000390,966078947,788335147 }, { 10000392,405077412,195436786 }, { 10000394,219749401,439828528 }, { 10000396,84051747,788335147 }, { 10000398,127877859,195436786 }, { 100000000,918810723,788947331 }, { 100000002,280842612,338629430 }, { 100000004,257384876,749441906 }, { 100000006,271649936,21788946 }, { 100000008,538099242,338629430 }, { 100000010,93391569,749441906 }, { 100000012,880114525,21788946 }, { 100000014,795355872,338629430 }, { 100000016,927642615,749441906 }, { 100000018,490334761,21788946 }, { 100000020,54368149,338629430 }, { 100000022,763649308,749441906 }, { 100000024,100554997,21788946 }, { 100000026,311624779,338629430 }, { 100000028,599656001,749441906 }, { 100000030,709019586,21788946 }, { 100000032,568881409,338629430 }, { 100000034,435662694,749441906 }, { 100000036,319239822,21788946 }, { 100000038,826138039,338629430 }, { 100000040,271669387,749441906 }, { 100000042,927704411,21788946 }, { 100000044,85150316,338629430 }, { 100000046,107676080,749441906 }, { 100000048,537924647,21788946 }, { 100000050,342406946,338629430 }, { 100000052,941927126,749441906 }, { 100000054,148144883,21788946 }, { 100000056,599663576,338629430 }, { 100000058,777933819,749441906 }, { 100000060,756609472,21788946 }, { 100000062,856920206,338629430 }, { 100000064,613940512,749441906 }, { 100000066,366829708,21788946 }, { 100000068,115932483,338629430 }, { 100000070,449947205,749441906 }, { 100000072,975294297,21788946 }, { 100000074,373189113,338629430 }, { 100000076,285953898,749441906 }, { 100000078,585514533,21788946 }, { 100000080,630445743,338629430 }, { 100000082,121960591,749441906 }, { 100000084,195734769,21788946 }, { 100000086,887702373,338629430 }, { 100000088,956211637,749441906 }, { 100000090,804199358,21788946 }, { 100000092,146714650,338629430 }, { 100000094,792218330,749441906 }, { 100000096,414419594,21788946 }, { 100000098,403971280,338629430 }, { 100000100,628225023,749441906 }, { 100000102,24639830,21788946 }, { 100000104,661227910,338629430 }, { 100000106,464231716,749441906 }, { 100000108,633104419,21788946 }, { 100000110,918484540,338629430 }, { 100000112,300238409,749441906 }, { 100000114,243324655,21788946 }, { 100000116,177496817,338629430 }, { 100000118,136245102,749441906 }, { 100000120,851789244,21788946 }, { 100000122,434753447,338629430 }, { 100000124,970496148,749441906 }, { 100000126,462009480,21788946 }, { 100000128,692010077,338629430 }, { 100000130,806502841,749441906 }, { 100000132,72229716,21788946 }, { 100000134,949266707,338629430 }, { 100000136,642509534,749441906 }, { 100000138,680694305,21788946 }, { 100000140,208278984,338629430 }, { 100000142,478516227,749441906 }, { 100000144,290914541,21788946 }, { 100000146,465535614,338629430 }, { 100000148,314522920,749441906 }, { 100000150,899379130,21788946 }, { 100000152,722792244,338629430 }, { 100000154,150529613,749441906 }, { 100000156,509599366,21788946 }, { 100000158,980048874,338629430 }, { 100000160,984780659,749441906 }, { 100000162,119819602,21788946 }, { 100000164,239061151,338629430 }, { 100000166,820787352,749441906 }, { 100000168,728284191,21788946 }, { 100000170,496317781,338629430 }, { 100000172,656794045,749441906 }, { 100000174,338504427,21788946 }, { 100000176,753574411,338629430 }, { 100000178,492800738,749441906 }, { 100000180,946969016,21788946 }, { 100000182,12586688,338629430 }, { 100000184,328807431,749441906 }, { 100000186,557189252,21788946 }, { 100000188,269843318,338629430 }, { 100000190,164814124,749441906 }, { 100000192,167409488,21788946 }, { 100000194,527099948,338629430 }, { 100000196,820817,749441906 }, { 100000198,775874077,21788946 }, { 100000200,784356578,338629430 }, { 100000202,835071863,749441906 }, { 100000204,386094313,21788946 }, { 100000206,43368855,338629430 }, { 100000208,671078556,749441906 }, { 100000210,994558902,21788946 }, { 100000212,300625485,338629430 }, { 100000214,507085249,749441906 }, { 100000216,604779138,21788946 }, { 100000218,557882115,338629430 }, { 100000220,343091942,749441906 }, { 100000222,214999374,21788946 }, { 100000224,815138745,338629430 }, { 100000226,179098635,749441906 }, { 100000228,823463963,21788946 }, { 100000230,74151022,338629430 }, { 100000232,15105328,749441906 }, { 100000234,433684199,21788946 }, { 100000236,331407652,338629430 }, { 100000238,849356374,749441906 }, { 100000240,43904435,21788946 }, { 100000242,588664282,338629430 }, { 100000244,685363067,749441906 }, { 100000246,652369024,21788946 }, { 100000248,845920912,338629430 }, { 100000250,521369760,749441906 }, { 100000252,262589260,21788946 }, { 100000254,104933189,338629430 }, { 100000256,357376453,749441906 }, { 100000258,871053849,21788946 }, { 100000260,362189819,338629430 }, { 100000262,193383146,749441906 }, { 100000264,481274085,21788946 }, { 100000266,619446449,338629430 }, { 100000268,29389839,749441906 }, { 100000270,91494321,21788946 }, { 100000272,876703079,338629430 }, { 100000274,863640885,749441906 }, { 100000276,699958910,21788946 }, { 100000278,135715356,338629430 }, { 100000280,699647578,749441906 }, { 100000282,310179146,21788946 }, { 100000284,392971986,338629430 }, { 100000286,535654271,749441906 }, { 100000288,918643735,21788946 }, { 100000290,650228616,338629430 }, { 100000292,371660964,749441906 }, { 100000294,528863971,21788946 }, { 100000296,907485246,338629430 }, { 100000298,207667657,749441906 }, { 100000300,139084207,21788946 }, { 100000302,166497523,338629430 }, { 100000304,43674350,749441906 }, { 100000306,747548796,21788946 }, { 100000308,423754153,338629430 }, { 100000310,877925396,749441906 }, { 100000312,357769032,21788946 }, { 100000314,681010783,338629430 }, { 100000316,713932089,749441906 }, { 100000318,966233621,21788946 }, { 100000320,938267413,338629430 }, { 100000322,549938782,749441906 }, { 100000324,576453857,21788946 }, { 100000326,197279690,338629430 }, { 100000328,385945475,749441906 }, { 100000330,186674093,21788946 }, { 100000332,454536320,338629430 }, { 100000334,221952168,749441906 }, { 100000336,795138682,21788946 }, { 100000338,711792950,338629430 }, { 100000340,57958861,749441906 }, { 100000342,405358918,21788946 }, { 100000344,969049580,338629430 }, { 100000346,892209907,749441906 }, { 100000348,15579154,21788946 }, { 100000350,228061857,338629430 }, { 100000352,728216600,749441906 }, { 100000354,624043743,21788946 }, { 100000356,485318487,338629430 }, { 100000358,564223293,749441906 }, { 100000360,234263979,21788946 }, { 100000362,742575117,338629430 }, { 100000364,400229986,749441906 }, { 100000366,842728568,21788946 }, { 100000368,1587394,338629430 }, { 100000370,236236679,749441906 }, { 100000372,452948804,21788946 }, { 100000374,258844024,338629430 }, { 100000376,72243372,749441906 }, { 100000378,63169040,21788946 }, { 100000380,516100654,338629430 }, { 100000382,906494418,749441906 }, { 100000384,671633629,21788946 }, { 100000386,773357284,338629430 }, { 100000388,742501111,749441906 }, { 100000390,281853865,21788946 }, { 100000392,32369561,338629430 }, { 100000394,578507804,749441906 }, { 100000396,890318454,21788946 }, { 100000398,289626191,338629430 }, { 1000000000,911934024,391561241 }, { 1000000002,28413049,762183754 }, { 1000000004,418593159,584762045 }, { 1000000006,946029033,343622622 }, { 1000000008,63594196,762183754 }, { 1000000010,974793796,584762045 }, { 1000000012,997911177,343622622 }, { 1000000014,98775343,762183754 }, { 1000000016,532750080,584762045 }, { 1000000018,51548968,343622622 }, { 1000000020,133956490,762183754 }, { 1000000022,90706364,584762045 }, { 1000000024,103431112,343622622 }, { 1000000026,169137637,762183754 }, { 1000000028,646907001,584762045 }, { 1000000030,155313256,343622622 }, { 1000000032,204318784,762183754 }, { 1000000034,204863285,584762045 }, { 1000000036,207195400,343622622 }, { 1000000038,239499931,762183754 }, { 1000000040,761063922,584762045 }, { 1000000042,259077544,343622622 }, { 1000000044,274681078,762183754 }, { 1000000046,319020206,584762045 }, { 1000000048,310959688,343622622 }, { 1000000050,309862225,762183754 }, { 1000000052,875220843,584762045 }, { 1000000054,362841832,343622622 }, { 1000000056,345043372,762183754 }, { 1000000058,433177127,584762045 }, { 1000000060,414723976,343622622 }, { 1000000062,380224519,762183754 }, { 1000000064,989377764,584762045 }, { 1000000066,466606120,343622622 }, { 1000000068,415405666,762183754 }, { 1000000070,547334048,584762045 }, { 1000000072,518488264,343622622 }, { 1000000074,450586813,762183754 }, { 1000000076,105290332,584762045 }, { 1000000078,570370408,343622622 }, { 1000000080,485767960,762183754 }, { 1000000082,661490969,584762045 }, { 1000000084,622252552,343622622 }, { 1000000086,520949107,762183754 }, { 1000000088,219447253,584762045 }, { 1000000090,674134696,343622622 }, { 1000000092,556130254,762183754 }, { 1000000094,775647890,584762045 }, { 1000000096,726016840,343622622 }, { 1000000098,591311401,762183754 }, { 1000000100,333604174,584762045 }, { 1000000102,777898984,343622622 }, { 1000000104,626492548,762183754 }, { 1000000106,889804811,584762045 }, { 1000000108,829781128,343622622 }, { 1000000110,661673695,762183754 }, { 1000000112,447761095,584762045 }, { 1000000114,881663272,343622622 }, { 1000000116,696854842,762183754 }, { 1000000118,5717379,584762045 }, { 1000000120,933545416,343622622 }, { 1000000122,732035989,762183754 }, { 1000000124,561918016,584762045 }, { 1000000126,985427560,343622622 }, { 1000000128,767217136,762183754 }, { 1000000130,119874300,584762045 }, { 1000000132,39065351,343622622 }, { 1000000134,802398283,762183754 }, { 1000000136,676074937,584762045 }, { 1000000138,90947495,343622622 }, { 1000000140,837579430,762183754 }, { 1000000142,234031221,584762045 }, { 1000000144,142829639,343622622 }, { 1000000146,872760577,762183754 }, { 1000000148,790231858,584762045 }, { 1000000150,194711783,343622622 }, { 1000000152,907941724,762183754 }, { 1000000154,348188142,584762045 }, { 1000000156,246593927,343622622 }, { 1000000158,943122871,762183754 }, { 1000000160,904388779,584762045 }, { 1000000162,298476071,343622622 }, { 1000000164,978304018,762183754 }, { 1000000166,462345063,584762045 }, { 1000000168,350358215,343622622 }, { 1000000170,15240812,762183754 }, { 1000000172,20301347,584762045 }, { 1000000174,402240359,343622622 }, { 1000000176,50421959,762183754 }, { 1000000178,576501984,584762045 }, { 1000000180,454122503,343622622 }, { 1000000182,85603106,762183754 }, { 1000000184,134458268,584762045 }, { 1000000186,506004647,343622622 }, { 1000000188,120784253,762183754 }, { 1000000190,690658905,584762045 }, { 1000000192,557886791,343622622 }, { 1000000194,155965400,762183754 }, { 1000000196,248615189,584762045 }, { 1000000198,609768935,343622622 }, { 1000000200,191146547,762183754 }, { 1000000202,804815826,584762045 }, { 1000000204,661651079,343622622 }, { 1000000206,226327694,762183754 }, { 1000000208,362772110,584762045 }, { 1000000210,713533223,343622622 }, { 1000000212,261508841,762183754 }, { 1000000214,918972747,584762045 }, { 1000000216,765415367,343622622 }, { 1000000218,296689988,762183754 }, { 1000000220,476929031,584762045 }, { 1000000222,817297511,343622622 }, { 1000000224,331871135,762183754 }, { 1000000226,34885315,584762045 }, { 1000000228,869179655,343622622 }, { 1000000230,367052282,762183754 }, { 1000000232,591085952,584762045 }, { 1000000234,921061799,343622622 }, { 1000000236,402233429,762183754 }, { 1000000238,149042236,584762045 }, { 1000000240,972943943,343622622 }, { 1000000242,437414576,762183754 }, { 1000000244,705242873,584762045 }, { 1000000246,26581734,343622622 }, { 1000000248,472595723,762183754 }, { 1000000250,263199157,584762045 }, { 1000000252,78463878,343622622 }, { 1000000254,507776870,762183754 }, { 1000000256,819399794,584762045 }, { 1000000258,130346022,343622622 }, { 1000000260,542958017,762183754 }, { 1000000262,377356078,584762045 }, { 1000000264,182228166,343622622 }, { 1000000266,578139164,762183754 }, { 1000000268,933556715,584762045 }, { 1000000270,234110310,343622622 }, { 1000000272,613320311,762183754 }, { 1000000274,491512999,584762045 }, { 1000000276,285992454,343622622 }, { 1000000278,648501458,762183754 }, { 1000000280,49469283,584762045 }, { 1000000282,337874598,343622622 }, { 1000000284,683682605,762183754 }, { 1000000286,605669920,584762045 }, { 1000000288,389756742,343622622 }, { 1000000290,718863752,762183754 }, { 1000000292,163626204,584762045 }, { 1000000294,441638886,343622622 }, { 1000000296,754044899,762183754 }, { 1000000298,719826841,584762045 }, { 1000000300,493521030,343622622 }, { 1000000302,789226046,762183754 }, { 1000000304,277783125,584762045 }, { 1000000306,545403174,343622622 }, { 1000000308,824407193,762183754 }, { 1000000310,833983762,584762045 }, { 1000000312,597285318,343622622 }, { 1000000314,859588340,762183754 }, { 1000000316,391940046,584762045 }, { 1000000318,649167462,343622622 }, { 1000000320,894769487,762183754 }, { 1000000322,948140683,584762045 }, { 1000000324,701049606,343622622 }, { 1000000326,929950634,762183754 }, { 1000000328,506096967,584762045 }, { 1000000330,752931750,343622622 }, { 1000000332,965131781,762183754 }, { 1000000334,64053251,584762045 }, { 1000000336,804813894,343622622 }, { 1000000338,2068575,762183754 }, { 1000000340,620253888,584762045 }, { 1000000342,856696038,343622622 }, { 1000000344,37249722,762183754 }, { 1000000346,178210172,584762045 }, { 1000000348,908578182,343622622 }, { 1000000350,72430869,762183754 }, { 1000000352,734410809,584762045 }, { 1000000354,960460326,343622622 }, { 1000000356,107612016,762183754 }, { 1000000358,292367093,584762045 }, { 1000000360,14098117,343622622 }, { 1000000362,142793163,762183754 }, { 1000000364,848567730,584762045 }, { 1000000366,65980261,343622622 }, { 1000000368,177974310,762183754 }, { 1000000370,406524014,584762045 }, { 1000000372,117862405,343622622 }, { 1000000374,213155457,762183754 }, { 1000000376,962724651,584762045 }, { 1000000378,169744549,343622622 }, { 1000000380,248336604,762183754 }, { 1000000382,520680935,584762045 }, { 1000000384,221626693,343622622 }, { 1000000386,283517751,762183754 }, { 1000000388,78637219,584762045 }, { 1000000390,273508837,343622622 }, { 1000000392,318698898,762183754 }, { 1000000394,634837856,584762045 }, { 1000000396,325390981,343622622 }, { 1000000398,353880045,762183754 }, { 10000000000,614239340,841319474 }, { 10000000002,586831411,500908756 }, { 10000000004,942469418,637075334 }, { 10000000006,277722473,24397693 }, { 10000000008,985247125,500908756 }, { 10000000010,344243851,637075334 }, { 10000000012,487083205,24397693 }, { 10000000014,385418486,500908756 }, { 10000000016,744262637,637075334 }, { 10000000018,696443937,24397693 }, { 10000000020,783834200,500908756 }, { 10000000022,146037070,637075334 }, { 10000000024,905804669,24397693 }, { 10000000026,184005561,500908756 }, { 10000000028,546055856,637075334 }, { 10000000030,116921048,24397693 }, { 10000000032,582421275,500908756 }, { 10000000034,946074642,637075334 }, { 10000000036,326281780,24397693 }, { 10000000038,980836989,500908756 }, { 10000000040,347849075,637075334 }, { 10000000042,535642512,24397693 }, { 10000000044,381008350,500908756 }, { 10000000046,747867861,637075334 }, { 10000000048,745003244,24397693 }, { 10000000050,779424064,500908756 }, { 10000000052,149642294,637075334 }, { 10000000054,954363976,24397693 }, { 10000000056,179595425,500908756 }, { 10000000058,549661080,637075334 }, { 10000000060,165480355,24397693 }, { 10000000062,578011139,500908756 }, { 10000000064,949679866,637075334 }, { 10000000066,374841087,24397693 }, { 10000000068,976426853,500908756 }, { 10000000070,351454299,637075334 }, { 10000000072,584201819,24397693 }, { 10000000074,376598214,500908756 }, { 10000000076,751473085,637075334 }, { 10000000078,793562551,24397693 }, { 10000000080,775013928,500908756 }, { 10000000082,153247518,637075334 }, { 10000000084,4678930,24397693 }, { 10000000086,175185289,500908756 }, { 10000000088,553266304,637075334 }, { 10000000090,214039662,24397693 }, { 10000000092,573601003,500908756 }, { 10000000094,953285090,637075334 }, { 10000000096,423400394,24397693 }, { 10000000098,972016717,500908756 }, { 10000000100,355059523,637075334 }, { 10000000102,632761126,24397693 }, { 10000000104,372188078,500908756 }, { 10000000106,755078309,637075334 }, { 10000000108,842121858,24397693 }, { 10000000110,770603792,500908756 }, { 10000000112,156852742,637075334 }, { 10000000114,53238237,24397693 }, { 10000000116,170775153,500908756 }, { 10000000118,556871528,637075334 }, { 10000000120,262598969,24397693 }, { 10000000122,569190867,500908756 }, { 10000000124,956890314,637075334 }, { 10000000126,471959701,24397693 }, { 10000000128,967606581,500908756 }, { 10000000130,358664747,637075334 }, { 10000000132,681320433,24397693 }, { 10000000134,367777942,500908756 }, { 10000000136,758683533,637075334 }, { 10000000138,890681165,24397693 }, { 10000000140,766193656,500908756 }, { 10000000142,160457966,637075334 }, { 10000000144,101797544,24397693 }, { 10000000146,166365017,500908756 }, { 10000000148,560476752,637075334 }, { 10000000150,311158276,24397693 }, { 10000000152,564780731,500908756 }, { 10000000154,960495538,637075334 }, { 10000000156,520519008,24397693 }, { 10000000158,963196445,500908756 }, { 10000000160,362269971,637075334 }, { 10000000162,729879740,24397693 }, { 10000000164,363367806,500908756 }, { 10000000166,762288757,637075334 }, { 10000000168,939240472,24397693 }, { 10000000170,761783520,500908756 }, { 10000000172,164063190,637075334 }, { 10000000174,150356851,24397693 }, { 10000000176,161954881,500908756 }, { 10000000178,564081976,637075334 }, { 10000000180,359717583,24397693 }, { 10000000182,560370595,500908756 }, { 10000000184,964100762,637075334 }, { 10000000186,569078315,24397693 }, { 10000000188,958786309,500908756 }, { 10000000190,365875195,637075334 }, { 10000000192,778439047,24397693 }, { 10000000194,358957670,500908756 }, { 10000000196,765893981,637075334 }, { 10000000198,987799779,24397693 }, { 10000000200,757373384,500908756 }, { 10000000202,167668414,637075334 }, { 10000000204,198916158,24397693 }, { 10000000206,157544745,500908756 }, { 10000000208,567687200,637075334 }, { 10000000210,408276890,24397693 }, { 10000000212,555960459,500908756 }, { 10000000214,967705986,637075334 }, { 10000000216,617637622,24397693 }, { 10000000218,954376173,500908756 }, { 10000000220,369480419,637075334 }, { 10000000222,826998354,24397693 }, { 10000000224,354547534,500908756 }, { 10000000226,769499205,637075334 }, { 10000000228,38114733,24397693 }, { 10000000230,752963248,500908756 }, { 10000000232,171273638,637075334 }, { 10000000234,247475465,24397693 }, { 10000000236,153134609,500908756 }, { 10000000238,571292424,637075334 }, { 10000000240,456836197,24397693 }, { 10000000242,551550323,500908756 }, { 10000000244,971311210,637075334 }, { 10000000246,666196929,24397693 }, { 10000000248,949966037,500908756 }, { 10000000250,373085643,637075334 }, { 10000000252,875557661,24397693 }, { 10000000254,350137398,500908756 }, { 10000000256,773104429,637075334 }, { 10000000258,86674040,24397693 }, { 10000000260,748553112,500908756 }, { 10000000262,174878862,637075334 }, { 10000000264,296034772,24397693 }, { 10000000266,148724473,500908756 }, { 10000000268,574897648,637075334 }, { 10000000270,505395504,24397693 }, { 10000000272,547140187,500908756 }, { 10000000274,974916434,637075334 }, { 10000000276,714756236,24397693 }, { 10000000278,945555901,500908756 }, { 10000000280,376690867,637075334 }, { 10000000282,924116968,24397693 }, { 10000000284,345727262,500908756 }, { 10000000286,776709653,637075334 }, { 10000000288,135233347,24397693 }, { 10000000290,744142976,500908756 }, { 10000000292,178484086,637075334 }, { 10000000294,344594079,24397693 }, { 10000000296,144314337,500908756 }, { 10000000298,578502872,637075334 }, { 10000000300,553954811,24397693 }, { 10000000302,542730051,500908756 }, { 10000000304,978521658,637075334 }, { 10000000306,763315543,24397693 }, { 10000000308,941145765,500908756 }, { 10000000310,380296091,637075334 }, { 10000000312,972676275,24397693 }, { 10000000314,341317126,500908756 }, { 10000000316,780314877,637075334 }, { 10000000318,183792654,24397693 }, { 10000000320,739732840,500908756 }, { 10000000322,182089310,637075334 }, { 10000000324,393153386,24397693 }, { 10000000326,139904201,500908756 }, { 10000000328,582108096,637075334 }, { 10000000330,602514118,24397693 }, { 10000000332,538319915,500908756 }, { 10000000334,982126882,637075334 }, { 10000000336,811874850,24397693 }, { 10000000338,936735629,500908756 }, { 10000000340,383901315,637075334 }, { 10000000342,22991229,24397693 }, { 10000000344,336906990,500908756 }, { 10000000346,783920101,637075334 }, { 10000000348,232351961,24397693 }, { 10000000350,735322704,500908756 }, { 10000000352,185694534,637075334 }, { 10000000354,441712693,24397693 }, { 10000000356,135494065,500908756 }, { 10000000358,585713320,637075334 }, { 10000000360,651073425,24397693 }, { 10000000362,533909779,500908756 }, { 10000000364,985732106,637075334 }, { 10000000366,860434157,24397693 }, { 10000000368,932325493,500908756 }, { 10000000370,387506539,637075334 }, { 10000000372,71550536,24397693 }, { 10000000374,332496854,500908756 }, { 10000000376,787525325,637075334 }, { 10000000378,280911268,24397693 }, { 10000000380,730912568,500908756 }, { 10000000382,189299758,637075334 }, { 10000000384,490272000,24397693 }, { 10000000386,131083929,500908756 }, { 10000000388,589318544,637075334 }, { 10000000390,699632732,24397693 }, { 10000000392,529499643,500908756 }, { 10000000394,989337330,637075334 }, { 10000000396,908993464,24397693 }, { 10000000398,927915357,500908756 }, { 100000000000,599244678,404761982} }; constexpr int W = 10000000; 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 <= 2 * 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(p10[l - 1] + W, MOD, N); vm a; rep(k, 4) { ll N2 = N00 + MOD * k; int i = ubpos(ume, make_tuple(N2, 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); } auto c = berlekamp_massey(a); a.resize(sz(c)); dump("a:", a); dump("c:", c); ll D = N - N00; ll Q = D / MOD; mint res = linearly_recurrent_sequence(a, c, Q); return res; } return 0; } int main() { ll n; cin >> n; cout << solve(n) << endl; }