#1014451 (C++17) No.2883 K-powered Sum of Fibonacci

提出ソース
結果

問題	No.2883 K-powered Sum of Fibonacci
ユーザー	Ryuhei Mori
提出日時	2024-09-29 21:13:05
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 3,000 ms
コード長	60,683 bytes
コンパイル時間	1,577 ms
コンパイル使用メモリ	104,000 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-09-29 21:13:11
合計ジャッジ時間	2,676 ms
ジャッジサーバーID （参考情報）	judge2 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,820 KB
testcase_07	AC	2 ms 6,820 KB
testcase_08	AC	2 ms 6,820 KB
testcase_09	AC	2 ms 6,820 KB
testcase_10	AC	1 ms 6,816 KB
testcase_11	AC	2 ms 6,820 KB
testcase_12	AC	1 ms 6,816 KB
testcase_13	AC	1 ms 6,816 KB
testcase_14	AC	2 ms 6,820 KB
testcase_15	AC	2 ms 6,816 KB
testcase_16	AC	1 ms 6,816 KB
testcase_17	AC	1 ms 6,816 KB
testcase_18	AC	1 ms 6,816 KB
testcase_19	AC	2 ms 6,816 KB
testcase_20	AC	2 ms 6,820 KB
testcase_21	AC	2 ms 6,816 KB
testcase_22	AC	2 ms 6,816 KB
testcase_23	AC	2 ms 6,816 KB
testcase_24	AC	2 ms 6,816 KB
testcase_25	AC	2 ms 6,820 KB
testcase_26	AC	2 ms 6,816 KB
testcase_27	AC	1 ms 6,816 KB
testcase_28	AC	1 ms 6,820 KB
testcase_29	AC	2 ms 6,816 KB
testcase_30	AC	2 ms 6,816 KB
testcase_31	AC	1 ms 6,820 KB
testcase_32	AC	2 ms 6,816 KB
testcase_33	AC	2 ms 6,820 KB
testcase_34	AC	1 ms 6,816 KB
testcase_35	AC	2 ms 6,820 KB
testcase_36	AC	2 ms 6,820 KB
testcase_37	AC	2 ms 6,816 KB
testcase_38	AC	1 ms 6,816 KB
testcase_39	AC	2 ms 6,816 KB
testcase_40	AC	2 ms 6,816 KB
testcase_41	AC	2 ms 6,820 KB
testcase_42	AC	1 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<mint> > init_vector() {
  std::vector<std::vector<mint> > v(101);

  v[1] = { 998244352, 1, 1 };
  v[2] = { 0, 0, 1, 0 };
  v[3] = { 499122177, 499122176, 0, 499122178, 499122176 };
  v[4] = { 918384805, 918384805, 479157290, 39929774, 638876386, 0 };
  v[5] = { 45374743, 952869610, 90749488, 725995894, 907494865, 317623203, 952869610 };
  v[6] = { 0, 0, 499122177, 748683266, 0, 249561087, 499122177, 0 };
  v[7] = { 549190859, 449053494, 391161580, 666539334, 843344369, 638375698, 761982757, 242520181, 449053494 };
  v[8] = { 95831458, 95831458, 388649802, 210296811, 346058042, 758665708, 114465353, 979610458, 5323970, 0 };
  v[9] = { 646857729, 351386624, 195663141, 649410575, 98490368, 503980812, 948999169, 463794112, 753336028, 27916584, 351386624 };
  v[10] = { 0, 0, 162052655, 230114771, 609317983, 226873715, 453747431, 771370638, 609317983, 768129582, 162052655, 0 };
  v[11] = { 712820338, 285424015, 318576226, 680669567, 319381933, 314925524, 780786236, 175971189, 361692768, 365853292, 216051543, 173645120, 285424015 };
  v[12] = { 42613055, 42613055, 516435727, 320316649, 314007744, 529748312, 927137411, 374445451, 671459081, 188348744, 740138294, 63200846, 260757397, 0 };
  v[13] = { 574586305, 423658048, 636216157, 229281029, 672984028, 437032718, 362484729, 817558571, 76838925, 136325107, 562303156, 830994289, 683906064, 119883298, 423658048 };
  v[14] = { 0, 0, 934093854, 82143933, 616818352, 492428967, 439839461, 140557393, 11474079, 857686960, 439839461, 505815386, 616818352, 916100420, 934093854, 0 };
  v[15] = { 916003548, 82240805, 451416259, 377609610, 485412971, 365121609, 971545926, 904678417, 709534187, 699123175, 790752296, 115865219, 885982323, 234045688, 696577803, 216048537, 82240805 };
  v[16] = { 808076408, 808076408, 981437692, 992079548, 192637613, 895875059, 970363785, 72682838, 885023291, 405686503, 745556572, 589883088, 303402395, 436948855, 192637613, 195783317, 506292546, 0 };
  v[17] = { 317187483, 681056870, 763889881, 112724018, 361883573, 560839158, 470232180, 310099882, 406704581, 216641684, 52650112, 673879628, 705149123, 708599754, 577795960, 562525445, 654672002, 166610974, 681056870 };
  v[18] = { 0, 0, 598562196, 96556901, 423101627, 743002006, 338671458, 450515341, 560132876, 446852841, 152041099, 551391512, 560132876, 547729012, 338671458, 255242347, 423101627, 901687452, 598562196, 0 };
  v[19] = { 254643697, 743600656, 672471690, 107593906, 120072530, 281357849, 152591445, 926470768, 747375344, 557211236, 957700598, 86333559, 870347173, 576938323, 531965267, 652383054, 577982651, 539852247, 360715067, 519480168, 743600656 };
  v[20] = { 436508253, 436508253, 124980114, 951169081, 544401700, 187200418, 343391286, 759965178, 392569973, 224074938, 123336778, 856917842, 824588980, 452153740, 263780661, 592492178, 42837670, 896917608, 426330699, 351198832, 751119349, 0 };
  v[21] = { 663930408, 334313945, 594001167, 709387984, 92534715, 816049634, 140636485, 692323590, 611972496, 669194362, 90857337, 938310686, 100605756, 948509647, 596702699, 192127665, 924724455, 896990129, 702066035, 229384037, 138876267, 561118793, 334313945 };
  v[22] = { 0, 0, 913982582, 612617934, 986305207, 451897263, 406943707, 33201521, 210682092, 24801741, 355992443, 109074993, 241654057, 889169360, 355992443, 973442612, 210682092, 965042832, 406943707, 546347090, 986305207, 385626419, 913982582, 0 };
  v[23] = { 995188491, 3055862, 621106711, 348254516, 279995208, 977312828, 135724068, 363882491, 240306997, 228978250, 747480529, 986939502, 744313885, 753611058, 41296677, 616913303, 619782090, 687138260, 575942314, 212199396, 551056737, 260358768, 434216549, 550821885, 3055862 };
  v[24] = { 397124940, 397124940, 649744489, 567042018, 759425774, 219582256, 532308285, 826825455, 609396177, 500397448, 395844939, 697247156, 313231704, 606417902, 873450248, 790077738, 52906515, 880375242, 994546426, 393542300, 582962475, 394822804, 750983409, 912817682, 875466974, 0 };
  v[25] = { 946179874, 52064479, 608245044, 875422709, 932967297, 200914672, 908675507, 558200739, 97619266, 137886238, 328609399, 371538428, 762611192, 730764393, 667270069, 284393815, 394083445, 82487876, 13947733, 411979947, 344627041, 5957498, 32169125, 974733550, 898641000, 304877422, 52064479 };
  v[26] = { 0, 0, 608595132, 619728679, 623925054, 628994653, 410371999, 350937092, 288226594, 565624877, 920443415, 991752519, 625623225, 420047098, 33339634, 578197255, 625623225, 6491834, 920443415, 432619476, 288226594, 647307261, 410371999, 369249700, 623925054, 378515674, 608595132, 0 };
  v[27] = { 420432633, 577811720, 299356328, 373198688, 202347677, 570925546, 351556711, 624172168, 363630564, 819359862, 547173859, 813241939, 38256540, 26233876, 153144380, 870378693, 60417502, 495822784, 37172610, 183977, 462388237, 155172197, 135845619, 744766844, 597488340, 246092642, 744199045, 670349536, 577811720 };
  v[28] = { 49171349, 49171349, 715802201, 662283390, 137352675, 832986700, 643052020, 448809263, 438397852, 190917027, 361946767, 13306868, 502751657, 29520697, 72133564, 672034019, 714253720, 750775966, 800722830, 914200024, 361946767, 343573880, 473492, 312915356, 467983725, 165257653, 172366334, 129177424, 27403315, 0 };
  v[29] = { 958595653, 39648700, 25085626, 480796681, 287099334, 657046040, 29161972, 480500187, 160125336, 298831843, 584785867, 435858734, 212522655, 905351576, 926874170, 257584965, 432755700, 914218994, 411235106, 352411053, 527624016, 993896357, 637676904, 636957342, 588525182, 11075949, 263888192, 650014372, 902106058, 871762032, 39648700 };
  v[30] = { 0, 0, 168420127, 944725312, 484081472, 922600278, 499749544, 104612509, 789272190, 751810826, 529299201, 296670696, 565266323, 815190304, 472902699, 294708724, 967971713, 703535629, 472902699, 183054049, 565266323, 701573657, 529299201, 246433527, 789272190, 893631844, 499749544, 75644075, 484081472, 53519041, 168420127, 0 };
  v[31] = { 117030354, 881213999, 867441423, 987016707, 197052876, 322999420, 329556437, 862140508, 185820681, 530457669, 43217538, 283260568, 831643754, 166490597, 308997302, 321378380, 26729479, 237772000, 857376920, 463053322, 126690347, 87459970, 955381755, 664260068, 219945190, 111453254, 248637012, 66373645, 386767757, 499975380, 404207647, 502404985, 881213999 };
  v[32] = { 517278769, 517278769, 614241074, 916721209, 229953236, 735454864, 3469310, 335206925, 52171215, 174647383, 531284306, 29264150, 942460302, 399983992, 542973994, 71784372, 128880596, 802629619, 916389549, 620430795, 58548351, 835232420, 341567291, 23419700, 370905023, 806829142, 834009396, 512742507, 411015504, 990526127, 409309754, 971564411, 323735594, 0 };
  v[33] = { 576469255, 421775098, 359756161, 952760810, 866490022, 111565928, 161414910, 550157657, 649161596, 610846701, 487749375, 170393363, 565172015, 680926233, 530757117, 750064603, 475669139, 335294306, 101447936, 115087752, 132942295, 610796313, 763421894, 864135678, 64685257, 914774959, 453572847, 269411555, 120219230, 429758205, 745238111, 779851148, 510012566, 416598869, 421775098 };
  v[34] = { 0, 0, 331821920, 483839915, 17005830, 861427747, 5199545, 826833122, 25641630, 272393853, 279147178, 629222667, 877259964, 48206420, 965506339, 933385601, 940363031, 817880612, 103819598, 180363741, 940363031, 64858752, 965506339, 950037933, 877259964, 369021686, 279147178, 725850500, 25641630, 171411231, 5199545, 136816606, 17005830, 514404438, 331821920, 0 };
  v[35] = { 823091621, 175152732, 172774130, 737740686, 57478448, 493657250, 837778879, 472155702, 573690750, 927268235, 387534866, 62454049, 249424309, 382758613, 419912357, 144758853, 460374661, 448130664, 772634062, 526222975, 386592902, 320901720, 487805467, 825143391, 796258620, 88323272, 997453456, 615804869, 816362600, 3857372, 25466356, 356869833, 291308102, 374615628, 253104859, 31894628, 175152732 };
  v[36] = { 187125926, 187125926, 373808233, 310697105, 287982842, 278454263, 2984356, 866884956, 569007256, 105721404, 906621931, 243534285, 38617578, 649954423, 355895038, 909044226, 532231364, 194979307, 587036633, 994116760, 150845903, 533030944, 340649382, 584107295, 611778639, 214252572, 137375942, 943560728, 884375317, 760923814, 793401485, 183999051, 447160943, 123936648, 685218470, 993438433, 274624, 0 };
  v[37] = { 345859510, 652384843, 863413903, 676927053, 453322253, 250286975, 636505074, 582063893, 161410878, 645439865, 908579658, 129673030, 194865240, 287106521, 72405374, 535755064, 18208872, 551064030, 197144469, 896620284, 274570745, 993543038, 215348177, 106956428, 958737250, 123087241, 516652488, 889698660, 835971776, 556234187, 696427609, 784223850, 981099992, 955662939, 207922048, 680920799, 791613371, 683039184, 652384843 };
  v[38] = { 0, 0, 75632578, 400958340, 739473272, 787487150, 742633951, 680589802, 205174769, 933544539, 71550477, 787261502, 36267750, 450718440, 227990094, 436191563, 898785338, 608463803, 244660117, 378024046, 503373780, 620220307, 244660117, 389780550, 898785338, 562052790, 227990094, 547525913, 36267750, 210982851, 71550477, 64699814, 205174769, 317654551, 742633951, 210757203, 739473272, 597286013, 75632578, 0 };
  v[39] = { 928163190, 70081163, 189192793, 888267246, 711399772, 620032090, 998141072, 193016288, 127989081, 25865617, 296016042, 244937486, 829040381, 454667322, 809958535, 905061461, 551370720, 774396339, 497590939, 315351588, 235502402, 157508270, 462231010, 621580248, 569074458, 604349969, 424888206, 687410413, 315653989, 674969755, 818120871, 503634689, 356101361, 966471160, 944088868, 397590467, 137996020, 426491465, 708087010, 450760495, 70081163 };
  v[40] = { 657579328, 657579328, 838140399, 948929334, 698576540, 852279522, 309020848, 130597978, 786753613, 25098996, 576915553, 290349129, 664239641, 681750188, 825284819, 298934139, 178994766, 851801258, 439817291, 469527296, 599344545, 848307019, 631170902, 663759509, 879204343, 489360051, 264572373, 817373285, 751505466, 525468556, 536398379, 263360105, 508065561, 698997862, 88475502, 758738437, 691888516, 4587959, 60463760, 34433243, 663730428, 0 };
  v[41] = { 627128207, 371116146, 812585584, 697139626, 962992339, 520520681, 940590939, 228550342, 905877644, 346891727, 916754974, 94112776, 515757464, 410309203, 23290139, 498203701, 109116308, 819502352, 170841830, 89110425, 888036716, 973060869, 184511186, 911683452, 710026529, 973462621, 913855935, 51096432, 319612428, 246185121, 65248468, 474150315, 881212312, 372555097, 219726200, 294715306, 536441817, 436598046, 915961454, 602990400, 986491970, 570488893, 371116146 };
  v[42] = { 0, 0, 258473211, 806601237, 74433031, 909818183, 595533094, 911712659, 838591171, 414306591, 442646379, 686148936, 871054512, 781200264, 618852224, 862457346, 530939772, 10521724, 298933436, 520279513, 12417588, 659503739, 898694695, 338740614, 12417588, 477964840, 298933436, 987722629, 530939772, 135787007, 618852224, 217044089, 871054512, 312095417, 442646379, 583937762, 838591171, 86531694, 595533094, 88426170, 74433031, 191643116, 258473211, 0 };
  v[43] = { 322239857, 676004496, 535907733, 485911945, 375343278, 678423010, 83329102, 72781293, 134758454, 778128727, 376581690, 893559771, 895182459, 719836098, 959922474, 327441228, 96896231, 737673905, 352965711, 823289109, 553988872, 290196463, 728881798, 177710301, 783490723, 814553185, 930235862, 88294672, 849820876, 566777414, 791025760, 200899363, 919229300, 940932138, 86094499, 199930968, 335091607, 132547323, 562652296, 556915328, 185366028, 402080505, 443923130, 416800642, 676004496 };
  v[44] = { 772961355, 772961355, 656869910, 725576768, 114361634, 533667458, 815651280, 298643046, 469098964, 90265627, 924833452, 42976308, 683843645, 376861970, 712810280, 890821632, 233659351, 902476029, 194407331, 810957984, 949454359, 891253660, 125411516, 346825553, 928950503, 394313893, 610863721, 312488782, 229266246, 757739517, 351643010, 958009933, 243006451, 724529301, 51165688, 448270233, 812641374, 590203081, 77036820, 763645286, 117462693, 127797727, 396055699, 106005594, 621874101, 0 };
  v[45] = { 958322047, 39922306, 29690782, 667240554, 505888796, 293112998, 764062418, 76606092, 412591819, 956945720, 942414536, 769990997, 843443866, 413443362, 87651403, 576821792, 909846132, 983787108, 932350553, 862614001, 989293649, 434228353, 418349977, 579617877, 873271566, 767091387, 359127543, 770109742, 669523913, 728748583, 594478989, 864093583, 228606532, 735760178, 794541957, 254232900, 142568033, 851632750, 449557271, 127811765, 724041583, 586393714, 355231599, 407295110, 950643672, 229675718, 39922306 };
  v[46] = { 0, 0, 658752945, 347398144, 608885002, 576931116, 504265629, 405917263, 469314305, 631925151, 562521850, 101362329, 135058551, 150670319, 897887832, 729062446, 683930426, 178589611, 236691937, 827376769, 459600689, 594261014, 941043044, 236366967, 661272170, 761877386, 941043044, 403983339, 459600689, 170867584, 236691937, 819654742, 683930426, 269181907, 897887832, 847574034, 135058551, 896882024, 562521850, 366319202, 469314305, 592327090, 504265629, 421313237, 608885002, 650846209, 658752945, 0 };
  v[47] = { 466468801, 531775552, 911701879, 98141795, 991271996, 719307809, 30092820, 434125590, 211076116, 544655841, 794080067, 535777634, 77666059, 971737760, 180840751, 61950026, 154111228, 477303648, 193961245, 650135352, 200481211, 661306491, 137040885, 124907669, 948302393, 185893357, 382393098, 136647275, 519405801, 516393068, 126223999, 266438179, 953298094, 962835873, 320351314, 23709961, 647154344, 37014942, 427633770, 327777171, 553881707, 698994263, 928379958, 206953521, 346352224, 932545347, 944986924, 874359760, 531775552 };
  v[48] = { 625765667, 625765667, 118122045, 697262259, 282840087, 713824787, 153196056, 851620602, 740941395, 518976528, 986351827, 990467032, 320504103, 191628932, 638604785, 444233981, 850975358, 924053947, 818950798, 633331278, 142120449, 235204460, 484179166, 685428648, 932574967, 397526651, 534979634, 93334654, 173633107, 719200994, 200934279, 51588585, 38511293, 78010077, 163100131, 59014554, 789623158, 925240282, 309909397, 499333108, 377752000, 210262181, 54312208, 927370990, 820317903, 48690292, 535316082, 271322404, 73411332, 0 };
  v[49] = { 746515328, 251729025, 482625907, 624178618, 895751352, 182749820, 60643541, 196295027, 286681644, 159627985, 943592608, 882470354, 644995562, 572985014, 384575001, 908511906, 568079886, 466064937, 926491570, 828700945, 601747876, 648984469, 372729721, 568791242, 56769369, 254935405, 316451973, 868880026, 200776888, 986076315, 496204009, 644322015, 24678052, 98153412, 560058152, 621084646, 780138774, 677921187, 931180040, 557415541, 786859146, 858617734, 475568695, 201454188, 418506049, 933634522, 791310661, 855000692, 970760113, 126835918, 251729025 };
  v[50] = { 0, 0, 90588689, 722056351, 27736380, 666442950, 216489927, 708848152, 810630776, 400901246, 889545879, 606835407, 207976751, 572786858, 683571318, 851778220, 192754800, 840201650, 3357664, 606459159, 954729662, 858465451, 555217199, 775078396, 513764738, 557217378, 687960318, 441026975, 513764738, 223165957, 555217199, 139778902, 954729662, 391785194, 3357664, 158042703, 192754800, 146466133, 683571318, 425457495, 207976751, 391408946, 889545879, 597343107, 810630776, 289396201, 216489927, 331801403, 27736380, 276188002, 90588689, 0 };
  v[51] = { 118437709, 879806644, 986417519, 947461393, 996146702, 152876676, 796823098, 402070821, 145448710, 239661986, 161521589, 261610005, 878020952, 444849093, 964762596, 46851593, 529612908, 456957375, 169851282, 110075571, 69108846, 35663654, 263622368, 382758220, 776237814, 240526490, 759434961, 95246637, 27432496, 504499624, 933911647, 808625794, 146769058, 733118685, 619636055, 292344403, 529034750, 440169865, 539982429, 619956646, 112868540, 374616821, 697425282, 121806993, 906067283, 986291138, 695598991, 584745560, 4063645, 779065990, 267377068, 39030207, 879806644 };
  v[52] = { 698596263, 698596263, 226329430, 45204630, 238106877, 49195554, 608836019, 426098938, 925789392, 342248249, 325918742, 207153473, 404158350, 325120983, 708062834, 444863053, 853997905, 163951957, 29014820, 393914205, 135187964, 18069630, 777346044, 655575044, 121497317, 268303197, 416678234, 327721362, 880649017, 782125481, 165412433, 496179208, 757157563, 285083533, 909661802, 325274518, 784699731, 535337895, 74977873, 116675031, 681328920, 435361345, 712948799, 820043752, 120077750, 728945380, 937777880, 597908746, 22627858, 141659828, 578935872, 202008230, 31224946, 0 };
  v[53] = { 92233061, 906011292, 804957342, 150545142, 21213123, 993255893, 509206479, 728388912, 336647392, 616415683, 740179030, 685341330, 161591032, 727313107, 198092501, 766198315, 565873058, 471781860, 284650783, 784944174, 938574837, 472412469, 107537230, 41796579, 120199258, 720489683, 975374104, 954883912, 795219256, 907685297, 228959279, 886118362, 887007610, 401500144, 682832189, 967271592, 75486710, 282013828, 541424755, 622028412, 713994042, 479249477, 559785707, 511803086, 515497218, 342097818, 300741402, 970608573, 291762869, 845660671, 723224073, 32250581, 897145310, 702087810, 906011292 };
  v[54] = { 0, 0, 549593157, 89675542, 816167205, 494846769, 293475036, 829377287, 174072161, 612263148, 417673305, 140038741, 960050824, 167741881, 207063803, 684196897, 43732698, 733837450, 432294459, 498031780, 831806273, 358496040, 871042512, 496038786, 598630114, 125297492, 445113762, 208839705, 693990325, 789404648, 445113762, 872946861, 598630114, 502205567, 871042512, 639748313, 831806273, 500212573, 432294459, 264406903, 43732698, 314047456, 207063803, 830502472, 960050824, 858205612, 417673305, 385981205, 174072161, 168867066, 293475036, 503397584, 816167205, 908568811, 549593157, 0 };
  v[55] = { 127576019, 870668334, 160235910, 342811789, 155654506, 996870953, 164131195, 311114534, 628127210, 900380312, 345340342, 710317910, 258631741, 907648555, 439187013, 514488758, 292684219, 521818555, 370320517, 336671296, 15031016, 819936870, 561128644, 666295120, 147412645, 565269360, 584622578, 748020073, 526067200, 740525360, 224033376, 245473141, 114517580, 855867230, 279807948, 988702845, 292880997, 779448715, 460291661, 60372743, 110810444, 489726125, 944304186, 823972861, 544406341, 288574390, 720379548, 274270259, 62203913, 455233588, 19352562, 70022217, 670569557, 498201272, 890310681, 189206484, 870668334 };
  v[56] = { 221829883, 221829883, 601968612, 250401151, 475082662, 224765077, 939786732, 855905475, 271256011, 918444474, 920445832, 885750459, 736773775, 165910748, 612726769, 411825713, 260041778, 459845884, 531484723, 973315779, 350003801, 651313203, 812293491, 708051605, 498103381, 331202388, 119956598, 370805932, 541379475, 498615954, 781243083, 487288669, 725120821, 131471908, 346561850, 426286567, 802983755, 764695108, 777572328, 307987106, 992887259, 883083044, 454793706, 917719771, 645859430, 12315862, 242351707, 161917338, 953515783, 160396926, 884199864, 131550464, 997324940, 749274501, 480615182, 525242718, 380198006, 0 };
  v[57] = { 664558374, 333685979, 493922192, 383504457, 866190539, 37509098, 414665850, 59300469, 615625570, 770289341, 135297506, 26201469, 499974818, 965537042, 693175671, 71965282, 924313260, 603353651, 561541080, 189499313, 92698086, 289524048, 857566294, 683440788, 939294474, 928191479, 405003574, 68571338, 882930804, 676967445, 467467182, 327097202, 499725497, 842178592, 603869303, 831576875, 807658861, 81429606, 866061047, 193355736, 870928160, 838815024, 712037873, 110356679, 878687306, 371158133, 229177022, 23620386, 333804738, 633651548, 216135852, 211499742, 729484028, 95360755, 199631490, 890826664, 175041571, 440464096, 333685979 };
  v[58] = { 0, 0, 39928549, 638841470, 663380702, 682830445, 706647093, 708129472, 378842103, 677341562, 263237515, 91776484, 855517142, 682941466, 122562390, 887699884, 102452318, 649009069, 271441600, 556667878, 968610314, 528487429, 811385376, 661270061, 519417490, 821168479, 327035007, 348085138, 827689424, 171874950, 259126897, 826369403, 827689424, 650159215, 327035007, 177075874, 519417490, 336974292, 811385376, 469756924, 968610314, 441576475, 271441600, 349235284, 102452318, 110544469, 122562390, 315302887, 855517142, 906467869, 263237515, 320902791, 378842103, 290114881, 706647093, 315413908, 663380702, 359402883, 39928549, 0 };
  v[59] = { 626098158, 372146195, 648818234, 650513016, 521656381, 825845789, 686933864, 905557683, 357413762, 697315751, 242747006, 40244929, 956151794, 581154946, 820665071, 734480984, 689094332, 335195511, 149644285, 927586342, 53794314, 290096094, 503668023, 380684789, 833875183, 148825828, 793776198, 401425832, 645884950, 690248284, 522158915, 737350550, 812596190, 85594092, 902222607, 683308825, 430715286, 710704213, 923918192, 319064687, 712760329, 438296093, 777540452, 840547311, 485991728, 365395518, 554444082, 631257446, 481744515, 759636513, 543973772, 305799017, 888762116, 581061293, 459443560, 496781661, 753419924, 382221962, 814583289, 653568495, 372146195 };
  v[60] = { 58164543, 58164543, 443848310, 148209800, 89507096, 548122096, 376869327, 438562997, 749930737, 454373898, 490594479, 457259988, 781722211, 524479067, 714033638, 357245829, 263347026, 79433175, 812876882, 303000844, 248213057, 5712595, 196498024, 682161483, 867860525, 459417509, 175622414, 947843474, 349321168, 324653639, 5657761, 551528932, 860632827, 922951709, 520611351, 35451822, 358926676, 80500303, 872288671, 26805612, 253225478, 390187308, 439113082, 385418952, 931063300, 829139900, 756810335, 272565979, 681969193, 363816605, 443544075, 655949966, 322716125, 512770686, 942026113, 334582276, 523245467, 908015701, 218064584, 448809996, 695400726, 0 };
  v[61] = { 475151091, 523093262, 701473947, 250310034, 150723722, 578793477, 697436476, 24968816, 825164114, 343489926, 294543381, 77665329, 698671261, 648748942, 139056541, 689725850, 391860572, 738299436, 19777140, 753841565, 701018465, 669958369, 529126342, 279168645, 933153723, 670838509, 591163136, 754521340, 820051802, 556604931, 52983744, 632676541, 485841234, 783414273, 454655394, 64225785, 439214465, 725616133, 977660475, 875540915, 737858521, 875809657, 536157716, 991370846, 135789253, 335346890, 472871380, 853070639, 583808786, 615583332, 334645997, 17515356, 848838825, 72126484, 885119712, 301213106, 370910802, 619005084, 131617396, 911006269, 32470973, 736604261, 523093262 };
  v[62] = { 0, 0, 315504625, 139569709, 784837602, 946287811, 993114976, 817084059, 111741577, 189193792, 1639959, 903167367, 369541112, 666262928, 921332813, 24074497, 795699845, 94995530, 902143554, 906710506, 694977805, 773152593, 131666927, 530556566, 848087465, 602828743, 158523044, 763722178, 377831208, 635160913, 669755794, 778167563, 817357390, 220076790, 669755794, 363083440, 377831208, 234522175, 158523044, 395415610, 848087465, 467687787, 131666927, 225091760, 694977805, 91533847, 902143554, 903248823, 795699845, 974169856, 921332813, 331981425, 369541112, 95076986, 1639959, 809050561, 111741577, 181160294, 993114976, 51956542, 784837602, 858674644, 315504625, 0 };
  v[63] = { 833315517, 164928836, 37165342, 224139505, 326627056, 477853101, 629705069, 884060, 705497184, 413447381, 448962015, 976456634, 647949599, 321571517, 396719367, 280807274, 18762896, 380667947, 988023760, 191588024, 554862557, 173426592, 61678650, 65190020, 809590469, 322579460, 951277450, 414140075, 457472509, 378486483, 14372626, 326316507, 629407070, 502845060, 411765112, 366691324, 551246214, 656150926, 494649437, 861402508, 156914042, 439092621, 463266978, 298879543, 231608939, 161596362, 735985689, 560340789, 130065157, 453086604, 142291969, 956362749, 531693026, 17779043, 849956569, 442875269, 148632621, 350751972, 67667624, 145213005, 793891897, 26044489, 587712049, 627336557, 164928836 };
  v[64] = { 368854422, 368854422, 949707983, 457902436, 777339683, 818596341, 280172333, 166867774, 399833724, 546652186, 627149859, 339571691, 412610512, 10543195, 319518660, 542663072, 808595188, 41255918, 987711854, 977726424, 386474782, 287355574, 498697987, 698589726, 847723594, 63131629, 710672829, 60650862, 702906296, 612072705, 695601306, 600719397, 407960382, 720446139, 971562091, 580901312, 813400451, 306728452, 861981884, 712503702, 97656584, 864269515, 91008160, 502289768, 670608423, 67471423, 544377497, 233938961, 159411648, 761457730, 548641396, 646465170, 35003593, 138007451, 426340379, 564863995, 861576223, 336409874, 463856019, 561501332, 340746355, 578674968, 589214685, 989009362, 127054362, 0 };
  v[65] = { 77661467, 920582886, 922205018, 397129613, 779735771, 364720566, 636871516, 899122665, 670034929, 583153722, 301173990, 423236065, 334277637, 213033586, 627242599, 25493154, 385707131, 656706013, 411967553, 267726652, 84095189, 132810283, 25430304, 769541574, 47228828, 37108089, 905427264, 18266979, 335263971, 793664683, 358365312, 680446223, 429288847, 781263873, 861610036, 114650764, 991039126, 70613287, 69170727, 726786070, 367455164, 74631584, 541570759, 432758149, 271164839, 735159629, 547147410, 74697906, 680244229, 798904299, 156701235, 282338097, 845410281, 908407981, 424220834, 664258298, 686387212, 901771352, 203342113, 933614749, 446157834, 937243911, 175568523, 371332692, 452159114, 978978608, 920582886 };
  v[66] = { 0, 0, 443618954, 442195063, 598009364, 31519688, 56966535, 563607125, 362773109, 6989739, 242347983, 51586920, 261351440, 642457505, 460840534, 129744230, 83315131, 397639498, 626046716, 462950602, 153601798, 993285620, 765519287, 112198022, 347651186, 243050041, 453583529, 959766953, 532017824, 614105134, 348489240, 299291055, 977176548, 240075217, 548802587, 758169136, 977176548, 698953298, 348489240, 384139219, 532017824, 38477400, 453583529, 755194312, 347651186, 886046331, 765519287, 4958733, 153601798, 535293751, 626046716, 600604855, 83315131, 868500123, 460840534, 355786848, 261351440, 946657433, 242347983, 991254614, 362773109, 434637228, 56966535, 966724665, 598009364, 556049290, 443618954, 0 };
  v[67] = { 797726566, 200517787, 835071127, 717609164, 258202857, 593175932, 984621244, 616213516, 250415570, 161275227, 701276531, 291984782, 95973253, 766987905, 414038441, 912298321, 794474502, 742341315, 560679219, 612865405, 416256147, 429818193, 272306931, 972647544, 873341467, 639825723, 708266700, 751882636, 145179876, 464884379, 452314337, 830617659, 828519669, 882183485, 305973870, 877504432, 648752445, 313582584, 829654083, 785360471, 741139322, 363928194, 898481888, 818672871, 879835837, 35280604, 355633449, 766396212, 388730048, 342936035, 14988748, 461090356, 21197796, 431203016, 1846285, 10683224, 323390206, 560785759, 465338459, 192534338, 684766683, 213119690, 779822231, 619767357, 408976258, 210868252, 630688522, 377555987, 200517787 };
  v[68] = { 425517036, 425517036, 329579884, 185588332, 295681788, 603891727, 707037177, 586267000, 532277506, 181623487, 788177566, 235033900, 392435118, 261201340, 89562620, 64593316, 65040322, 583683544, 958397209, 567393460, 126154994, 728105432, 311420898, 773669447, 334238124, 505624692, 604627620, 190540521, 955110958, 376808274, 334795991, 391890732, 449718233, 170078263, 863024925, 845152031, 148642978, 277585115, 361202674, 157553240, 169629221, 978682211, 362275885, 169223413, 143845570, 419657499, 828274044, 187905025, 843633858, 683520631, 350380010, 797177316, 603349113, 288646884, 993913657, 108038874, 227205620, 143146664, 99900360, 829979627, 511008478, 255483555, 501416017, 63102533, 421857550, 696659771, 792396525, 455154568, 835665955, 0 };
  v[69] = { 789057334, 209187019, 587166207, 855171268, 336124441, 772207309, 624051961, 944054412, 452067393, 960188455, 754307214, 278273727, 330819460, 775677361, 840027121, 970531742, 124751042, 738088798, 711625927, 253048353, 694734806, 725087617, 487342027, 353575852, 878617486, 435021918, 603537058, 637903914, 757019711, 685490250, 523283160, 11243200, 819572558, 430119976, 236880914, 244789487, 817314445, 3391527, 565215515, 876290353, 182979893, 376797355, 644142982, 424141527, 642067396, 491944945, 83099729, 247157875, 537544937, 427436212, 411751257, 665186698, 669081138, 934451680, 692329462, 829769223, 472473572, 3593514, 808016783, 664081769, 873062138, 138560397, 993780561, 863322473, 412160860, 178842725, 923769696, 435086586, 474168210, 128682838, 209187019 };
  v[70] = { 0, 0, 624646108, 587159313, 462915201, 716787665, 711084043, 105683818, 425847914, 160583894, 550971291, 6142666, 885188413, 620292205, 864554369, 151793940, 276589677, 334647689, 152323925, 179123905, 736127180, 554968322, 898340919, 375771117, 778559923, 508663166, 63615223, 680987577, 552169642, 196697913, 727424875, 334350708, 632051359, 631006203, 901281077, 116667263, 475749136, 881577090, 901281077, 367238150, 632051359, 663893645, 727424875, 801546440, 552169642, 317256776, 63615223, 489581187, 778559923, 622473236, 898340919, 443276031, 736127180, 819120448, 152323925, 663596664, 276589677, 846450413, 864554369, 377952148, 885188413, 992101687, 550971291, 837660459, 425847914, 892560535, 711084043, 281456688, 462915201, 411085040, 624646108, 0 };
  v[71] = { 853097203, 145147150, 655776180, 61436800, 130477720, 16086296, 880317119, 581785269, 620007714, 334721309, 457598459, 236093573, 926508282, 339881885, 424741478, 882217014, 969823389, 222098037, 935463262, 358800012, 672819373, 251369091, 191354640, 106732384, 112073852, 654139723, 598806170, 488844253, 818213445, 633869665, 267525796, 980141104, 181623657, 210192183, 281502806, 499780233, 511229284, 490689961, 269717136, 355148941, 560309419, 768284865, 291667673, 512707466, 175159708, 921908657, 355863533, 386887364, 983265912, 11515255, 646859794, 263507134, 282061004, 405764670, 92402823, 610500026, 343838641, 274375022, 387013794, 234728631, 393801982, 806222917, 873235646, 271323780, 256554632, 417377808, 746164646, 14908451, 275574277, 891706307, 400800755, 332772060, 145147150 };
  v[72] = { 256726167, 256726167, 680240055, 780087557, 337950686, 230687883, 358424190, 666017118, 325568742, 267836250, 850962115, 711527181, 453023542, 522139666, 815436119, 890785067, 816910902, 957415528, 563958743, 659041804, 211939941, 632663594, 286716030, 552267604, 731873664, 429718565, 418096726, 461093048, 191591118, 33373895, 429743984, 941728022, 445276342, 147598070, 914480254, 663687247, 512527704, 676708732, 175928267, 611135726, 280916827, 238817863, 868823675, 20662285, 59753842, 549056290, 969799093, 182277251, 981072827, 195001973, 413882177, 767840628, 478783096, 634731781, 676133128, 296728165, 635300572, 868088267, 557906220, 454938409, 971668426, 185400521, 943220080, 531739769, 236432798, 124706773, 41913090, 379033008, 888572977, 96019216, 133550462, 980358338, 422297220, 0 };
  v[73] = { 4787490, 993456863, 237982777, 96201018, 377017581, 880669123, 530992390, 505361392, 724250217, 437966720, 735444746, 713520472, 619374458, 520807801, 227391632, 738535587, 235689681, 494323312, 827679621, 953832888, 692526100, 158066174, 515499066, 608089694, 539673670, 399563017, 882793697, 887324719, 48698868, 879496402, 345481605, 461640931, 229526528, 865675475, 900401603, 671716000, 135403022, 353159167, 82695758, 647031803, 169055485, 874145158, 563156936, 21550360, 575433225, 224911014, 551313300, 154761037, 988175529, 443974538, 965540394, 37656993, 151625619, 879689643, 300981984, 335635969, 146668942, 821895170, 305033579, 171200791, 614190315, 215608463, 709377689, 76059748, 83998779, 199243108, 77303880, 695543923, 896433753, 785569386, 656093628, 175289302, 327247944, 587469547, 993456863 };
  v[74] = { 0, 0, 561756542, 539226723, 403803543, 744344203, 509569263, 708366632, 190534074, 85251508, 23120224, 110339127, 724963891, 432220389, 606853652, 31741040, 404947174, 805242352, 217546611, 446833252, 652058613, 787702591, 645613858, 144757618, 107252943, 780290465, 274495018, 913663840, 564572304, 283636783, 219168514, 442453349, 904969807, 961897652, 139408098, 250592780, 717912440, 195976365, 234816511, 802267988, 717912440, 747651573, 139408098, 36346701, 904969807, 555791004, 219168514, 714607570, 564572304, 84580513, 274495018, 217953888, 107252943, 853486735, 645613858, 210541762, 652058613, 551411101, 217546611, 193002001, 404947174, 966503313, 606853652, 566023964, 724963891, 887905226, 23120224, 912992845, 190534074, 289877721, 509569263, 253900150, 403803543, 459017630, 561756542, 0 };
  v[75] = { 468077458, 530166895, 956345377, 937320089, 27087910, 374384723, 332543748, 941121457, 41419294, 449488972, 739394608, 320546196, 622169329, 904530980, 20174407, 655832026, 916330619, 563451177, 75284119, 925807954, 254919733, 650257031, 349429771, 745438142, 378133859, 600549575, 541674455, 123709268, 877270388, 404629205, 203579049, 288652277, 592575255, 305412513, 881306137, 90039161, 369078149, 550975566, 551854175, 73144551, 930086989, 206397958, 163648539, 148745662, 3046654, 501055286, 265722443, 876213707, 557170015, 940728583, 113735541, 780190621, 266017132, 656301206, 210291654, 964186630, 204295945, 408719793, 452315030, 409026630, 447588590, 15536500, 394261869, 135880358, 689015331, 737448130, 777522750, 960184855, 150450625, 156593854, 240289516, 875155264, 531812086, 631706247, 844068557, 125358019, 530166895 };
  v[76] = { 269290009, 269290009, 82208887, 566907905, 923021639, 330715945, 235815136, 377040477, 734719888, 484772405, 953540588, 6007363, 615364152, 720373587, 586480248, 870346975, 295613529, 607545106, 814297095, 927119810, 104532030, 468570185, 674901735, 579911150, 611773652, 625458547, 532490014, 977251616, 486040986, 471181323, 381792968, 955498367, 399712443, 630334975, 144969205, 106300217, 471640417, 244043249, 213367031, 315313287, 752136402, 915275998, 221050832, 557869693, 496089089, 813031541, 415623024, 142992930, 800259518, 510726756, 160221708, 900416774, 380618758, 470163778, 36140183, 701326349, 343248679, 305269177, 297584732, 85264172, 222833216, 443733063, 604967390, 144357367, 31199641, 974701239, 48390343, 53865275, 813016067, 138874867, 91280830, 350019942, 772971025, 735085223, 485551657, 823453246, 829876428, 0 };
  v[77] = { 325816364, 672427989, 27041392, 10614802, 185792042, 42473837, 328990606, 396563452, 940611382, 155872199, 711762618, 144068289, 910263703, 380161766, 869051890, 284040602, 183362855, 846508947, 518442046, 500125918, 515896424, 335098571, 758671896, 693424691, 897620818, 438884412, 880655118, 700349845, 847792057, 858696346, 447637900, 102930550, 728196517, 461793001, 938535770, 616535355, 761519618, 768631754, 221962261, 132268499, 295325439, 229045308, 80079509, 48505908, 43484355, 442131237, 411176600, 511514203, 320039676, 49573403, 86581210, 757092156, 883239798, 375321459, 909610159, 98142938, 663855902, 441718404, 870529935, 39981545, 721164057, 5148695, 419265308, 338147565, 955603537, 145014997, 371093874, 842332726, 321132226, 437970669, 118807786, 29781698, 60287278, 507801976, 823169731, 974176989, 934878120, 158792595, 672427989 };
  v[78] = { 0, 0, 618721510, 861158016, 289628518, 110508672, 196513229, 760312393, 729790442, 576919395, 495527106, 411189498, 741106089, 345304420, 510573094, 664175092, 470146636, 14636879, 559729198, 560865512, 784597555, 747293792, 652623407, 722349148, 240838826, 493785204, 749451981, 519410612, 511459399, 641008924, 630689505, 898871107, 535582998, 505613579, 412192670, 2766961, 605552036, 301238333, 583686185, 948395570, 326310646, 49848783, 583686185, 697006020, 605552036, 995477392, 412192670, 492630774, 535582998, 99373246, 630689505, 357235429, 511459399, 478833741, 749451981, 504459149, 240838826, 275895205, 652623407, 250950561, 784597555, 437378841, 559729198, 983607474, 470146636, 334069261, 510573094, 652939933, 741106089, 587054855, 495527106, 421324958, 729790442, 237931960, 196513229, 887735681, 289628518, 137086337, 618721510, 0 };
  v[79] = { 821616432, 176627921, 375698050, 219612505, 680456875, 806933599, 24725537, 93678998, 197909895, 165928681, 222808034, 844215045, 309153152, 438423543, 463982191, 667055201, 308591396, 987363395, 22429641, 238675629, 798953864, 370734373, 367703965, 680999326, 230003576, 506741039, 176208623, 637100078, 699433212, 177944702, 835112994, 977651001, 209621904, 393962448, 843030946, 864204459, 932391480, 167138040, 206058679, 669859107, 383316167, 868038617, 380474009, 526747053, 407507591, 947344955, 40366996, 971538638, 980785595, 990493646, 49115819, 993478179, 571265865, 31847415, 184104112, 146032000, 791942530, 487403580, 618086884, 848073579, 507675136, 289172860, 405924542, 705216213, 243727645, 262468643, 322911442, 892159951, 878828866, 484694649, 485950234, 576811713, 209223420, 337999531, 381077656, 298296554, 213648067, 821195668, 11703058, 397513233, 176627921 };
  v[80] = { 685151113, 685151113, 502027638, 325261402, 945662278, 362844063, 608214097, 948016802, 236233708, 682967891, 43424748, 354091019, 480747839, 537115755, 23816134, 29461761, 664800247, 947849377, 399679372, 281328746, 612617698, 774051861, 58646487, 114041302, 946446374, 206440945, 839183558, 137644923, 501950120, 726097080, 335831125, 493485158, 865939151, 440205847, 936799912, 527944036, 343971062, 591808354, 246596387, 614679887, 259827547, 326330056, 468811173, 89755724, 163578561, 257467529, 447655013, 206697951, 893239825, 148003398, 697379705, 997171235, 596191890, 758458380, 720250372, 112220194, 559516566, 643750653, 59882474, 620143472, 163348172, 437595457, 588427978, 173247772, 485910905, 749422114, 860230825, 362296787, 349508245, 324553820, 778620705, 914938154, 164054902, 974412741, 534106574, 871358308, 540914804, 483354126, 463657748, 576675247, 48580649, 0 };
  v[81] = { 701169185, 297075168, 712344478, 41130682, 337570029, 581686267, 488093033, 488830516, 357055086, 655754718, 856120942, 428166856, 602638919, 250132938, 812637044, 275060871, 817527217, 88926816, 338443250, 364042255, 556667157, 221647758, 11332457, 260326127, 184464311, 497599530, 710242490, 242700043, 10116119, 126701644, 576111129, 741707815, 571341086, 143545688, 334672687, 677894571, 406753176, 326606712, 629449644, 475449937, 351568418, 937365720, 255444689, 212116367, 861680051, 736009682, 501655455, 694779570, 23947742, 751792071, 751434861, 728657130, 367126439, 84536063, 648553378, 931000038, 847427025, 197867407, 278282765, 750444846, 661635780, 934971127, 387232896, 611024763, 114269643, 414139536, 224373870, 687786271, 529582065, 344916470, 490615135, 993631576, 743397257, 246547482, 354771465, 459030743, 987810582, 438371654, 102764346, 19546938, 169488591, 607120342, 297075168 };
  v[82] = { 0, 0, 131985284, 354182237, 51913096, 855290679, 578941235, 259746545, 890725271, 927790442, 206584664, 735712504, 870226297, 766740296, 772866800, 11243207, 315196078, 436413014, 592419259, 423481081, 56978355, 222131205, 796548542, 934098336, 843142100, 250896873, 339057555, 879086682, 207873622, 810050653, 372561692, 122091148, 90869078, 339437615, 143108719, 431578270, 825400693, 437177076, 180718937, 956324442, 835118981, 25155052, 762170192, 973089301, 835118981, 41919911, 180718937, 561067277, 825400693, 566666083, 143108719, 658806738, 90869078, 876153205, 372561692, 188193700, 207873622, 119157671, 339057555, 747347480, 843142100, 64146017, 796548542, 776113148, 56978355, 574763272, 592419259, 561831339, 315196078, 987001146, 772866800, 231504057, 870226297, 262531849, 206584664, 70453911, 890725271, 738497808, 578941235, 142953674, 51913096, 644062116, 131985284, 0 };
  v[83] = { 711127804, 287116549, 916674346, 150268900, 385535439, 808110847, 769196533, 648701285, 507243445, 642930056, 320981491, 837507800, 621581219, 977834327, 45698228, 784562692, 164952701, 36871065, 77567287, 483752028, 340755357, 735868912, 896563699, 866182911, 952128301, 352759723, 692678300, 738302024, 118105476, 453470108, 620148878, 965948831, 863194858, 665977280, 622052638, 308442484, 645740372, 456941893, 210494360, 829841486, 782646737, 704062003, 399471422, 431578998, 901324214, 801455914, 610367143, 748914176, 481938920, 161689851, 905110063, 894387430, 305722727, 336262883, 252052293, 972660706, 79889363, 700523463, 335511207, 795076690, 384109949, 628954120, 377747957, 523643878, 564450738, 901716682, 676035858, 693600288, 52038429, 511994705, 862572373, 499939228, 578782928, 871489982, 173351691, 448638703, 752556094, 223305060, 865257585, 160166361, 224962778, 869035606, 625938016, 45620898, 287116549 };
  v[84] = { 657971457, 657971457, 465122798, 301138119, 845218157, 116990519, 596622114, 475563595, 738991298, 520138789, 594826361, 345135057, 960887448, 346541941, 798923616, 690565443, 480447556, 49261873, 63544160, 129503063, 3662561, 363947566, 62943241, 988229411, 907450196, 250705733, 719237880, 811704332, 182072227, 624948252, 104445518, 165029282, 948889116, 790210302, 867916697, 824704119, 771929735, 785508100, 424947474, 466163338, 510734871, 967075526, 823598344, 920509776, 258121456, 373921922, 988530468, 311379084, 769396143, 330781788, 864083294, 894206320, 437173955, 617655216, 9712468, 42350103, 842651780, 19527523, 33488601, 602284966, 200746302, 181891436, 845013167, 747231247, 723183955, 289017742, 106866570, 861781698, 81467848, 180871805, 114435657, 752768785, 39912030, 649038080, 960403024, 599785130, 391380334, 8664161, 451488023, 942998560, 632735933, 271514909, 69174894, 523778897, 781163488, 0 };
  v[85] = { 689202392, 309041961, 276693614, 669364009, 915793041, 868686351, 874341554, 944955293, 15557924, 6584505, 838333457, 884328074, 929304596, 531980861, 680759130, 6023901, 514882181, 587162881, 192863308, 741713296, 202258873, 938056909, 644711409, 264604390, 662948673, 192150942, 227690903, 820118842, 942625147, 802679260, 748184672, 504010656, 809898521, 103162685, 826329148, 535591379, 364460230, 927684959, 93916190, 594925737, 719383943, 751896944, 575256041, 805629840, 108851450, 998086130, 259968066, 625195735, 894055878, 459889191, 492819460, 839017152, 648566943, 286843385, 839097605, 312902691, 339996202, 129364071, 168657856, 123689273, 137986445, 806899335, 929838012, 519662559, 631529458, 38368594, 709471753, 613687766, 413322647, 318666634, 13191478, 870364173, 103847846, 3000090, 948812731, 929684056, 710684281, 837515501, 625923787, 606117180, 625119704, 134581643, 695174705, 753251179, 606511257, 960724460, 309041961 };
  v[86] = { 0, 0, 378550104, 116469772, 786364115, 402847772, 428021741, 821506354, 148019833, 116671954, 183692742, 851468412, 567454597, 788858484, 40547662, 81834516, 582380411, 579234227, 116448584, 522174060, 279041834, 261543987, 12288624, 237107422, 398136545, 893391363, 127797715, 958289782, 262885598, 958611055, 46544481, 522696874, 266086551, 263547009, 184916449, 878301375, 273524917, 593894926, 833736511, 273617934, 38545414, 475602542, 330154473, 144322878, 406898788, 853921475, 330154473, 522641811, 38545414, 724626419, 833736511, 404349427, 273524917, 119942978, 184916449, 734697344, 266086551, 475547479, 46544481, 39633298, 262885598, 39954571, 127797715, 104852990, 398136545, 761136931, 12288624, 736700366, 279041834, 476070293, 116448584, 419010126, 582380411, 916409837, 40547662, 209385869, 567454597, 146775941, 183692742, 881572399, 148019833, 176737999, 428021741, 595396581, 786364115, 881774581, 378550104, 0 };
  v[87] = { 452443513, 545800840, 310517296, 965323021, 912502119, 896877441, 584149443, 108168950, 777112433, 133468335, 298698725, 746817892, 815738969, 649716272, 944064679, 381509264, 451152774, 595608157, 890464229, 579917992, 827708866, 275726214, 713291925, 309780933, 409539115, 174097010, 114648451, 737963877, 939933070, 590625201, 360908508, 478362389, 883495685, 10455125, 594721588, 17735245, 247602430, 633414196, 43634557, 839684640, 633428955, 393773463, 777403318, 87012323, 588103829, 959779068, 396989394, 96291749, 407773415, 67282123, 598588420, 863109004, 272269888, 259023009, 928545428, 886780487, 824631044, 766284903, 795106304, 542809496, 947300000, 133198965, 424024516, 368979632, 672351337, 546426357, 402727515, 387687773, 69028773, 202834413, 446261404, 545678796, 629158448, 945479253, 336361809, 315931590, 927468859, 78256684, 80514490, 746634088, 280416605, 249560503, 566155608, 361523820, 186940953, 746167761, 646429298, 741573160, 545800840 };
  v[88] = { 987207223, 987207223, 97695929, 944805353, 92910174, 254410525, 386144942, 723898941, 351095464, 890708910, 552603759, 927903913, 49854791, 264059632, 456012406, 580728072, 844697595, 308565323, 576194132, 169339656, 148556934, 123278295, 49835014, 373487337, 59938263, 805213149, 739166945, 515029933, 520443937, 47815320, 295333651, 562153950, 506808801, 736647211, 379181009, 925818171, 417824663, 6442029, 903043898, 332003013, 120356546, 122996139, 267876857, 47893081, 965185936, 426046718, 476345163, 254437171, 362421178, 168068319, 139721671, 730926567, 587023966, 180799210, 968040706, 355018192, 885158028, 364976711, 349728147, 310994475, 813616833, 384284025, 962577896, 633763247, 506667012, 559638225, 113347181, 565201112, 274543821, 656748991, 199470814, 17430885, 156739734, 800281794, 653813335, 306530701, 538583490, 773488299, 953003555, 910800770, 368395871, 332629941, 271521008, 848281255, 430766243, 646469794, 605865809, 80391270, 583329649, 0 };
  v[89] = { 642845111, 355399242, 805236360, 797580742, 422486961, 742539464, 322175098, 43396336, 127640037, 92664382, 408072199, 842245366, 310123093, 297172381, 313301755, 323109115, 618407861, 944456874, 174558325, 427568984, 519650427, 673478919, 798520048, 949405779, 825879990, 172262180, 398166553, 849544073, 419917655, 500619982, 438189179, 954165354, 795375261, 293557232, 223495987, 290308320, 665996737, 37899764, 740168801, 452541889, 421114991, 22409007, 287095570, 667869923, 582606179, 713114362, 723150128, 287868189, 503430969, 744991120, 834287858, 652629753, 368241774, 614361775, 862468836, 944839541, 611168425, 766600748, 457240379, 183625999, 808629561, 63298509, 478711632, 432098090, 586078496, 237938964, 911154023, 474705006, 456736256, 972688769, 896875327, 652915780, 315222572, 332286164, 916017220, 8125931, 905080421, 116397704, 597153837, 147099677, 294845244, 992411200, 507627748, 740063889, 608590501, 798631736, 692284836, 234208788, 4689362, 120278765, 355399242 };
  v[90] = { 0, 0, 409315424, 246138014, 584598926, 162254945, 283926803, 946600813, 122756013, 470536085, 921616759, 551002298, 876320565, 651123165, 223526891, 473895386, 865383042, 567616178, 717453396, 199684715, 963688113, 632278816, 286001705, 11806045, 250830285, 98501243, 264268750, 174856548, 56936168, 664346149, 133255607, 380414857, 202533923, 791120852, 644335473, 450760371, 393086212, 137797201, 232025878, 302728287, 943330707, 894873694, 559554829, 629905794, 856045606, 605888004, 379793617, 392356349, 856045606, 368338559, 559554829, 103370659, 943330707, 695516066, 232025878, 860447152, 393086212, 547483982, 644335473, 207123501, 202533923, 617829496, 133255607, 333898204, 56936168, 823387805, 264268750, 899743110, 250830285, 986438308, 286001705, 365965537, 963688113, 798559638, 717453396, 430628175, 865383042, 524348967, 223526891, 347121188, 876320565, 447242055, 921616759, 527708268, 122756013, 51643540, 283926803, 835989408, 584598926, 752106339, 409315424, 0 };
  v[91] = { 523485044, 474759309, 998166656, 473748015, 505182028, 82861599, 90782508, 131451613, 989879418, 613391458, 662753711, 941013117, 791070800, 853691712, 782074996, 380705048, 482729518, 277550047, 533528258, 394229114, 157345197, 886736723, 385890624, 318523849, 491561671, 98641206, 964497221, 572306701, 909685227, 496624630, 859056730, 846868728, 308957123, 886530919, 536749148, 478279857, 32420140, 498553521, 727741406, 728402788, 328417035, 718872949, 144341014, 552804859, 356915219, 869930609, 627689207, 927217304, 883570405, 334293623, 507770296, 674354103, 52035126, 291802659, 886429985, 468172351, 903670287, 942246300, 269222978, 293364345, 187462292, 24947330, 920898202, 188069684, 815781311, 495587814, 763007686, 137516801, 524816586, 331264977, 916101794, 742872424, 688212810, 45490837, 858530603, 774614244, 534311667, 742734996, 811926386, 922370276, 244107613, 864040350, 433165702, 70740099, 810079173, 556844992, 507427437, 448995074, 728278528, 384268803, 40111456, 719576716, 474759309 };
  v[92] = { 328925127, 328925127, 731479665, 68743216, 350414079, 663949629, 558221904, 422139216, 622333271, 486746749, 17468096, 58140973, 880625481, 561506057, 635790780, 458418660, 881834198, 668095443, 695317775, 646320562, 166826172, 309348854, 48685315, 199934215, 215352499, 957154254, 660193292, 850816184, 788318857, 49191326, 951257142, 556553946, 936430045, 238986130, 542796171, 580876394, 559761135, 663076960, 309633049, 951760635, 313014974, 78353919, 505986501, 639244568, 391922414, 595216996, 997535683, 39357964, 849892305, 621821766, 926029562, 733360888, 417767585, 434034371, 605775561, 349940645, 566097114, 569329138, 684951571, 489238706, 369315900, 672931829, 591882120, 650107911, 497439823, 613158483, 300570273, 127843067, 43140671, 635500617, 278334714, 416951120, 424328529, 259055047, 663119431, 597282050, 690948528, 155491809, 17423767, 650442431, 515028478, 242589837, 192765221, 556038967, 118860929, 405603677, 564985964, 739644489, 751549228, 822943019, 557604069, 808792662, 574589118, 0 };
  v[93] = { 233211067, 765033286, 383536601, 833003566, 492894599, 782841600, 330662171, 793799113, 920656653, 392974783, 94060099, 901042378, 651618254, 943470554, 362154605, 241348889, 468529291, 291198748, 331426995, 736155303, 977106682, 571580196, 498371369, 888214434, 435580005, 453295033, 762393137, 527037176, 581061286, 791867659, 719380151, 407996647, 86039710, 794126823, 95486949, 820091427, 761832569, 969763905, 61802250, 704742881, 382230068, 726154629, 32240361, 198057459, 622778345, 864962138, 958608000, 16072180, 224401136, 56979503, 920321327, 993297013, 229219617, 523233259, 992960198, 491542109, 381005151, 37905464, 750618336, 505291361, 337112679, 461418483, 992140939, 406019475, 609047732, 37732037, 278443908, 857072354, 970611996, 568634352, 219334501, 726431704, 947391023, 523362655, 19926470, 932450388, 664409824, 427824031, 753714242, 524598450, 539302740, 6172595, 618006316, 284508481, 748511652, 582481304, 684958840, 699304628, 814054646, 825769156, 196568399, 954947857, 55352650, 110790066, 765033286 };
  v[94] = { 0, 0, 136655534, 365016213, 291827076, 193620781, 900361459, 21707581, 955629037, 509895577, 639621435, 290749571, 819138675, 545160530, 189512787, 602030435, 635319087, 952075719, 619312443, 951384406, 111634273, 459597822, 263357024, 331146091, 954211428, 664569378, 837057616, 439800242, 55049414, 874452606, 578302006, 165385673, 137745912, 205596339, 261246827, 771698211, 342078835, 751976122, 532980685, 364591415, 183587291, 162374464, 468468325, 331685179, 521486285, 952575831, 389277965, 701473649, 313652929, 296770704, 389277965, 45668522, 521486285, 666559174, 468468325, 835869889, 183587291, 633652938, 532980685, 246268231, 342078835, 226546142, 261246827, 792648014, 137745912, 832858680, 578302006, 123791747, 55049414, 558444111, 837057616, 333674975, 954211428, 667098262, 263357024, 538646531, 111634273, 46859947, 619312443, 46168634, 635319087, 396213918, 189512787, 453083823, 819138675, 707494782, 639621435, 488348776, 955629037, 976536772, 900361459, 804623572, 291827076, 633228140, 136655534, 0 };
  v[95] = { 475697524, 522546829, 373158815, 724294852, 957000084, 310355592, 727795764, 758990934, 494919131, 331045332, 482545905, 829927213, 359249531, 670012353, 962855899, 695678409, 444955827, 645755999, 887536433, 944728967, 865227613, 108960495, 291802852, 635915773, 955473814, 351519735, 829493593, 163396213, 691537675, 515903005, 258911793, 377085376, 323898191, 522810246, 168229531, 213432077, 145194939, 755569274, 48231956, 873714975, 260297368, 843165993, 970343744, 305766619, 758992337, 310657489, 947317070, 92448745, 327838229, 321310854, 252650457, 937044378, 664818041, 295964415, 280067868, 538672498, 657388616, 321866636, 274298487, 181134986, 214269265, 371869785, 143588367, 784402433, 102501435, 796832217, 837406535, 98552758, 504082213, 85339401, 844209148, 258206946, 250528003, 688424925, 956245656, 813391862, 893133429, 284620542, 878201537, 805391348, 465272462, 745826816, 422003476, 229650475, 881518691, 359753155, 506825980, 870239130, 737143495, 298670759, 282262042, 822469307, 512672760, 899362995, 860457121, 643427710, 522546829 };
  v[96] = { 576727850, 576727850, 34073713, 829295820, 391874074, 146781041, 590038877, 337729926, 608001532, 487091384, 656597519, 695760936, 107236070, 110321755, 394324737, 763911233, 522399738, 254353617, 887369149, 808653332, 123531733, 954908426, 496780997, 982750184, 350841437, 59599355, 381721628, 662313645, 922162281, 311246143, 455506701, 596722486, 496741154, 145771649, 751547873, 497010397, 538130139, 51425459, 536252569, 289244670, 707890523, 827396312, 832585831, 552357565, 109534688, 619508990, 961110722, 531518733, 633902321, 992556652, 14433120, 510000277, 590772961, 880138759, 574478635, 604323723, 760348425, 560172192, 635156541, 417364357, 193856389, 928095406, 438567808, 388075193, 388342514, 139848312, 42599868, 743013194, 439795310, 437969771, 393320778, 95072358, 966777685, 880322232, 197003542, 585504099, 213255262, 701472977, 415281803, 219518860, 603660337, 971874681, 134479705, 552915705, 45278088, 730700516, 779178258, 267479825, 804935624, 438046213, 749236534, 247741090, 769685417, 729315189, 150193291, 130550261, 301978797, 0 };
  v[97] = { 105819201, 892425152, 474192535, 496679650, 106552918, 326039420, 650178490, 882198433, 406215978, 380141716, 395636403, 851324316, 293622525, 218784889, 664187388, 420023237, 596654275, 363897236, 554296496, 709886844, 961919459, 137345682, 176559761, 451437899, 668225887, 168956159, 460438830, 809134867, 192739430, 341321056, 738949916, 603921932, 278282123, 868684200, 936628545, 5242532, 244255717, 545807458, 119279189, 764813296, 500484548, 237173220, 246349952, 407744971, 895821720, 328949754, 937716013, 55924878, 126291992, 88933216, 258978824, 41529808, 255493280, 901626135, 510490679, 858407956, 164011030, 361790882, 462121450, 636515931, 35637393, 821984036, 872774560, 61558913, 417717176, 607318868, 375648230, 166751879, 756579402, 883428295, 614441174, 453181837, 151269774, 16843912, 484262830, 531657520, 545741712, 445811807, 459362729, 546392136, 820571412, 633596785, 388651026, 758367357, 743963674, 296871252, 508666320, 114622035, 801318705, 435542024, 639284976, 117169462, 89422178, 773483611, 644028794, 382164164, 333702701, 756211502, 892425152 };
  v[98] = { 0, 0, 636001682, 898750987, 437973804, 587255962, 49040621, 739157263, 538939255, 42292567, 464395793, 100360039, 324059763, 847049606, 427046624, 469262116, 335193195, 939337915, 124384100, 975181041, 302298867, 589272933, 660723497, 621176525, 734954169, 692470594, 451867175, 901482730, 839486662, 107553787, 594653080, 602315268, 304223064, 927192500, 340810035, 611422979, 844339818, 244417239, 873999495, 239151176, 207134943, 793477894, 318177977, 194301408, 158295349, 715681524, 824634691, 537282819, 835539658, 437741096, 701517839, 560503257, 835539658, 460961534, 824634691, 282562829, 158295349, 803942945, 318177977, 204766459, 207134943, 759093177, 873999495, 753827114, 844339818, 386821374, 340810035, 71051853, 304223064, 395929085, 594653080, 890690566, 839486662, 96761623, 451867175, 305773759, 734954169, 377067828, 660723497, 408971420, 302298867, 23063312, 124384100, 58906438, 335193195, 528982237, 427046624, 151194747, 324059763, 897884314, 464395793, 955951786, 538939255, 259087090, 49040621, 410988391, 437973804, 99493366, 636001682, 0 };
  v[99] = { 18708023, 979536330, 223798342, 839945169, 788139269, 664369009, 753583350, 47022933, 764386442, 806906557, 227127037, 41426989, 21431386, 785558188, 217013084, 409668924, 143597831, 690710056, 297934583, 621833009, 970870439, 373208371, 881733001, 702549544, 797689958, 556020705, 449565747, 324172414, 326320187, 708449072, 137016959, 357544298, 116224327, 377585047, 301310386, 36455231, 272656773, 126416914, 254963316, 857040740, 185346562, 218283832, 670161637, 205281102, 633155416, 486334387, 611866481, 102185096, 893362061, 161280901, 611697216, 352162312, 76438689, 95094202, 523763353, 617661890, 745682344, 667460651, 222192267, 460384663, 190461831, 952810185, 27784818, 337943089, 949431545, 810074916, 775845673, 806616600, 44050492, 311685609, 990672057, 773500108, 687532539, 415476638, 382843212, 657327099, 239467849, 606550742, 271733412, 208187951, 355185429, 993936857, 348956309, 207019234, 763470736, 198303159, 423572171, 346850107, 228320973, 525294275, 477900008, 843357989, 303103876, 531544258, 479262043, 428597451, 944296734, 250835757, 956699969, 79403913, 979536330 };
  v[100] = { 175890360, 175890360, 268473226, 252736935, 785667681, 145279879, 276684944, 922896646, 721129042, 893410393, 428970247, 253233578, 18477937, 301324991, 229722873, 24300208, 620444130, 799314956, 436922199, 994173697, 194671886, 114653992, 628785667, 962787481, 909218669, 266657260, 405856194, 937267838, 642659240, 55336314, 732195051, 834737977, 423121651, 674559315, 299990189, 550934649, 51667312, 446554765, 888731212, 678102799, 228322698, 954785191, 36805492, 933218400, 822647947, 928994869, 87029769, 757257023, 944670257, 364979301, 694071667, 939347929, 210728882, 429473344, 5449460, 197024350, 475386301, 569809418, 515899342, 462389924, 764828236, 754169759, 817106293, 771502051, 390737256, 166483363, 587041949, 36623960, 28996062, 846337530, 807000765, 818628116, 829957473, 724613637, 95277100, 664441186, 849032585, 339952563, 716071488, 30848376, 914099862, 669128812, 458935834, 394727306, 129597107, 948983796, 781185130, 118961713, 349261427, 714616651, 509407623, 130617198, 113143737, 833187782, 132946037, 526673864, 16418954, 946756272, 960428447, 780099347, 458154403, 0 };

  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);

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

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

結果

テストケース

ソースコード
