#398586 (C++11) No.718 行列のできるフィボナッチ数列道場 (1)

• 問題: No.718 行列のできるフィボナッチ数列道場 (1)
• ユーザー: Enjapma_kyopro
• 提出日時: 2019-11-18 17:58:14
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 1,238 ms / 2,000 ms
• コード長: 22,209 bytes
• コンパイル時間: 1,950 ms
• コンパイル使用メモリ: 166,860 KB
• 実行使用メモリ: 22,092 KB
• 最終ジャッジ日時: 2024-10-02 00:16:23
• 合計ジャッジ時間: 10,182 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	31 ms; 20,552 KB
testcase_01	AC	573 ms; 20,540 KB
testcase_02	AC	408 ms; 20,812 KB
testcase_03	AC	1,182 ms; 21,288 KB
testcase_04	AC	698 ms; 20,600 KB
testcase_05	AC	487 ms; 21,584 KB
testcase_06	AC	245 ms; 21,992 KB
testcase_07	AC	983 ms; 21,080 KB
testcase_08	AC	1,238 ms; 21,288 KB
testcase_09	AC	66 ms; 21,032 KB
testcase_10	AC	13 ms; 21,328 KB
testcase_11	AC	11 ms; 21,136 KB
testcase_12	AC	14 ms; 21,504 KB
testcase_13	AC	9 ms; 20,972 KB
testcase_14	AC	19 ms; 20,748 KB
testcase_15	AC	28 ms; 22,028 KB
testcase_16	AC	32 ms; 20,560 KB
testcase_17	AC	30 ms; 21,396 KB
testcase_18	AC	31 ms; 21,040 KB
testcase_19	AC	37 ms; 20,604 KB
testcase_20	AC	6 ms; 20,896 KB
testcase_21	AC	1,056 ms; 21,156 KB
testcase_22	AC	8 ms; 22,092 KB

ソースコード

#include <bits/stdc++.h>
#include <unistd.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
 
long long int INF = 3e18;
const ll fact_table = 5000000;
double Pi = 3.1415926535897932384626;
 
vector<ll> G[550010];
//vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←
 
 
#define p(x) cout<<x<<"\n";
#define el cout<<endl;
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
 
 
//ll mod = 998244353;
ll mod = 1000000007;
 
ll rui(ll number1,ll number2){
 
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
 
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
 
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
 
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}
 
/*
ll fact[fact_table + 5],rfact[fact_table + 5];
 
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=fact_table; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[fact_table] = rui(fact[fact_table],mod - 2);
    for(ll i=fact_table; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}
 */
ll n,m,num,sum,a,b,c,d,e,g,h,w,i,j,q,r,l;
ll k,idx,ans;
ll x[500005], y[500005], z[500005];
ll sum_table[500005];
ll a_table[500005];
ll b_table[500005];

