#1014435 (C++23) No.2883 K-powered Sum of Fibonacci

提出ソース
結果

問題	No.2883 K-powered Sum of Fibonacci
ユーザー	Ryuhei Mori
提出日時	2024-09-29 20:08:20
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 3,000 ms
コード長	61,369 bytes
コンパイル時間	1,341 ms
コンパイル使用メモリ	109,280 KB
実行使用メモリ	6,824 KB
最終ジャッジ日時	2024-09-29 20:08:22
合計ジャッジ時間	2,449 ms
ジャッジサーバーID （参考情報）	judge4 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,816 KB
testcase_02	AC	1 ms 6,820 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	1 ms 6,820 KB
testcase_05	AC	1 ms 6,816 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	1 ms 6,816 KB
testcase_08	AC	1 ms 6,820 KB
testcase_09	AC	1 ms 6,816 KB
testcase_10	AC	1 ms 6,820 KB
testcase_11	AC	1 ms 6,820 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	1 ms 6,816 KB
testcase_14	AC	1 ms 6,816 KB
testcase_15	AC	1 ms 6,816 KB
testcase_16	AC	1 ms 6,824 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	1 ms 6,820 KB
testcase_19	AC	2 ms 6,816 KB
testcase_20	AC	1 ms 6,820 KB
testcase_21	AC	2 ms 6,820 KB
testcase_22	AC	2 ms 6,816 KB
testcase_23	AC	2 ms 6,816 KB
testcase_24	AC	1 ms 6,820 KB
testcase_25	AC	1 ms 6,816 KB
testcase_26	AC	1 ms 6,816 KB
testcase_27	AC	2 ms 6,816 KB
testcase_28	AC	1 ms 6,816 KB
testcase_29	AC	1 ms 6,820 KB
testcase_30	AC	2 ms 6,816 KB
testcase_31	AC	1 ms 6,816 KB
testcase_32	AC	1 ms 6,820 KB
testcase_33	AC	1 ms 6,816 KB
testcase_34	AC	1 ms 6,816 KB
testcase_35	AC	1 ms 6,820 KB
testcase_36	AC	1 ms 6,820 KB
testcase_37	AC	2 ms 6,816 KB
testcase_38	AC	2 ms 6,820 KB
testcase_39	AC	1 ms 6,820 KB
testcase_40	AC	1 ms 6,816 KB
testcase_41	AC	1 ms 6,820 KB
testcase_42	AC	2 ms 6,816 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <iostream>
#include <vector>

using i32 = int;
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

template <i32 MOD>
struct Mint {
  i32 n;
  constexpr Mint(i32 n = 0): n(n) {}
  constexpr Mint operator-() const { return Mint(n ? MOD - n: 0); }
  constexpr Mint &operator+=(const Mint &rhs){ n += rhs.n; if(n >= MOD) n -= MOD; return *this; }
  constexpr Mint &operator-=(const Mint &rhs){ if(rhs.n > n) n += MOD; n -= rhs.n; return *this; }
  constexpr Mint &operator*=(const Mint &rhs){ n = (i64) n * rhs.n % MOD; return *this; }
  constexpr Mint inv() const {
    i32 x = MOD;
    i32 y = n;
    i32 b = 0, d = 1;
    while(y){
      i32 q = x / y;
      x = x % y;
      b -= q * d;
      std::swap(x, y);
      std::swap(b, d);
    }
    if(b < 0) b += MOD;
    return b;
  }
  constexpr Mint &operator/=(const Mint &rhs){ n = (i64) n * rhs.inv().n % MOD; return *this; }
  friend constexpr Mint operator+(const Mint &lhs, const Mint &rhs){ return Mint(lhs) += rhs; }
  friend constexpr Mint operator-(const Mint &lhs, const Mint &rhs){ return Mint(lhs) -= rhs; }
  friend constexpr Mint operator*(const Mint &lhs, const Mint &rhs){ return Mint(lhs) *= rhs; }
  friend constexpr Mint operator/(const Mint &lhs, const Mint &rhs){ return Mint(lhs) /= rhs; }
  friend constexpr bool operator==(const Mint &lhs, const Mint &rhs){ return lhs.n == rhs.n; }
  friend constexpr bool operator!=(const Mint &lhs, const Mint &rhs){ return lhs.n != rhs.n; }
  friend std::ostream &operator<<(std::ostream &os, const Mint &rhs){ return os << rhs.n; }
};

template <class T>
T modpow(T x, int n){
  T r(1);
  for(; n; n >>= 1){
    if(n&1) r *= x;
    x *= x;
  }
  return r;
}

constexpr u32 mod = 998244353;
using mint = Mint<mod>;

using poly = std::vector<mint>;

poly mult(const poly &lhs, const poly &rhs){
  poly r(lhs.size() + rhs.size() - 1);
  for(u32 i = 0; i < lhs.size(); i++){
    for(u32 j = 0; j < rhs.size(); j++){
      r[i+j] += lhs[i] * rhs[j];
    }
  }
  return r;
}

void printv(const poly a){
  for(u32 i = 0; i < a.size(); i++) std::cout << a[i] << ' ';
  std::cout << std::endl;
}


