API tools faq
paste
Advertisement
Guest User

problem

a guest
May 6th, 2020
272
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 38.68 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef unsigned long long ull;
  5.  
  6. const ull M = 1099511627776;
  7.  
  8. ull savePC[668];
  9. pair<ull, ull> PCA[668];
  10.  
  11. ull saveC[334];
  12. pair<ull, ull> CA[334];
  13.  
  14. void setup(){
  15.     PCA[0] = {1, 1611516670};
  16.     PCA[1] = {263604, 11068662391};
  17.     PCA[2] = {528898, 26670330982};
  18.     PCA[3] = {785681, 52408758781};
  19.     PCA[4] = {1046225, 94870028976};
  20.     PCA[5] = {1310639, 164919352981};
  21.     PCA[6] = {1572539, 280481317338};
  22.     PCA[7] = {1835514, 471126520589};
  23.     PCA[8] = {2098846, 785638252174};
  24.     PCA[9] = {2360543, 2385630144};
  25.     PCA[10] = {2626550, 12345734984};
  26.     PCA[11] = {2888861, 28777146674};
  27.     PCA[12] = {3151130, 55884420560};
  28.     PCA[13] = {3413301, 100603907439};
  29.     PCA[14] = {3672500, 174378662776};
  30.     PCA[15] = {3936051, 296086556099};
  31.     PCA[16] = {4199987, 496870838270};
  32.     PCA[17] = {4462747, 828109238860};
  33.     PCA[18] = {4724584, 3201004330};
  34.     PCA[19] = {4991684, 13690876326};
  35.     PCA[20] = {5254825, 30996256975};
  36.     PCA[21] = {5524307, 59545337318};
  37.     PCA[22] = {5785824, 106643405080};
  38.     PCA[23] = {6048739, 184342159513};
  39.     PCA[24] = {6310671, 312523563448};
  40.     PCA[25] = {6573214, 523987343459};
  41.     PCA[26] = {6835704, 872843954681};
  42.     PCA[27] = {7096232, 4059725053};
  43.     PCA[28] = {7352741, 15107527338};
  44.     PCA[29] = {7611465, 33333338333};
  45.     PCA[30] = {7875504, 63400873535};
  46.     PCA[31] = {8137613, 113003971003};
  47.     PCA[32] = {8398631, 194835330044};
  48.     PCA[33] = {8660931, 329834385723};
  49.     PCA[34] = {8923698, 552545401303};
  50.     PCA[35] = {9186084, 919956833194};
  51.     PCA[36] = {9452641, 4963543754};
  52.     PCA[37] = {9717661, 16598577655};
  53.     PCA[38] = {9978217, 35793158007};
  54.     PCA[39] = {10240910, 67458894124};
  55.     PCA[40] = {10502645, 119698579876};
  56.     PCA[41] = {10764898, 205879578640};
  57.     PCA[42] = {11028879, 348054334032};
  58.     PCA[43] = {11291806, 582603264480};
  59.     PCA[44] = {11554349, 969543974143};
  60.     PCA[45] = {11814606, 5916818226};
  61.     PCA[46] = {12078412, 18171216320};
  62.     PCA[47] = {12338392, 38387575803};
  63.     PCA[48] = {12603838, 71738964329};
  64.     PCA[49] = {12866702, 126759508982};
  65.     PCA[50] = {13129636, 217528154202};
  66.     PCA[51] = {13391028, 367271254233};
  67.     PCA[52] = {13653700, 614305854948};
  68.     PCA[53] = {13915838, 1021844459240};
  69.     PCA[54] = {14176084, 6920141508};
  70.     PCA[55] = {14444241, 19826421617};
  71.     PCA[56] = {14706067, 41118205683};
  72.     PCA[57] = {14973238, 76243746545};
  73.     PCA[58] = {15236176, 134191150875};
  74.     PCA[59] = {15499763, 229788302870};
  75.     PCA[60] = {15762796, 387497100667};
  76.     PCA[61] = {16025508, 647672894217};
  77.     PCA[62] = {16288037, 1076890823561};
  78.     PCA[63] = {16551411, 7976495826};
  79.     PCA[64] = {16810898, 21569113268};
  80.     PCA[65] = {17075959, 43993163796};
  81.     PCA[66] = {17339621, 80986630295};
  82.     PCA[67] = {17603438, 142015594299};
  83.     PCA[68] = {17866100, 242696465153};
  84.     PCA[69] = {18127524, 408791990186};
  85.     PCA[70] = {18390042, 682803558601};
  86.     PCA[71] = {18653036, 411186361};
  87.     PCA[72] = {18916637, 9088450136};
  88.     PCA[73] = {19177041, 23403529691};
  89.     PCA[74] = {19437711, 47019442289};
  90.     PCA[75] = {19700518, 85979150964};
  91.     PCA[76] = {19958654, 150251869089};
  92.     PCA[77] = {20221283, 256284035296};
  93.     PCA[78] = {20485064, 431207713516};
  94.     PCA[79] = {20748866, 719783287160};
  95.     PCA[80] = {21012238, 1121374168};
  96.     PCA[81] = {21276153, 10260063022};
  97.     PCA[82] = {21543815, 25336366126};
  98.     PCA[83] = {21812826, 50208086540};
  99.     PCA[84] = {22075604, 91239529765};
  100.     PCA[85] = {22338176, 158930035668};
  101.     PCA[86] = {22601522, 270600604366};
  102.     PCA[87] = {22865035, 454826083387};
  103.     PCA[88] = {23128625, 758747050280};
  104.     PCA[89] = {23394341, 1869884447};
  105.     PCA[90] = {23658326, 11494897482};
  106.     PCA[91] = {23918411, 27373500610};
  107.     PCA[92] = {24179846, 53568793640};
  108.     PCA[93] = {24438989, 96783764840};
  109.     PCA[94] = {24701518, 168076486389};
  110.     PCA[95] = {24964321, 285689712229};
  111.     PCA[96] = {25229390, 479718927928};
  112.     PCA[97] = {25492196, 799813342377};
  113.     PCA[98] = {25756418, 2658122688};
  114.     PCA[99] = {26019504, 12795272150};
  115.     PCA[100] = {26286634, 29518758251};
  116.     PCA[101] = {26549009, 57107874130};
  117.     PCA[102] = {26809617, 102622266600};
  118.     PCA[103] = {27072576, 177708395908};
  119.     PCA[104] = {27334469, 301579692619};
  120.     PCA[105] = {27597893, 505932990419};
  121.     PCA[106] = {27860462, 843059277723};
  122.     PCA[107] = {28121755, 3488151422};
  123.     PCA[108] = {28387245, 14164589341};
  124.     PCA[109] = {28651287, 31777752141};
  125.     PCA[110] = {28913766, 60834587634};
  126.     PCA[111] = {29172779, 108770310602};
  127.     PCA[112] = {29435645, 187850964031};
  128.     PCA[113] = {29699423, 318312118053};
  129.     PCA[114] = {29961835, 533536853694};
  130.     PCA[115] = {30223792, 888597999748};
  131.     PCA[116] = {30486176, 4362692672};
  132.     PCA[117] = {30746952, 15607339977};
  133.     PCA[118] = {31007577, 34157890573};
  134.     PCA[119] = {31269866, 64761156241};
  135.     PCA[120] = {31534864, 115248060275};
  136.     PCA[121] = {31795613, 198537455159};
  137.     PCA[122] = {32057992, 335941865835};
  138.     PCA[123] = {32321131, 562621049842};
  139.     PCA[124] = {32584097, 936578860195};
  140.     PCA[125] = {32846552, 5283487095};
  141.     PCA[126] = {33113000, 17126395494};
  142.     PCA[127] = {33377709, 36663911086};
  143.     PCA[128] = {33637637, 68895395297};
  144.     PCA[129] = {33901187, 122068408494};
  145.     PCA[130] = {34162912, 209789138710};
  146.     PCA[131] = {34425910, 354504024121};
  147.     PCA[132] = {34690134, 593243465073};
  148.     PCA[133] = {34952438, 987097355478};
  149.     PCA[134] = {35214208, 6253397206};
  150.     PCA[135] = {35478110, 18726478304};
  151.     PCA[136] = {35736871, 39303604026};
  152.     PCA[137] = {35996716, 73250156824};
  153.     PCA[138] = {36258571, 129252557614};
  154.     PCA[139] = {36521619, 221640993186};
  155.     PCA[140] = {36785514, 374056298317};
  156.     PCA[141] = {37048123, 625499296752};
  157.     PCA[142] = {37310927, 1040310535551};
  158.     PCA[143] = {37572068, 7274827284};
  159.     PCA[144] = {37835804, 20411554724};
  160.     PCA[145] = {38093485, 42083513030};
  161.     PCA[146] = {38357326, 77836235961};
  162.     PCA[147] = {38620919, 136818316936};
  163.     PCA[148] = {38884440, 234122398393};
  164.     PCA[149] = {39146703, 394647156768};
  165.     PCA[150] = {39408539, 659468504882};
  166.     PCA[151] = {39670966, 1096350310860};
  167.     PCA[152] = {39936030, 8351096190};
  168.     PCA[153] = {40200004, 22187100147};
  169.     PCA[154] = {40467213, 45012670777};
  170.     PCA[155] = {40727553, 82668534236};
  171.     PCA[156] = {40987124, 144790269499};
  172.     PCA[157] = {41252012, 247273910128};
  173.     PCA[158] = {41515326, 416343504953};
  174.     PCA[159] = {41778076, 695261464172};
  175.     PCA[160] = {42041470, 650835677};
  176.     PCA[161] = {42300196, 9483805041};
  177.     PCA[162] = {42564863, 24055755656};
  178.     PCA[163] = {42828864, 48095434320};
  179.     PCA[164] = {43093181, 87754239454};
  180.     PCA[165] = {43357956, 153180273190};
  181.     PCA[166] = {43619477, 261115090224};
  182.     PCA[167] = {43881766, 439177614821};
  183.     PCA[168] = {44146670, 732931415188};
  184.     PCA[169] = {44412513, 1373685404};
  185.     PCA[170] = {44674665, 10676306644};
  186.     PCA[171] = {44936360, 26023052691};
  187.     PCA[172] = {45197460, 51340928946};
  188.     PCA[173] = {45461832, 93108405721};
  189.     PCA[174] = {45722456, 162013162845};
  190.     PCA[175] = {45983741, 275686909361};
  191.     PCA[176] = {46245526, 463217076412};
  192.     PCA[177] = {46507889, 772589862381};
  193.     PCA[178] = {46772428, 2135552411};
  194.     PCA[179] = {47032433, 11933175968};
  195.     PCA[180] = {47293526, 28096538614};
  196.     PCA[181] = {47554392, 54761605921};
  197.     PCA[182] = {47817190, 98751574401};
  198.     PCA[183] = {48076589, 171322826839};
  199.     PCA[184] = {48338814, 291045273887};
  200.     PCA[185] = {48599630, 488554120087};
  201.     PCA[186] = {48864028, 814388960315};
  202.     PCA[187] = {49128843, 2938002576};
  203.     PCA[188] = {49393077, 13256996277};
  204.     PCA[189] = {49656672, 30280475092};
  205.     PCA[190] = {49924062, 58364495626};
  206.     PCA[191] = {50188173, 104695343644};
  207.     PCA[192] = {50450380, 181128398221};
  208.     PCA[193] = {50712296, 307221748278};
  209.     PCA[194] = {50975087, 515240818221};
  210.     PCA[195] = {51239097, 858414613424};
  211.     PCA[196] = {51498483, 3783017332};
  212.     PCA[197] = {51761903, 14651036352};
  213.     PCA[198] = {52025419, 32580254772};
  214.     PCA[199] = {52293009, 62158494507};
  215.     PCA[200] = {52558293, 110954389972};
  216.     PCA[201] = {52820625, 191454089471};
  217.     PCA[202] = {53081633, 324256276225};
  218.     PCA[203] = {53344827, 543343066807};
  219.     PCA[204] = {53607229, 904775532293};
  220.     PCA[205] = {53870033, 4673441109};
  221.     PCA[206] = {54126287, 16119988694};
  222.     PCA[207] = {54385947, 35003618877};
  223.     PCA[208] = {54648142, 66156373411};
  224.     PCA[209] = {54909488, 117549781816};
  225.     PCA[210] = {55173688, 202334657639};
  226.     PCA[211] = {55436499, 342206197181};
  227.     PCA[212] = {55698965, 572955460344};
  228.     PCA[213] = {55961011, 953627772167};
  229.     PCA[214] = {56218206, 5609885385};
  230.     PCA[215] = {56482558, 17664862263};
  231.     PCA[216] = {56751429, 37552232000};
  232.     PCA[217] = {57014715, 70360878641};
  233.     PCA[218] = {57277934, 124486049805};
  234.     PCA[219] = {57538849, 213777576713};
  235.     PCA[220] = {57802141, 361083841287};
  236.     PCA[221] = {58065228, 604098339043};
  237.     PCA[222] = {58328816, 1005004888159};
  238.     PCA[223] = {58590778, 6596379902};
  239.     PCA[224] = {58853347, 19292304658};
  240.     PCA[225] = {59114981, 40237060802};
  241.     PCA[226] = {59377294, 74790101796};
  242.     PCA[227] = {59641182, 131793040162};
  243.     PCA[228] = {59902490, 225832085017};
  244.     PCA[229] = {60161398, 380970438283};
  245.     PCA[230] = {60425435, 636905710900};
  246.     PCA[231] = {60687817, 1059127956322};
  247.     PCA[232] = {60951891, 7635157016};
  248.     PCA[233] = {61215592, 21005998959};
  249.     PCA[234] = {61475023, 43064181289};
  250.     PCA[235] = {61736819, 79454066797};
  251.     PCA[236] = {61997301, 139487289267};
  252.     PCA[237] = {62257783, 238525462994};
  253.     PCA[238] = {62521100, 401910992447};
  254.     PCA[239] = {62781198, 671451819823};
  255.     PCA[240] = {63044408, 193751266};
  256.     PCA[241] = {63309716, 8729742480};
  257.     PCA[242] = {63575599, 22811761497};
  258.     PCA[243] = {63837390, 46043188895};
  259.     PCA[244] = {64099691, 84368603504};
  260.     PCA[245] = {64362513, 147594912409};
  261.     PCA[246] = {64625673, 251900793457};
  262.     PCA[247] = {64890300, 423976580015};
  263.     PCA[248] = {65153431, 707853921635};
  264.     PCA[249] = {65416503, 892233849};
  265.     PCA[250] = {65681433, 9882045041};
  266.     PCA[251] = {65944066, 24712741275};
  267.     PCA[252] = {66211578, 49179278440};
  268.     PCA[253] = {66475246, 89542281617};
  269.     PCA[254] = {66737703, 156130046809};
  270.     PCA[255] = {67001038, 265981398848};
  271.     PCA[256] = {67264963, 447205674888};
  272.     PCA[257] = {67527849, 746175488868};
  273.     PCA[258] = {67788574, 1628607872};
  274.     PCA[259] = {68055176, 11096858010};
  275.     PCA[260] = {68315776, 26716845856};
  276.     PCA[261] = {68579488, 52485495307};
  277.     PCA[262] = {68841904, 94996622889};
  278.     PCA[263] = {69102963, 165128197786};
  279.     PCA[264] = {69367240, 280825853639};
  280.     PCA[265] = {69631435, 471694909987};
  281.     PCA[266] = {69893485, 786575937185};
  282.     PCA[267] = {70154481, 2404254632};
  283.     PCA[268] = {70414509, 12376460175};
  284.     PCA[269] = {70675563, 28827834628};
  285.     PCA[270] = {70937464, 55968041629};
  286.     PCA[271] = {71200888, 100741858960};
  287.     PCA[272] = {71460169, 174606244670};
  288.     PCA[273] = {71722016, 296462003220};
  289.     PCA[274] = {71984621, 497490221818};
  290.     PCA[275] = {72248088, 829131050287};
  291.     PCA[276] = {72513497, 3220831399};
  292.     PCA[277] = {72773321, 13723585544};
  293.     PCA[278] = {73038353, 31050218071};
  294.     PCA[279] = {73302294, 59634358188};
  295.     PCA[280] = {73566108, 106790264807};
  296.     PCA[281] = {73827972, 184584437341};
  297.     PCA[282] = {74090823, 312923254733};
  298.     PCA[283] = {74351267, 524646723310};
  299.     PCA[284] = {74614458, 873931748703};
  300.     PCA[285] = {74874705, 4080491859};
  301.     PCA[286] = {75136698, 15141786825};
  302.     PCA[287] = {75405024, 33389857019};
  303.     PCA[288] = {75668298, 63494113712};
  304.     PCA[289] = {75933190, 113157791263};
  305.     PCA[290] = {76193986, 195089090779};
  306.     PCA[291] = {76457601, 330253020719};
  307.     PCA[292] = {76719618, 553236032855};
  308.     PCA[293] = {76982676, 921096183560};
  309.     PCA[294] = {77245697, 4986638655};
  310.     PCA[295] = {77513535, 16636677964};
  311.     PCA[296] = {77772852, 35856012937};
  312.     PCA[297] = {78035079, 67562587436};
  313.     PCA[298] = {78297657, 119869645020};
  314.     PCA[299] = {78564345, 206161788690};
  315.     PCA[300] = {78827441, 348519902328};
  316.     PCA[301] = {79090204, 583371323086};
  317.     PCA[302] = {79352680, 970811058028};
  318.     PCA[303] = {79614661, 5940293258};
  319.     PCA[304] = {79878160, 18209943569};
  320.     PCA[305] = {80140054, 38451465109};
  321.     PCA[306] = {80402851, 71844363791};
  322.     PCA[307] = {80666562, 126933388895};
  323.     PCA[308] = {80927061, 217815007750};
  324.     PCA[309] = {81187605, 367744482996};
  325.     PCA[310] = {81448159, 615086551783};
  326.     PCA[311] = {81710659, 1023132392802};
  327.     PCA[312] = {81970494, 6945320931};
  328.     PCA[313] = {82231427, 19867960622};
  329.     PCA[314] = {82493020, 41186733399};
  330.     PCA[315] = {82750675, 76356798265};
  331.     PCA[316] = {83014146, 134377654791};
  332.     PCA[317] = {83275055, 230095982774};
  333.     PCA[318] = {83537692, 388004687131};
  334.     PCA[319] = {83800868, 648510271390};
  335.     PCA[320] = {84062612, 1078272264090};
  336.     PCA[321] = {84322823, 8003524247};
  337.     PCA[322] = {84589786, 21613702741};
  338.     PCA[323] = {84851750, 44066724037};
  339.     PCA[324] = {85113884, 81107984304};
  340.     PCA[325] = {85377973, 142215794600};
  341.     PCA[326] = {85640337, 243026740310};
  342.     PCA[327] = {85904469, 409336852193};
  343.     PCA[328] = {86165550, 683702430000};
  344.     PCA[329] = {86426915, 429344282};
  345.     PCA[330] = {86689141, 9118405595};
  346.     PCA[331] = {86946044, 23452947849};
  347.     PCA[332] = {87209545, 47100968526};
  348.     PCA[333] = {87471824, 86113646529};
  349.     PCA[334] = {87732265, 150473749615};
  350.     PCA[335] = {87993071, 256650076592};
  351.     PCA[336] = {88254126, 431811580433};
  352.     PCA[337] = {88515137, 720779500446};
  353.     PCA[338] = {88778467, 1140123196};
  354.     PCA[339] = {89034766, 10290993795};
  355.     PCA[340] = {89300531, 25387393262};
  356.     PCA[341] = {89557558, 50292267222};
  357.     PCA[342] = {89819704, 91378404740};
  358.     PCA[343] = {90084284, 159159140992};
  359.     PCA[344] = {90346858, 270978564551};
  360.     PCA[345] = {90608448, 455449612887};
  361.     PCA[346] = {90869521, 759775700584};
  362.     PCA[347] = {91131284, 1889394524};
  363.     PCA[348] = {91394986, 11527083700};
  364.     PCA[349] = {91655247, 27426598965};
  365.     PCA[350] = {91919716, 53656391261};
  366.     PCA[351] = {92183470, 96928276607};
  367.     PCA[352] = {92443440, 168314890858};
  368.     PCA[353] = {92704383, 286083013614};
  369.     PCA[354] = {92966155, 480367766405};
  370.     PCA[355] = {93228520, 800883746198};
  371.     PCA[356] = {93493732, 2678758574};
  372.     PCA[357] = {93761280, 12829315650};
  373.     PCA[358] = {94027987, 29574920622};
  374.     PCA[359] = {94292226, 57200526466};
  375.     PCA[360] = {94555191, 102775117172};
  376.     PCA[361] = {94816941, 177960556858};
  377.     PCA[362] = {95078498, 301995688445};
  378.     PCA[363] = {95341857, 506619268241};
  379.     PCA[364] = {95604274, 844191445747};
  380.     PCA[365] = {95869971, 3509822286};
  381.     PCA[366] = {96133147, 14200340272};
  382.     PCA[367] = {96399661, 31836731229};
  383.     PCA[368] = {96666839, 60931886769};
  384.     PCA[369] = {96931620, 108930827152};
  385.     PCA[370] = {97194251, 188115771788};
  386.     PCA[371] = {97455697, 318748977462};
  387.     PCA[372] = {97718442, 534257550560};
  388.     PCA[373] = {97982218, 889786949775};
  389.     PCA[374] = {98246500, 4385442712};
  390.     PCA[375] = {98506511, 15644871212};
  391.     PCA[376] = {98769682, 34219806785};
  392.     PCA[377] = {99036567, 64863300840};
  393.     PCA[378] = {99300196, 115416570645};
  394.     PCA[379] = {99561371, 198815450443};
  395.     PCA[380] = {99824319, 336400481016};
  396.     PCA[381] = {100087416, 563377638120};
  397.     PCA[382] = {100349811, 937827020825};
  398.     PCA[383] = {100611169, 5306654175};
  399.     PCA[384] = {100869236, 17164614766};
  400.     PCA[385] = {101128028, 36726962232};
  401.     PCA[386] = {101393261, 68999412247};
  402.     PCA[387] = {101653314, 122240007696};
  403.     PCA[388] = {101913523, 210072230102};
  404.     PCA[389] = {102175844, 354971046537};
  405.     PCA[390] = {102438376, 594013922396};
  406.     PCA[391] = {102701460, 988368396323};
  407.     PCA[392] = {102967989, 6277613479};
  408.     PCA[393] = {103229821, 18766428445};
  409.     PCA[394] = {103492965, 39369510804};
  410.     PCA[395] = {103754738, 73358884825};
  411.     PCA[396] = {104014276, 129431928700};
  412.     PCA[397] = {104276652, 221936905893};
  413.     PCA[398] = {104539121, 374544472272};
  414.     PCA[399] = {104802653, 626304648388};
  415.     PCA[400] = {105065564, 1041639141932};
  416.     PCA[401] = {105322681, 7300121720};
  417.     PCA[402] = {105586261, 20453283524};
  418.     PCA[403] = {105851139, 42152353962};
  419.     PCA[404] = {106110898, 77949804341};
  420.     PCA[405] = {106376184, 137005673265};
  421.     PCA[406] = {106638246, 234431484432};
  422.     PCA[407] = {106901895, 395157063076};
  423.     PCA[408] = {107160752, 660309708914};
  424.     PCA[409] = {107423158, 1097738064411};
  425.     PCA[410] = {107691295, 8377692234};
  426.     PCA[411] = {107955898, 22230976246};
  427.     PCA[412] = {108222606, 45085054150};
  428.     PCA[413] = {108487756, 82787946767};
  429.     PCA[414] = {108749934, 144987267021};
  430.     PCA[415] = {109009672, 247598901440};
  431.     PCA[416] = {109271999, 416879650600};
  432.     PCA[417] = {109536741, 696145955847};
  433.     PCA[418] = {109799958, 667562189};
  434.     PCA[419] = {110053277, 9511399153};
  435.     PCA[420] = {110316454, 24101278284};
  436.     PCA[421] = {110581481, 48170534023};
  437.     PCA[422] = {110845187, 87878133149};
  438.     PCA[423] = {111106044, 153384663226};
  439.     PCA[424] = {111366562, 261452277112};
  440.     PCA[425] = {111628962, 439733879533};
  441.     PCA[426] = {111891247, 733849097452};
  442.     PCA[427] = {112152819, 1391666547};
  443.     PCA[428] = {112413444, 10705970532};
  444.     PCA[429] = {112674021, 26071989869};
  445.     PCA[430] = {112933905, 51421661780};
  446.     PCA[431] = {113197426, 93241592502};
  447.     PCA[432] = {113462288, 162232884155};
  448.     PCA[433] = {113725238, 276049388656};
  449.     PCA[434] = {113987631, 463815066908};
  450.     PCA[435] = {114249841, 773576381090};
  451.     PCA[436] = {114510655, 2154534674};
  452.     PCA[437] = {114772152, 11964491443};
  453.     PCA[438] = {115031183, 28148200522};
  454.     PCA[439] = {115290367, 54846833729};
  455.     PCA[440] = {115552843, 98892176686};
  456.     PCA[441] = {115817299, 171554781645};
  457.     PCA[442] = {116078679, 291427935068};
  458.     PCA[443] = {116341207, 489185404951};
  459.     PCA[444] = {116605455, 815430404968};
  460.     PCA[445] = {116871604, 2958143522};
  461.     PCA[446] = {117138696, 13290223360};
  462.     PCA[447] = {117402729, 30335290526};
  463.     PCA[448] = {117669157, 58454926012};
  464.     PCA[449] = {117932153, 104844528746};
  465.     PCA[450] = {118195660, 181374512327};
  466.     PCA[451] = {118458707, 307627768325};
  467.     PCA[452] = {118720956, 515910638566};
  468.     PCA[453] = {118984917, 859519630941};
  469.     PCA[454] = {119251603, 3804114088};
  470.     PCA[455] = {119514413, 14685840172};
  471.     PCA[456] = {119775578, 32637671395};
  472.     PCA[457] = {120035370, 62253216031};
  473.     PCA[458] = {120298274, 111110654211};
  474.     PCA[459] = {120560318, 191711882242};
  475.     PCA[460] = {120824404, 324681562787};
  476.     PCA[461] = {121085323, 544044671572};
  477.     PCA[462] = {121348380, 905932985987};
  478.     PCA[463] = {121613758, 4695176003};
  479.     PCA[464] = {121879272, 16155845265};
  480.     PCA[465] = {122141946, 35062772335};
  481.     PCA[466] = {122408791, 66253960167};
  482.     PCA[467] = {122674170, 117710772836};
  483.     PCA[468] = {122936402, 202600248123};
  484.     PCA[469] = {123200727, 342644347973};
  485.     PCA[470] = {123462097, 573678287492};
  486.     PCA[471] = {123724205, 954820236367};
  487.     PCA[472] = {123983228, 5634033406};
  488.     PCA[473] = {124247155, 17704699699};
  489.     PCA[474] = {124511170, 37617952694};
  490.     PCA[475] = {124771503, 70469299429};
  491.     PCA[476] = {125032161, 124664914113};
  492.     PCA[477] = {125295517, 214072653154};
  493.     PCA[478] = {125556920, 361570635875};
  494.     PCA[479] = {125818608, 604901415364};
  495.     PCA[480] = {126080241, 1006329741386};
  496.     PCA[481] = {126345973, 6621538013};
  497.     PCA[482] = {126608420, 19333808668};
  498.     PCA[483] = {126867764, 40305530833};
  499.     PCA[484] = {127129183, 74903058405};
  500.     PCA[485] = {127392900, 131979387094};
  501.     PCA[486] = {127655587, 226139505691};
  502.     PCA[487] = {127916586, 381477596975};
  503.     PCA[488] = {128180815, 637742382058};
  504.     PCA[489] = {128443701, 1060508231800};
  505.     PCA[490] = {128704419, 7661913974};
  506.     PCA[491] = {128968016, 21050140458};
  507.     PCA[492] = {129234461, 43137002443};
  508.     PCA[493] = {129499435, 79574201403};
  509.     PCA[494] = {129761621, 139685477980};
  510.     PCA[495] = {130022804, 238852419302};
  511.     PCA[496] = {130286478, 402450379961};
  512.     PCA[497] = {130552145, 672341659870};
  513.     PCA[498] = {130814998, 211318899};
  514.     PCA[499] = {131071294, 8758724236};
  515.     PCA[500] = {131329885, 22859573424};
  516.     PCA[501] = {131592602, 46122065296};
  517.     PCA[502] = {131857087, 84498727606};
  518.     PCA[503] = {132123220, 147809580975};
  519.     PCA[504] = {132387316, 252254937042};
  520.     PCA[505] = {132649834, 424560818401};
  521.     PCA[506] = {132911269, 708817753162};
  522.     PCA[507] = {133172995, 910949763};
  523.     PCA[508] = {133439983, 9912921184};
  524.     PCA[509] = {133709143, 24763678335};
  525.     PCA[510] = {133966200, 49263310450};
  526.     PCA[511] = {134229948, 89680911320};
  527.     PCA[512] = {134493192, 156358747627};
  528.     PCA[513] = {134757300, 266358691867};
  529.     PCA[514] = {135020035, 447828103869};
  530.     PCA[515] = {135281768, 747202323837};
  531.     PCA[516] = {135543951, 1647629004};
  532.     PCA[517] = {135805044, 11128237640};
  533.     PCA[518] = {136063453, 26768613487};
  534.     PCA[519] = {136324080, 52570897568};
  535.     PCA[520] = {136586062, 95137512983};
  536.     PCA[521] = {136848802, 165360627312};
  537.     PCA[522] = {137110824, 281209297666};
  538.     PCA[523] = {137374177, 472327486246};
  539.     PCA[524] = {137635477, 787619512744};
  540.     PCA[525] = {137896458, 2423995016};
  541.     PCA[526] = {138161422, 12409026438};
  542.     PCA[527] = {138425845, 28881560036};
  543.     PCA[528] = {138694303, 56056673674};
  544.     PCA[529] = {138959780, 100888077188};
  545.     PCA[530] = {139218536, 174847464122};
  546.     PCA[531] = {139479020, 296859948323};
  547.     PCA[532] = {139740998, 498146721027};
  548.     PCA[533] = {140003495, 830214091870};
  549.     PCA[534] = {140271275, 3241318615};
  550.     PCA[535] = {140533491, 13757383745};
  551.     PCA[536] = {140795058, 31105975764};
  552.     PCA[537] = {141056728, 59726342929};
  553.     PCA[538] = {141322290, 106942014157};
  554.     PCA[539] = {141583965, 184834781753};
  555.     PCA[540] = {141845772, 313336253597};
  556.     PCA[541] = {142110263, 525328056940};
  557.     PCA[542] = {142371295, 875055760194};
  558.     PCA[543] = {142629536, 4102215739};
  559.     PCA[544] = {142887544, 15177625202};
  560.     PCA[545] = {143149404, 33448980365};
  561.     PCA[546] = {143415943, 63591650826};
  562.     PCA[547] = {143681620, 113318700642};
  563.     PCA[548] = {143945334, 195354546675};
  564.     PCA[549] = {144207282, 330690949234};
  565.     PCA[550] = {144468010, 553958493649};
  566.     PCA[551] = {144731247, 922288043745};
  567.     PCA[552] = {144997645, 5008295520};
  568.     PCA[553] = {145261518, 16672405718};
  569.     PCA[554] = {145520501, 35914953846};
  570.     PCA[555] = {145781056, 67659823566};
  571.     PCA[556] = {146044662, 120030057802};
  572.     PCA[557] = {146308200, 206426425335};
  573.     PCA[558] = {146569749, 348956479589};
  574.     PCA[559] = {146830499, 584091554731};
  575.     PCA[560] = {147093654, 971999240550};
  576.     PCA[561] = {147355373, 5962658099};
  577.     PCA[562] = {147620655, 18246839355};
  578.     PCA[563] = {147885520, 38512332821};
  579.     PCA[564] = {148146358, 71944778579};
  580.     PCA[565] = {148409428, 127099045529};
  581.     PCA[566] = {148673568, 218088295224};
  582.     PCA[567] = {148937639, 368195331777};
  583.     PCA[568] = {149198579, 615830327087};
  584.     PCA[569] = {149461160, 1024359415865};
  585.     PCA[570] = {149729640, 6969024455};
  586.     PCA[571] = {149986387, 19907064868};
  587.     PCA[572] = {150247621, 41251244661};
  588.     PCA[573] = {150511255, 76463224001};
  589.     PCA[574] = {150774850, 134553227730};
  590.     PCA[575] = {151038170, 230385629435};
  591.     PCA[576] = {151300313, 388482523790};
  592.     PCA[577] = {151560982, 649298569208};
  593.     PCA[578] = {151822775, 1079572736637};
  594.     PCA[579] = {152080957, 8028339217};
  595.     PCA[580] = {152342225, 21654640644};
  596.     PCA[581] = {152605233, 44134260168};
  597.     PCA[582] = {152869193, 81219400316};
  598.     PCA[583] = {153132858, 142399600125};
  599.     PCA[584] = {153394898, 243329968385};
  600.     PCA[585] = {153657474, 409837094582};
  601.     PCA[586] = {153921651, 684527690820};
  602.     PCA[587] = {154185285, 444567713};
  603.     PCA[588] = {154446238, 9143520042};
  604.     PCA[589] = {154707698, 23494379728};
  605.     PCA[590] = {154971679, 47169319582};
  606.     PCA[591] = {155232140, 86226406808};
  607.     PCA[592] = {155493102, 150659772701};
  608.     PCA[593] = {155756522, 256956963124};
  609.     PCA[594] = {156020284, 432317858105};
  610.     PCA[595] = {156280236, 721614718376};
  611.     PCA[596] = {156542451, 1157234840};
  612.     PCA[597] = {156803507, 10319223202};
  613.     PCA[598] = {157062237, 25433964002};
  614.     PCA[599] = {157323397, 50369096018};
  615.     PCA[600] = {157587243, 91505150782};
  616.     PCA[601] = {157848570, 159368236705};
  617.     PCA[602] = {158112764, 271323514589};
  618.     PCA[603] = {158373364, 456018684902};
  619.     PCA[604] = {158634684, 760714512142};
  620.     PCA[605] = {158899020, 1907643109};
  621.     PCA[606] = {159159740, 11557188821};
  622.     PCA[607] = {159424196, 27476264058};
  623.     PCA[608] = {159685443, 53738324808};
  624.     PCA[609] = {159947711, 97063444296};
  625.     PCA[610] = {160208821, 168537880145};
  626.     PCA[611] = {160468541, 286450884062};
  627.     PCA[612] = {160732685, 480974650683};
  628.     PCA[613] = {160994921, 801884936720};
  629.     PCA[614] = {161255338, 2698220755};
  630.     PCA[615] = {161524488, 12861422747};
  631.     PCA[616] = {161786641, 29627888455};
  632.     PCA[617] = {162046635, 57287908591};
  633.     PCA[618] = {162307989, 102919273480};
  634.     PCA[619] = {162570141, 178198374952};
  635.     PCA[620] = {162831181, 302388022105};
  636.     PCA[621] = {163094987, 507266510045};
  637.     PCA[622] = {163356913, 845259215570};
  638.     PCA[623] = {163619744, 3530910747};
  639.     PCA[624] = {163884397, 14235130379};
  640.     PCA[625] = {164148588, 31894125306};
  641.     PCA[626] = {164410306, 61026571089};
  642.     PCA[627] = {164673644, 109087030095};
  643.     PCA[628] = {164935117, 188373463389};
  644.     PCA[629] = {165197737, 319174097108};
  645.     PCA[630] = {165459596, 534958880126};
  646.     PCA[631] = {165720620, 890943949044};
  647.     PCA[632] = {165981971, 4407743139};
  648.     PCA[633] = {166240528, 15681660807};
  649.     PCA[634] = {166505520, 34280499327};
  650.     PCA[635] = {166767094, 64963426767};
  651.     PCA[636] = {167030038, 115581750573};
  652.     PCA[637] = {167293433, 199087951725};
  653.     PCA[638] = {167556569, 336850032501};
  654.     PCA[639] = {167817600, 564119272933};
  655.     PCA[640] = {168080722, 939050512587};
  656.     PCA[641] = {168346196, 5330856034};
  657.     PCA[642] = {168605013, 17204541165};
  658.     PCA[643] = {168866074, 36792829749};
  659.     PCA[644] = {169126031, 69108075507};
  660.     PCA[645] = {169391591, 122419271980};
  661.     PCA[646] = {169653614, 210367966267};
  662.     PCA[647] = {169914192, 355458929612};
  663.     PCA[648] = {170176998, 594818794228};
  664.     PCA[649] = {170440214, 989696211794};
  665.     PCA[650] = {170701902, 6302433299};
  666.     PCA[651] = {170965265, 18807374224};
  667.     PCA[652] = {171225327, 39437059939};
  668.     PCA[653] = {171487693, 73470322145};
  669.     PCA[654] = {171751304, 129615769512};
  670.     PCA[655] = {172013214, 222240192288};
  671.     PCA[656] = {172275661, 375044810750};
  672.     PCA[657] = {172537571, 627130068242};
  673.     PCA[658] = {172799542, 1043000856241};
  674.     PCA[659] = {173053456, 7326400893};
  675.     PCA[660] = {173316135, 20496636958};
  676.     PCA[661] = {173577723, 42223875254};
  677.     PCA[662] = {173837450, 78067794804};
  678.     PCA[663] = {174098799, 137200324870};
  679.     PCA[664] = {174359559, 234752605749};
  680.     PCA[665] = {174621942, 395686824215};
  681.     PCA[666] = {174885970, 661183667650};
  682.     PCA[667] = {175147760, 1099179854628};
  683.     CA[0] = {1, 516914};
  684.     CA[1] = {270365, 8863927488};
  685.     CA[2] = {541323, 23796251957};
  686.     CA[3] = {809725, 48952969319};
  687.     CA[4] = {1082943, 91334878888};
  688.     CA[5] = {1356437, 162736335754};
  689.     CA[6] = {1628675, 283027471039};
  690.     CA[7] = {1902147, 485683801721};
  691.     CA[8] = {2175869, 827102047303};
  692.     CA[9] = {2447164, 3523104215};
  693.     CA[10] = {2723185, 14798484608};
  694.     CA[11] = {2995363, 33794291960};
  695.     CA[12] = {3269546, 65796821394};
  696.     CA[13] = {3543859, 119711976341};
  697.     CA[14] = {3818185, 210543669240};
  698.     CA[15] = {4092854, 363569223049};
  699.     CA[16] = {4365980, 621373733496};
  700.     CA[17] = {4638855, 1055700967498};
  701.     CA[18] = {4912460, 8005759214};
  702.     CA[19] = {5182295, 22350482651};
  703.     CA[20] = {5451291, 46517259392};
  704.     CA[21] = {5727278, 87231400943};
  705.     CA[22] = {6001571, 155823142884};
  706.     CA[23] = {6276303, 271380708405};
  707.     CA[24] = {6550099, 466062320787};
  708.     CA[25] = {6822113, 794045435861};
  709.     CA[26] = {7092333, 2876022256};
  710.     CA[27] = {7360915, 13708335774};
  711.     CA[28] = {7634832, 31957701290};
  712.     CA[29] = {7909128, 62702688931};
  713.     CA[30] = {8181852, 114499243654};
  714.     CA[31] = {8455733, 201761698227};
  715.     CA[32] = {8730602, 348774100931};
  716.     CA[33] = {9002149, 596448162607};
  717.     CA[34] = {9275852, 1013708473901};
  718.     CA[35] = {9550896, 7182035482};
  719.     CA[36] = {9826173, 20962742557};
  720.     CA[37] = {10101653, 44179312273};
  721.     CA[38] = {10375206, 83292625377};
  722.     CA[39] = {10649540, 149187427102};
  723.     CA[40] = {10923754, 260201415910};
  724.     CA[41] = {11197817, 447228394350};
  725.     CA[42] = {11472189, 762315629073};
  726.     CA[43] = {11748088, 2253844603};
  727.     CA[44] = {12019815, 12660143436};
  728.     CA[45] = {12289479, 30191795552};
  729.     CA[46] = {12562684, 59727640309};
  730.     CA[47] = {12834508, 109487133391};
  731.     CA[48] = {13107633, 193317718683};
  732.     CA[49] = {13384246, 334548398578};
  733.     CA[50] = {13658608, 572481902776};
  734.     CA[51] = {13932752, 973332146444};
  735.     CA[52] = {14203065, 6389917533};
  736.     CA[53] = {14480363, 19628249221};
  737.     CA[54] = {14750721, 41931070797};
  738.     CA[55] = {15026378, 79504978235};
  739.     CA[56] = {15300236, 142806319678};
  740.     CA[57] = {15576158, 249451065515};
  741.     CA[58] = {15850292, 429117113988};
  742.     CA[59] = {16125017, 731803276004};
  743.     CA[60] = {16400836, 1655061227};
  744.     CA[61] = {16672737, 11651363826};
  745.     CA[62] = {16945410, 28492288932};
  746.     CA[63] = {17216979, 56864455230};
  747.     CA[64] = {17488935, 104663481307};
  748.     CA[65] = {17762291, 185191237745};
  749.     CA[66] = {18034783, 320857590782};
  750.     CA[67] = {18307195, 549416787670};
  751.     CA[68] = {18580494, 934473991401};
  752.     CA[69] = {18854836, 5628813528};
  753.     CA[70] = {19128787, 18346005740};
  754.     CA[71] = {19405098, 39770855497};
  755.     CA[72] = {19676947, 75865630262};
  756.     CA[73] = {19951469, 136675053782};
  757.     CA[74] = {20224510, 239121627499};
  758.     CA[75] = {20497238, 411714949824};
  759.     CA[76] = {20771986, 702485581762};
  760.     CA[77] = {21045483, 1080727201};
  761.     CA[78] = {21320543, 10683774472};
  762.     CA[79] = {21593987, 26862176295};
  763.     CA[80] = {21866524, 54118179398};
  764.     CA[81] = {22136829, 100036788081};
  765.     CA[82] = {22410975, 177396576272};
  766.     CA[83] = {22682499, 307725804419};
  767.     CA[84] = {22957072, 527293464843};
  768.     CA[85] = {23230980, 897202488156};
  769.     CA[86] = {23505156, 4897544813};
  770.     CA[87] = {23774464, 17114025997};
  771.     CA[88] = {24049572, 37695320154};
  772.     CA[89] = {24323976, 72368943900};
  773.     CA[90] = {24594890, 130784132432};
  774.     CA[91] = {24867447, 229197101349};
  775.     CA[92] = {25138765, 394994947660};
  776.     CA[93] = {25413526, 674317135906};
  777.     CA[94] = {25685647, 528421634};
  778.     CA[95] = {25957950, 9753296735};
  779.     CA[96] = {26236585, 25294586053};
  780.     CA[97] = {26511430, 51477235831};
  781.     CA[98] = {26785857, 95587549642};
  782.     CA[99] = {27060058, 169900875380};
  783.     CA[100] = {27332979, 295097681455};
  784.     CA[101] = {27605894, 506018671087};
  785.     CA[102] = {27879483, 861360515374};
  786.     CA[103] = {28148850, 4195659722};
  787.     CA[104] = {28412196, 15931549417};
  788.     CA[105] = {28683022, 35703183688};
  789.     CA[106] = {28958165, 69012760892};
  790.     CA[107] = {29232649, 125129919059};
  791.     CA[108] = {29504645, 219671361080};
  792.     CA[109] = {29778380, 378946786003};
  793.     CA[110] = {30052912, 647280550786};
  794.     CA[111] = {30326918, 1099346582366};
  795.     CA[112] = {30601554, 8860563650};
  796.     CA[113] = {30875521, 23790584925};
  797.     CA[114] = {31151868, 48943421935};
  798.     CA[115] = {31425772, 91318794418};
  799.     CA[116] = {31698358, 162709238007};
  800.     CA[117] = {31972548, 282981818996};
  801.     CA[118] = {32246700, 485606891015};
  802.     CA[119] = {32521303, 826972474604};
  803.     CA[120] = {32795238, 3520898356};
  804.     CA[121] = {33070206, 14794768505};
  805.     CA[122] = {33345246, 33788031366};
  806.     CA[123] = {33611760, 65786274258};
  807.     CA[124] = {33884009, 119694207262};
  808.     CA[125] = {34157344, 210513733534};
  809.     CA[126] = {34431008, 363518789630};
  810.     CA[127] = {34702232, 621288767398};
  811.     CA[128] = {34975191, 1055557823965};
  812.     CA[129] = {35247905, 8002164773};
  813.     CA[130] = {35521774, 22344427036};
  814.     CA[131] = {35792931, 46507057483};
  815.     CA[132] = {36069718, 87214213479};
  816.     CA[133] = {36344072, 155794186967};
  817.     CA[134] = {36617568, 271331925943};
  818.     CA[135] = {36890081, 465980136392};
  819.     CA[136] = {37162151, 793906978649};
  820.     CA[137] = {37436299, 2873407334};
  821.     CA[138] = {37710157, 13703930332};
  822.     CA[139] = {37976174, 31950279409};
  823.     CA[140] = {38252362, 62690185144};
  824.     CA[141] = {38523288, 114478178282};
  825.     CA[142] = {38796768, 201726209055};
  826.     CA[143] = {39069680, 348714311781};
  827.     CA[144] = {39343513, 596347435237};
  828.     CA[145] = {39616529, 1013538777225};
  829.     CA[146] = {39885131, 7178163698};
  830.     CA[147] = {40164132, 20956219730};
  831.     CA[148] = {40439355, 44168323212};
  832.     CA[149] = {40713254, 83274111857};
  833.     CA[150] = {40989461, 149156237050};
  834.     CA[151] = {41263633, 260148869356};
  835.     CA[152] = {41536089, 447139868546};
  836.     CA[153] = {41808622, 762166488678};
  837.     CA[154] = {42084287, 2251241895};
  838.     CA[155] = {42361114, 12655758599};
  839.     CA[156] = {42636007, 30184408288};
  840.     CA[157] = {42911452, 59715194855};
  841.     CA[158] = {43179869, 109466166313};
  842.     CA[159] = {43453297, 193282395249};
  843.     CA[160] = {43725402, 334488888553};
  844.     CA[161] = {43999234, 572381645050};
  845.     CA[162] = {44272535, 973163240694};
  846.     CA[163] = {44546945, 6387247128};
  847.     CA[164] = {44816277, 19623750453};
  848.     CA[165] = {45089004, 41923491660};
  849.     CA[166] = {45363425, 79492209617};
  850.     CA[167] = {45636406, 142784808142};
  851.     CA[168] = {45910887, 249414824725};
  852.     CA[169] = {46185906, 429056058007};
  853.     CA[170] = {46460038, 731700414026};
  854.     CA[171] = {46735193, 1653238845};
  855.     CA[172] = {47005704, 11648293596};
  856.     CA[173] = {47274589, 28487116497};
  857.     CA[174] = {47551910, 56855741082};
  858.     CA[175] = {47824642, 104648800382};
  859.     CA[176] = {48099149, 185166504306};
  860.     CA[177] = {48373834, 320815921698};
  861.     CA[178] = {48646763, 549346587055};
  862.     CA[179] = {48919191, 934355723404};
  863.     CA[180] = {49200924, 5626639300};
  864.     CA[181] = {49466629, 18342342638};
  865.     CA[182] = {49741772, 39764684099};
  866.     CA[183] = {50016948, 75855233165};
  867.     CA[184] = {50289549, 136657537693};
  868.     CA[185] = {50562482, 239092118013};
  869.     CA[186] = {50839257, 411665234797};
  870.     CA[187] = {51115626, 702401825869};
  871.     CA[188] = {51390976, 1079352332};
  872.     CA[189] = {51664420, 10681458235};
  873.     CA[190] = {51939561, 26858274174};
  874.     CA[191] = {52209447, 54111605372};
  875.     CA[192] = {52483663, 100025712703};
  876.     CA[193] = {52759183, 177377917334};
  877.     CA[194] = {53032668, 307694369278};
  878.     CA[195] = {53304894, 527240505619};
  879.     CA[196] = {53578251, 897113266907};
  880.     CA[197] = {53852198, 4896089522};
  881.     CA[198] = {54117640, 17111574160};
  882.     CA[199] = {54385196, 37691189560};
  883.     CA[200] = {54657782, 72361984958};
  884.     CA[201] = {54931968, 130772408560};
  885.     CA[202] = {55205675, 229177350063};
  886.     CA[203] = {55480447, 394961672422};
  887.     CA[204] = {55755224, 674261077119};
  888.     CA[205] = {56027724, 527830397};
  889.     CA[206] = {56307018, 9752300645};
  890.     CA[207] = {56581701, 25292907900};
  891.     CA[208] = {56858655, 51474408654};
  892.     CA[209] = {57133875, 95582786621};
  893.     CA[210] = {57408475, 169892851022};
  894.     CA[211] = {57682288, 295084162652};
  895.     CA[212] = {57956631, 505995895617};
  896.     CA[213] = {58230989, 861322145238};
  897.     CA[214] = {58505968, 4194880773};
  898.     CA[215] = {58780029, 15930236974};
  899.     CA[216] = {59051253, 35700972571};
  900.     CA[217] = {59324054, 69009035680};
  901.     CA[218] = {59597984, 125123643256};
  902.     CA[219] = {59874035, 219660787949};
  903.     CA[220] = {60148656, 378928973305};
  904.     CA[221] = {60421477, 647250541763};
  905.     CA[222] = {60694944, 1099296025449};
  906.     CA[223] = {60965453, 8860169549};
  907.     CA[224] = {61245238, 23789920966};
  908.     CA[225] = {61522200, 48942303338};
  909.     CA[226] = {61795402, 91316909962};
  910.     CA[227] = {62068942, 162706063062};
  911.     CA[228] = {62339579, 282976470161};
  912.     CA[229] = {62612383, 485597879612};
  913.     CA[230] = {62884488, 826957292677};
  914.     CA[231] = {63156895, 3520662301};
  915.     CA[232] = {63433336, 14794370822};
  916.     CA[233] = {63708746, 33787361373};
  917.     CA[234] = {63984638, 65785145502};
  918.     CA[235] = {64254435, 119692305662};
  919.     CA[236] = {64526480, 210510529870};
  920.     CA[237] = {64802023, 363513392488};
  921.     CA[238] = {65076096, 621279674513};
  922.     CA[239] = {65349623, 1055542505029};
  923.     CA[240] = {65632858, 8001807938};
  924.     CA[241] = {65904999, 22343825836};
  925.     CA[242] = {66176658, 46506044560};
  926.     CA[243] = {66447328, 87212507054};
  927.     CA[244] = {66718744, 155791312171};
  928.     CA[245] = {66991357, 271327082790};
  929.     CA[246] = {67266033, 465971977071};
  930.     CA[247] = {67540614, 793893232215};
  931.     CA[248] = {67816335, 2873311317};
  932.     CA[249] = {68087274, 13703768503};
  933.     CA[250] = {68355568, 31950006856};
  934.     CA[251] = {68630318, 62689725842};
  935.     CA[252] = {68905119, 114477404510};
  936.     CA[253] = {69175040, 201724905465};
  937.     CA[254] = {69449687, 348712115670};
  938.     CA[255] = {69722804, 596343735453};
  939.     CA[256] = {69996181, 1013532543759};
  940.     CA[257] = {70268773, 7179071509};
  941.     CA[258] = {70548434, 20957749133};
  942.     CA[259] = {70821060, 44170899899};
  943.     CA[260] = {71095845, 83278452938};
  944.     CA[261] = {71367802, 149163550662};
  945.     CA[262] = {71639229, 260161190782};
  946.     CA[263] = {71914469, 447160626795};
  947.     CA[264] = {72188542, 762201460208};
  948.     CA[265] = {72459909, 2251077345};
  949.     CA[266] = {72730958, 12655481437};
  950.     CA[267] = {73005837, 30183941391};
  951.     CA[268] = {73274497, 59714408190};
  952.     CA[269] = {73544800, 109464841006};
  953.     CA[270] = {73820522, 193280162435};
  954.     CA[271] = {74093977, 334485126796};
  955.     CA[272] = {74366189, 572375307829};
  956.     CA[273] = {74639783, 973152564569};
  957.     CA[274] = {74910924, 6386486534};
  958.     CA[275] = {75183834, 19622468974};
  959.     CA[276] = {75458096, 41921332758};
  960.     CA[277] = {75731160, 79488572365};
  961.     CA[278] = {76002762, 142778680387};
  962.     CA[279] = {76276480, 249404501192};
  963.     CA[280] = {76548082, 429038666013};
  964.     CA[281] = {76823332, 731671113344};
  965.     CA[282] = {77096594, 1653538050};
  966.     CA[283] = {77374051, 11648797755};
  967.     CA[284] = {77647368, 28487965899};
  968.     CA[285] = {77920897, 56857172244};
  969.     CA[286] = {78193384, 104651211514};
  970.     CA[287] = {78470592, 185170566623};
  971.     CA[288] = {78740895, 320822765818};
  972.     CA[289] = {79014921, 549358117610};
  973.     CA[290] = {79287733, 934375149059};
  974.     CA[291] = {79559766, 5626272217};
  975.     CA[292] = {79829276, 18341724191};
  976.     CA[293] = {80101891, 39763642256};
  977.     CA[294] = {80372674, 75853477828};
  978.     CA[295] = {80648887, 136654580457};
  979.     CA[296] = {80921580, 239087135702};
  980.     CA[297] = {81196226, 411656841171};
  981.     CA[298] = {81468131, 702387685291};
  982.     CA[299] = {81741521, 1079384007};
  983.     CA[300] = {82016646, 10681511515};
  984.     CA[301] = {82292024, 26858363799};
  985.     CA[302] = {82566908, 54111756329};
  986.     CA[303] = {82838281, 100025966955};
  987.     CA[304] = {83111389, 177378345672};
  988.     CA[305] = {83386337, 307695090830};
  989.     CA[306] = {83660304, 527241721048};
  990.     CA[307] = {83934581, 897115315130};
  991.     CA[308] = {84209088, 4896649448};
  992.     CA[309] = {84482547, 17112517497};
  993.     CA[310] = {84756584, 37692778685};
  994.     CA[311] = {85028753, 72364662136};
  995.     CA[312] = {85301836, 130776918722};
  996.     CA[313] = {85574461, 229184948338};
  997.     CA[314] = {85846471, 394974473256};
  998.     CA[315] = {86120350, 674282642626};
  999.     CA[316] = {86392622, 528150315};
  1000.     CA[317] = {86669134, 9752839639};
  1001.     CA[318] = {86939120, 25293815945};
  1002.     CA[319] = {87211126, 51475938442};
  1003.     CA[320] = {87482537, 95585363993};
  1004.     CA[321] = {87751927, 169897193435};
  1005.     CA[322] = {88024826, 295091478460};
  1006.     CA[323] = {88297198, 506008220911};
  1007.     CA[324] = {88571033, 861342909378};
  1008.     CA[325] = {88842930, 4195154133};
  1009.     CA[326] = {89114891, 15930697612};
  1010.     CA[327] = {89389654, 35701748635};
  1011.     CA[328] = {89661589, 69010343154};
  1012.     CA[329] = {89935566, 125125846033};
  1013.     CA[330] = {90208474, 219664499095};
  1014.     CA[331] = {90481266, 378935225545};
  1015.     CA[332] = {90755477, 647261074655};
  1016.     CA[333] = {91029210, 1099313770247};
  1017.     return;
  1018. }
  1019.  
  1020. ull f(ull x){
  1021.     return ((x + (x>>20) + 12345ULL) % M);
  1022. }
  1023.  
  1024. ull n, mul, ans;
  1025. ull startIndex = 350125310;
  1026. ull cycleLen = 182129209;
  1027. ull wholeCycleAns = 91029304;
  1028. ull beforeCycleAns = 175147925;
  1029.  
  1030. void solvePreCycle(){
  1031.    
  1032.     ull interval = startIndex/667;
  1033.     ull ind = 0;
  1034.    
  1035.     for(ind = 0 ; ind < 668 ; ind ++)
  1036.         if(interval*ind > n) break;
  1037.    
  1038.     ind -= 1;
  1039.    
  1040.     ans = PCA[ind].first;
  1041.     ull xi = PCA[ind].second;
  1042.    
  1043.     for(ull i = interval*ind + 1 ; i <= n ; i ++){
  1044.         xi = f(xi);
  1045.         if((xi % 2ULL) == 0ULL) ans++;
  1046.     }
  1047.    
  1048.     printf("%llu\n", ans);
  1049.    
  1050.     return;
  1051. }
  1052.  
  1053. void solveCycle(){
  1054.    
  1055.     ull interval = cycleLen/333;
  1056.     ull ind = 0;
  1057.    
  1058.     for(ind = 0 ; ind < 334 ; ind ++)
  1059.         if(interval*ind > n) break;
  1060.    
  1061.     ind -= 1;
  1062.    
  1063.     ans += CA[ind].first;
  1064.     ull xi = CA[ind].second;
  1065.    
  1066.     for(ull i = interval*ind + 1 ; i <= n ; i ++){
  1067.         xi = f(xi);
  1068.         if((xi % 2ULL) == 0ULL) ans++;
  1069.     }
  1070.    
  1071.     printf("%llu\n", ans);
  1072.    
  1073.     return;
  1074. }
  1075.  
  1076. int main(){
  1077.    
  1078.     setup();
  1079.    
  1080.     scanf("%llu", &n);
  1081.    
  1082.     if(n == 0){
  1083.         printf("0\n");
  1084.         return 0;
  1085.     }
  1086.    
  1087.     n -= 1;
  1088.    
  1089.     if(n < startIndex){
  1090.         solvePreCycle();
  1091.         return 0;
  1092.     }
  1093.    
  1094.     ans = beforeCycleAns;
  1095.     n -= startIndex;
  1096.    
  1097.     mul = n/cycleLen;
  1098.     ans += mul*wholeCycleAns;
  1099.    
  1100.     n -= mul*cycleLen;
  1101.     solveCycle();
  1102.    
  1103.     return 0;
  1104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!