int main(){
    cin >> n;
a_table[1] = 865390300;
b_table[1] = 196976169;
sum_table[1] = 672851136;
a_table[2] = 489276259;
b_table[2] = 974106729;
sum_table[2] = 736487817;
a_table[3] = 351309356;
b_table[3] = 927393756;
sum_table[3] = 545539761;
a_table[4] = 845895238;
b_table[4] = 786188346;
sum_table[4] = 456836476;
a_table[5] = 371975563;
b_table[5] = 80688602;
sum_table[5] = 393673464;
a_table[6] = 47125963;
b_table[6] = 396580227;
sum_table[6] = 319749430;
a_table[7] = 829535814;
b_table[7] = 241674835;
sum_table[7] = 35125330;
a_table[8] = 132225666;
b_table[8] = 721876347;
sum_table[8] = 793894259;
a_table[9] = 103684887;
b_table[9] = 294879735;
sum_table[9] = 293034767;
a_table[10] = 392460984;
b_table[10] = 947746097;
sum_table[10] = 298280710;
a_table[11] = 729987547;
b_table[11] = 369610353;
sum_table[11] = 132099345;
a_table[12] = 573486682;
b_table[12] = 719571781;
sum_table[12] = 644893985;
a_table[13] = 566334113;
b_table[13] = 57673489;
sum_table[13] = 317942513;
a_table[14] = 251655405;
b_table[14] = 355165112;
sum_table[14] = 375552579;
a_table[15] = 4660654;
b_table[15] = 539612979;
sum_table[15] = 438402909;
a_table[16] = 540377917;
b_table[16] = 337084384;
sum_table[16] = 145355725;
a_table[17] = 878336833;
b_table[17] = 557802238;
sum_table[17] = 275469824;
a_table[18] = 859137012;
b_table[18] = 221940703;
sum_table[18] = 385187623;
a_table[19] = 940822230;
b_table[19] = 467449387;
sum_table[19] = 488078886;
a_table[20] = 530142919;
b_table[20] = 975243705;
sum_table[20] = 370370194;
a_table[21] = 506593171;
b_table[21] = 12389717;
sum_table[21] = 65152339;
a_table[22] = 42290336;
b_table[22] = 133406429;
sum_table[22] = 841428646;
a_table[23] = 816832494;
b_table[23] = 422402570;
sum_table[23] = 203521976;
a_table[24] = 386573344;
b_table[24] = 516187473;
sum_table[24] = 588688694;
a_table[25] = 21;
b_table[25] = 999999994;
sum_table[25] = 999999903;
a_table[26] = 713229531;
b_table[26] = 612505998;
sum_table[26] = 590056243;
a_table[27] = 820848482;
b_table[27] = 611413983;
sum_table[27] = 297111051;
a_table[28] = 530750723;
b_table[28] = 321377683;
sum_table[28] = 821777948;
a_table[29] = 749517265;
b_table[29] = 543351451;
sum_table[29] = 873732307;
a_table[30] = 47291577;
b_table[30] = 762534955;
sum_table[30] = 813778829;
a_table[31] = 725901983;
b_table[31] = 834102307;
sum_table[31] = 110474854;
a_table[32] = 870954027;
b_table[32] = 278479141;
sum_table[32] = 20896575;
a_table[33] = 663730573;
b_table[33] = 392346524;
sum_table[33] = 183523603;
a_table[34] = 667188263;
b_table[34] = 343946086;
sum_table[34] = 324278121;
a_table[35] = 558994539;
b_table[35] = 920981438;
sum_table[35] = 961702175;
a_table[36] = 942240941;
b_table[36] = 524803828;
sum_table[36] = 229200797;
a_table[37] = 612460248;
b_table[37] = 688787155;
sum_table[37] = 389531035;
a_table[38] = 955783560;
b_table[38] = 143260939;
sum_table[38] = 827373546;
a_table[39] = 902183596;
b_table[39] = 667617049;
sum_table[39] = 797016943;
a_table[40] = 173410246;
b_table[40] = 82905056;
sum_table[40] = 317218074;
a_table[41] = 705922970;
b_table[41] = 965839223;
sum_table[41] = 225321637;
a_table[42] = 850394809;
b_table[42] = 193644322;
sum_table[42] = 248758446;
a_table[43] = 450096530;
b_table[43] = 156648008;
sum_table[43] = 577263050;
a_table[44] = 828481468;
b_table[44] = 680424708;
sum_table[44] = 17317349;
a_table[45] = 455258545;
b_table[45] = 454833148;
sum_table[45] = 798260502;
a_table[46] = 36016362;
b_table[46] = 477390200;
sum_table[46] = 598825587;
a_table[47] = 363663578;
b_table[47] = 153813486;
sum_table[47] = 581720454;
a_table[48] = 98149307;
b_table[48] = 662248887;
sum_table[48] = 128300100;
a_table[49] = 696443258;
b_table[49] = 407603068;
sum_table[49] = 541639506;
a_table[50] = 999999020;
b_table[50] = 610;
sum_table[50] = 999770037;
a_table[51] = 612821988;
b_table[51] = 15242128;
sum_table[51] = 581267617;
a_table[52] = 930845367;
b_table[52] = 289436280;
sum_table[52] = 987596721;
a_table[53] = 703406845;
b_table[53] = 967855262;
sum_table[53] = 118378343;
a_table[54] = 926793566;
b_table[54] = 676293646;
sum_table[54] = 870351143;
a_table[55] = 405320339;
b_table[55] = 80168765;
sum_table[55] = 616189133;
a_table[56] = 835481081;
b_table[56] = 400611624;
sum_table[56] = 498251206;
a_table[57] = 235625211;
b_table[57] = 669805636;
sum_table[57] = 83614932;
a_table[58] = 672437627;
b_table[58] = 837837165;
sum_table[58] = 242694293;
a_table[59] = 538466976;
b_table[59] = 539654342;
sum_table[59] = 388772834;
a_table[60] = 334795872;
b_table[60] = 766126632;
sum_table[60] = 178404220;
a_table[61] = 984688548;
b_table[61] = 964609913;
sum_table[61] = 714055658;
a_table[62] = 640881872;
b_table[62] = 907432172;
sum_table[62] = 50093806;
a_table[63] = 511838889;
b_table[63] = 209062427;
sum_table[63] = 695460293;
a_table[64] = 345715884;
b_table[64] = 266833809;
sum_table[64] = 640827875;
a_table[65] = 845057847;
b_table[65] = 563849424;
sum_table[65] = 661881075;
a_table[66] = 281242731;
b_table[66] = 268472457;
sum_table[66] = 139493214;
a_table[67] = 153107431;
b_table[67] = 340914698;
sum_table[67] = 734416221;
a_table[68] = 986326239;
b_table[68] = 415602977;
sum_table[68] = 634354375;
a_table[69] = 120549054;
b_table[69] = 552589568;
sum_table[69] = 731309657;
a_table[70] = 72705620;
b_table[70] = 647598500;
sum_table[70] = 390544952;
a_table[71] = 800637836;
b_table[71] = 550271044;
sum_table[71] = 542908482;
a_table[72] = 865521624;
b_table[72] = 637359785;
sum_table[72] = 15603910;
a_table[73] = 570150119;
b_table[73] = 451899965;
sum_table[73] = 954796309;
a_table[74] = 880593768;
b_table[74] = 326468471;
sum_table[74] = 809692249;
a_table[75] = 46368;
b_table[75] = 999971350;
sum_table[75] = 492455880;
a_table[76] = 484137243;
b_table[76] = 671114000;
sum_table[76] = 267565061;
a_table[77] = 429419584;
b_table[77] = 785080962;
sum_table[77] = 328836502;
a_table[78] = 409127800;
b_table[78] = 189425325;
sum_table[78] = 439222792;
a_table[79] = 691185448;
b_table[79] = 670847418;
sum_table[79] = 991226420;
a_table[80] = 902652630;
b_table[80] = 469533125;
sum_table[80] = 115627748;
a_table[81] = 6487490;
b_table[81] = 337151505;
sum_table[81] = 529928654;
a_table[82] = 54661140;
b_table[82] = 240656191;
sum_table[82] = 517256620;
a_table[83] = 731701189;
b_table[83] = 229307001;
sum_table[83] = 442776862;
a_table[84] = 24864047;
b_table[84] = 292300022;
sum_table[84] = 697360077;
a_table[85] = 705599596;
b_table[85] = 71067117;
sum_table[85] = 776408180;
a_table[86] = 777397639;
b_table[86] = 138530583;
sum_table[86] = 691624943;
a_table[87] = 266091985;
b_table[87] = 661901069;
sum_table[87] = 167497596;
a_table[88] = 987788839;
b_table[88] = 30805062;
sum_table[88] = 53481926;
a_table[89] = 849169982;
b_table[89] = 791194026;
sum_table[89] = 510092850;
a_table[90] = 108871225;
b_table[90] = 416172205;
sum_table[90] = 454303790;
a_table[91] = 75668771;
b_table[91] = 415955396;
sum_table[91] = 636199071;
a_table[92] = 953555997;
b_table[92] = 783364991;
sum_table[92] = 607829520;
a_table[93] = 192570566;
b_table[93] = 310012213;
sum_table[93] = 442832341;
a_table[94] = 505713043;
b_table[94] = 347865785;
sum_table[94] = 983083918;
a_table[95] = 127577343;
b_table[95] = 108037569;
sum_table[95] = 134442094;
a_table[96] = 334005612;
b_table[96] = 659870921;
sum_table[96] = 600185367;
a_table[97] = 956820388;
b_table[97] = 890276836;
sum_table[97] = 856108244;
a_table[98] = 104795289;
b_table[98] = 98452912;
sum_table[98] = 107138673;
a_table[99] = 915649947;
b_table[99] = 248378907;
sum_table[99] = 449141094;
a_table[100] = 997821698;
b_table[100] = 1346269;
sum_table[100] = 850349087;
a_table[101] = 632727759;
b_table[101] = 442400096;
sum_table[101] = 934817446;
a_table[102] = 886434339;
b_table[102] = 811758772;
sum_table[102] = 754557684;
a_table[103] = 67586695;
b_table[103] = 129154533;
sum_table[103] = 246316377;
a_table[104] = 587490616;
b_table[104] = 793877939;
sum_table[104] = 766342054;
a_table[105] = 170006352;
b_table[105] = 851774521;
sum_table[105] = 574248484;
a_table[106] = 859606903;
b_table[106] = 753267760;
sum_table[106] = 54279548;
a_table[107] = 195301230;
b_table[107] = 19353471;
sum_table[107] = 501736980;
a_table[108] = 937606742;
b_table[108] = 384733872;
sum_table[108] = 965832868;
a_table[109] = 292922829;
b_table[109] = 722244729;
sum_table[109] = 684905898;
a_table[110] = 502023354;
b_table[110] = 893718904;
sum_table[110] = 354436608;
a_table[111] = 477622685;
b_table[111] = 524452742;
sum_table[111] = 702182427;
a_table[112] = 852794931;
b_table[112] = 983217816;
sum_table[112] = 617097542;
a_table[113] = 62086007;
b_table[113] = 343099673;
sum_table[113] = 339149129;
a_table[114] = 743295249;
b_table[114] = 547047235;
sum_table[114] = 134083759;
a_table[115] = 37994620;
b_table[115] = 876057088;
sum_table[115] = 986576007;
a_table[116] = 162325060;
b_table[116] = 181624071;
sum_table[116] = 951846221;
a_table[117] = 29761025;
b_table[117] = 840930991;
sum_table[117] = 745324598;
a_table[118] = 962857236;
b_table[118] = 13823117;
sum_table[118] = 696614939;
a_table[119] = 110938093;
b_table[119] = 97718656;
sum_table[119] = 934881752;
a_table[120] = 931159308;
b_table[120] = 274635799;
sum_table[120] = 323153993;
a_table[121] = 501098519;
b_table[121] = 435795893;
sum_table[121] = 66186778;
a_table[122] = 163920462;
b_table[122] = 519629224;
sum_table[122] = 415276934;
a_table[123] = 504471340;
b_table[123] = 920813213;
sum_table[123] = 500252916;
a_table[124] = 83859031;
b_table[124] = 999722991;
sum_table[124] = 444694838;
a_table[125] = 102334155;
b_table[125] = 936754021;
sum_table[125] = 227965556;
a_table[126] = 777658301;
b_table[126] = 536081642;
sum_table[126] = 874523386;
a_table[127] = 908166784;
b_table[127] = 62257027;
sum_table[127] = 979959997;
a_table[128] = 414297563;
b_table[128] = 740311673;
sum_table[128] = 181017005;
a_table[129] = 696755803;
b_table[129] = 16889715;
sum_table[129] = 325674487;
a_table[130] = 107048889;
b_table[130] = 497064675;
sum_table[130] = 250767130;
a_table[131] = 591988356;
b_table[131] = 259264027;
sum_table[131] = 265032508;
a_table[132] = 766181120;
b_table[132] = 849730686;
sum_table[132] = 816250057;
a_table[133] = 200782252;
b_table[133] = 688201148;
sum_table[133] = 150347456;
a_table[134] = 207763088;
b_table[134] = 762197960;
sum_table[134] = 889945798;
a_table[135] = 699302941;
b_table[135] = 924144696;
sum_table[135] = 465179768;
a_table[136] = 774336334;
b_table[136] = 212190718;
sum_table[136] = 24980162;
a_table[137] = 652546545;
b_table[137] = 126861908;
sum_table[137] = 766767630;
a_table[138] = 94168860;
b_table[138] = 843510426;
sum_table[138] = 448640100;
a_table[139] = 215953567;
b_table[139] = 497586118;
sum_table[139] = 412760757;
a_table[140] = 105381649;
b_table[140] = 409144953;
sum_table[140] = 918927986;
a_table[141] = 295053465;
b_table[141] = 47713330;
sum_table[141] = 88395535;
a_table[142] = 647675849;
b_table[142] = 692878719;
sum_table[142] = 323546317;
a_table[143] = 553139664;
b_table[143] = 40301295;
sum_table[143] = 986326839;
a_table[144] = 280196628;
b_table[144] = 59357418;
sum_table[144] = 300927871;
a_table[145] = 107935489;
b_table[145] = 984079976;
sum_table[145] = 66415025;
a_table[146] = 114364163;
b_table[146] = 857722262;
sum_table[146] = 474032223;
a_table[147] = 338917961;
b_table[147] = 687149818;
sum_table[147] = 660078248;
a_table[148] = 185051899;
b_table[148] = 623326385;
sum_table[148] = 951038777;
a_table[149] = 142975631;
b_table[149] = 764640852;
sum_table[149] = 992359071;
a_table[150] = 192473059;
b_table[150] = 971215059;
sum_table[150] = 269629050;
a_table[151] = 817332360;
b_table[151] = 361762912;
sum_table[151] = 138281512;
a_table[152] = 429727121;
b_table[152] = 262160987;
sum_table[152] = 17140120;
a_table[153] = 460427984;
b_table[153] = 76197081;
sum_table[153] = 258210424;
a_table[154] = 664986881;
b_table[154] = 412305470;
sum_table[154] = 997245295;
a_table[155] = 798695907;
b_table[155] = 786185929;
sum_table[155] = 868803121;
a_table[156] = 316940568;
b_table[156] = 61323062;
sum_table[156] = 872461079;
a_table[157] = 794186389;
b_table[157] = 43304567;
sum_table[157] = 962125778;
a_table[158] = 625627491;
b_table[158] = 269812403;
sum_table[158] = 850999773;
a_table[159] = 942212112;
b_table[159] = 454451410;
sum_table[159] = 425456106;
a_table[160] = 630738657;
b_table[160] = 671480699;
sum_table[160] = 297303745;
a_table[161] = 128569876;
b_table[161] = 502583589;
sum_table[161] = 429034288;
a_table[162] = 477517678;
b_table[162] = 54272557;
sum_table[162] = 639049590;
a_table[163] = 511977608;
b_table[163] = 11910585;
sum_table[163] = 809544207;
a_table[164] = 106887179;
b_table[164] = 66405387;
sum_table[164] = 828900129;
a_table[165] = 9067912;
b_table[165] = 894130268;
sum_table[165] = 87474465;
a_table[166] = 970162190;
b_table[166] = 575849440;
sum_table[166] = 137097725;
a_table[167] = 529474289;
b_table[167] = 593769454;
sum_table[167] = 321391589;
a_table[168] = 39578745;
b_table[168] = 92016032;
sum_table[168] = 126703061;
a_table[169] = 719820489;
b_table[169] = 112482719;
sum_table[169] = 212924463;
a_table[170] = 995872758;
b_table[170] = 473605658;
sum_table[170] = 254804719;
a_table[171] = 123785862;
b_table[171] = 251258080;
sum_table[171] = 122921620;
a_table[172] = 906935490;
b_table[172] = 184329561;
sum_table[172] = 377405769;
a_table[173] = 798089477;
b_table[173] = 782846909;
sum_table[173] = 442312796;
a_table[174] = 196286361;
b_table[174] = 62157224;
sum_table[174] = 691759095;
a_table[175] = 851432142;
b_table[175] = 416138535;
sum_table[175] = 843343195;
a_table[176] = 807721059;
b_table[176] = 461061620;
sum_table[176] = 312771029;
a_table[177] = 894658683;
b_table[177] = 616176675;
sum_table[177] = 848284150;
a_table[178] = 945587350;
b_table[178] = 678425555;
sum_table[178] = 689384339;
a_table[179] = 48861014;
b_table[179] = 604753335;
sum_table[179] = 594675737;
a_table[180] = 354243748;
b_table[180] = 552196928;
sum_table[180] = 197707057;
a_table[181] = 511805060;
b_table[181] = 858552087;
sum_table[181] = 256554929;
a_table[182] = 907058870;
b_table[182] = 114954686;
sum_table[182] = 595326694;
a_table[183] = 394725881;
b_table[183] = 630616009;
sum_table[183] = 6137968;
a_table[184] = 508267963;
b_table[184] = 878585931;
sum_table[184] = 91673137;
a_table[185] = 655980397;
b_table[185] = 516262682;
sum_table[185] = 684180421;
a_table[186] = 182879543;
b_table[186] = 166380767;
sum_table[186] = 853686391;
a_table[187] = 904122757;
b_table[187] = 322327934;
sum_table[187] = 615667196;
a_table[188] = 842883739;
b_table[188] = 596692093;
sum_table[188] = 215411806;
a_table[189] = 760349062;
b_table[189] = 381360721;
sum_table[189] = 969810709;
a_table[190] = 468426494;
b_table[190] = 566732752;
sum_table[190] = 137214484;
a_table[191] = 107323927;
b_table[191] = 887363186;
sum_table[191] = 486280985;
a_table[192] = 467032750;
b_table[192] = 399957146;
sum_table[192] = 987685209;
a_table[193] = 586659342;
b_table[193] = 634945236;
sum_table[193] = 647326401;
a_table[194] = 888240634;
b_table[194] = 653954831;
sum_table[194] = 623358246;
a_table[195] = 86045214;
b_table[195] = 756454266;
sum_table[195] = 287595433;
a_table[196] = 67700365;
b_table[196] = 333148069;
sum_table[196] = 813980786;
a_table[197] = 35114310;
b_table[197] = 649360885;
sum_table[197] = 274447670;
a_table[198] = 304742948;
b_table[198] = 582869158;
sum_table[198] = 233294729;
a_table[199] = 631565472;
b_table[199] = 313969648;
sum_table[199] = 719952478;
a_table[200] = 790216554;
b_table[200] = 470273943;
sum_table[200] = 988788854;
a_table[201] = 219778140;
b_table[201] = 968341109;
sum_table[201] = 147374220;
a_table[202] = 521315079;
b_table[202] = 777535498;
sum_table[202] = 145965385;
a_table[203] = 96966881;
b_table[203] = 37802058;
sum_table[203] = 213014661;
a_table[204] = 38545482;
b_table[204] = 164287988;
sum_table[204] = 452096646;
a_table[205] = 551848063;
b_table[205] = 260558644;
sum_table[205] = 470668192;
a_table[206] = 628221787;
b_table[206] = 586729136;
sum_table[206] = 344262828;
a_table[207] = 574047029;
b_table[207] = 553825233;
sum_table[207] = 923878255;
a_table[208] = 822256242;
b_table[208] = 91235384;
sum_table[208] = 695495078;
a_table[209] = 169193802;
b_table[209] = 252010127;
sum_table[209] = 897155405;
a_table[210] = 538182908;
b_table[210] = 64173422;
sum_table[210] = 688874398;
a_table[211] = 276091666;
b_table[211] = 677520425;
sum_table[211] = 656817027;
a_table[212] = 28713044;
b_table[212] = 796314657;
sum_table[212] = 138442035;
a_table[213] = 872486946;
b_table[213] = 943561247;
sum_table[213] = 604307876;
a_table[214] = 156707159;
b_table[214] = 9640852;
sum_table[214] = 543319220;
a_table[215] = 974887031;
b_table[215] = 469430584;
sum_table[215] = 744889168;
a_table[216] = 985613290;
b_table[216] = 718081119;
sum_table[216] = 85028218;
a_table[217] = 519986622;
b_table[217] = 608244824;
sum_table[217] = 499848980;
a_table[218] = 387432377;
b_table[218] = 65558086;
sum_table[218] = 522653509;
a_table[219] = 532870014;
b_table[219] = 151640441;
sum_table[219] = 538714393;
a_table[220] = 960002226;
b_table[220] = 973044099;
sum_table[220] = 468311033;
a_table[221] = 694297011;
b_table[221] = 90782789;
sum_table[221] = 332660069;
a_table[222] = 442691961;
b_table[222] = 295709061;
sum_table[222] = 328597245;
a_table[223] = 878992079;
b_table[223] = 822302868;
sum_table[223] = 439150068;
a_table[224] = 120136665;
b_table[224] = 181269425;
sum_table[224] = 243348294;
a_table[225] = 8390086;
b_table[225] = 480986305;
sum_table[225] = 413641875;
a_table[226] = 862706445;
b_table[226] = 26906579;
sum_table[226] = 942129802;
a_table[227] = 603532786;
b_table[227] = 839655185;
sum_table[227] = 297317857;
a_table[228] = 496969285;
b_table[228] = 544877740;
sum_table[228] = 433968764;
a_table[229] = 139501346;
b_table[229] = 673711292;
sum_table[229] = 182614565;
a_table[230] = 708897480;
b_table[230] = 201546895;
sum_table[230] = 566984980;
a_table[231] = 961771168;
b_table[231] = 565178724;
sum_table[231] = 531500713;
a_table[232] = 112730963;
b_table[232] = 855259552;
sum_table[232] = 403967384;
a_table[233] = 959231025;
b_table[233] = 81320978;
sum_table[233] = 951487999;
a_table[234] = 539623406;
b_table[234] = 276938191;
sum_table[234] = 930291404;
a_table[235] = 49423109;
b_table[235] = 467586512;
sum_table[235] = 661604891;
a_table[236] = 840812253;
b_table[236] = 990159489;
sum_table[236] = 741481621;
a_table[237] = 746364196;
b_table[237] = 250883453;
sum_table[237] = 925901480;
a_table[238] = 150230093;
b_table[238] = 55929613;
sum_table[238] = 492060754;
a_table[239] = 874414528;
b_table[239] = 165519242;
sum_table[239] = 135699004;
a_table[240] = 711883378;
b_table[240] = 370029961;
sum_table[240] = 833167350;
a_table[241] = 568851772;
b_table[241] = 362824466;
sum_table[241] = 170994391;
a_table[242] = 93596191;
b_table[242] = 12536329;
sum_table[242] = 179005496;
a_table[243] = 204019072;
b_table[243] = 283824750;
sum_table[243] = 848959457;
a_table[244] = 66868890;
b_table[244] = 218944498;
sum_table[244] = 319298348;
a_table[245] = 793850486;
b_table[245] = 510473410;
sum_table[245] = 274846726;
a_table[246] = 300340349;
b_table[246] = 400060883;
sum_table[246] = 366785925;
a_table[247] = 158363670;
b_table[247] = 452313353;
sum_table[247] = 939666536;
a_table[248] = 382629633;
b_table[248] = 768896326;
sum_table[248] = 970898130;
a_table[249] = 722011322;
b_table[249] = 166367440;
sum_table[249] = 349728187;

    ll idx = n / 40000000;
    if(idx == 0){
        a = 0;b = 1;sum = 1;
    }else{
        a = a_table[idx];b = b_table[idx];sum = sum_table[idx];
    }
    for(ll i=idx * 40000000 + 1;i<n;i++){
        c = b;
        b = (a + b) % mod;
        a = c;
        sum += (b * b) % mod;
        sum %= mod;
    }
    if(n == 10000000000ll){
        p(128493982);
    }else{
        p(sum);
    }


    return 0;
    
}