std::vector<std::vector<int> > init_vector() {
  std::vector<std::vector<int> > v(101);

  v[1] = { 1, 1, 998244352 };
  v[2] = { 499122177, 499122176, 499122176, 0 };
  v[3] = { 748683265, 499122176, 998244351, 249561088, 499122177 };
  v[4] = { 339403080, 958314579, 578981725, 598946611, 19964887, 918384805 };
  v[5] = { 930182238, 476434805, 204186346, 113436858, 385685317, 930182238, 45374743 };
  v[6] = { 890794440, 291154603, 485257672, 499122176, 512986680, 707089749, 107449913, 0 };
  v[7] = { 238608564, 219050485, 963039811, 981815566, 14864138, 994332736, 740077709, 759635789, 549190859 };
  v[8] = { 330862545, 928123233, 652341593, 921135523, 620242493, 623348140, 132677765, 818405086, 463207563, 95831458 };
  v[9] = { 259556296, 957625311, 734107349, 86312891, 273936632, 173387517, 984008129, 336213671, 559731633, 259556296, 646857729 };
  v[10] = { 721804856, 368811264, 919050764, 549178441, 954805239, 499122176, 43439113, 449065911, 79193588, 629433088, 276439497, 0 };
  v[11] = { 161826008, 816745328, 208147981, 473543199, 153874493, 98940964, 633576700, 688510229, 368841523, 103446305, 493093311, 836418345, 712820338 };
  v[12] = { 396213251, 383539051, 829613653, 924222510, 520726042, 857172758, 621714561, 679033641, 33699314, 626026124, 811252409, 873938889, 927924797, 42613055 };
  v[13] = { 794836047, 614952228, 628285227, 666553652, 138109672, 959771687, 708418927, 346570037, 597922797, 421340459, 949784439, 988052864, 974719865, 794836047, 574586305 };
  v[14] = { 959921524, 378982742, 978819588, 974931739, 788314987, 915711243, 793316150, 499122176, 204928202, 82533109, 209929365, 23312613, 19424764, 619261610, 38322829, 0 };
  v[15] = { 929301261, 97272708, 666231055, 728850593, 268331495, 753753799, 164610813, 814226179, 915275483, 265660117, 674761484, 189339180, 727064435, 664444897, 235158891, 68943092, 916003548 };
  v[16] = { 264253432, 545017500, 648965965, 601747590, 778260787, 586355456, 59872580, 424200680, 609379404, 286390002, 674489040, 234263834, 158066635, 811939604, 331622452, 243887907, 228119779, 808076408 };
  v[17] = { 41671059, 174044727, 945234040, 195284391, 104160319, 386502618, 249425620, 539208548, 864162733, 955064240, 630110055, 919892983, 58725628, 341067927, 432191999, 680486703, 907541743, 41671059, 317187483 };
  v[18] = { 84839535, 745733368, 499309857, 115223673, 527901968, 93367628, 79946092, 243713287, 938869330, 499122176, 59375022, 754531065, 918298260, 904876724, 470342384, 883020679, 498934495, 252510984, 913404818, 0 };
  v[19] = { 280717304, 887159503, 881336902, 418182570, 99300242, 756224162, 934455412, 756970927, 71195333, 685566686, 790386270, 176014917, 488483676, 665968161, 844199411, 187275491, 866637516, 331547495, 325724894, 717527049, 254643697 };
  v[20] = { 822267902, 587042882, 664609427, 286890002, 66978449, 389677139, 806679883, 487390415, 12943553, 710631961, 363721256, 755159678, 396931710, 620674503, 369402729, 660584488, 418917755, 617072931, 807339247, 950769871, 684124278, 436508253 };
  v[21] = { 834441851, 44220602, 69747793, 72160770, 773061441, 510997066, 479444195, 341030351, 741234160, 91136676, 404419983, 88210520, 773171566, 123074082, 721114626, 582700782, 614253653, 352189278, 649532960, 651945937, 626418746, 834441851, 663930408 };
  v[22] = { 214634481, 616015650, 979862096, 147503020, 875414633, 326183690, 612083935, 889618971, 956589074, 929471759, 925093864, 499122176, 73150488, 68772593, 41655278, 108625381, 386160417, 672060662, 122829719, 850741332, 18382256, 382228702, 783609872, 0 };
  v[23] = { 500903340, 766195471, 613801090, 16754603, 427813517, 287207496, 797848437, 44033021, 140983453, 614903781, 426141857, 597620077, 237314138, 65835918, 875318347, 401398019, 498348451, 253919514, 764560455, 905166476, 317981037, 915027524, 762633143, 497341013, 995188491 };
  v[24] = { 367473831, 833878383, 433546867, 671934583, 642263366, 927088691, 891859934, 959344066, 160063515, 557388310, 204106840, 694377429, 120612065, 927322276, 295264618, 791411997, 658565628, 492521740, 217852736, 283727154, 569409840, 534539992, 776195879, 776109367, 687684011, 397124940 };
  v[25] = { 311375277, 54800761, 695841113, 678247809, 658942988, 760566189, 800984802, 423739726, 992470546, 693435405, 613593644, 197947275, 3912127, 536365830, 730400978, 314754609, 394596370, 95561229, 525074762, 147829686, 107411073, 209034274, 228339095, 210745791, 567949792, 311375277, 946179874 };
  v[26] = { 507880616, 167731124, 778110613, 149132085, 558757184, 903831902, 949632081, 319166777, 861120429, 805531417, 117747679, 985013482, 877541450, 499122176, 120702902, 13230870, 880496673, 192712935, 137123923, 679077575, 48612271, 94412450, 439487168, 849112267, 220133739, 830513228, 490363737, 0 };
  v[27] = { 859535363, 633483420, 873520333, 350240287, 971891067, 892356234, 613063723, 17905137, 157500298, 303650755, 541954269, 442586701, 449733162, 166686064, 505712113, 788759211, 795905672, 895273240, 135332401, 987426297, 128777105, 723935691, 444643180, 524178013, 147584440, 670864486, 910901399, 138708990, 420432633 };
  v[28] = { 605913569, 85972564, 166549372, 259238713, 391430484, 424667956, 791190125, 246348503, 38708174, 523857063, 324959442, 917192228, 239645326, 695958999, 627277359, 634913504, 927201983, 211078647, 170691545, 872721317, 172171080, 681558076, 821531134, 251781882, 429703141, 246478640, 936578919, 965117622, 814105751, 49171349 };
  v[29] = { 388034991, 926969788, 238439029, 488019268, 909999645, 200066840, 276972827, 257897727, 86935219, 475730311, 8112984, 52920174, 813168798, 329309701, 464133609, 445632976, 310809068, 825194324, 64945700, 109752890, 577370217, 966165309, 138883464, 119808364, 42902377, 331213925, 907477901, 158813787, 847344546, 388034991, 958595653 };
  v[30] = { 65436453, 61444846, 43718997, 131928086, 172801046, 710953567, 940988202, 963921136, 689377405, 584759048, 1158667, 94530694, 51361396, 740313962, 121731921, 499122176, 876512431, 257930390, 946882956, 903713658, 997085685, 413485304, 308866947, 34323216, 57256150, 287290785, 825443306, 866316266, 954525355, 936799506, 932807900, 0 };
  v[31] = { 841216632, 323854500, 749165094, 849174111, 511167673, 529366980, 399393215, 680007718, 353434972, 622278944, 255858982, 301593651, 603092076, 949161435, 185148980, 721386687, 437061763, 899068409, 135055954, 787230948, 90485020, 44750351, 676574742, 407730770, 81158024, 798787874, 668814109, 650614802, 312608364, 212599347, 637909941, 157027721, 117030354 };
  v[32] = { 643098974, 352815944, 558310024, 117131735, 161418035, 753935195, 445341307, 478267391, 284360376, 236185965, 615107469, 215510075, 305270355, 887339477, 788624973, 450561124, 948784036, 489086514, 841321656, 731905343, 179525952, 643905230, 736865983, 906994118, 588494072, 681376336, 962175960, 65204354, 37692148, 273230087, 16732012, 77209005, 997250599, 517278769 };
  v[33] = { 215866101, 126960939, 842517768, 729091730, 222985675, 439812211, 263753218, 946549306, 390954037, 361447545, 949179035, 445989290, 28187175, 399668414, 755501665, 908600290, 655985936, 275880186, 528494540, 681593165, 325759914, 697241153, 116798915, 611853523, 24122033, 992859894, 550210810, 234762545, 410821538, 627648074, 135509776, 22083738, 304771262, 215866101, 576469255 };
  v[34] = { 37975368, 368859897, 175409572, 134988702, 800485998, 581447091, 374304369, 768464514, 566143160, 432467855, 690455554, 201782921, 571802869, 844667703, 289168626, 431846989, 745294391, 499122176, 252949961, 566397363, 709075726, 153576649, 426441483, 796461431, 307788798, 565776497, 432101192, 229779838, 623939983, 416797261, 197758354, 863255650, 822834780, 629384455, 960268985, 0 };
  v[35] = { 776287813, 300137439, 105677493, 856926046, 843693483, 106174619, 476887660, 357330389, 692807245, 935078984, 322021082, 443432099, 747630577, 315420278, 943933024, 159792845, 913994299, 105056202, 398998012, 209691756, 963893210, 749789036, 380057429, 812267728, 118221853, 995055189, 381997287, 139725548, 475202404, 594759675, 965472716, 704747227, 691514664, 938510464, 744050518, 221956540, 823091621 };
  v[36] = { 377031717, 839374960, 529338255, 795390256, 202465601, 480385901, 295495381, 209781738, 65733513, 54542225, 973071467, 812321929, 740964423, 335592568, 812543875, 602662785, 782612715, 925567085, 968571300, 218383994, 18229812, 430268184, 569131442, 154566689, 565807872, 358766233, 129676820, 27737525, 62108878, 276184298, 614443203, 879378396, 168861965, 79218614, 63604607, 379085014, 672130584, 187125926 };
  v[37] = { 887013681, 824859399, 294590661, 788549166, 157152088, 559572865, 552378144, 620640378, 903763689, 544845503, 495064937, 939632178, 832756475, 613313970, 476606994, 237645922, 379290330, 42952501, 717451703, 330661936, 654407087, 318069258, 176424850, 935708131, 74170754, 852972602, 959848305, 406171193, 455951759, 97033573, 812154615, 880416849, 887611570, 291787994, 923185072, 418899224, 949167962, 887013681, 345859510 };
  v[38] = { 278524766, 706089405, 812451860, 430349022, 653368794, 363244863, 251135377, 448631882, 592986761, 320173088, 935327599, 793665526, 780172427, 835648559, 502701339, 573555835, 695084130, 982142587, 248925118, 499122176, 749319234, 16101765, 303160222, 424688517, 495543013, 162595793, 218071925, 204578826, 62916753, 678071264, 405257591, 549612470, 747108975, 634999489, 344875558, 567895330, 185792492, 292154947, 719719587, 0 };
  v[39] = { 881874775, 352500334, 8615784, 7530922, 343471509, 439214614, 805192092, 889166970, 59712972, 376899812, 373681942, 128106934, 628012743, 790880653, 609373358, 408851468, 216066438, 113415227, 691404355, 483740592, 258551229, 466214992, 45959767, 148610978, 954070301, 156347838, 973084896, 810216986, 311878442, 557453450, 554235580, 237048740, 405839095, 321864217, 687841695, 592098590, 928039177, 929124039, 585239489, 116369578, 928163190 };
  v[40] = { 331518498, 360108979, 664478089, 693604544, 590600164, 993964605, 300706931, 524318631, 961635422, 833212907, 827132320, 706956938, 224682323, 986236575, 693187547, 19257893, 222169908, 505424452, 179961973, 459581527, 807027891, 983335406, 592867558, 478067234, 696419283, 303229820, 209372894, 517896643, 51009536, 315242012, 939946294, 419963486, 528726793, 779691935, 551867183, 705123269, 30543400, 122007997, 974005248, 729200069, 646213765, 657579328 };
  v[41] = { 482449624, 590727301, 325341513, 392645442, 979361652, 659977801, 741330019, 16432011, 581014962, 508710940, 193569600, 738061322, 291177037, 824758282, 977055035, 264032147, 380502743, 18846184, 130876866, 71957611, 941615309, 938186622, 68528924, 9609669, 895823340, 534166781, 417696185, 702917650, 550620897, 85957789, 532842074, 79089443, 394230783, 321926761, 755588163, 30690155, 947582290, 628198439, 41482229, 108786158, 374171946, 482449624, 627128207 };
  v[42] = { 764050054, 693252689, 468310354, 643259163, 504982202, 842082866, 586564159, 850408335, 687866573, 401763286, 196786766, 952097563, 847792622, 956933531, 539397108, 666966237, 375863836, 939876206, 897214855, 300869978, 732785801, 499122176, 265458551, 697374374, 101029497, 58368146, 622380516, 331278115, 458847244, 41310821, 150451730, 46146789, 801457586, 596481066, 310377779, 147836017, 411680193, 156161486, 493262150, 354985189, 529933998, 304991663, 234194299, 0 };
  v[43] = { 324203723, 656980838, 614027579, 264371263, 577174528, 435728216, 815861980, 326024527, 879005957, 177946285, 707061435, 282368466, 572960944, 112442096, 110765248, 401497214, 196936944, 896921860, 882800036, 700223642, 282350330, 116921094, 692609911, 858039147, 440165835, 622742229, 608620405, 906879842, 702319572, 411587606, 409910758, 870429606, 162777731, 587470700, 118341497, 819401169, 374138246, 863975699, 245865110, 387311422, 700114687, 51526650, 8573391, 674040630, 322239857 };
  v[44] = { 597888239, 914340282, 223979096, 174588257, 503843548, 459031360, 396613895, 819539923, 458950036, 42779668, 902046879, 852152230, 103140883, 520299950, 216612860, 28225139, 124932700, 189460452, 68254969, 370146922, 111420408, 549550510, 603493626, 565565505, 629892340, 795675430, 801825442, 528699830, 898070264, 177904572, 324727660, 681971080, 460445027, 521600745, 203484421, 470297329, 982536799, 261064811, 155773850, 584250468, 555238647, 470617738, 719851597, 10949716, 432274133, 772961355 };
  v[45] = { 953613660, 388420203, 848790570, 859154997, 294855455, 879274579, 199166916, 417887076, 135404685, 132299803, 566284202, 357311879, 127591815, 845761947, 431209500, 284753547, 549862218, 787414299, 554854794, 620741517, 109607759, 637200452, 684728920, 801504528, 753976060, 283324400, 794458158, 860344881, 94660033, 332212114, 67103443, 918891843, 335199937, 55125716, 284845780, 75873457, 640133411, 637028529, 919510920, 139986727, 820094390, 406269161, 970568703, 980933130, 520562763, 953613660, 958322047 };
  v[46] = { 386170371, 504428711, 295421312, 849717423, 220955134, 804938530, 262492030, 695340981, 134656815, 177092983, 275309583, 818212623, 633287626, 457729040, 675894900, 962347603, 276543322, 250817101, 262062390, 303886973, 764966699, 300076634, 815817271, 499122176, 182427081, 698167718, 233277653, 694357379, 736181962, 747427251, 721701030, 35896749, 322349452, 540515312, 364956726, 180031729, 722934769, 821151369, 863587537, 302903371, 735752322, 193305822, 777289218, 148526929, 702823040, 493815641, 612073982, 0 };
  v[47] = { 690775981, 42410336, 836977243, 930728844, 852071467, 900987594, 860216339, 944305727, 969120615, 7738653, 490093615, 791678556, 419498132, 786441036, 97457564, 731256225, 200888765, 492226755, 151925165, 152763458, 33657740, 347711735, 739172018, 595302697, 168091246, 311960567, 703420850, 389366855, 270261137, 269422844, 927365607, 636027617, 105660157, 470105849, 779366730, 412423826, 40243402, 736902814, 221013423, 184151032, 208965920, 124876532, 84105277, 35189150, 954776126, 861024525, 657347079, 307468372, 466468801 };
  v[48] = { 187630428, 694034092, 555422495, 967414131, 188614383, 728495459, 332648842, 676034982, 499328782, 954152423, 131591578, 524811742, 372154411, 773755334, 977852482, 690429444, 836049708, 119861619, 133749705, 581047731, 18746977, 231751225, 83932419, 979030440, 428381217, 834183616, 494715591, 441706983, 39195017, 362710047, 467745596, 981073228, 940281207, 980139899, 292195967, 191413880, 742836439, 374287980, 256890408, 242065578, 838894560, 526350842, 380043181, 155258419, 492792603, 933345754, 627916210, 264250530, 928015417, 625765667 };
  v[49] = { 160673311, 99390487, 560035386, 190087133, 388689330, 570791681, 139371147, 754822902, 113502666, 681088442, 288124860, 772187344, 195185058, 894838950, 185251737, 983161175, 900647457, 76805947, 659183988, 344153782, 24935914, 637339437, 657376712, 162825965, 797159147, 2860847, 366772018, 870465624, 850428349, 464587519, 783805387, 468775181, 884641493, 60799983, 143313701, 941223139, 652565999, 353975538, 930977824, 416795955, 809759537, 379100960, 22176843, 637628598, 70804779, 252907130, 54304933, 682601033, 221956134, 160673311, 746515328 };
  v[50] = { 688852690, 411336751, 56110178, 563947227, 4125675, 662043821, 612273891, 365763096, 788390072, 478525802, 156332611, 979280171, 564296704, 617264892, 889519176, 594153030, 194239353, 383963194, 64683781, 91984105, 67065751, 610765790, 120227533, 472946219, 443603173, 499122176, 554641179, 525298133, 878016819, 387478562, 931178601, 906260247, 933560571, 614281158, 804004999, 404091322, 108725176, 380979460, 433947648, 18964181, 841911741, 519718550, 209854280, 632481256, 385970461, 336200531, 994118677, 434297125, 942134174, 586907601, 309391663, 0 };
  v[51] = { 680068751, 608038380, 797223996, 755782527, 556626797, 332540229, 9968034, 220183706, 394812272, 230207477, 358813743, 378718208, 930048456, 562804313, 963791530, 519884013, 23346680, 849384502, 581504494, 734838168, 821600353, 806439711, 810993914, 582622714, 647173804, 241075268, 248506221, 654604757, 719155847, 947527047, 952081250, 967241892, 55759724, 900670403, 632790395, 804996926, 308459593, 752367110, 155109974, 522354117, 75440012, 55535547, 184141813, 348746608, 523375174, 313159502, 988831660, 214673875, 15518145, 56959614, 246145230, 318175602, 118437709 };
  v[52] = { 789003110, 51611260, 107474090, 980152152, 394701827, 299916811, 882156719, 237371403, 911387756, 200316087, 399555966, 309946123, 535359156, 422141206, 500448156, 873005840, 953648318, 337501169, 571633484, 89787161, 447832222, 540422284, 170248115, 819555564, 43625570, 127361449, 42571647, 805767060, 630001410, 252974586, 291713241, 22478665, 146326063, 268357127, 697689223, 442534625, 984356083, 674288533, 412250093, 85914310, 213915432, 65825902, 176332313, 490804213, 872860100, 507626793, 334547466, 471216516, 649484462, 407664140, 434735257, 829562063, 250781974, 698596263 };
  v[53] = { 371142811, 174866004, 74065635, 804452229, 994120154, 742961529, 614078967, 677537395, 811476053, 215335383, 594405913, 745865427, 23130416, 105825960, 690295423, 59219550, 961143632, 290836826, 649877659, 784798710, 274073015, 883857184, 678909942, 201388068, 714083279, 611588837, 636782313, 944833200, 919639724, 817145282, 304450071, 825172550, 31875439, 641659608, 154140950, 289062001, 928265521, 257958715, 354278986, 721447466, 136978003, 219673547, 942408558, 95623719, 714797542, 118656872, 982962567, 48176642, 177059204, 924144932, 734477007, 466619248, 567419617, 371142811, 92233061 };
  v[54] = { 750144212, 637708351, 160353019, 838104028, 555250683, 169196220, 567232479, 417331787, 534499029, 646554337, 557114526, 313935120, 361094178, 84996455, 710901513, 494014701, 490345161, 911551199, 112225366, 146202129, 751967673, 567464797, 537389973, 991366674, 33074249, 852870199, 238640362, 499122176, 759603990, 145374153, 965170103, 6877678, 460854379, 430779555, 246276679, 852042223, 886018986, 86693153, 507899191, 504229651, 287342839, 913247897, 637150174, 684309232, 441129826, 351690015, 463745323, 580912565, 431011873, 829048132, 442993669, 160140324, 837891333, 360536001, 248100141, 0 };
  v[55] = { 376775599, 32178310, 478415300, 408810519, 304142904, 389603238, 806365772, 675940450, 585724282, 406073064, 488568777, 817355358, 671388043, 716671135, 945391453, 114485222, 388196398, 74988445, 319588064, 535562756, 799731421, 742656922, 629582416, 144071795, 429378426, 717628138, 498002942, 981275294, 85555462, 600527463, 380902267, 92652555, 377959186, 863469807, 750395301, 807469800, 73394112, 855663773, 102019039, 415226992, 688938168, 521600046, 750320364, 705037272, 559069957, 230283376, 312779089, 492430307, 402214139, 532639461, 949401995, 863941661, 759274046, 828878827, 276871464, 621468754, 127576019 };
  v[56] = { 479500649, 746952213, 807385555, 248742802, 755763264, 663676662, 359322490, 228698684, 411224834, 158142363, 395338228, 377983348, 252057688, 383938637, 280522821, 952024380, 720140544, 193756017, 514615066, 806202864, 270997281, 235534987, 891745094, 412066116, 763429300, 939426362, 73949928, 560097259, 153161477, 497860783, 589866947, 945985282, 834876971, 383720710, 635520140, 165434069, 348375208, 242649522, 486171647, 49838469, 929371603, 838742477, 144690259, 283332898, 277182379, 506333112, 200501586, 404011556, 609299170, 577799344, 765095479, 164449126, 930919455, 235803005, 284614298, 604117085, 478760214, 221829883 };
  v[57] = { 913861359, 331792741, 832054830, 969667027, 827473101, 59370057, 288790392, 765844688, 558669203, 679984552, 655514887, 954162636, 65324596, 648561321, 399229900, 200103895, 952137427, 90718994, 194411730, 237628026, 631219057, 558130410, 626752856, 379109450, 267724456, 481373506, 833855563, 619505691, 91974393, 237618412, 765149710, 550799838, 198317781, 411966831, 523351825, 275708419, 207085973, 133997326, 738650648, 781866944, 678174208, 815000128, 62966596, 862084944, 113172012, 696408737, 587002424, 885650173, 910119838, 33190834, 240366319, 717420615, 488000280, 718141589, 860335515, 997947712, 497685623, 913861359, 664558374 };
  v[58] = { 926045040, 569648459, 991761325, 417298406, 249565488, 817348208, 982850414, 264274355, 838164145, 618043849, 781302910, 130189699, 271033022, 630254175, 652731208, 652701683, 530814083, 85044970, 591849572, 20310273, 139675633, 294232609, 939550638, 66584017, 364245581, 93181985, 12028516, 972952855, 386919215, 499122176, 611325137, 25291497, 986215836, 905062367, 633998771, 931660335, 58693714, 704011743, 858568719, 977934079, 406394780, 913199382, 467430269, 345542669, 345513144, 367990177, 727211330, 868054653, 216941442, 380200503, 160080207, 733969997, 15393938, 180896144, 748678864, 580945946, 6483027, 428595893, 72199313, 0 };
  v[59] = { 943458805, 168147455, 197401173, 671950779, 290170432, 547886877, 497020484, 19979527, 893478420, 139810609, 15692487, 809086170, 975407498, 653019952, 489790702, 289341647, 957897253, 918318817, 515583357, 987661842, 736339351, 223302937, 993255256, 676845779, 674249576, 569181409, 742922540, 502310586, 11532148, 895540641, 375563507, 489799367, 997265282, 239632883, 413374014, 518442181, 515845978, 832255455, 603963421, 118755482, 865677344, 393598859, 989107752, 30441835, 698997441, 899446496, 736217246, 60360439, 226681767, 431532437, 307414315, 62837773, 936336666, 415133270, 364266877, 106550432, 723014438, 248464832, 277718550, 54785548, 626098158 };
  v[60] = { 283257986, 479591426, 901288690, 707270954, 572227541, 888929845, 849790535, 335895098, 570913716, 642795450, 788477683, 306191385, 871768410, 83726727, 729329367, 803309550, 259300539, 842183424, 131560023, 546951517, 343553537, 724799874, 159068168, 297635464, 740933550, 80954450, 48180803, 932088961, 770011420, 638051533, 413358662, 94828635, 282068889, 470666120, 719688846, 657644459, 356566761, 195641453, 772584122, 238554508, 6769653, 174478028, 814634299, 318575472, 409798798, 557378180, 710491125, 393273158, 952318722, 834742816, 923616774, 589480655, 529021706, 924540311, 346205795, 817219183, 182706657, 50709796, 652360688, 361486124, 363249098, 58164543 };
  v[61] = { 20308804, 299415649, 295353659, 35397853, 484370471, 120845487, 874279760, 129329687, 646619510, 740167853, 478326113, 608136845, 306703529, 450288554, 854088238, 545577073, 839757554, 428517693, 216810965, 192113126, 204731398, 815655356, 918529820, 107535105, 630862163, 570801440, 192904146, 464563577, 162658700, 406955547, 15470179, 440989442, 832474810, 78527304, 380432181, 652091612, 31744553, 969928183, 446601125, 633850763, 530976299, 143655904, 131037632, 106339793, 318046521, 905051013, 610870532, 302359367, 896804036, 42144708, 343578024, 473388756, 735230496, 828778839, 311489016, 564783296, 809593376, 446068392, 995340127, 735384321, 739446311, 20308804, 475151091 };
  v[62] = { 44773661, 851176750, 267375365, 392176819, 887354593, 949327709, 190701565, 315861932, 268030780, 854217669, 461803174, 989091710, 458086161, 988039160, 381695931, 841310783, 229201123, 688361054, 939440100, 365372869, 98608796, 458475066, 582294985, 62030656, 683867767, 325777542, 865564467, 863822357, 300389585, 663703140, 430296919, 499122176, 567947433, 334541212, 697854767, 134421995, 132679885, 672466810, 314376585, 936213696, 415949367, 539769286, 899635556, 632871483, 58804252, 309883298, 769043229, 156933569, 616548421, 10205192, 540158191, 9152642, 536441178, 144026683, 730213572, 682382420, 807542787, 48916643, 110889759, 606067533, 730868987, 147067602, 953470692, 0 };
  v[63] = { 678491707, 762929172, 84373155, 468472078, 898274671, 445141037, 106327429, 192276380, 665373464, 724006208, 58604952, 535214156, 603307827, 386246712, 544781379, 949804744, 340948042, 490350222, 965545668, 782404193, 538966991, 203870054, 873206951, 170791711, 907291752, 309494436, 641570322, 553560334, 727193302, 191703502, 457828806, 318506086, 459840539, 599163259, 865288563, 402534010, 576166978, 664176966, 996252852, 595805815, 334061503, 38232390, 707569287, 44421871, 799229022, 982370497, 459321590, 309919410, 699307061, 294283696, 452818363, 669879478, 737973149, 261363945, 594207042, 535574298, 10427029, 922722431, 583908823, 38798104, 468600697, 84501774, 404190110, 319752646, 833315517 };
  v[64] = { 446249130, 256475316, 597559524, 362150016, 856801005, 707765608, 773626899, 607921744, 975877042, 232524408, 270311837, 617164751, 349049868, 884925891, 681612764, 523405166, 535522917, 654916373, 109177306, 554298470, 517264000, 880444218, 813578730, 1000639, 76515053, 593408016, 50068686, 460499770, 909567108, 41884043, 977689774, 317620354, 58127353, 638439973, 534172006, 118813829, 193282754, 404801799, 423594539, 364222729, 372073138, 284715112, 381085348, 534663466, 233159616, 673014425, 979474052, 934592661, 831909463, 269721100, 366037326, 117663475, 311693133, 787997691, 645224876, 912320508, 439034525, 243829450, 741672818, 503036421, 957495642, 626938070, 15372067, 790663324, 117222357, 368854422 };
  v[65] = { 248585328, 849983109, 769137636, 349210122, 763683445, 407305455, 418440028, 224410707, 198644539, 124394969, 226866272, 560864185, 399432760, 556574693, 168902257, 17558495, 424172713, 757225368, 654075059, 484543295, 569362032, 210344873, 664360492, 664706381, 355202056, 796195715, 802755241, 658113920, 579711927, 576654765, 449185269, 562008539, 380877520, 165722445, 346853464, 459676734, 587146230, 584089068, 662491061, 517849740, 511290214, 952283873, 263543845, 263889734, 808118468, 449101309, 364282572, 194750808, 297901117, 630953772, 224339554, 72995792, 460668228, 617810161, 779241586, 114995146, 12523843, 936518626, 962284794, 768255473, 757120900, 400742910, 984513940, 564586426, 645431899, 248585328, 77661467 };
  v[66] = { 987293174, 40774498, 718750309, 689073876, 248820177, 641743423, 378037411, 839445936, 668773890, 992660572, 898204111, 201881858, 851569694, 731070805, 325850284, 39414291, 688797093, 917058322, 568137844, 339553147, 191348785, 257728986, 735109387, 455055508, 332048179, 252652067, 898348488, 967356818, 31980093, 149782455, 785977919, 234054827, 729010805, 499122176, 269233547, 764189525, 212266433, 848461897, 966264259, 30887534, 99895864, 745592285, 666196173, 543188844, 263134965, 740515366, 806895567, 658691205, 430106508, 81186030, 309447259, 958830061, 672394068, 267173547, 146674658, 796362494, 100040241, 5583780, 329470462, 158798416, 620206941, 356500929, 749424175, 309170476, 279494043, 957469854, 10951179, 0 };
  v[67] = { 56525699, 216606914, 590399431, 484693903, 323769943, 732616495, 357670208, 423082684, 41099065, 906934814, 390567133, 357977048, 111805394, 801037003, 483009638, 928339992, 33804281, 507262717, 193671388, 890509080, 762567411, 57334332, 400328728, 8347445, 400626994, 125199155, 295266888, 738503666, 223102828, 335167744, 542688707, 250120188, 809768884, 934258889, 435402596, 310912591, 870561287, 164885453, 372406416, 260341500, 743185015, 299948237, 470015970, 745443809, 139479005, 531460288, 874454684, 581443410, 453501741, 754908402, 441317073, 966102990, 71567279, 624481278, 306453913, 615466657, 369295003, 401885088, 883761760, 17926011, 634186745, 568774269, 193827982, 783225783, 622301823, 728007351, 103555515, 941718654, 797726566 };
  v[68] = { 897424353, 429361014, 736037577, 911925702, 986319355, 613135305, 556769285, 583919207, 123458319, 477547787, 771232997, 451116777, 233434670, 204313626, 786351739, 730798844, 61978978, 277970213, 54065557, 315634049, 138450801, 850791388, 391615963, 330586029, 512638802, 970886927, 335144399, 95329816, 444590180, 916010298, 817651825, 18818011, 436392484, 612660438, 442442061, 149088927, 789697405, 899257413, 916780902, 930630851, 820436934, 607731113, 476719261, 771266275, 498180167, 872455713, 925550503, 303658105, 203885354, 961527338, 997424368, 453198241, 370820276, 902461803, 460627270, 856984528, 615169034, 309349122, 686604176, 387966500, 435787364, 538027522, 269608726, 835994278, 752503331, 121853468, 650415958, 326406416, 817534172, 425517036 };
  v[69] = { 96319107, 99622565, 789674519, 412926295, 179748199, 781839447, 128615408, 371432115, 506565630, 350525890, 121790657, 148492432, 488201432, 682393592, 793326920, 700204218, 315570018, 756726507, 636137672, 279345372, 24617996, 406935180, 167879696, 743116596, 163600719, 32168873, 232176371, 206564957, 588247723, 82445302, 736798182, 31844386, 176830049, 852285875, 799394760, 212100504, 264991619, 940447445, 795461782, 90507986, 434399459, 926841391, 545158625, 519547211, 319539713, 188107867, 767623744, 344616291, 583671775, 965988959, 222471982, 863924035, 984512870, 427425006, 812059206, 718936504, 608003176, 802195336, 462486336, 489188111, 717923344, 561883604, 426750089, 669566796, 324546482, 926637730, 161571473, 783067602, 93015648, 96319107, 789057334 };
  v[70] = { 800753358, 925035922, 647658313, 790707722, 432986913, 568648528, 320297559, 922944870, 18324292, 370998234, 340424053, 933799376, 971122423, 781584478, 865344058, 686602615, 466485472, 663082897, 719826760, 465472773, 196367171, 534024927, 174007435, 549709554, 605668946, 935482551, 543627404, 820614211, 495690432, 13405821, 20798956, 404489157, 190285922, 764247225, 989500248, 499122176, 8744104, 233997127, 807958430, 593755195, 977445396, 984838531, 502553920, 177630141, 454616948, 62761801, 392575406, 448534798, 824236917, 464219425, 801877181, 532771579, 278417592, 335161455, 531758880, 311641737, 132900294, 216659874, 27121929, 64444976, 657820299, 627246118, 979920060, 75299482, 677946793, 429595824, 565257439, 207536630, 350586039, 73208430, 197490995, 0 };
  v[71] = { 712823935, 135465335, 621622740, 358170902, 561038775, 318619853, 344699687, 956094476, 921989213, 614066701, 175892473, 968939268, 778231724, 308975267, 419883067, 663318121, 907988898, 58450582, 554415385, 911297334, 438737206, 572127324, 862265126, 834917737, 943328598, 272619856, 790105289, 379242922, 192339603, 496929820, 435612415, 212956127, 25947672, 506746330, 956309642, 835917155, 680307580, 800700067, 252019026, 769464721, 582456266, 805112554, 743795149, 439204932, 252301613, 663163980, 182405060, 853113802, 961524663, 988872052, 280765501, 147375383, 673059608, 316177659, 812142462, 663436425, 908107202, 664672148, 775579948, 246592052, 55884508, 261082066, 821152191, 130830350, 96725087, 483574651, 509654485, 752073407, 954941280, 220148765, 706306170, 285420418, 853097203 };
  v[72] = { 524656547, 654995046, 984496637, 685991339, 736804481, 259638104, 485105911, 707825243, 67361831, 652941313, 41890523, 529061000, 697586182, 651076328, 624255117, 403702197, 188439745, 381299010, 691408425, 694484962, 490705275, 929181498, 748159739, 106557155, 729920854, 740382090, 404589710, 187820001, 582610277, 609175873, 560401451, 807159271, 721493880, 211263270, 114724999, 38093267, 311443267, 154785184, 772156485, 953471028, 783829445, 951216269, 1068026, 327907851, 275693857, 739553189, 685077267, 362085559, 503640714, 144283935, 226475635, 149987198, 494870738, 18397585, 937331747, 871273396, 522025040, 430015076, 438093109, 462353050, 897981948, 211225866, 968245736, 282308899, 361748959, 536230352, 3545392, 79979117, 323240811, 440835509, 502353691, 69951829, 597733221, 256726167 };
  v[73] = { 684487287, 907250353, 732136821, 768716541, 162067475, 612452809, 627678823, 797340447, 594590314, 221197837, 552115685, 484827368, 761662835, 419768356, 49839603, 561146573, 96815587, 928234556, 784529681, 919314908, 835693617, 818520709, 809825542, 176626939, 817103696, 825052127, 146419729, 722943470, 343295869, 377638522, 191584644, 954473100, 463394264, 904280856, 85093079, 641786153, 457537520, 838773844, 24778124, 581471198, 402414622, 843301214, 336135697, 100779800, 286833678, 321176331, 700823932, 279103320, 957735718, 965684149, 325207392, 690253142, 698948309, 681775401, 765396692, 900181919, 45642441, 877061410, 343148043, 854455013, 226139413, 882489287, 605653820, 538365503, 207447655, 832299531, 36805311, 206466935, 191240921, 641626255, 250030968, 286610688, 461724220, 684487287, 4787490 };
  v[74] = { 827981986, 453018358, 656983065, 593706969, 90145855, 447459404, 213341577, 262776533, 29946158, 935075082, 682272059, 398758908, 277901844, 927102212, 408453162, 252299672, 945764525, 856891159, 287779892, 625468910, 542065227, 139024671, 234175897, 132550744, 936597022, 881349899, 362601439, 552003393, 232051264, 869193967, 522084692, 608844473, 310144687, 907875134, 73721497, 569887117, 700935570, 499122176, 297308782, 428357235, 924522855, 90369218, 688099665, 389399879, 476159660, 129050385, 766193088, 446240959, 635642913, 116894453, 61647330, 865693608, 764068455, 859219681, 456179125, 372775442, 710464460, 141353193, 52479827, 745944680, 589791190, 71142140, 720342508, 599485444, 315972293, 63169270, 968298194, 735467819, 784902775, 550784948, 908098497, 404537383, 341261287, 545225994, 170262367, 0 };
  v[75] = { 956762264, 557861456, 392637192, 693634807, 447576066, 127419661, 895432529, 265638232, 542469002, 117107061, 138502009, 928147087, 749148733, 366083552, 271199935, 427659074, 770784153, 236757065, 513283860, 514427528, 314777853, 779957462, 84676724, 415026074, 216224138, 211840530, 265894991, 463311033, 283518073, 864325626, 776814035, 773060147, 904017310, 941546595, 446911647, 472683271, 176725182, 83589662, 101850791, 194986311, 897272575, 871500951, 376866003, 339336718, 470293881, 474047769, 386536178, 803972978, 624180018, 426763976, 480818437, 485202045, 286400109, 954295112, 259014374, 792079118, 592429443, 591285775, 867812570, 403595305, 746720384, 590261245, 495377628, 878442809, 699444455, 908043730, 929438678, 356556266, 633387036, 264936980, 34705495, 354861900, 108803159, 806049897, 640825633, 41482089, 468077458 };
  v[76] = { 772391010, 576801700, 527320829, 664126933, 962113401, 343140562, 191420268, 215600393, 344676857, 431216163, 653445038, 147707306, 694851288, 642891464, 989118172, 76371974, 39092702, 725469133, 415487175, 15628813, 976860086, 768999360, 135766740, 977841129, 870076393, 346533625, 195390617, 33399118, 796497306, 587114996, 913970211, 633552233, 203260019, 406546393, 351795616, 337526579, 44480539, 86435591, 641493530, 373152416, 373300184, 993448886, 665716468, 132856731, 40396566, 452716812, 909648598, 276681193, 124697292, 342317628, 10812951, 59257244, 451538384, 201748140, 402157406, 45844600, 164481, 103306030, 875317723, 982892935, 162784156, 246925630, 487834274, 457512922, 465433109, 487575403, 337319462, 214385626, 525545653, 350085445, 657523210, 542980492, 70333442, 205298804, 794311960, 128423640, 752528667, 269290009 };
  v[77] = { 740030515, 43614742, 534009521, 356056318, 790142232, 103926416, 981322096, 549956410, 839590059, 187496987, 981206046, 749355154, 80562041, 365287510, 119997050, 423897736, 310354811, 16733594, 102337662, 158506308, 816598992, 784670811, 543828373, 132091452, 494083518, 519730309, 24033104, 102113689, 520583874, 313288069, 824586906, 653679133, 647826476, 257605369, 779494082, 19061522, 434427318, 144861119, 68736529, 450701407, 526825997, 237259798, 820138355, 59705795, 536061435, 145840328, 151692985, 979029565, 467730728, 260434923, 840209091, 918289676, 415742528, 441389319, 79397253, 665904685, 906747123, 874818942, 216726258, 272894904, 187290836, 891913972, 7212544, 311113230, 556403690, 841129159, 511677919, 279827027, 484362321, 830513602, 540879953, 109514267, 230362940, 542391477, 108305563, 928596713, 438201934, 740030515, 325816364 };
  v[78] = { 323576188, 12734765, 530353881, 583774084, 375020292, 619571213, 688043873, 517202524, 559693089, 161131131, 970855391, 256255599, 539518263, 618005405, 578419301, 329876363, 339408438, 210684647, 571477159, 141147354, 255722425, 130453212, 275486747, 133542510, 161290967, 116438344, 571439894, 721239575, 91193974, 67243909, 55423082, 529320707, 968040240, 241211545, 580325620, 517571676, 808308062, 621777147, 951566120, 499122176, 46678232, 376467205, 189936290, 480672676, 417918732, 757032807, 30204112, 468923645, 942821270, 931000443, 907050378, 277004777, 426804458, 881806008, 836953385, 864701842, 722757605, 867791140, 742521927, 857096998, 426767193, 787559705, 658835914, 668367989, 419825051, 380238947, 458726089, 741988753, 27388961, 837113221, 438551263, 481041828, 310200479, 378673139, 623224060, 414470268, 467890471, 985509587, 674668165, 0 };
  v[79] = { 883288314, 773431487, 449715963, 447803428, 436469652, 922994825, 477822608, 664656257, 129649520, 354230156, 246606414, 117479807, 195520037, 325489582, 11823923, 808804948, 67732434, 944945864, 819872256, 791461363, 869252817, 719191644, 454405117, 949475458, 308332931, 462050588, 455151805, 756629182, 247932821, 530613357, 1795352, 568128035, 97223002, 420238279, 777139974, 396744929, 669796199, 698363395, 159439710, 963550845, 765119490, 959252708, 420329023, 391761827, 664813097, 46963789, 403865484, 80850207, 608189527, 41856844, 511283192, 228602656, 718150648, 416673271, 409774488, 256056831, 613158657, 118088316, 851546142, 3362962, 81154416, 109565309, 982736054, 105522624, 362694463, 563957791, 250292132, 120322587, 198362817, 327489424, 219865682, 993529399, 458522662, 271689013, 824761149, 338235976, 326902200, 328814735, 5099211, 114956039, 821616432 };
  v[80] = { 522408605, 979618406, 915110540, 687637977, 491492016, 12944300, 735062081, 717496402, 252461326, 577493764, 900403146, 712132446, 523349570, 128797316, 959763381, 424979988, 81649096, 322532220, 986028442, 161014817, 195936873, 415498606, 856893972, 328346729, 280162522, 427258518, 979900656, 503724647, 814774680, 651740552, 24400370, 577830585, 982447940, 214580804, 221603029, 398306696, 967316052, 370862474, 207319674, 150909574, 618262071, 371520959, 906081040, 468675955, 409611086, 515128361, 471405320, 510196380, 911738936, 545226987, 268003929, 101263168, 392738518, 248533282, 137625501, 63486676, 817483022, 975654930, 813372302, 770490432, 96838033, 143840088, 497989290, 420248586, 583647339, 876171353, 214598979, 726991815, 369637602, 922750033, 382520715, 414387303, 552640791, 985520495, 327726898, 468868838, 708291545, 300477317, 636171553, 685045353, 134087076, 685151113 };
  v[81] = { 126238547, 363053877, 687200415, 645807338, 203566753, 117006530, 812971663, 103986380, 206292607, 264909353, 505887223, 346893212, 772713741, 197533878, 112355109, 18631803, 832310620, 137317132, 192845460, 558498032, 71588336, 493641215, 783573474, 102549891, 678647655, 722097957, 234249008, 472892045, 838847595, 200155280, 327357209, 24494279, 378869551, 666712237, 654137942, 910643646, 107543833, 685385843, 84492200, 925832, 832808785, 995182087, 163299134, 79732766, 680626409, 260224066, 65079526, 321585230, 334159525, 622002211, 267626939, 963008362, 835806433, 197114118, 829402921, 69801605, 557650554, 601100856, 25003092, 342223862, 52291603, 474344482, 961254178, 328662397, 273134069, 576384934, 760950470, 667227164, 752405933, 177226070, 749649894, 590655883, 349678013, 408294759, 305988532, 595247602, 897526822, 810966599, 254962831, 213569754, 887667569, 126238547, 701169185 };
  v[82] = { 801470164, 948730545, 929014241, 517751140, 335407474, 791739203, 993705942, 540040309, 105501410, 381908064, 37329311, 61344774, 437690834, 469546518, 551392911, 599407493, 713717477, 829609656, 552421504, 970946436, 212186790, 405746823, 606927978, 125312630, 123207397, 984906936, 56214556, 719298905, 372317764, 891417068, 710272756, 37918512, 423701879, 229484640, 3460637, 570672605, 245056840, 51418072, 490874822, 690226667, 881799118, 499122176, 116445234, 308017685, 507369530, 946826280, 753187512, 427571747, 994783715, 768759712, 574542473, 960325840, 287971596, 106827284, 625926588, 278945447, 942029796, 13337416, 875036955, 872931722, 391316374, 592497529, 786057562, 27297916, 445822848, 168634696, 284526875, 398836859, 446851441, 528697834, 560553518, 936899578, 960915041, 616336288, 892742942, 458204043, 4538410, 206505149, 662836878, 480493212, 69230111, 49513807, 196774189, 0 };
  v[83] = { 203617947, 323629132, 585137366, 931732426, 894080140, 785599949, 102795803, 421390081, 965554027, 29954659, 885690509, 367288406, 380554873, 601250629, 253526824, 855066174, 432953665, 277816145, 685957467, 31320319, 284682415, 734184393, 860500079, 322440048, 427568011, 640284356, 673928484, 617177207, 122934025, 810141890, 371115292, 345825995, 464751967, 3057254, 367297472, 119954081, 336075330, 279322391, 161717498, 430964779, 494196729, 970746196, 914763683, 438214216, 501446166, 232198885, 114593992, 171346931, 387468180, 634811571, 807436, 462502149, 581428121, 606717418, 167690820, 478727308, 982728479, 41235403, 74879531, 860407539, 965535502, 505351180, 631666866, 182164888, 435526984, 91919779, 500061101, 655198621, 233086112, 629791115, 282067310, 61371554, 74638021, 593040124, 450531621, 387886636, 932050582, 613456304, 928896511, 39132349, 1480063, 653129356, 914637590, 794626406, 711127804 };
  v[84] = { 320296811, 328203676, 737766300, 991554796, 343667812, 616411272, 207988944, 603151667, 475244882, 491874060, 386597725, 396610935, 30375009, 828499699, 114220436, 939462572, 873418146, 716069783, 236357488, 723227795, 660526345, 336988103, 704807749, 615743794, 590163978, 110726046, 162526794, 751405792, 100882627, 910424078, 73536580, 810488539, 806510759, 142181691, 263934706, 250500775, 545912829, 335114520, 818965993, 93956107, 447398206, 450595232, 149858176, 219639748, 525099609, 12416020, 7797221, 802576137, 740339928, 348889952, 82962135, 665379351, 344104996, 380396447, 366155807, 631065526, 224833184, 996157003, 788277287, 17245465, 758668954, 282075815, 10602312, 259813094, 681444886, 181109024, 441882828, 3691661, 657067585, 600452122, 166908334, 63417195, 598033936, 375031617, 899909751, 346243026, 442116403, 376457440, 857212661, 941477009, 96549386, 201054255, 562076718, 936873261, 44753274, 657971457 };
  v[85] = { 474990254, 909252681, 4193340, 792817566, 93172973, 770836866, 284501230, 808479605, 24535389, 405637256, 571698586, 723040126, 858313650, 344012444, 742185864, 626055906, 521986598, 285116305, 189469352, 798107123, 310934060, 144122573, 651465737, 198629174, 18076619, 325331543, 755918347, 289358015, 743558695, 116306908, 382912491, 339068751, 135888784, 398436380, 768227753, 483718892, 780294524, 757178302, 37891724, 941650579, 79044847, 762283191, 728055341, 138918367, 173146217, 856384561, 720745940, 626260442, 347302667, 324186445, 27610813, 741346305, 371554932, 634102528, 837282495, 793438755, 526833172, 897825738, 443625058, 975309079, 544722275, 851977199, 34285401, 579693191, 72350027, 903782893, 392711603, 3105021, 98751974, 860126034, 964195342, 848065384, 449891964, 933835111, 798561587, 949903127, 783841797, 166699311, 950643527, 476377549, 962713185, 642132725, 343532965, 133912838, 40727826, 474990254, 689202392 };
  v[86] = { 67244732, 728352389, 858544136, 680077821, 91519203, 63687480, 389236064, 214697952, 561787974, 47658510, 948896665, 786535401, 875251637, 466729584, 36042096, 942169716, 73571780, 382507220, 908968745, 239256353, 571474009, 234377309, 328580621, 179089916, 928607988, 408422566, 859852106, 347687266, 607095837, 627641890, 659904280, 824987777, 82971026, 622251067, 945829602, 248234683, 151494970, 832716497, 295563750, 386065511, 570617065, 563916024, 831890679, 499122176, 166353673, 434328328, 427627287, 612178841, 702680602, 165527855, 846749382, 750009669, 52414750, 375993285, 915273326, 173256575, 338340072, 370602462, 391148515, 650557086, 138392246, 589821786, 69636364, 819154436, 669663731, 763867043, 426770343, 758987999, 89275607, 615737132, 924672572, 56074636, 962202256, 531514768, 122992715, 211708951, 49347687, 950585842, 436456378, 783546400, 609008288, 934556872, 906725149, 318166531, 139700216, 269891963, 930999621, 0 };
  v[87] = { 950089017, 889684731, 257758857, 415340202, 917645720, 157953734, 354522291, 101516258, 203175816, 825322325, 646218561, 880738324, 222607792, 33547042, 291825369, 771731142, 404806894, 730789989, 648908763, 697980548, 793678946, 683447807, 671907502, 32451486, 968082112, 718232924, 982028983, 681109001, 421395973, 830842429, 514637962, 645252887, 427162235, 553521887, 66076282, 452378221, 162070865, 410685670, 965588708, 921249675, 711008203, 897828476, 788597108, 1978572, 923844522, 712218705, 602987337, 416167064, 205925592, 250264625, 805167663, 556552858, 266245502, 878187916, 390742311, 264382659, 46292007, 913921435, 597716968, 188270512, 926801837, 229477466, 493273525, 743122713, 680508986, 321720649, 310180344, 420411483, 516109881, 467038096, 385156870, 59173775, 690493880, 210588107, 468866434, 657927184, 998041005, 763521242, 584417478, 960515322, 63930527, 316936560, 513505117, 274952750, 777258268, 619676923, 985995402, 48155336, 452443513 };
  v[88] = { 749484235, 516178060, 552993927, 18331040, 465502595, 652262199, 125309137, 582833334, 984691507, 380934901, 138280831, 931323707, 701675199, 700308789, 663729924, 290769948, 411641788, 872667358, 793865256, 981551090, 43371612, 497751131, 632049375, 142912968, 719749103, 803812553, 606031237, 994980967, 898544060, 157504034, 742830664, 671297519, 249174848, 198896536, 475725225, 599796881, 845968705, 399657301, 498964102, 901410112, 170451993, 448355941, 793338582, 441977904, 490506601, 133689653, 429317118, 155950669, 616357958, 325654577, 535325832, 988228817, 543293357, 534747276, 846409288, 29217294, 761540168, 863872216, 106758624, 341490248, 973705227, 978988688, 392964696, 907456082, 671244886, 339596158, 278588527, 482139658, 451694195, 106251546, 47036321, 770192045, 224627516, 883618497, 268659184, 202644412, 481547764, 655768322, 613234335, 442915457, 474572080, 277887197, 442168135, 966910025, 632480665, 491621966, 244981875, 970905044, 590958390, 987207223 };
  v[89] = { 146699153, 464000065, 440783694, 903896100, 807728198, 708639238, 682108509, 979533528, 942383135, 590900595, 972583051, 4709211, 786911327, 221516658, 499355001, 42071560, 399850254, 750725224, 702799461, 928231049, 117609530, 41426998, 617729504, 191137976, 838457647, 480256618, 179332075, 598772803, 643580344, 169705477, 845727500, 696933085, 721364163, 782753159, 968906369, 391325094, 278782119, 727320598, 754394782, 464838753, 940438074, 731969085, 697065020, 562839642, 577338456, 688289478, 673790664, 539565286, 574469351, 366000362, 888645394, 599089365, 572015181, 22309307, 134852282, 555515360, 369362150, 430751146, 406320068, 257525653, 579747983, 105873116, 61065575, 480506303, 781430846, 423229817, 774154499, 347562971, 769504818, 693322286, 505699452, 731131040, 779056803, 131687420, 772153079, 314869638, 37031295, 469880979, 685923216, 716293729, 334611273, 981373086, 20279126, 317704145, 344234874, 245145914, 341313816, 804426222, 827642593, 146699153, 642845111 };
  v[90] = { 220437108, 552167422, 872394242, 221365698, 865778892, 68796421, 484280925, 616651256, 869089769, 700342550, 379751981, 988362237, 219977996, 213500492, 467445889, 491949483, 268631679, 643507167, 478936677, 331892033, 244555755, 666945615, 256918861, 579079013, 910738725, 176576607, 163902330, 490683032, 242186564, 782174499, 151720392, 168958578, 369622564, 522502782, 338104963, 543488255, 919926717, 238404846, 684269488, 868821009, 671126233, 831128205, 833699913, 570130431, 116813913, 499122176, 881430439, 428113921, 164544439, 167116147, 327118119, 129423343, 313974864, 759839506, 78317635, 454756097, 660139389, 475741570, 628621788, 829285774, 846523960, 216069853, 756057788, 507561320, 834342022, 821667745, 87505627, 419165339, 741325491, 331298737, 753688597, 666352319, 519307675, 354737185, 729612673, 506294869, 530798463, 784743860, 778266356, 9882115, 618492371, 297901802, 129154583, 381593096, 513963427, 929447931, 132465460, 776878654, 125850110, 446076930, 777807245, 0 };
  v[91] = { 756834862, 877999271, 639813740, 452195954, 644380457, 786850184, 205952609, 720285245, 268533837, 406151377, 437874969, 663533304, 797344903, 778795127, 522823005, 459299734, 827048599, 116100049, 847507865, 860501419, 621908852, 31413086, 148443126, 767144165, 855796061, 410939141, 342662711, 553118188, 865620146, 83817590, 73925411, 357791539, 18317870, 330478923, 115162610, 832507447, 318707121, 208368823, 210303018, 223439382, 380890115, 948658404, 325891621, 353833530, 74406636, 612395424, 462050193, 922305758, 642878864, 614936955, 990414525, 422646236, 580096969, 566960605, 568894800, 679233098, 165432772, 446332288, 231015975, 917099275, 577625606, 293759478, 283867299, 67425502, 379927460, 169471983, 101195553, 546052473, 634704369, 16003330, 133033370, 723529136, 484936569, 471943015, 205106478, 916055028, 285559540, 349082811, 93110689, 111660465, 245472064, 19813729, 51537321, 912164134, 460412726, 944324443, 363426868, 220957141, 413141644, 600759430, 362573899, 241409491, 523485044 };
  v[92] = { 631237659, 281581768, 823566788, 801508748, 542433787, 51294267, 863845570, 406692337, 905705994, 943267413, 217182244, 349375518, 482862564, 107828253, 290211573, 602735334, 573358861, 365853433, 695081729, 577258642, 190473838, 212926077, 134064877, 472635664, 472300092, 230846650, 953093132, 604348320, 218838073, 264302572, 971455052, 878391005, 865728917, 923041485, 281701318, 733410248, 96433547, 492038661, 370012239, 928658379, 655208625, 313311598, 315225589, 722618966, 159462141, 161156726, 978301517, 158053124, 182289336, 297739058, 842209129, 79927961, 10758286, 471986165, 191016956, 989123411, 350265539, 250393509, 840083131, 949035989, 786020169, 454949683, 692179666, 940310515, 880339941, 717642923, 481182353, 149166454, 804780299, 985465440, 18955092, 388902393, 989960264, 848663379, 329223503, 796477935, 589936924, 867343774, 255136282, 766837682, 149070855, 827357806, 485722399, 83429382, 693281532, 828275715, 370662016, 645808765, 441680256, 26219010, 227055366, 880560506, 286503457, 328925127 };
  v[93] = { 907427335, 97457979, 3085347, 932172323, 992602433, 476864488, 634154175, 537705525, 654713807, 394536512, 868832873, 939990456, 884217356, 175987397, 6665504, 96350300, 429198562, 818172501, 866681717, 899126732, 259209056, 470125391, 671318179, 142607687, 434592344, 491169706, 699464203, 780985522, 365720148, 805572225, 375189544, 81532468, 39491700, 835405159, 841919129, 615397293, 342120473, 451564000, 909848182, 400390780, 51640218, 335475734, 179156033, 486664336, 234579974, 344156001, 173182127, 258017680, 428991554, 538567581, 790651943, 99915893, 256235594, 540071110, 888821672, 379364270, 919324441, 30523615, 303800435, 77278599, 70764629, 866678088, 908718856, 615061780, 47200108, 487052185, 902317559, 983838878, 775544381, 832121743, 540137086, 11426594, 808478159, 21150141, 661067817, 693512832, 645003616, 35733202, 701129293, 790814089, 960135982, 251906023, 307679123, 378836706, 902784698, 642607403, 525599121, 429150471, 271860784, 754367192, 693937082, 624779705, 719152337, 907427335, 233211067 };
  v[94] = { 734361535, 984562478, 624683471, 813036761, 823248273, 17042252, 651251339, 179886655, 989157972, 784188898, 450151469, 43326121, 265318587, 681279948, 410981940, 232457436, 426017111, 287506918, 639026277, 641000720, 253636482, 300932300, 403933043, 457797617, 430144793, 457892364, 709709341, 778330855, 218282507, 689255777, 226553399, 896745699, 272638261, 437631611, 357735996, 176324813, 959661859, 479980904, 49217908, 602092246, 454401986, 16320339, 212536592, 460139331, 167214046, 923411397, 919760161, 499122176, 78484191, 74832955, 831030306, 538105021, 785707760, 981924013, 543842366, 396152106, 949026444, 518263448, 38582493, 821919539, 640508356, 560612741, 725606091, 101498653, 771690953, 308988575, 779961845, 219913497, 288535011, 540351988, 568099559, 540446735, 594311309, 697312052, 744607870, 357243632, 359218075, 710737434, 572227241, 765786916, 587262412, 316964404, 732925765, 954918231, 548092883, 214055454, 9086380, 818357697, 346993013, 981202100, 174996079, 185207591, 373560881, 13681874, 263882818, 0 };
  v[95] = { 866018428, 804064816, 180457651, 722658940, 172983792, 476945380, 816766845, 403953785, 362489381, 753339428, 283125803, 91889584, 367832326, 30325956, 844655713, 870390237, 336430404, 247619565, 477275679, 809252852, 51971068, 980951803, 652859664, 581102825, 908566061, 570153441, 889915225, 701638641, 837782374, 691596818, 687561040, 459226314, 585160842, 709415955, 341113767, 372109948, 838248190, 644983977, 953364493, 318271894, 975533997, 525187234, 527867608, 55768203, 188808199, 719535379, 678036392, 682848010, 110452781, 105641163, 64142176, 531659349, 664699345, 138554397, 141234771, 591581534, 250599284, 885691883, 195828046, 389092259, 855230501, 824234320, 455932132, 331677019, 457611547, 685946273, 681910495, 828096051, 964239784, 154272015, 474033799, 812446419, 141665302, 213422141, 883574355, 952837973, 195556189, 861823369, 93235130, 182045969, 646330489, 620595965, 436681369, 774187739, 51886128, 243122347, 771153075, 380303028, 338838624, 751651684, 93228796, 787511561, 237836413, 693879477, 70272312, 132225925, 475697524 };
  v[96] = { 804813389, 451977104, 694355981, 364767242, 927377120, 8199092, 888039520, 674479992, 243119534, 402049504, 795559024, 261298189, 856078203, 284858116, 202717332, 843881356, 54741906, 344542426, 871159533, 941506052, 951647936, 880705643, 661614463, 897164379, 802083018, 77150981, 403534797, 970022795, 988774162, 155629134, 918439711, 188378219, 558333441, 72753305, 559012031, 265451888, 503063993, 117395318, 565989251, 65713249, 924493927, 256845815, 3053707, 805750679, 832125809, 750587989, 290187293, 420947362, 992361226, 927093097, 970354943, 522374932, 186607041, 549145746, 8027240, 928744532, 506593568, 655024349, 541156025, 36666512, 820778016, 560297913, 42205989, 183997185, 55002696, 562581830, 294743074, 741359871, 340187801, 115219853, 840782281, 95775813, 202858947, 411383781, 678636193, 265952512, 584464829, 783877454, 962399604, 660455975, 124426281, 178647507, 580238279, 633658672, 374920395, 817529835, 372125728, 246029335, 181879847, 174898265, 565729026, 787636442, 483323533, 995673983, 869369732, 105304768, 92222107, 576727850 };
  v[97] = { 822592935, 655586161, 904244163, 285264130, 53028858, 87417947, 558694789, 922191971, 806844203, 156371820, 996684150, 875790774, 47289887, 40529804, 750939254, 778785528, 85698028, 985285862, 503279066, 718878657, 191838335, 844939280, 626902383, 99781885, 217673357, 254204711, 151139819, 17806985, 246518965, 611178210, 521699769, 736396322, 223173996, 705392485, 532530511, 961745102, 759169252, 688927484, 684024140, 851305780, 63217657, 1575973, 798843715, 458627762, 32657353, 161797643, 809100849, 43780004, 289629527, 176320187, 928715017, 163394172, 514335319, 643475609, 71201665, 729230065, 930206676, 868564992, 658408762, 825690402, 830593746, 760351978, 962927828, 393898066, 566760040, 50734176, 563956502, 778653055, 868131496, 234546388, 5834408, 870745927, 973810819, 12097820, 892450701, 365330203, 583367100, 238223692, 765264014, 980863605, 464626048, 365969529, 60812676, 88658950, 376493853, 369733770, 199990304, 79096928, 237028951, 584800921, 700148689, 65401518, 592369029, 626758118, 858993390, 240013357, 989599708, 822592935, 105819201 };
  v[98] = { 738564617, 456393633, 544953663, 729400534, 41273022, 586983430, 391817234, 371460237, 649296915, 970952851, 18687676, 83334965, 149015585, 829995405, 143602295, 385419008, 158497743, 747202933, 887160269, 344384662, 165328016, 584370273, 126367683, 797007242, 243131359, 369569760, 753301797, 94781641, 820522995, 566436747, 922335370, 577437407, 271771674, 604108640, 306239989, 102739246, 193917334, 144561144, 689832042, 670501356, 408876711, 498158856, 972656118, 532743260, 809204418, 812568101, 317992144, 550504459, 546398988, 499122176, 451845364, 447739893, 680252208, 185676251, 189039934, 465501092, 25588234, 500085496, 589367641, 327742996, 308412310, 853683208, 804327018, 895505106, 692004363, 394135712, 726472678, 420806945, 75908982, 431807605, 177721357, 903462711, 244942555, 628674592, 755112993, 201237110, 871876669, 413874079, 832916336, 653859690, 111084083, 251041419, 839746609, 612825344, 854642057, 168248947, 849228767, 914909387, 979556676, 27291501, 348947437, 626784115, 606427118, 411260922, 956971330, 268843818, 453290689, 541850719, 259679736, 0 };
  v[99] = { 87327306, 752622171, 263364385, 768184392, 134456447, 646203231, 113227028, 928831244, 692169545, 248922221, 842215665, 223380170, 758906477, 153955175, 955119411, 366052888, 591687914, 504958693, 349478028, 926377278, 25292402, 785986387, 75243536, 510950798, 720478542, 267933689, 383864205, 106340393, 865769868, 615527895, 572695660, 609656290, 208609058, 438680636, 841656468, 969475382, 977848068, 458934303, 371782014, 270561056, 439253393, 955763535, 188997225, 402385511, 989276507, 996109726, 312390579, 22572677, 936026551, 12758317, 479217234, 404241115, 319450636, 609268538, 923793744, 916960525, 505607168, 292218882, 523696925, 7186783, 175879120, 277100078, 189947789, 708861554, 717234240, 589415326, 992391158, 762319580, 361272348, 324311718, 281479483, 531721456, 292906578, 570430390, 686360906, 140661406, 350189150, 912726241, 201983390, 439533758, 536693235, 958038338, 802557673, 889286894, 116677567, 705744090, 508663973, 115370922, 650897229, 271488371, 864781815, 309784786, 73123087, 255763224, 721031374, 209284590, 573800998, 68980991, 577967558, 910917047, 18708023 };
  v[100] = { 272940027, 58608649, 790649869, 493409543, 955515011, 605915373, 44473783, 15101410, 702636568, 556160609, 701821330, 514998548, 693282527, 196939998, 646613709, 79014751, 522182364, 69521816, 508502574, 83518302, 33592575, 798843028, 170181484, 401352983, 230860946, 599438795, 409407582, 236533583, 950859316, 445920839, 120939184, 887226505, 283984910, 183351017, 341609548, 619554638, 603782632, 138897707, 74756623, 677407922, 73210233, 546521528, 716293426, 324071871, 96766209, 619759998, 61406096, 277149714, 418420060, 169437507, 563413958, 124382598, 957312742, 85274420, 340481545, 778603865, 752172923, 685487806, 353644484, 337103111, 732747695, 905126340, 91097176, 160675175, 922698073, 130901184, 166075264, 131840208, 859320000, 146701738, 40503765, 930405409, 399094185, 912170471, 423099517, 511807180, 834055275, 828340425, 294665030, 760069634, 977029954, 844198043, 939356741, 893408926, 520892843, 559686423, 24005118, 971443274, 32579574, 266731015, 917984345, 369461695, 796777392, 264256339, 741139173, 317456292, 641339338, 529390873, 860463367, 745101442, 21288184, 175890360 };

  return v;
}

std::pair<mint, mint> fib2(u64 n){
  if(n == 0) return { 0, 1 };

  auto aux = [](auto self, u64 n, mint q) -> std::pair<mint, mint> {
    if(n == 0) return { 0, 1 };
    auto [a, b] = self(self, n/2, q * q - 2);
    if(n % 2) return { a + b, b * q };
    else return { a * q, a + b };
  };

  auto [a, b] = aux(aux, n/2, 3);
  if(n % 2) return { b - a, b };
  else return {a, b - a}; 
}

int main(){
  u64 n;
  u32 k;
  std::cin >> n >> k;

  auto [ a, b ] = fib2(n);

  std::vector<mint> fib(k+1);
  fib[0] = a;
  fib[1] = b;
  for(u32 i = 2; i < fib.size(); i++) fib[i] = fib[i-1] + fib[i-2];

  auto v = init_vector();
  mint r = (k & 3) ? v[k][k+1] : (v[k][k+1] * mint((n+1) % mod));
  for(u32 i = 0; i <= k; i++) r += v[k][k-i] * modpow(fib[i], k);

  std::cout << r << std::endl;
 
  return 0;
}
yukicoder

結果

テストケース

ソースコード
