結果
| 問題 | No.1561 connect x connect |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2021-06-25 22:40:23 |
| 言語 | D (dmd 2.106.1) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 48,886 bytes |
| コンパイル時間 | 1,331 ms |
| コンパイル使用メモリ | 155,692 KB |
| 実行使用メモリ | 10,396 KB |
| 最終ジャッジ日時 | 2024-06-22 11:37:43 |
| 合計ジャッジ時間 | 6,550 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
10,396 KB |
| testcase_01 | AC | 1 ms
6,940 KB |
| testcase_02 | AC | 4 ms
6,944 KB |
| testcase_03 | AC | 1 ms
6,944 KB |
| testcase_04 | AC | 1 ms
6,944 KB |
| testcase_05 | AC | 1 ms
6,944 KB |
| testcase_06 | AC | 1 ms
6,940 KB |
| testcase_07 | AC | 1 ms
6,940 KB |
| testcase_08 | AC | 1 ms
6,940 KB |
| testcase_09 | AC | 1 ms
6,940 KB |
| testcase_10 | AC | 1 ms
6,940 KB |
| testcase_11 | AC | 1 ms
6,940 KB |
| testcase_12 | AC | 2 ms
6,944 KB |
| testcase_13 | AC | 4 ms
6,940 KB |
| testcase_14 | AC | 13 ms
6,940 KB |
| testcase_15 | AC | 23 ms
6,944 KB |
| testcase_16 | AC | 61 ms
6,944 KB |
| testcase_17 | AC | 3 ms
6,940 KB |
| testcase_18 | AC | 2 ms
6,944 KB |
| testcase_19 | AC | 382 ms
6,940 KB |
| testcase_20 | AC | 12 ms
6,944 KB |
| testcase_21 | AC | 1 ms
6,940 KB |
| testcase_22 | AC | 12 ms
6,940 KB |
| testcase_23 | AC | 1 ms
6,944 KB |
| testcase_24 | AC | 368 ms
6,944 KB |
| testcase_25 | AC | 1 ms
6,940 KB |
| testcase_26 | TLE | - |
| testcase_27 | TLE | - |
| testcase_28 | TLE | - |
| testcase_29 | TLE | - |
| testcase_30 | TLE | - |
| testcase_31 | AC | 2 ms
6,944 KB |
| testcase_32 | AC | 4 ms
6,940 KB |
| testcase_33 | AC | 20 ms
6,944 KB |
| testcase_34 | AC | 363 ms
6,944 KB |
| testcase_35 | AC | 26 ms
6,944 KB |
| testcase_36 | AC | 195 ms
6,940 KB |
| testcase_37 | TLE | - |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }
bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }
int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }
struct ModInt(uint M_) {
import std.conv : to;
alias M = M_;
uint x;
this(ModInt a) { x = a.x; }
this(uint x_) { x = x_ % M; }
this(ulong x_) { x = x_ % M; }
this(int x_) { x = ((x_ %= cast(int)(M)) < 0) ? (x_ + cast(int)(M)) : x_; }
this(long x_) { x = cast(uint)(((x_ %= cast(long)(M)) < 0) ? (x_ + cast(long)(M)) : x_); }
ref ModInt opAssign(T)(T a) if (is(T == uint) || is(T == ulong) || is(T == int) || is(T == long)) { return this = ModInt(a); }
ref ModInt opOpAssign(string op, T)(T a) {
static if (is(T == ModInt)) {
static if (op == "+") { x = ((x += a.x) >= M) ? (x - M) : x; }
else static if (op == "-") { x = ((x -= a.x) >= M) ? (x + M) : x; }
else static if (op == "*") { x = cast(uint)((cast(ulong)(x) * a.x) % M); }
else static if (op == "/") { this *= a.inv(); }
else static assert(false);
return this;
} else static if (op == "^^") {
if (a < 0) return this = inv()^^(-a);
ModInt b = this, c = 1U;
for (long e = a; e; e >>= 1) { if (e & 1) c *= b; b *= b; }
return this = c;
} else {
return mixin("this " ~ op ~ "= ModInt(a)");
}
}
ModInt inv() const {
uint a = M, b = x; int y = 0, z = 1;
for (; b; ) { const q = a / b; const c = a - q * b; a = b; b = c; const w = y - cast(int)(q) * z; y = z; z = w; }
assert(a == 1); return ModInt(y);
}
ModInt opUnary(string op)() const {
static if (op == "+") { return this; }
else static if (op == "-") { ModInt a; a.x = x ? (M - x) : 0U; return a; }
else static assert(false);
}
ModInt opBinary(string op, T)(T a) const { return mixin("ModInt(this) " ~ op ~ "= a"); }
ModInt opBinaryRight(string op, T)(T a) const { return mixin("ModInt(a) " ~ op ~ "= this"); }
bool opCast(T: bool)() const { return (x != 0U); }
string toString() const { return x.to!string; }
}
enum MO = 1000000007;
alias Mint = ModInt!MO;
// Berlekamp-Massey
// F: field
// \sum_{j=1}^0 cs[j] as[i - j] = 0 (d <= i < |as|), cs[0] = 1
// M must be prime
F[] findLinearRecurrence(F)(inout(F)[] as) {
import std.algorithm : min;
const n = cast(int)(as.length);
int d, m;
auto cs = new F[n + 1], bs = new F[n + 1];
cs[0] = bs[0] = 1;
F invBef = 1;
foreach (i; 0 .. n) {
++m;
F dif = as[i];
foreach (j; 1 .. d + 1) dif += cs[j] * as[i - j];
if (dif.x != 0) {
auto csDup = cs.dup;
const r = dif * invBef;
foreach (j; m .. n) cs[j] -= r * bs[j - m];
if (2 * d <= i) {
d = i + 1 - d;
m = 0;
bs = csDup;
invBef = dif.inv;
}
}
}
return cs[0 .. d + 1];
}
Mint solve(Mint[] as, Mint[] cs, long N) {
const d = cast(int)(cs.length) - 1;
Mint[] mul(Mint[] fs, Mint[] gs) {
auto hs = new Mint[d + d - 1];
foreach (i; 0 .. d) foreach (j; 0 .. d) {
hs[i + j] += fs[i] * gs[j];
}
foreach_reverse (i; d .. d + d - 1) {
foreach (j; 1 .. d + 1) {
hs[i - j] -= cs[j] * hs[i];
}
}
hs.length = d;
return hs;
}
auto xs = new Mint[d];
auto ys = new Mint[d];
xs[1] = 1;
ys[0] = 1;
for (long e = N; e; e >>= 1) {
if (e & 1) ys = mul(ys, xs);
xs = mul(xs, xs);
}
Mint ans;
foreach (i; 0 .. d) {
ans += as[i] * ys[i];
}
return ans;
}
uint[][] AS = [
[]
,[0, 1, 3, 6]
,[0, 3, 13, 40, 108]
,[0, 6, 40, 218, 1126, 5726, 28992, 146642, 741556]
,[0, 10, 108, 1126, 11506, 116166, 1168586, 11749134, 118127408, 187692415, 941503421, 64334502, 171422003, 349404639, 414370691]
,[0, 15, 275, 5726, 116166, 2301877, 45280509, 889477656, 470102989, 131617800, 543346538, 672693081, 528691884, 433100319, 259856352, 631703746, 121492784, 65000963, 67868821, 431503520, 556143263, 898859209, 822402657, 746831347, 942022314, 42461886, 245383965, 159194955, 442319965, 719053964, 735342087, 986228635, 385914410, 746460380]
,[0, 21, 681, 28992, 1168586, 45280509, 732082734, 37461992, 885687205, 403247903, 630794366, 96311199, 188560385, 132214957, 81864959, 656832813, 129969437, 337127917, 885747691, 994734031, 901081506, 113735510, 330166803, 692897482, 221245902, 823578678, 149151767, 513212823, 565413378, 343413792, 552163984, 401017125, 775469314, 768705741, 822998669, 524634565, 141276343, 644398112, 617812249, 791340223, 983870515, 203398182, 625614815, 683890375, 368195928, 142285464, 986226417, 160965035, 405204827, 206471233, 652493150, 587867820, 808610901, 707659600, 22802536, 445444835, 187616183, 160982744, 457176050, 436730256, 169883893, 240716120, 405440669, 340484060, 656210817, 36771327, 96126498, 306426249, 814430155, 444930212, 988328253, 540530995]
,[0, 28, 1664, 146642, 11749134, 889477656, 37461992, 949940562, 34890374, 408395779, 465431123, 169444072, 476095424, 659247954, 873440607, 926228358, 615656154, 946323264, 52968124, 753942504, 466886220, 131497623, 574943442, 651491966, 558045773, 251030380, 281770571, 626734327, 538734009, 338782739, 544266404, 882070771, 638524752, 866251039, 377115307, 677270990, 923683803, 407681394, 135644897, 799433050, 734586418, 252356851, 562319011, 202766611, 459305661, 237631148, 937873188, 999735041, 471421437, 196454674, 548587822, 155433694, 513218158, 425727801, 201766011, 618282733, 853358524, 794224019, 317787454, 420202005, 208101995, 561508157, 165138107, 680690785, 440574802, 642204069, 1519935, 740668820, 993620892, 358321040, 609591537, 544950607, 452208170, 885834624, 821590676, 398458087, 516061104, 713420418, 988022777, 345184826, 285034175, 821685364, 13669476, 704448103, 129864472, 272789356, 791468167, 22642555, 191074948, 725893030, 621310461, 91319075, 716141215, 100651620, 124026881, 366140815, 685675711, 544588613, 31892809, 733368799, 814661720, 416829950, 25354705, 920576064, 404858750, 224503153, 408647840, 32879424, 449601451, 954308700, 384324116, 674296838, 792515237, 188224955, 323348585, 972509240, 558237931, 478379644, 769454589, 5532215, 665030504, 378063244, 50177022, 152536855, 592606999, 936002695, 561844587, 98320627, 393845743, 234288387, 975460550, 94761064, 230083310, 437478027, 493404365, 809166706, 952865395, 30537948, 269093029, 454344596, 528546169, 743583991, 647074729, 593751773, 863574928, 753557944, 354148307, 464934709, 275033859, 450276861, 375178856, 24286587, 880771043, 120621725, 710396662, 135056587, 742687865, 845401042, 8181486, 277891374, 585736419, 570298110, 955283694, 601817563, 141857657, 613931527, 134904117, 127307580, 914760872, 56527073, 515151064, 85256390, 867641311, 644658123, 516456196, 546485053, 695768127, 950249035, 737354235, 328196921, 664437558]
,[0, 36, 4040, 741556, 118127408, 470102989, 885687205, 34890374, 247777016, 233426110, 328755371, 705627253, 787442872, 382905968, 14599213, 54410761, 601006292, 612557411, 15449456, 990194963, 286282085, 699722725, 781620769, 840139026, 489073872, 334785849, 435236311, 109774734, 741619354, 198733961, 979223831, 316303898, 39151097, 758722723, 846456337, 302710767, 751509519, 910422866, 269441528, 739223079, 47041872, 144990978, 835832181, 94144832, 432122371, 718847361, 143249505, 202420879, 524474077, 175432350, 259981775, 949834434, 650788361, 314338901, 308488393, 925015945, 735629952, 55340122, 870087004, 914406437, 652461932, 824517283, 13384791, 734924498, 195917202, 347913012, 345009223, 72962601, 728865665, 529666843, 443583543, 797807890, 499559112, 582526183, 750449603, 794171249, 339435367, 795879914, 610395113, 651525515, 665256279, 771083632, 124044838, 103256298, 555278857, 168723782, 37135886, 926137424, 193565944, 44104251, 848927128, 311714530, 740363205, 103826476, 426742610, 675142274, 731839743, 444416323, 663478468, 724122696, 351972777, 394976529, 438819547, 910482232, 104665901, 409225876, 167205682, 514913255, 760105145, 29299318, 710711305, 114816263, 854763814, 393789740, 110116602, 971095517, 965304627, 656067527, 345333181, 54369787, 393350947, 645767328, 278297447, 584309442, 643959646, 760481447, 306899117, 556007296, 90782544, 501999191, 487093902, 851119019, 214855164, 290938704, 483935411, 931413698, 87706720, 543982301, 557974404, 993894344, 617966931, 450284946, 530064541, 635450110, 955879320, 855098870, 534537883, 745899211, 102957101, 662330955, 760521286, 880202513, 410332359, 896841550, 21942388, 327590993, 607470931, 510274101, 755158989, 271684724, 681115728, 979634385, 116288824, 441075062, 869557219, 498624604, 668265455, 563569496, 411144207, 372553915, 26571455, 299681786, 483501145, 332251237, 514296631, 262088005, 767350800, 242709545, 312245270, 625558060, 630739736, 166453361, 987400268, 534085288, 177342293, 635886216, 360697926, 830064107, 142999667, 796390630, 541632626, 524331979, 832128250, 56784302, 599770934, 420185002, 36118708, 960687380, 886180310, 494123322, 256629996, 167297430, 422622751, 387880447, 805197257, 990906673, 197392117, 409215677, 751867399, 114891717, 20016317, 539423303, 506437722, 420323843, 17970683, 326175155, 607163024, 810675077, 843118080, 586603097, 332437402, 683685949, 604167445, 591515392, 281318475, 78155302, 77262870, 295568742, 84378564, 642943804, 12418388, 229594263, 734305604, 17384828, 186823879, 593406287, 961690928, 25278271, 599757507, 378599083, 885999372, 931931154, 847818732, 310703306, 179718037, 657210250, 145528035, 460498835, 941558183, 335135033, 141616629, 159440568, 260876848, 890714211, 188331960, 684788951, 962770200, 647749365, 692000110, 84789890, 537064226, 34450693, 41361159, 550194872, 245249510, 900342927, 708273455, 11582750, 128969774, 512056024, 55621840, 349004103, 637116327, 221258619, 579454604, 113893155, 576214565, 70474670, 23918406, 481813326, 650352628, 246808992, 284149773, 322921320, 932867440, 994253316, 940618752, 728504628, 428989277, 122474883, 119546567, 24132989, 106306057, 431011676, 611024275, 216092722, 58878209, 120907053, 721629563, 912245906, 362994491, 77928369, 598179975, 862251408, 302060801, 740845851, 459478020, 470575531, 272055896, 271404799, 997912850, 546477555, 102801686, 821058456, 253389281, 766070116, 630671870, 387593406, 363890599, 503970373, 198459011, 993364983, 210948547, 542855600, 819226189, 105570790, 913838629, 104902492, 762607730, 954174415, 72362182, 262189042, 660554698, 644882931, 306650491, 22189921, 453123535, 325669077, 343206525, 974951457, 351413353, 739439727, 691749300, 370158155, 944047087, 188614448, 382554560, 385741341, 62378861, 740868823, 256532720, 721260792, 546722312, 476298563, 606762613, 98776597, 898445055, 605244416, 333859175, 433695415, 401161555, 572855900, 243667256, 85343275, 675159111, 922771403, 996753883, 954048792, 469148681, 19943310, 296231983, 99393046, 204271242, 312577414, 956614050, 159362747, 723539464, 111719269, 894138283, 588450712, 602782641, 981925081, 900433722, 180543976, 267328359, 522848269, 4196876, 67000221, 107779275, 321728788, 528597009, 269434052, 964941752, 949825535, 975030569, 458728260, 549511657, 418171228, 245570031, 648210002, 972434486, 581872841, 635344873, 319802131, 678265430, 806155028, 954458488, 526854316, 847377932, 635338258, 992797405, 996032138, 354562941, 45336905, 183006406, 369367986, 247817599, 491651791, 494803388, 962480389, 263666033, 589248787, 333002562, 984917436, 533517314, 834849849, 760791455, 813814450, 264438765, 491534108, 918145304, 179243081, 160538845, 82373668, 881806227, 278695929, 385349193]
,[0, 45, 9779, 3749816, 187692415, 131617800, 403247903, 408395779, 233426110, 197302784, 177620321, 206888828, 835061252, 770003207, 167817536, 517820843, 580617827, 469175694, 251779825, 370582103, 72645164, 713328911, 277616510, 902795788, 659852725, 220506451, 987735057, 337008278, 326694483, 929531709, 623473947, 796684890, 777051644, 795130911, 868689620, 888962474, 15266105, 133906102, 896971307, 432781360, 609904712, 139195228, 582320632, 810000435, 144947710, 694533822, 353828777, 974567746, 545012102, 655590198, 684583110, 709008352, 516538184, 177659042, 730381723, 46966182, 70580724, 546296538, 649380101, 839329069, 521579662, 795443379, 918648017, 416884199, 467381920, 180180330, 922394205, 388926319, 338398209, 519862997, 15436054, 832899909, 25205988, 638023458, 397967187, 958525485, 625245409, 761065828, 308642848, 984865575, 166574801, 351074508, 483949359, 826042702, 587151802, 332893090, 23588721, 198575871, 217064634, 935342647, 875830166, 870762060, 431430866, 714037905, 451514552, 118685251, 876908840, 648215587, 848279668, 60298648, 631459253, 423970402, 946540283, 520092027, 98956341, 792001638, 336970096, 931916670, 592163792, 698538791, 255778677, 599081543, 736931826, 498542055, 487642144, 167722474, 425497074, 479036070, 196741185, 39983686, 490171826, 41410688, 950392180, 499418290, 916512858, 995578975, 364239372, 287759310, 305160181, 776807436, 795631950, 394372202, 993536736, 574952319, 609892554, 374430406, 859025147, 436507546, 532241817, 70196027, 667557733, 86629981, 53437441, 215255354, 775586987, 386301783, 329730035, 202594580, 163573385, 90440286, 830055244, 592282175, 146234819, 713607860, 431108208, 391672172, 89707230, 227887893, 635772628, 670074546, 823064293, 429723599, 720075550, 708101376, 728992627, 35839866, 649628048, 777233024, 769395244, 273231976, 452388241, 103609465, 50984607, 571111271, 37433616, 645071594, 241717405, 852257157, 792730997, 762093846, 260970344, 710690387, 581362111, 325183396, 887018246, 894572200, 248056865, 450822007, 28780679, 485097554, 610718927, 844021940, 806875641, 356112859, 159635847, 788536148, 115844061, 32006334, 343606685, 949709181, 501111333, 368083991, 85114366, 231716730, 758617505, 42613424, 792424028, 406591750, 7556235, 372313392, 875852936, 303229657, 493990389, 413068577, 970321428, 914931582, 883280547, 348694252, 48829705, 693879473, 956820845, 494398843, 524838672, 55642290, 291803820, 838072276, 937627886, 352806075, 872719356, 645619108, 203657091, 833772501, 188791198, 15808272, 336497713, 294256664, 801099446, 152749995, 41154832, 192492036, 312034558, 714016971, 939095632, 362217612, 344871905, 183574935, 889188174, 138994256, 960429161, 296389559, 883734447, 484177868, 83759713, 357767259, 405799384, 404997964, 179592455, 903922102, 309177362, 762328559, 846181321, 186860329, 535482051, 303516149, 218656364, 107450950, 239712834, 878534309, 957325925, 369018716, 743188094, 890784475, 179418699, 403243176, 82350077, 760467414, 628649939, 536068242, 546840675, 460160401, 131727617, 556807821, 103868149, 100658424, 320228785, 310512098, 723638547, 644759206, 54096166, 438468025, 280923557, 715718353, 545633130, 123399383, 171267284, 991718619, 983352761, 402614189, 319762846, 922715169, 183148106, 404824713, 482568353, 237420087, 669034731, 275370689, 906758281, 912995718, 736734514, 669078916, 551700747, 844999682, 490707946, 397056376, 72201274, 440950741, 308110319, 99342341, 252577468, 439457763, 862615164, 97430404, 650977533, 227567872, 732837766, 486412310, 424158571, 314727501, 706889056, 657623511, 936876993, 355562470, 9669720, 793140369, 959968300, 899351234, 219020216, 880286167, 595856391, 493610283, 799709671, 824990610, 720595839, 329639104, 976749337, 936889221, 809494863, 315709609, 237042146, 110330913, 567862810, 101728268, 746956576, 529866255, 586725298, 648040801, 779748452, 153236583, 914584631, 749408847, 513718701, 14088744, 993137657, 564190068, 564615128, 218058108, 134675641, 474742395, 687879968, 690548088, 277156362, 833518401, 580665444, 577772528, 19376544, 299323127, 895099027, 299338547, 839803398, 687138570, 578794727, 71021961, 41918341, 510329763, 609712540, 451003507, 709704951, 186996194, 578245109, 487769767, 658075788, 864769755, 506366568, 233278984, 86797707, 695583509, 153704084, 307322932, 831266923, 199868472, 103620682, 993020713, 659107946, 396528525, 448813397, 73914984, 907386095, 831778457, 594736347, 150616395, 988883526, 366215643, 167086401, 868932945, 313717943, 593312471, 235565012, 521329248, 311252446, 123949902, 964499849, 144982401, 326364967, 391588166, 501164095, 279706676, 683502822, 592927881, 202357005, 297878695, 111559939, 437962853, 837545570, 371947446, 187758155, 101943565, 305769633, 487510260, 916387514, 682044268, 61059324, 657929288, 460684128, 163896142, 161536407, 538311886, 723564214, 36418739, 327436336, 989827281, 124248645, 832708688, 882308790, 710452531, 77716353, 875129876, 836074411, 531835865, 56875321, 833407105, 423331035, 393581722, 167353704, 46338145, 795984501, 429448793, 921170554, 895713357, 399606530, 448677100, 376663936, 565811400, 301582936, 103096130, 89229646, 456280484, 935984940, 257863967, 62176804, 520077003, 989724020, 230216016, 198426323, 232816551, 723398169, 947598119, 145563483, 543560195, 769283254, 687695853, 412141785, 458246892, 322562821, 870174788, 792046447, 992281653, 261650102, 321433331, 28258915, 361339155, 916537223, 304030644, 26483722, 311683688, 962388783, 635976431, 109322303, 111089464, 562711339, 932659823, 884184806, 961770497, 482763443, 787907009, 283606372, 844167426, 96801505, 102993913, 616787769, 332259272, 90020691, 33473958, 108789187, 901500422, 168357636, 853210301, 871337077, 376008840, 609311701, 33409148, 458480523, 530786778, 390698056, 481382022, 680007463, 849208790, 270019810, 368593263, 287960378, 683678741, 840373286, 472091096, 256821798, 909688373, 636672904, 857109891, 992260814, 638259714, 682582093, 715207690, 600484323, 181860536, 177868141, 849248564, 743213709, 255749170, 601589780, 577202203, 715681221, 735331176, 522995960, 337047396, 380280967, 562020808, 449068543, 963757501, 321956499, 151307217, 161277903, 285233282, 762020021, 339297753, 69679348, 52568303, 535629098, 658030018, 319086680, 600634301, 532594728, 293331051, 603165887, 881090116, 441710021, 197876329, 311209998, 65489057, 438038471, 846586492, 841740111, 900892505, 272268279, 272662986, 89882804, 789135775, 548746487, 93712454, 214835785, 687205843, 809953436, 716639879, 931867150, 5763196, 404820388, 529438877, 222826259, 393767310, 372063277, 755012934, 553961581, 34305285, 137826363, 970617902, 758748623, 22630688, 297099624, 233382191, 919549105, 715661682, 204181124, 621028315, 733111353, 820512193, 577134999, 902996456, 829943695, 846032894, 905693877, 542196551, 252622955, 523732069, 530997965, 533006837, 460888302, 533952669, 844001205, 812367056, 483211338, 158530789, 288773918, 681553155, 968699783, 254686618, 449601998, 599196037, 225007854, 290070160, 539848030, 608861062, 188322344, 747926660, 538066172, 847178687, 798739308, 292443380, 645523492, 583709863, 519984309, 947227788, 785996221, 849492107, 217296632, 379082083, 328454321, 948218307, 458921548, 733036260, 335345610, 773876458, 744463437, 69765238, 106787889, 312188870, 578318834, 7590839, 644251670, 957688430, 335704885, 472634567, 890314526, 887231598, 869685716, 675313178, 908538033, 362098899, 320019526, 244292819, 322269049, 505039770, 483852205, 866472202, 694039567, 823738103, 892325140, 758360001, 346368562, 815348254, 412182503, 471602176, 990001493, 666290216, 161636116, 879511684, 412410210, 446019037, 337121630, 658855385, 784637957, 536675583, 404218240, 960104489, 897138435, 48992282, 548012990, 560174715, 792156454, 160189169, 705905872, 573054279, 928960434, 598430005, 723118328, 3133966, 709956394, 400173006, 843883821, 846982537, 379029168, 361068204, 661888589, 887835679, 493479920, 976133608, 354917572, 765784969, 49078976, 364396665, 502948009, 205972104, 807960031, 802286021, 744327814, 245246294, 420470862, 538828146, 696329703, 411129575, 588274570, 6230560, 547505555, 473360733, 576825268, 869928171, 485124875, 32250130, 382711654, 49947367, 690021132, 761491956, 113839876, 634613886, 973389949, 360297061, 350465803, 385111971, 501526753, 394165342, 117902532, 47188185, 669058037, 586179392, 803534253, 9867730, 117081149, 270343570, 869732012, 535560128, 74135321, 913166862, 745264069, 367865464, 623137053, 135895289, 799585395, 704614475, 888437551, 472048245, 210649737, 887519734, 367380507, 467654308, 310951744, 120246371, 1570185, 489874614, 177001364, 639465634, 752300677, 618186089, 125694494, 282846280, 736316609, 953882934, 653497932, 841032400, 979929908, 640731760, 744566282, 956866912, 308789171, 978715397, 648405630, 702106874, 252210450, 37223998, 173800106, 569247455, 870763443, 145425498, 15568087, 948078131, 543632996, 464071584, 555186162, 273468192, 844935944, 319095366, 541561522, 462755462, 976898547, 38432185, 745007341, 431518992, 996017081, 641720868, 979768983, 850953140, 572191500, 305562385, 828023713, 101969831, 319513329, 411569368, 498489858, 687104004, 861506575, 386766011, 47630047, 485950686, 906252626, 435904945, 523398217, 237981274, 184197706, 269135307, 723734629, 996762583, 961708129, 184077468, 987996423, 232884778, 412092659, 38185479, 920544354, 863648751, 226193943, 388570440, 67028234, 139276129, 987378193, 100903448, 903580344, 405505214, 867338867, 333622878, 921218665, 511487222, 463201346, 414182967, 124574190, 125984615, 331268678, 712901251, 926814813, 792501262, 571854656, 980486453, 67546855, 150063837, 986275190, 522883996, 773384884, 81195741, 381162217, 512867735, 787522767, 774407258, 380624609, 500979859, 425339121, 963880441, 911568272, 792258594, 350130673, 602869571, 264295247, 559699881, 354311181, 316717483, 974583423, 385148768, 775793636, 276045306, 192338240, 677282938, 975826894, 376504882, 438875821, 650005503, 18308145, 573861618, 505201938, 646594656, 659950897, 130894025, 249286645, 298317355, 654311532, 836465450, 865286055, 895177950, 246676014, 195480007, 816931196, 479506395, 881134448, 708030910, 402627578, 94318479, 239737460, 50326524, 124781860, 692461839, 182412976, 588599601, 905280444, 671991486, 149716817, 47905658, 64714287, 716724851, 557647216, 28241812, 713896117, 846376494, 206401418, 428739231, 942397989, 324941900, 306688147, 258918808, 206428157, 459115203, 714606128, 901629112, 466484868, 310408763, 294905148, 749311051, 394101771, 403806550, 498739596, 248404900, 190125924, 522025988, 356210447, 962389205, 814535861, 3980315, 250331408, 790031419, 402340345, 314834487, 602818980, 373056826, 513025448, 514106359, 330630795, 280415656, 110664532, 260357566, 438075255, 589257527, 858090853, 422891205, 620257075, 790506377, 952563016, 765975974, 960893637, 543352842, 365161673, 624020379, 800469365, 251809505, 622790780, 765922253, 402911760, 997555042, 559439272, 29544238, 878217449, 228591540, 899811201, 871109199, 546784719, 253989180, 599758115, 684560325, 694533607, 280703340, 236096123, 66961640, 589317182, 148043719, 775804319, 268637104, 330635805, 56702421, 125110763, 721113904, 467948371, 559561215, 304843404, 297100892, 617590242, 296473496, 369817637, 718004636, 526124218, 325406214, 131642557, 869709758, 216629105, 687991036, 573256824, 311737341, 758758392, 234589476, 806451920, 213768729, 631008009, 285161193, 822185858, 233315562, 217016673, 677480896, 804760339, 303459984, 221413383, 399022533, 365958714, 40799195, 381705662, 789465567, 637528335, 343565435, 451970239, 746068672, 166867880, 819274545, 76504657, 397541090, 634573222, 532288800, 461447953, 593079116, 206340568, 73124197, 802335966, 905865702, 467513529, 84938694, 290540136, 695515463, 3667894, 705686513, 717484972, 407798786, 866250512, 73759857, 988625790, 225509686, 921183249, 230949763, 381533094, 278804584, 32480390, 574582357, 123789423, 768169179, 487732014, 297765428, 731832401, 432860256, 598148966, 289492130, 97013575, 442023507, 762069525, 931825284, 458140597, 189544522, 921471521, 275855481, 956391146, 193634695, 84677511, 113885808, 830941679, 431684736, 119795183, 940323412, 300483044, 11521577, 885580158, 695593645, 494983307, 139383566, 821276667, 477452984, 683243183, 361935517, 273621685, 4025495, 476432519, 678629225, 920228510, 134283532, 278793091, 224178916, 869681152, 174441945, 438098978, 983179206]
];
uint[][] CS = [
[]
,[1, 1000000004, 3, 1000000006]
,[1, 1000000003, 4, 0, 1000000006]
,[1, 999999998, 26, 999999972, 22, 3, 999999991, 9, 1000000006]
,[1, 999999990, 90, 999999777, 272, 75, 999999384, 632, 999999942, 999999752, 198, 999999845, 96, 999999996, 1000000006]
,[1, 999999966, 626, 999994795, 26632, 999916042, 135637, 57937, 999199739, 1620135, 999093191, 998485993, 2551590, 997377220, 7154119, 991457770, 993019186, 21987911, 983996162, 6152683, 999036138, 990231089, 13699534, 997404693, 994521618, 3355642, 999776210, 999597590, 189183, 999956725, 4214, 198, 999999956, 1]
,[1, 999999918, 3110, 999939541, 742664, 993958208, 31995434, 906653130, 979867988, 450143629, 57940041, 51719115, 329658325, 705040706, 38479371, 724108123, 810715054, 484591080, 77586872, 13495283, 20514139, 279183132, 513975810, 178497912, 771592522, 295194475, 776332021, 223981658, 58083192, 17050708, 16230911, 494464705, 476519393, 189155785, 937991413, 54201070, 63313885, 20151946, 118575609, 776692687, 610711296, 884756831, 128167752, 845202278, 735369307, 206268113, 525852836, 826291169, 922972595, 693304349, 776356265, 548131137, 141958987, 152522485, 798387263, 987311741, 558683120, 404633960, 238042460, 920984885, 675315088, 341916115, 676073373, 221240708, 211895609, 29348012, 576165, 999444951, 999942165, 999998535, 107, 1]
,[1, 999999781, 22133, 998708004, 51265818, 517360108, 546845912, 149828812, 946233573, 211651202, 232405750, 811285267, 401128294, 116600453, 290384294, 677300925, 13623411, 155729746, 111188901, 452410975, 117842397, 332838981, 970845792, 94569547, 820027654, 200913625, 890068520, 67908380, 76368293, 461783299, 774230873, 809781530, 66759279, 19585253, 349823801, 504256321, 826122746, 84252359, 578059214, 341123611, 323641562, 621647519, 633413775, 635711110, 932952837, 35095443, 981566491, 537648957, 564758649, 706798990, 100000385, 128921008, 717726991, 383849221, 750895077, 470510190, 554514183, 475290790, 79252471, 926030996, 307209159, 522079494, 32775585, 101415276, 271705401, 266458448, 606062420, 260120971, 123407489, 837735148, 245028769, 821505999, 329034147, 44511599, 943629170, 138511469, 145790140, 346792223, 395988572, 925480272, 909141629, 573883305, 305237182, 934272686, 724968146, 362587964, 615079501, 821387966, 307899471, 611914183, 219979031, 157062462, 192214867, 530161994, 276049689, 109370078, 332843953, 437308315, 752536534, 225262744, 767746693, 118820492, 659915009, 148956346, 342326029, 932826231, 121257500, 190435414, 682932862, 93801129, 679311932, 391327856, 174721612, 371261815, 658110054, 823002334, 293616027, 350408100, 31341195, 162686635, 380434359, 514468457, 464117410, 565005604, 56215077, 112578061, 257377860, 902941141, 918227775, 565229996, 757086971, 827775747, 329062828, 480907436, 157361700, 70022425, 878622562, 520826406, 187978351, 283088291, 593161595, 117585205, 327508906, 663456512, 92016231, 699721310, 209521382, 807714963, 131675232, 261081137, 577438817, 42318841, 923821258, 380930212, 199917502, 581730944, 726241975, 812221768, 292515948, 848519168, 545507143, 238738168, 216060021, 879877364, 711496839, 917027319, 282174451, 185267082, 643028099, 857050431, 163144958, 546075680, 193151642, 893859690, 268322266, 377828077, 871297985, 1077829, 18317, 999999639, 1]
,[1, 999999487, 121621, 982609880, 728058965, 987778989, 174829068, 53727628, 7205002, 429985264, 238803947, 725474573, 741291920, 842076511, 80566125, 630047723, 243273237, 704919909, 467750756, 898645900, 284015712, 120666140, 525076163, 502048647, 41285713, 236154320, 944501774, 488500488, 710436225, 929390983, 946198532, 360474668, 349764997, 546341165, 947196857, 642988951, 368966218, 168715782, 469670802, 231397888, 68229010, 683271338, 664890364, 139880593, 745193967, 857773494, 996357368, 296985699, 387800445, 999535757, 347864702, 663192692, 941229752, 652195017, 974804757, 617212988, 303782980, 637798607, 506484052, 240297013, 25400671, 836103437, 265982407, 689584959, 996104694, 900416203, 918296796, 522286080, 187612087, 362933090, 864532307, 302981624, 112204968, 54400905, 784706585, 26473224, 668712640, 375257376, 41403686, 733299902, 290472213, 417704505, 968163964, 206305019, 642117922, 452197323, 528501014, 758704660, 723789950, 861488883, 186442869, 911469844, 189585922, 385531334, 883639965, 340445857, 803030761, 906058405, 283729103, 556838458, 207205455, 236582603, 332247614, 512751191, 978031986, 933348343, 439583198, 259555183, 667111524, 134423267, 627265370, 1218547, 652309453, 774086416, 819442729, 303725740, 362324759, 808079315, 666491770, 170076746, 67455926, 981783870, 962127145, 308555979, 63650406, 671285897, 392101680, 496994999, 356899672, 113429770, 530326097, 799630760, 988646538, 838587591, 155025630, 192022364, 334997493, 224438207, 150157191, 926202557, 508901327, 384387352, 201600983, 922499010, 934485700, 211414346, 320838066, 944419484, 970282204, 759269994, 379210257, 366839751, 849660169, 369564163, 397878810, 842191624, 914513850, 81262954, 512817858, 699572773, 73984848, 652395150, 274641274, 19567651, 313454866, 517733797, 732834732, 683830859, 851387499, 41462608, 755742719, 327386893, 146422653, 280719585, 245862381, 75849368, 400405900, 623426624, 323900502, 995684701, 649837950, 712790652, 689384867, 712068630, 251496879, 603708479, 652192881, 830106386, 434833194, 562491712, 7093190, 794371622, 230556813, 346620116, 863101446, 583807218, 349090587, 349434449, 580680839, 164857387, 858407370, 420826464, 111043596, 706255236, 828752073, 486821786, 945421669, 334275891, 7749670, 469804619, 531998487, 577456543, 437330438, 192802364, 339161210, 79451038, 697562910, 762676651, 378714174, 136277270, 612489667, 226816771, 18447731, 814031151, 302415632, 895311508, 826637650, 480121030, 72644533, 104253907, 526628766, 785779519, 212194261, 162176985, 229171858, 660299181, 405518105, 475658895, 271893670, 153602347, 227044504, 493230361, 220368386, 2456839, 278002827, 509864003, 579236359, 144720094, 69430502, 353996002, 902690656, 738366048, 18491633, 902501522, 549399509, 522545766, 557160850, 294333309, 944294748, 733035016, 521453600, 654630136, 355163957, 83445555, 446062789, 602883516, 58164724, 907889336, 968279122, 486960845, 6092978, 488051217, 239187866, 500350824, 446413026, 364867970, 293570497, 437561632, 546514652, 353147020, 184699732, 342059370, 90908034, 203706709, 419444183, 495246668, 590236228, 529826205, 783503620, 543077435, 389342496, 300468224, 737345482, 593103076, 962272241, 268050333, 700208604, 630238783, 377190644, 663585254, 531081907, 562207598, 560055481, 462273498, 340097385, 577843235, 438543318, 542695407, 240460506, 85696197, 852960749, 708243855, 357474416, 35233189, 886404820, 783773695, 580663937, 979996091, 54888582, 153040947, 805904119, 560313486, 116387497, 794826272, 896287073, 767874291, 430061171, 754591084, 641547207, 599926992, 982019810, 84811201, 545913874, 673760737, 565719119, 887158365, 542060632, 884307697, 809680891, 644419759, 749572988, 894828730, 645628517, 789681045, 397480957, 690692127, 925108787, 631439798, 221405719, 420992738, 823536228, 850184166, 686938582, 561412994, 694931701, 590472721, 857763370, 547795108, 908024031, 163676569, 93224809, 952424240, 603702399, 777896391, 615989257, 387932407, 947630136, 596984018, 844375184, 408007263, 527596252, 126707118, 904693720, 637968858, 181854776, 988697472, 216218687, 884035973, 801361388, 871033102, 799464827, 419251246, 860180888, 670516234, 13638879, 174702108, 43525788, 380590669, 150639864, 155316288, 473919774, 213510789, 852837503, 258472507, 369947189, 718610519, 657211677, 950407319, 309727757, 488494822, 113764870, 952317721, 323855947, 982056241, 119995213, 903306923, 573858592, 335915859, 665953195, 729432528, 421470818, 444041677, 440431099, 828648704, 521790123, 730000703, 609341909, 439574410, 852276450, 76946971, 58248143, 435433334, 803096862, 777840536, 960372939, 89722122, 328721511, 305873657, 57219747, 566132089, 355343950, 589824792, 224852426, 977308292, 38843, 850, 1]
,[1, 999998634, 887468, 636765977, 512955430, 525538310, 263188713, 723603795, 663342771, 426029874, 465917941, 373172336, 471704457, 374416355, 90720607, 963591976, 383389817, 992867728, 387967057, 390941572, 175887743, 527637438, 907504359, 995034273, 975557621, 770794884, 318998174, 418277007, 924200673, 80796745, 446606388, 39013644, 87909285, 153438989, 75423150, 33138204, 836049554, 83516262, 270722166, 296760831, 606272291, 578760298, 749044898, 932574756, 532785966, 638095905, 648265703, 799294492, 204769497, 955271760, 752030222, 308839561, 881538231, 161756750, 148346572, 9071147, 17237043, 184452281, 564082255, 330692428, 739212293, 707636504, 953269920, 217921818, 314118749, 520150234, 62649533, 827359956, 831719578, 318980353, 226472927, 807716175, 105271580, 313191103, 593471752, 996256970, 793592044, 156539568, 114712417, 393656163, 428156850, 899213550, 805684845, 814163441, 964433169, 787384611, 817127197, 472959112, 701518041, 360685647, 621707852, 491366042, 956499001, 734377890, 993818110, 602143401, 924419979, 872051934, 141663455, 78603207, 531565266, 910627798, 853688947, 19294036, 920243768, 30273821, 281553994, 607934591, 42457358, 582559393, 14657389, 534910961, 155813558, 25410440, 135626065, 307764773, 766499510, 120141812, 499621443, 310846754, 142009620, 150026338, 628053072, 133383727, 323867994, 912776511, 624993249, 977582982, 973570163, 612638585, 779736102, 721939712, 180767932, 137222963, 411616687, 125962869, 13378164, 393885569, 66561015, 663116966, 464841646, 486136046, 189563926, 869882201, 302054688, 635074760, 48614053, 521405223, 489300064, 746293387, 963233328, 530252777, 425045195, 311452627, 860340857, 180599476, 157565365, 453868374, 397105781, 809919285, 588463039, 15314268, 660910612, 804562453, 835216831, 768323323, 370185013, 691315867, 380585151, 78674131, 239678521, 155686467, 94677753, 59598160, 220840085, 684279558, 217290022, 109891184, 537533994, 788550460, 493818683, 398326064, 100654646, 91818874, 748945885, 13967106, 999584994, 117149360, 155794470, 571414884, 842747259, 27619428, 708243130, 555454982, 132710029, 359258633, 649254832, 96073570, 164623856, 695815112, 433785701, 144702297, 287008859, 208486309, 582462971, 818808524, 624194385, 829364850, 767325231, 374192297, 383851216, 738357704, 779132099, 498306982, 328195479, 477313943, 558409401, 371209236, 956319182, 308596107, 117333624, 293875220, 770314431, 17785829, 214273614, 204584119, 1885352, 780917052, 611432218, 636571429, 88982515, 220961381, 136741667, 188431674, 363996303, 565021830, 748623169, 967051752, 505227200, 976504403, 483333177, 308335078, 252003793, 742575387, 117566958, 316162961, 326062761, 936108821, 791872863, 750773942, 111991111, 116963784, 220708288, 696125856, 933859774, 646508845, 236485719, 20856496, 979894319, 960044698, 138632529, 543500774, 884058526, 237429450, 58221448, 45757574, 769671472, 447171964, 331552052, 922834877, 252964523, 664226175, 183022332, 606265167, 339303689, 259823103, 386888293, 456424734, 264719437, 542405816, 61014214, 579557574, 570833325, 673723287, 923365863, 463740456, 464324063, 244701079, 508482473, 755158690, 308038108, 868776133, 885173340, 214289642, 911248450, 221722543, 827133960, 500985325, 225421199, 247305708, 521460412, 392123474, 88393916, 921924998, 670279037, 509375238, 565038799, 920284560, 975304356, 198634940, 519729553, 168077726, 679142010, 359629911, 354565784, 462518581, 638310372, 120298036, 713512692, 745047820, 447806631, 229105402, 693687635, 967738727, 988166857, 478650666, 934929168, 256021584, 499561074, 138903129, 836960011, 716814465, 634488588, 995045809, 3579592, 374835562, 744275649, 90380511, 257773156, 640608445, 676879587, 430016053, 912191060, 404304927, 310193629, 118932777, 966949225, 543282539, 889279307, 681655812, 95752265, 732338572, 798957510, 388113918, 868845304, 63433967, 121049105, 385117354, 849911462, 69911011, 121222552, 435855305, 677326463, 896682737, 672775134, 135713567, 187997959, 758080922, 854610996, 246856578, 611090572, 304445917, 123388453, 73222325, 878310198, 408659279, 515745945, 286533478, 316598487, 46958408, 853604087, 432874269, 11032266, 590981153, 794365040, 548753964, 630858088, 589633475, 36775454, 24490596, 695412533, 424127744, 853134294, 791581147, 272666228, 571765352, 549437872, 53758664, 653995891, 527094987, 892515125, 508079938, 222515632, 550508162, 386906276, 720884286, 600488256, 361858313, 174743385, 391972274, 518509829, 310454767, 185986944, 178791476, 584814673, 642140859, 812783458, 693804635, 923561626, 425371988, 830134796, 487122015, 881828835, 870140021, 813168849, 288326091, 242817999, 625727136, 227470782, 794766334, 314375597, 913073972, 624410345, 890817174, 240809544, 56407029, 731823406, 501915110, 27476215, 548245010, 716349128, 524168039, 417769653, 8586882, 31166870, 632949179, 888561310, 129554943, 619396566, 39625246, 234860680, 291386311, 740663132, 335836890, 786742556, 105157797, 964597128, 689192126, 95735934, 474554916, 540166926, 120056440, 573796043, 526302779, 379352121, 335250356, 91932472, 24456515, 655357702, 177825658, 273631310, 703150156, 679386464, 860947276, 968783942, 511284994, 639490913, 578488155, 677841260, 166000409, 602307025, 985019676, 923729003, 729476310, 136109704, 284749271, 522837466, 397516033, 73056708, 1079340, 625377850, 722682687, 768821892, 581572980, 950764922, 746870966, 444334755, 665874851, 661377657, 940995412, 963081675, 77278279, 577231116, 242536390, 674919117, 515911260, 859428450, 958553647, 571412759, 713007028, 228071352, 327275188, 443218927, 913554812, 607741011, 792151329, 513850403, 532876855, 139626039, 252889099, 675166660, 563041269, 370848153, 597267281, 921068146, 553300880, 721080291, 899433543, 781433901, 335967887, 210694213, 505038856, 664282057, 992763583, 338025707, 193497833, 876462511, 476965025, 167571210, 814924575, 321173468, 300677987, 462714259, 708123227, 221868248, 448701061, 163647083, 916355960, 781511521, 99293964, 273311414, 163417638, 145634981, 908779048, 809636616, 837765599, 420832395, 239095347, 801318026, 853894182, 600645274, 907627540, 762184454, 793293168, 885649457, 155422657, 644743445, 10206734, 143901315, 305920251, 175684819, 838672, 866944322, 483316669, 944104244, 242003185, 246439089, 339108439, 282673140, 443726190, 463542957, 635720729, 431791768, 450009688, 555642602, 238091229, 461217484, 770328990, 991872604, 522750228, 822281455, 387740481, 887611461, 111535658, 511178348, 659448949, 597246427, 706958673, 514833, 109243689, 834213503, 137085595, 98851645, 101688111, 108699309, 887141640, 329470574, 308693780, 328461500, 425599814, 526225648, 448264531, 888110697, 479488490, 863216709, 317067808, 759435334, 592217643, 260280758, 41519528, 160082770, 860326027, 496449401, 495668709, 234331302, 449573203, 176904473, 93212799, 958101457, 545015436, 820967634, 563296471, 336685110, 423580019, 987089736, 784111517, 878745857, 535420954, 416396185, 485432719, 97194216, 830274486, 524906813, 61946450, 436734522, 177556551, 914916605, 132168363, 888689493, 326600816, 834309630, 788615493, 716233754, 890966556, 689147663, 963745520, 294781020, 244487576, 648302165, 698437501, 956060464, 62649118, 122452833, 231683728, 179184395, 870475103, 92066698, 752021384, 862716816, 135452402, 309842828, 496762430, 281075790, 58075351, 523812771, 601130188, 594865117, 521525761, 923644861, 268771803, 187784311, 103817575, 418826495, 344648958, 829681127, 348094629, 563389769, 137664581, 19205041, 809660555, 886436947, 949644232, 865608001, 970073278, 819566210, 80484367, 356281683, 573846132, 392309173, 178355283, 521963079, 300840049, 824031155, 123946819, 528665456, 362683831, 399155039, 453436298, 659723037, 757885199, 107881930, 993520154, 742233487, 697527461, 67363836, 102854731, 550265866, 529219228, 612183298, 663070607, 605998407, 734647597, 427811238, 178315801, 876664013, 253547527, 960588710, 649393471, 164822117, 73236452, 626390971, 331956502, 647978083, 493004813, 898717942, 514840676, 962877678, 722435496, 660064255, 741146076, 13919165, 407860414, 744072262, 801735376, 887799652, 190384062, 986617306, 93899888, 682403108, 968293247, 148423221, 328578142, 49840930, 548948047, 644869612, 661483156, 299894639, 828058724, 83604729, 15611259, 334996708, 256867466, 794072866, 389474596, 365001136, 918386893, 444905336, 21185636, 687563048, 761714354, 738432134, 761006149, 752747760, 864657245, 338657790, 158159430, 720902059, 741719695, 812168470, 796592514, 722266704, 927239385, 437940916, 493929496, 490480930, 705685913, 148767413, 485983444, 89126870, 932366328, 394311274, 874277287, 476167235, 506084552, 562446339, 76763965, 90907667, 851639756, 967312702, 723319887, 751696047, 952848342, 100816774, 578421205, 861935900, 38089218, 321958510, 17382277, 11524455, 592391551, 505963973, 462253958, 108703025, 607374561, 639133718, 886081515, 722994210, 61834394, 407482391, 456692341, 461760111, 130958636, 511084926, 54062691, 70775864, 289964743, 364800199, 988972988, 23871665, 85145094, 818209109, 917636208, 502864659, 35350184, 815451060, 989631917, 142980133, 798249471, 237624348, 606243935, 864831660, 118627048, 99036299, 42238937, 346340655, 545273792, 567015313, 720329351, 823479844, 882929487, 384395578, 797882659, 295950529, 349779954, 34154355, 427805571, 729598924, 49278931, 793890934, 929891152, 746233170, 547461158, 522817670, 981418181, 15193421, 41781169, 636135321, 577580146, 5964243, 64517365, 56768936, 380825421, 15716078, 783408725, 462483489, 632327355, 848851954, 61427551, 805667525, 176033345, 418470057, 855472087, 688623396, 455908563, 29616323, 433159860, 225339137, 740392284, 888935806, 665103011, 606244755, 502013715, 388760860, 776788528, 277268937, 237934207, 100199628, 274957208, 455214611, 739393510, 332721000, 730827374, 149104414, 508150451, 617153235, 695104685, 928841024, 514012598, 324076019, 354840271, 907284628, 681632451, 277893038, 879024123, 851791236, 837589465, 352174973, 519651011, 782562875, 202656727, 355512281, 990209292, 490680151, 508964529, 393133746, 583016190, 718651208, 500279812, 302852404, 345279890, 301100327, 500286045, 908139904, 796970687, 752283086, 205901880, 642711922, 816250085, 305217687, 189407116, 50517712, 418454600, 124088743, 788490148, 245791183, 34486677, 397532777, 110633380, 983168687, 268420035, 263123869, 800106675, 722941531, 725647782, 487579756, 768338253, 602993, 193033876, 629428967, 166273016, 349612330, 171107996, 762235392, 267470783, 427641079, 13383714, 402101930, 398940074, 877982217, 638853579, 715086356, 120222650, 863722183, 191842250, 955079918, 198407224, 905774037, 137081145, 344671879, 374292999, 676610027, 576374590, 633610541, 896352642, 24976184, 843710568, 577551952, 297154735, 50457832, 272989769, 62953344, 710692718, 787400483, 863480460, 100461791, 634958064, 253923471, 937569180, 819813666, 516941111, 976478434, 916708104, 480681648, 323316751, 994195648, 319955565, 720027672, 639589801, 231486854, 403729696, 302235622, 272403274, 445320248, 610401104, 969148013, 388341900, 590475476, 637356187, 567858155, 816345764, 569661057, 340816142, 394291560, 476248978, 578865195, 889166585, 47113815, 520428784, 336542468, 274779009, 824207398, 323985852, 629330435, 399379037, 82661867, 469235669, 250259693, 667622574, 389583309, 323272209, 685828869, 583024151, 562432957, 595445633, 156373582, 408232309, 360900093, 515794409, 545342710, 184147235, 918810876, 932442780, 820313351, 179682138, 965540209, 129727143, 911369151, 352579754, 38546435, 95687532, 971080160, 652561608, 156062732, 610479020, 902044767, 9337295, 301989687, 243625359, 261208471, 378979899, 242626014, 751359956, 968580027, 393168509, 924321812, 647751516, 556290208, 872977075, 800826621, 199310310, 437094045, 659426486, 577909113, 660048988, 837915820, 393907243, 942521929, 255804362, 950067297, 434407016, 999800271, 840079405, 117308643, 882966929, 302161847, 809504464, 842726551, 973612005, 422899737, 291205927, 639919449, 302558127, 75365727, 335870847, 839348444, 180838947, 75591691, 829487121, 307727773, 238841009, 330790782, 502618921, 477143691, 983895071, 705513480, 769936442, 576528085, 466863065, 860143685, 974756020, 267619825, 825191367, 641726662, 344240382, 900675477, 210552637, 685077842, 228148626, 125247389, 369452687, 104296235, 711361075, 249868562, 734763102, 294504257, 692399212, 861495097, 706749917, 674459620, 444166015, 78442197, 998202226, 2830, 1000000006]
];
void main() {
debug {
enum L = 3000;
foreach (N; 1 .. 9 + 1) {
auto as = new Mint[L];
Mint[int] crt;
crt[0] = 1;
foreach (x; 0 .. L - 1) {
foreach (y; 0 .. N) {
Mint[int] nxt;
foreach (p, val; crt) {
if (p == -1) {
if ((-1) !in nxt) nxt[-1] = 0;
nxt[-1] += val;
continue;
}
int[9] fs;
foreach (z; 0 .. N) {
fs[z] = (p >> (3 * z)) & 7;
}
debug {
if (N == 4 && x < 3) {
// writeln(x, " ", y, " ", fs, " ", val);
}
}
// white
{
const pp = p - (fs[y] << (3 * y));
if (p) {
if (pp) {
bool ok;
ok = ok || !fs[y];
foreach (z; 0 .. N) {
ok = ok || (y != z && fs[y] == fs[z]);
}
if (ok) {
if (pp !in nxt) nxt[pp] = 0;
nxt[pp] += val;
}
} else {
// ending
if ((-1) !in nxt) nxt[-1] = 0;
nxt[-1] += val;
}
} else {
// not started
if (pp !in nxt) nxt[pp] = 0;
nxt[pp] += val;
}
}
// black
{
if (y >= 1 && fs[y - 1]) {
if (fs[y]) {
const f1 = fs[y - 1], f0 = fs[y];
foreach (z; 0 .. N) {
if (fs[z] == f0) {
fs[z] = f1;
}
}
fs[y] = f1;
} else {
fs[y] = fs[y - 1];
}
} else {
if (fs[y]) {
//
} else {
fs[y] = 7;
}
}
int id;
int[8] tr;
int pp;
foreach (z; 0 .. N) {
if (fs[z]) {
if (!tr[fs[z]]) tr[fs[z]] = ++id;
pp |= tr[fs[z]] << (3 * z);
}
}
assert(id <= 6, format("HELP N = %s, x = %s, y = %s, fs = %s", N, x, y, fs));
if (pp !in nxt) nxt[pp] = 0;
nxt[pp] += val;
}
}
crt = nxt;
}
foreach (p, val; crt) {
if (p == -1) {
as[x + 1] += val;
continue;
}
int[9] fs;
foreach (z; 0 .. N) {
fs[z] = (p >> (3 * z)) & 7;
}
int mx;
foreach (z; 0 .. N) {
chmax(mx, fs[z]);
}
if (mx == 1) {
as[x + 1] += val;
}
}
}
const cs = as.findLinearRecurrence;
debug {
writeln("N = ", N);
writeln("as = ", as[0 .. cs.length]);
writeln("cs = ", cs);
writeln("|cs| = ", cs.length);
stdout.flush;
}
}
}
try {
for (; ; ) {
const N = readInt();
const M = readLong();
auto as = new Mint[AS[N].length];
auto cs = new Mint[CS[N].length];
foreach (j; 0 .. CS[N].length) {
as[j] = AS[N][j];
cs[j] = CS[N][j];
}
const ans = solve(as, cs, M);
writeln(ans);
}
} catch (EOFException e) {
}
}