67a00eb228b41af71d062843cc7deff1def8f597815b413ef41b6ed63757944e
// https://szkopul.edu.pl/problemset/problem/hHq1mMMY5VOAzO_WNuQ2iQ1y/site/?key=statement
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int sizik = 1000 * 1001;
#define ar std::array
#define pr std::pair
#define vec std::vector
typedef vec<vec<int>> _kra;
int ans[sizik];
void solve() {
int m;
std::cin >> m;
m--;
std::cout << ans[m] << '\n';
}
int32_t main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
ans[0] = 1ll;
ans[1] = 2ll;
ans[2] = 4ll;
ans[3] = 8ll;
ans[4] = 16ll;
ans[5] = 5ll;
ans[6] = 10ll;
ans[7] = 3ll;
ans[8] = 6ll;
ans[9] = 12ll;
ans[10] = 24ll;
ans[11] = 48ll;
ans[12] = 17ll;
ans[13] = 34ll;
ans[14] = 11ll;
ans[15] = 22ll;
ans[16] = 7ll;
ans[17] = 14ll;
ans[18] = 28ll;
ans[19] = 9ll;
ans[20] = 18ll;
ans[21] = 36ll;
ans[22] = 72ll;
ans[23] = 25ll;
ans[24] = 49ll;
ans[25] = 98ll;
ans[26] = 33ll;
ans[27] = 65ll;
ans[28] = 130ll;
ans[29] = 43ll;
ans[30] = 86ll;
ans[31] = 172ll;
ans[32] = 57ll;
ans[33] = 114ll;
ans[34] = 39ll;
ans[35] = 78ll;
ans[36] = 153ll;
ans[37] = 305ll;
ans[38] = 105ll;
ans[39] = 203ll;
ans[40] = 406ll;
ans[41] = 135ll;
ans[42] = 270ll;
ans[43] = 540ll;
ans[44] = 185ll;
ans[45] = 361ll;
ans[46] = 123ll;
ans[47] = 246ll;
ans[48] = 481ll;
ans[49] = 169ll;
ans[50] = 329ll;
ans[51] = 641ll;
ans[52] = 219ll;
ans[53] = 427ll;
ans[54] = 159ll;
ans[55] = 295ll;
ans[56] = 569ll;
ans[57] = 1138ll;
ans[58] = 379ll;
ans[59] = 758ll;
ans[60] = 283ll;
ans[61] = 505ll;
ans[62] = 1010ll;
ans[63] = 377ll;
ans[64] = 673ll;
ans[65] = 251ll;
ans[66] = 502ll;
ans[67] = 167ll;
ans[68] = 334ll;
ans[69] = 111ll;
ans[70] = 222ll;
ans[71] = 444ll;
ans[72] = 799ll;
ans[73] = 297ll;
ans[74] = 593ll;
ans[75] = 1063ll;
ans[76] = 395ll;
ans[77] = 790ll;
ans[78] = 263ll;
ans[79] = 526ll;
ans[80] = 175ll;
ans[81] = 350ll;
ans[82] = 700ll;
ans[83] = 233ll;
ans[84] = 466ll;
ans[85] = 155ll;
ans[86] = 310ll;
ans[87] = 103ll;
ans[88] = 206ll;
ans[89] = 412ll;
ans[90] = 137ll;
ans[91] = 274ll;
ans[92] = 91ll;
ans[93] = 182ll;
ans[94] = 364ll;
ans[95] = 121ll;
ans[96] = 242ll;
ans[97] = 447ll;
ans[98] = 161ll;
ans[99] = 322ll;
ans[100] = 107ll;
ans[101] = 214ll;
ans[102] = 71ll;
ans[103] = 142ll;
ans[104] = 47ll;
ans[105] = 94ll;
ans[106] = 31ll;
ans[107] = 62ll;
ans[108] = 124ll;
ans[109] = 41ll;
ans[110] = 82ll;
ans[111] = 27ll;
ans[112] = 54ll;
ans[113] = 108ll;
ans[114] = 216ll;
ans[115] = 73ll;
ans[116] = 145ll;
ans[117] = 290ll;
ans[118] = 97ll;
ans[119] = 193ll;
ans[120] = 386ll;
ans[121] = 129ll;
ans[122] = 257ll;
ans[123] = 514ll;
ans[124] = 171ll;
ans[125] = 342ll;
ans[126] = 684ll;
ans[127] = 231ll;
ans[128] = 457ll;
ans[129] = 913ll;
ans[130] = 313ll;
ans[131] = 609ll;
ans[132] = 1217ll;
ans[133] = 411ll;
ans[134] = 811ll;
ans[135] = 1622ll;
ans[136] = 543ll;
ans[137] = 1081ll;
ans[138] = 2162ll;
ans[139] = 731ll;
ans[140] = 1441ll;
ans[141] = 487ll;
ans[142] = 967ll;
ans[143] = 327ll;
ans[144] = 649ll;
ans[145] = 1287ll;
ans[146] = 2561ll;
ans[147] = 859ll;
ans[148] = 1707ll;
ans[149] = 3414ll;
ans[150] = 1145ll;
ans[151] = 2279ll;
ans[152] = 763ll;
ans[153] = 1519ll;
ans[154] = 3007ll;
ans[155] = 1017ll;
ans[156] = 2023ll;
ans[157] = 4009ll;
ans[158] = 1351ll;
ans[159] = 2697ll;
ans[160] = 5345ll;
ans[161] = 1801ll;
ans[162] = 3563ll;
ans[163] = 1215ll;
ans[164] = 2375ll;
ans[165] = 4750ll;
ans[166] = 1583ll;
ans[167] = 3166ll;
ans[168] = 1055ll;
ans[169] = 2110ll;
ans[170] = 703ll;
ans[171] = 1406ll;
ans[172] = 2751ll;
ans[173] = 937ll;
ans[174] = 1874ll;
ans[175] = 3748ll;
ans[176] = 1249ll;
ans[177] = 2498ll;
ans[178] = 871ll;
ans[179] = 1665ll;
ans[180] = 3330ll;
ans[181] = 1161ll;
ans[182] = 2223ll;
ans[183] = 4347ll;
ans[184] = 8694ll;
ans[185] = 3097ll;
ans[186] = 5921ll;
ans[187] = 11593ll;
ans[188] = 3947ll;
ans[189] = 7894ll;
ans[190] = 2631ll;
ans[191] = 5262ll;
ans[192] = 10524ll;
ans[193] = 3567ll;
ans[194] = 7017ll;
ans[195] = 13739ll;
ans[196] = 4763ll;
ans[197] = 9159ll;
ans[198] = 3175ll;
ans[199] = 6319ll;
ans[200] = 12473ll;
ans[201] = 4233ll;
ans[202] = 8315ll;
ans[203] = 16283ll;
ans[204] = 5543ll;
ans[205] = 10855ll;
ans[206] = 3695ll;
ans[207] = 7390ll;
ans[208] = 2463ll;
ans[209] = 4926ll;
ans[210] = 9852ll;
ans[211] = 19297ll;
ans[212] = 6569ll;
ans[213] = 13137ll;
ans[214] = 4379ll;
ans[215] = 8758ll;
ans[216] = 2919ll;
ans[217] = 5838ll;
ans[218] = 11676ll;
ans[219] = 22697ll;
ans[220] = 7785ll;
ans[221] = 15131ll;
ans[222] = 30262ll;
ans[223] = 10087ll;
ans[224] = 20174ll;
ans[225] = 6919ll;
ans[226] = 13449ll;
ans[227] = 26898ll;
ans[228] = 9225ll;
ans[229] = 18450ll;
ans[230] = 35865ll;
ans[231] = 12527ll;
ans[232] = 24095ll;
ans[233] = 8351ll;
ans[234] = 16063ll;
ans[235] = 5567ll;
ans[236] = 11134ll;
ans[237] = 3711ll;
ans[238] = 7422ll;
ans[239] = 14831ll;
ans[240] = 29161ll;
ans[241] = 9887ll;
ans[242] = 19774ll;
ans[243] = 6591ll;
ans[244] = 13182ll;
ans[245] = 25383ll;
ans[246] = 8959ll;
ans[247] = 17577ll;
ans[248] = 34555ll;
ans[249] = 11945ll;
ans[250] = 23435ll;
ans[251] = 7963ll;
ans[252] = 15623ll;
ans[253] = 30715ll;
ans[254] = 10415ll;
ans[255] = 20830ll;
ans[256] = 6943ll;
ans[257] = 13886ll;
ans[258] = 27135ll;
ans[259] = 9257ll;
ans[260] = 18514ll;
ans[261] = 6171ll;
ans[262] = 12342ll;
ans[263] = 24684ll;
ans[264] = 48623ll;
ans[265] = 16457ll;
ans[266] = 32415ll;
ans[267] = 10971ll;
ans[268] = 21942ll;
ans[269] = 43884ll;
ans[270] = 14695ll;
ans[271] = 29257ll;
ans[272] = 57627ll;
ans[273] = 19593ll;
ans[274] = 39009ll;
ans[275] = 13255ll;
ans[276] = 26471ll;
ans[277] = 50815ll;
ans[278] = 17647ll;
ans[279] = 34719ll;
ans[280] = 67583ll;
ans[281] = 23529ll;
ans[282] = 45055ll;
ans[283] = 90110ll;
ans[284] = 31419ll;
ans[285] = 60073ll;
ans[286] = 120146ll;
ans[287] = 40959ll;
ans[288] = 80097ll;
ans[289] = 158299ll;
ans[290] = 56487ll;
ans[291] = 107065ll;
ans[292] = 211065ll;
ans[293] = 73063ll;
ans[294] = 142395ll;
ans[295] = 48927ll;
ans[296] = 96383ll;
ans[297] = 189863ll;
ans[298] = 64255ll;
ans[299] = 126575ll;
ans[300] = 250151ll;
ans[301] = 84383ll;
ans[302] = 166767ll;
ans[303] = 56255ll;
ans[304] = 112510ll;
ans[305] = 37503ll;
ans[306] = 75006ll;
ans[307] = 26623ll;
ans[308] = 51359ll;
ans[309] = 100009ll;
ans[310] = 34239ll;
ans[311] = 67691ll;
ans[312] = 133345ll;
ans[313] = 45127ll;
ans[314] = 89119ll;
ans[315] = 177793ll;
ans[316] = 60169ll;
ans[317] = 118825ll;
ans[318] = 237057ll;
ans[319] = 80225ll;
ans[320] = 158433ll;
ans[321] = 53483ll;
ans[322] = 106966ll;
ans[323] = 35655ll;
ans[324] = 71310ll;
ans[325] = 140479ll;
ans[326] = 277631ll;
ans[327] = 95081ll;
ans[328] = 185087ll;
ans[329] = 63387ll;
ans[330] = 123391ll;
ans[331] = 243951ll;
ans[332] = 87087ll;
ans[333] = 164521ll;
ans[334] = 60975ll;
ans[335] = 118187ll;
ans[336] = 219361ll;
ans[337] = 78791ll;
ans[338] = 150251ll;
ans[339] = 52527ll;
ans[340] = 100167ll;
ans[341] = 192751ll;
ans[342] = 385502ll;
ans[343] = 129991ll;
ans[344] = 257001ll;
ans[345] = 514002ll;
ans[346] = 173321ll;
ans[347] = 346642ll;
ans[348] = 115547ll;
ans[349] = 231094ll;
ans[350] = 77031ll;
ans[351] = 154062ll;
ans[352] = 308124ll;
ans[353] = 106239ll;
ans[354] = 205417ll;
ans[355] = 410833ll;
ans[356] = 146599ll;
ans[357] = 273889ll;
ans[358] = 543515ll;
ans[359] = 189855ll;
ans[360] = 362343ll;
ans[361] = 724686ll;
ans[362] = 254911ll;
ans[363] = 486913ll;
ans[364] = 180463ll;
ans[365] = 336199ll;
ans[366] = 649217ll;
ans[367] = 225023ll;
ans[368] = 432811ll;
ans[369] = 150015ll;
ans[370] = 298843ll;
ans[371] = 572591ll;
ans[372] = 206847ll;
ans[373] = 381727ll;
ans[374] = 142587ll;
ans[375] = 285174ll;
ans[376] = 508969ll;
ans[377] = 1017938ll;
ans[378] = 351359ll;
ans[379] = 678625ll;
ans[380] = 234239ll;
ans[381] = 468478ll;
ans[382] = 156159ll;
ans[383] = 312318ll;
ans[384] = 601727ll;
ans[385] = 216367ll;
ans[386] = 401151ll;
ans[387] = 802302ll;
ans[388] = 277615ll;
ans[389] = 555230ll;
ans[390] = 1069737ll;
ans[391] = 370153ll;
ans[392] = 740306ll;
ans[393] = 1426315ll;
ans[394] = 493537ll;
ans[395] = 987074ll;
ans[396] = 1901753ll;
ans[397] = 658049ll;
ans[398] = 1267835ll;
ans[399] = 438699ll;
ans[400] = 845223ll;
ans[401] = 1690446ll;
ans[402] = 591983ll;
ans[403] = 1169865ll;
ans[404] = 394655ll;
ans[405] = 788315ll;
ans[406] = 263103ll;
ans[407] = 525543ll;
ans[408] = 1039879ll;
ans[409] = 360361ll;
ans[410] = 701607ll;
ans[411] = 1349487ll;
ans[412] = 467739ll;
ans[413] = 934299ll;
ans[414] = 1848673ll;
ans[415] = 635519ll;
ans[416] = 1241255ll;
ans[417] = 423679ll;
ans[418] = 827503ll;
ans[419] = 1583007ll;
ans[420] = 554143ll;
ans[421] = 1103337ll;
ans[422] = 376603ll;
ans[423] = 735679ll;
ans[424] = 1460679ll;
ans[425] = 492571ll;
ans[426] = 980905ll;
ans[427] = 1923163ll;
ans[428] = 656761ll;
ans[429] = 1307873ll;
ans[430] = 2564217ll;
ans[431] = 871915ll;
ans[432] = 1709695ll;
ans[433] = 583787ll;
ans[434] = 1162553ll;
ans[435] = 389191ll;
ans[436] = 775035ll;
ans[437] = 1496735ll;
ans[438] = 518921ll;
ans[439] = 997823ll;
ans[440] = 345947ll;
ans[441] = 665215ll;
ans[442] = 230631ll;
ans[443] = 461262ll;
ans[444] = 886953ll;
ans[445] = 1773906ll;
ans[446] = 615017ll;
ans[447] = 1208233ll;
ans[448] = 410011ll;
ans[449] = 818943ll;
ans[450] = 1565727ll;
ans[451] = 546681ll;
ans[452] = 1093362ll;
ans[453] = 2102407ll;
ans[454] = 4175273ll;
ans[455] = 1431979ll;
ans[456] = 2783515ll;
ans[457] = 970599ll;
ans[458] = 1909305ll;
ans[459] = 3711353ll;
ans[460] = 1290267ll;
ans[461] = 2474235ll;
ans[462] = 4923135ll;
ans[463] = 1727783ll;
ans[464] = 3440667ll;
ans[465] = 1151855ll;
ans[466] = 2300679ll;
ans[467] = 767903ll;
ans[468] = 1535806ll;
ans[469] = 511935ll;
ans[470] = 1023870ll;
ans[471] = 2047740ll;
ans[472] = 3941191ll;
ans[473] = 1365161ll;
ans[474] = 2718587ll;
ans[475] = 910107ll;
ans[476] = 1812391ll;
ans[477] = 3605743ll;
ans[478] = 6950939ll;
ans[479] = 2416521ll;
ans[480] = 4633959ll;
ans[481] = 9267918ll;
ans[482] = 3216799ll;
ans[483] = 6206655ll;
ans[484] = 2157291ll;
ans[485] = 4289065ll;
ans[486] = 1504895ll;
ans[487] = 2929787ll;
ans[488] = 1003263ll;
ans[489] = 1953191ll;
ans[490] = 3772583ll;
ans[491] = 1302127ll;
ans[492] = 2515055ll;
ans[493] = 5030110ll;
ans[494] = 1676703ll;
ans[495] = 3353406ll;
ans[496] = 6706812ll;
ans[497] = 2270335ll;
ans[498] = 4471209ll;
ans[499] = 1585403ll;
ans[500] = 3027113ll;
ans[501] = 1056935ll;
ans[502] = 2018075ll;
ans[503] = 704623ll;
ans[504] = 1345383ll;
ans[505] = 2690766ll;
ans[506] = 939497ll;
ans[507] = 1878994ll;
ans[508] = 626331ll;
ans[509] = 1252662ll;
ans[510] = 2385767ll;
ans[511] = 4771534ll;
ans[512] = 1590511ll;
ans[513] = 3181022ll;
ans[514] = 6255855ll;
ans[515] = 2120681ll;
ans[516] = 4241362ll;
ans[517] = 1413787ll;
ans[518] = 2827574ll;
ans[519] = 5655148ll;
ans[520] = 1885049ll;
ans[521] = 3770098ll;
ans[522] = 1256699ll;
ans[523] = 2513398ll;
ans[524] = 837799ll;
ans[525] = 1675598ll;
ans[526] = 3351196ll;
ans[527] = 1117065ll;
ans[528] = 2234130ll;
ans[529] = 4468260ll;
ans[530] = 1501353ll;
ans[531] = 2978841ll;
ans[532] = 5957681ll;
ans[533] = 1993215ll;
ans[534] = 3971787ll;
ans[535] = 7943574ll;
ans[536] = 15163483ll;
ans[537] = 5315241ll;
ans[538] = 10348991ll;
ans[539] = 3558763ll;
ans[540] = 6899327ll;
ans[541] = 13478651ll;
ans[542] = 4599551ll;
ans[543] = 8985767ll;
ans[544] = 3066367ll;
ans[545] = 5990511ll;
ans[546] = 11981022ll;
ans[547] = 4088489ll;
ans[548] = 8176978ll;
ans[549] = 2725659ll;
ans[550] = 5451318ll;
ans[551] = 10902636ll;
ans[552] = 3877919ll;
ans[553] = 7268425ll;
ans[554] = 2585279ll;
ans[555] = 5143151ll;
ans[556] = 1723519ll;
ans[557] = 3428767ll;
ans[558] = 6857534ll;
ans[559] = 2298025ll;
ans[560] = 4571689ll;
ans[561] = 8614431ll;
ans[562] = 3064033ll;
ans[563] = 6095585ll;
ans[564] = 11739887ll;
ans[565] = 4063723ll;
ans[566] = 7826591ll;
ans[567] = 15314539ll;
ans[568] = 5217727ll;
ans[569] = 10435454ll;
ans[570] = 20177855ll;
ans[571] = 6956969ll;
ans[572] = 13451903ll;
ans[573] = 4637979ll;
ans[574] = 8967935ll;
ans[575] = 17935870ll;
ans[576] = 5978623ll;
ans[577] = 11957246ll;
ans[578] = 23914492ll;
ans[579] = 7971497ll;
ans[580] = 15942994ll;
ans[581] = 5314331ll;
ans[582] = 10628662ll;
ans[583] = 3542887ll;
ans[584] = 7085774ll;
ans[585] = 14171548ll;
ans[586] = 4723849ll;
ans[587] = 9447698ll;
ans[588] = 18895396ll;
ans[589] = 6298465ll;
ans[590] = 12596930ll;
ans[591] = 25193860ll;
ans[592] = 8397953ll;
ans[593] = 16795906ll;
ans[594] = 5598635ll;
ans[595] = 11197270ll;
ans[596] = 3732423ll;
ans[597] = 7464846ll;
ans[598] = 14929692ll;
ans[599] = 29859384ll;
ans[600] = 9953129ll;
ans[601] = 19906257ll;
ans[602] = 6635419ll;
ans[603] = 13270838ll;
ans[604] = 26541676ll;
ans[605] = 8847225ll;
ans[606] = 17694450ll;
ans[607] = 6355687ll;
ans[608] = 12711374ll;
ans[609] = 23321343ll;
ans[610] = 8474249ll;
ans[611] = 16497899ll;
ans[612] = 5649499ll;
ans[613] = 10998599ll;
ans[614] = 21797023ll;
ans[615] = 7332399ll;
ans[616] = 14664798ll;
ans[617] = 28553703ll;
ans[618] = 10011263ll;
ans[619] = 19375131ll;
ans[620] = 6674175ll;
ans[621] = 13002751ll;
ans[622] = 26005502ll;
ans[623] = 49709511ll;
ans[624] = 17337001ll;
ans[625] = 34385063ll;
ans[626] = 67072767ll;
ans[627] = 22923375ll;
ans[628] = 45703931ll;
ans[629] = 15410667ll;
ans[630] = 30469287ll;
ans[631] = 58237599ll;
ans[632] = 21093689ll;
ans[633] = 40752667ll;
ans[634] = 14062459ll;
ans[635] = 27988635ll;
ans[636] = 54336889ll;
ans[637] = 18749945ll;
ans[638] = 37499890ll;
ans[639] = 12499963ll;
ans[640] = 24999926ll;
ans[641] = 48562939ll;
ans[642] = 16666617ll;
ans[643] = 33333234ll;
ans[644] = 64281327ll;
ans[645] = 123734443ll;
ans[646] = 44444313ll;
ans[647] = 82755751ll;
ans[648] = 164979257ll;
ans[649] = 56804591ll;
ans[650] = 109986171ll;
ans[651] = 37869727ll;
ans[652] = 73560667ll;
ans[653] = 147106799ll;
ans[654] = 50492969ll;
ans[655] = 98071199ll;
ans[656] = 33661979ll;
ans[657] = 65380799ll;
ans[658] = 22441319ll;
ans[659] = 43587199ll;
ans[660] = 14960879ll;
ans[661] = 29921758ll;
ans[662] = 9973919ll;
ans[663] = 19947838ll;
ans[664] = 6649279ll;
ans[665] = 13298558ll;
ans[666] = 26597116ll;
ans[667] = 8865705ll;
ans[668] = 17731410ll;
ans[669] = 35184731ll;
ans[670] = 70369462ll;
ans[671] = 23456487ll;
ans[672] = 46912974ll;
ans[673] = 15761255ll;
ans[674] = 31522507ll;
ans[675] = 10507503ll;
ans[676] = 21015006ll;
ans[677] = 42030009ll;
ans[678] = 81641887ll;
ans[679] = 28020007ll;
ans[680] = 56040014ll;
ans[681] = 18901151ll;
ans[682] = 37360009ll;
ans[683] = 12600767ll;
ans[684] = 25201534ll;
ans[685] = 8400511ll;
ans[686] = 16801022ll;
ans[687] = 33602044ll;
ans[688] = 11200681ll;
ans[689] = 22401362ll;
ans[690] = 44481895ll;
ans[691] = 14934241ll;
ans[692] = 29868482ll;
ans[693] = 59038043ll;
ans[694] = 19912321ll;
ans[695] = 39358695ll;
ans[696] = 78235419ll;
ans[697] = 26549761ll;
ans[698] = 53099522ll;
ans[699] = 101937255ll;
ans[700] = 35399681ll;
ans[701] = 70799362ll;
ans[702] = 23599787ll;
ans[703] = 47199574ll;
ans[704] = 15733191ll;
ans[705] = 31466382ll;
ans[706] = 62196455ll;
ans[707] = 120560383ll;
ans[708] = 41464303ll;
ans[709] = 82928606ll;
ans[710] = 160747177ll;
ans[711] = 55285737ll;
ans[712] = 110571474ll;
ans[713] = 212311899ll;
ans[714] = 424623798ll;
ans[715] = 142886379ll;
ans[716] = 285772758ll;
ans[717] = 98285755ll;
ans[718] = 195030047ll;
ans[719] = 380646847ll;
ans[720] = 130020031ll;
ans[721] = 260040062ll;
ans[722] = 87365115ll;
ans[723] = 173360041ll;
ans[724] = 335505223ll;
ans[725] = 116486823ll;
ans[726] = 225795759ll;
ans[727] = 447340297ll;
ans[728] = 157154471ll;
ans[729] = 301695657ll;
ans[730] = 104769647ll;
ans[731] = 207803039ll;
ans[732] = 69846431ll;
ans[733] = 138535359ll;
ans[734] = 46564287ll;
ans[735] = 93128574ll;
ans[736] = 184077951ll;
ans[737] = 63101607ll;
ans[738] = 124171433ll;
ans[739] = 237875367ll;
ans[740] = 82780955ll;
ans[741] = 164190055ll;
ans[742] = 55187303ll;
ans[743] = 110374606ll;
ans[744] = 36791535ll;
ans[745] = 73583070ll;
ans[746] = 145946715ll;
ans[747] = 291893430ll;
ans[748] = 98110761ll;
ans[749] = 196213995ll;
ans[750] = 389191241ll;
ans[751] = 130814347ll;
ans[752] = 259460827ll;
ans[753] = 513830247ll;
ans[754] = 174419129ll;
ans[755] = 345947769ll;
ans[756] = 116279419ll;
ans[757] = 231812223ll;
ans[758] = 461387807ll;
ans[759] = 155039225ll;
ans[760] = 307591871ll;
ans[761] = 103359483ll;
ans[762] = 205061247ll;
ans[763] = 392325631ll;
ans[764] = 784567579ll;
ans[765] = 275625289ll;
ans[766] = 523100841ll;
ans[767] = 189535835ll;
ans[768] = 356975335ll;
ans[769] = 126357223ll;
ans[770] = 252714446ll;
ans[771] = 464928935ll;
ans[772] = 168476297ll;
ans[773] = 309952623ll;
ans[774] = 112317531ll;
ans[775] = 224635062ll;
ans[776] = 434117991ll;
ans[777] = 158560799ll;
ans[778] = 299513417ll;
ans[779] = 105707199ll;
ans[780] = 199675611ll;
ans[781] = 367390439ll;
ans[782] = 734780878ll;
ans[783] = 244926959ll;
ans[784] = 489853918ll;
ans[785] = 163284639ll;
ans[786] = 326569278ll;
ans[787] = 653138556ll;
ans[788] = 227588847ll;
ans[789] = 435425705ll;
ans[790] = 155428635ll;
ans[791] = 290283803ll;
ans[792] = 580567606ll;
ans[793] = 193522535ll;
ans[794] = 387045070ll;
ans[795] = 129015023ll;
ans[796] = 258030046ll;
ans[797] = 86010015ll;
ans[798] = 172020030ll;
ans[799] = 344040060ll;
ans[800] = 688080120ll;
ans[801] = 229360041ll;
ans[802] = 458720081ll;
ans[803] = 165276159ll;
ans[804] = 305813387ll;
ans[805] = 611626774ll;
ans[806] = 203875591ll;
ans[807] = 407751182ll;
ans[808] = 145324775ll;
ans[809] = 271834121ll;
ans[810] = 96883183ll;
ans[811] = 181222747ll;
ans[812] = 362445494ll;
ans[813] = 129177577ll;
ans[814] = 241630329ll;
ans[815] = 483260658ll;
ans[816] = 172236769ll;
ans[817] = 344473538ll;
ans[818] = 644347545ll;
ans[819] = 229649025ll;
ans[820] = 459298050ll;
ans[821] = 859130059ll;
ans[822] = 306198703ll;
ans[823] = 612397401ll;
ans[824] = 1145384687ll;
ans[825] = 408264937ll;
ans[826] = 763589791ll;
ans[827] = 1527179582ll;
ans[828] = 544353249ll;
ans[829] = 1018119721ll;
ans[830] = 369953007ll;
ans[831] = 678818811ll;
ans[832] = 1357492961ll;
ans[833] = 483869551ll;
ans[834] = 904995307ll;
ans[835] = 1809990614ll;
ans[836] = 644034303ll;
ans[837] = 1206660409ll;
ans[838] = 430106267ll;
ans[839] = 852146267ll;
ans[840] = 286737511ll;
ans[841] = 568097511ll;
ans[842] = 1071797407ll;
ans[843] = 382316681ll;
ans[844] = 764633362ll;
ans[845] = 254877787ll;
ans[846] = 509755574ll;
ans[847] = 984082943ll;
ans[848] = 339837049ll;
ans[849] = 656055295ll;
ans[850] = 1312110590ll;
ans[851] = 453116065ll;
ans[852] = 874740393ll;
ans[853] = 1749480786ll;
ans[854] = 604154753ll;
ans[855] = 1208309506ll;
ans[856] = 402769835ll;
ans[857] = 805539670ll;
ans[858] = 268513223ll;
ans[859] = 537026446ll;
ans[860] = 179008815ll;
ans[861] = 358017630ll;
ans[862] = 716035260ll;
ans[863] = 1432070520ll;
ans[864] = 477356841ll;
ans[865] = 954713681ll;
ans[866] = 1845417375ll;
ans[867] = 636475787ll;
ans[868] = 1272951574ll;
ans[869] = 424317191ll;
ans[870] = 848634382ll;
ans[871] = 282878127ll;
ans[872] = 565756254ll;
ans[873] = 1120902255ll;
ans[874] = 2214586823ll;
ans[875] = 754341673ll;
ans[876] = 1476391215ll;
ans[877] = 2845683047ll;
ans[878] = 1005788897ll;
ans[879] = 1897122031ll;
ans[880] = 670525931ll;
ans[881] = 1341051862ll;
ans[882] = 447017287ll;
ans[883] = 894034574ll;
ans[884] = 1788069148ll;
ans[885] = 596023049ll;
ans[886] = 1192046098ll;
ans[887] = 397348699ll;
ans[888] = 794697398ll;
ans[889] = 1589394796ll;
ans[890] = 529798265ll;
ans[891] = 1059596530ll;
ans[892] = 353198843ll;
ans[893] = 706397686ll;
ans[894] = 235465895ll;
ans[895] = 470931790ll;
ans[896] = 156977263ll;
ans[897] = 313954526ll;
ans[898] = 627909052ll;
ans[899] = 209303017ll;
ans[900] = 418606034ll;
ans[901] = 837212068ll;
ans[902] = 279070689ll;
ans[903] = 558141378ll;
ans[904] = 1116282756ll;
ans[905] = 2232565512ll;
ans[906] = 744188505ll;
ans[907] = 1488377009ll;
ans[908] = 2880124135ll;
ans[909] = 992251339ll;
ans[910] = 1966561135ll;
ans[911] = 3840165513ll;
ans[912] = 1323001785ll;
ans[913] = 2622081513ll;
ans[914] = 882001191ll;
ans[915] = 1764002382ll;
ans[916] = 3528004761ll;
ans[917] = 6872993447ll;
ans[918] = 2352003177ll;
ans[919] = 4581995631ll;
ans[920] = 8832114927ll;
ans[921] = 3097885415ll;
ans[922] = 6068409703ll;
ans[923] = 2065256943ll;
ans[924] = 4072885191ll;
ans[925] = 8091212937ll;
ans[926] = 2741096351ll;
ans[927] = 5482192702ll;
ans[928] = 1827397567ll;
ans[929] = 3654795134ll;
ans[930] = 1224961663ll;
ans[931] = 2436530089ll;
ans[932] = 4873060178ll;
ans[933] = 1633282217ll;
ans[934] = 3248706785ll;
ans[935] = 1088854811ll;
ans[936] = 2165804523ll;
ans[937] = 725903207ll;
ans[938] = 1451806414ll;
ans[939] = 483935471ll;
ans[940] = 967870942ll;
ans[941] = 322623647ll;
ans[942] = 645247294ll;
ans[943] = 215082431ll;
ans[944] = 430164862ll;
ans[945] = 143388287ll;
ans[946] = 286776574ll;
ans[947] = 95592191ll;
ans[948] = 191184382ll;
ans[949] = 63728127ll;
ans[950] = 127456254ll;
ans[951] = 254912508ll;
ans[952] = 509825016ll;
ans[953] = 169941673ll;
ans[954] = 339883345ll;
ans[955] = 679766690ll;
ans[956] = 226588897ll;
ans[957] = 453177793ll;
ans[958] = 906355586ll;
ans[959] = 302118529ll;
ans[960] = 604237057ll;
ans[961] = 1208474114ll;
ans[962] = 402824705ll;
ans[963] = 805649409ll;
ans[964] = 268549803ll;
ans[965] = 537099606ll;
ans[966] = 1074199212ll;
ans[967] = 2148398424ll;
ans[968] = 716132809ll;
ans[969] = 1432265617ll;
ans[970] = 2864531233ll;
ans[971] = 954843745ll;
ans[972] = 1909687489ll;
ans[973] = 3819374977ll;
ans[974] = 1273124993ll;
ans[975] = 2546249985ll;
ans[976] = 848749995ll;
ans[977] = 1697499990ll;
ans[978] = 3394999979ll;
ans[979] = 1131666663ll;
ans[980] = 2263333319ll;
ans[981] = 4521664679ll;
ans[982] = 1508888879ll;
ans[983] = 3014443119ll;
ans[984] = 1005925919ll;
ans[985] = 2011851838ll;
ans[986] = 670617279ll;
ans[987] = 1341234558ll;
ans[988] = 2682469116ll;
ans[989] = 5364938232ll;
ans[990] = 1788312745ll;
ans[991] = 3576625489ll;
ans[992] = 7153250978ll;
ans[993] = 2384416993ll;
ans[994] = 4768833985ll;
ans[995] = 9318765211ll;
ans[996] = 3179222657ll;
ans[997] = 6351419247ll;
ans[998] = 2119481771ll;
ans[999] = 4238963542ll;
ans[1000] = 1412987847ll;
ans[1001] = 2825975694ll;
ans[1002] = 5651951388ll;
ans[1003] = 11291411995ll;
ans[1004] = 3767967593ll;
ans[1005] = 7535935185ll;
ans[1006] = 2511978395ll;
ans[1007] = 5023956790ll;
ans[1008] = 1674652263ll;
ans[1009] = 3349304526ll;
ans[1010] = 6698609052ll;
ans[1011] = 13397218104ll;
ans[1012] = 4465739369ll;
ans[1013] = 8931478737ll;
ans[1014] = 2977159579ll;
ans[1015] = 5954319158ll;
ans[1016] = 11908638316ll;
ans[1017] = 3969546105ll;
ans[1018] = 7939092210ll;
ans[1019] = 15519276187ll;
ans[1020] = 30035713951ll;
ans[1021] = 10585456281ll;
ans[1022] = 20692368249ll;
ans[1023] = 7056970855ll;
ans[1024] = 14113941707ll;
ans[1025] = 28036093055ll;
ans[1026] = 9409294471ll;
ans[1027] = 18690728703ll;
ans[1028] = 6272863003ll;
ans[1029] = 12545725961ll;
ans[1030] = 24524288295ll;
ans[1031] = 8363817307ll;
ans[1032] = 16727634614ll;
ans[1033] = 33227962139ll;
ans[1034] = 11151756409ll;
ans[1035] = 22151974759ll;
ans[1036] = 7434504283ll;
ans[1037] = 14869008545ll;
ans[1038] = 4956336199ll;
ans[1039] = 9912672363ll;
ans[1040] = 19825344726ll;
ans[1041] = 6608448251ll;
ans[1042] = 13216896491ll;
ans[1043] = 4405632167ll;
ans[1044] = 8811264327ll;
ans[1045] = 2937088111ll;
ans[1046] = 5874176222ll;
ans[1047] = 11694004975ll;
ans[1048] = 3916117481ll;
ans[1049] = 7832234962ll;
ans[1050] = 2610744987ll;
ans[1051] = 5221489974ll;
ans[1052] = 10442979943ll;
ans[1053] = 20789342177ll;
ans[1054] = 6961986633ll;
ans[1055] = 13859561451ll;
ans[1056] = 27719122902ll;
ans[1057] = 9282648843ll;
ans[1058] = 18565297686ll;
ans[1059] = 36294639727ll;
ans[1060] = 70244989055ll;
ans[1061] = 24753730235ll;
ans[1062] = 46829992703ll;
ans[1063] = 16502486823ll;
ans[1064] = 31219995135ll;
ans[1065] = 62439990270ll;
ans[1066] = 22003315783ll;
ans[1067] = 43015869305ll;
ans[1068] = 83253320361ll;
ans[1069] = 28677246203ll;
ans[1070] = 56155224575ll;
ans[1071] = 19118164135ll;
ans[1072] = 37436816383ll;
ans[1073] = 74002951431ll;
ans[1074] = 25490885513ll;
ans[1075] = 49915755177ll;
ans[1076] = 16993923675ll;
ans[1077] = 33987847350ll;
ans[1078] = 11590223975ll;
ans[1079] = 23180447950ll;
ans[1080] = 7726815983ll;
ans[1081] = 15453631966ll;
ans[1082] = 5151210655ll;
ans[1083] = 10302421310ll;
ans[1084] = 20604842620ll;
ans[1085] = 6868280873ll;
ans[1086] = 13736561746ll;
ans[1087] = 4578853915ll;
ans[1088] = 9157707830ll;
ans[1089] = 18315415660ll;
ans[1090] = 6105138553ll;
ans[1091] = 12210277106ll;
ans[1092] = 24420554212ll;
ans[1093] = 8140184737ll;
ans[1094] = 16280369474ll;
ans[1095] = 31162160219ll;
ans[1096] = 10853579649ll;
ans[1097] = 20774773479ll;
ans[1098] = 41549546958ll;
ans[1099] = 14471439535ll;
ans[1100] = 28942879065ll;
ans[1101] = 55399395945ll;
ans[1102] = 19295252713ll;
ans[1103] = 38590505339ll;
ans[1104] = 72945377791ll;
ans[1105] = 25727003559ll;
ans[1106] = 51215129959ll;
ans[1107] = 17625062639ll;
ans[1108] = 34302671483ll;
ans[1109] = 11750041759ll;
ans[1110] = 22868447655ll;
ans[1111] = 45524559963ll;
ans[1112] = 15666722345ll;
ans[1113] = 30491263545ll;
ans[1114] = 10444481563ll;
ans[1115] = 20888963126ll;
ans[1116] = 40655018055ll;
ans[1117] = 13925975417ll;
ans[1118] = 27103345383ll;
ans[1119] = 9283983611ll;
ans[1120] = 18567967222ll;
ans[1121] = 6189322407ll;
ans[1122] = 12378644814ll;
ans[1123] = 24757289628ll;
ans[1124] = 49514579256ll;
ans[1125] = 16504859753ll;
ans[1126] = 33009719505ll;
ans[1127] = 11003239835ll;
ans[1128] = 22006479670ll;
ans[1129] = 7335493223ll;
ans[1130] = 14670986446ll;
ans[1131] = 4890328815ll;
ans[1132] = 9780657630ll;
ans[1133] = 19561315260ll;
ans[1134] = 39122630520ll;
ans[1135] = 13040876841ll;
ans[1136] = 26081753681ll;
ans[1137] = 52163507362ll;
ans[1138] = 17387835787ll;
ans[1139] = 34775671574ll;
ans[1140] = 67681940347ll;
ans[1141] = 23183781049ll;
ans[1142] = 46367562098ll;
ans[1143] = 90242587129ll;
ans[1144] = 30911708065ll;
ans[1145] = 61823416130ll;
ans[1146] = 117698631103ll;
ans[1147] = 41215610753ll;
ans[1148] = 80215632999ll;
ans[1149] = 27477073835ll;
ans[1150] = 54954147670ll;
ans[1151] = 18318049223ll;
ans[1152] = 36636098446ll;
ans[1153] = 12212032815ll;
ans[1154] = 24424065630ll;
ans[1155] = 47535189927ll;
ans[1156] = 95070379854ll;
ans[1157] = 32565420841ll;
ans[1158] = 64102222335ll;
ans[1159] = 126760506473ll;
ans[1160] = 43420561121ll;
ans[1161] = 84507004315ll;
ans[1162] = 28947040747ll;
ans[1163] = 57894081494ll;
ans[1164] = 19298027167ll;
ans[1165] = 38596054329ll;
ans[1166] = 77192108658ll;
ans[1167] = 25730702889ll;
ans[1168] = 51461405778ll;
ans[1169] = 100156449279ll;
ans[1170] = 34841246377ll;
ans[1171] = 68615207705ll;
ans[1172] = 126836000191ll;
ans[1173] = 45743471803ll;
ans[1174] = 88541975023ll;
ans[1175] = 30969996779ll;
ans[1176] = 60991295737ll;
ans[1177] = 20646664519ll;
ans[1178] = 41293329038ll;
ans[1179] = 81321727649ll;
ans[1180] = 27528886025ll;
ans[1181] = 54214485099ll;
ans[1182] = 18352590683ll;
ans[1183] = 36705181366ll;
ans[1184] = 12235060455ll;
ans[1185] = 24470120910ll;
ans[1186] = 48190653423ll;
ans[1187] = 96381306843ll;
ans[1188] = 32626827881ll;
ans[1189] = 65253655761ll;
ans[1190] = 21751218587ll;
ans[1191] = 43502437174ll;
ans[1192] = 14500812391ll;
ans[1193] = 29001624782ll;
ans[1194] = 57114848495ll;
ans[1195] = 19334416521ll;
ans[1196] = 38076565663ll;
ans[1197] = 76153131326ll;
ans[1198] = 146012790719ll;
ans[1199] = 50768754217ll;
ans[1200] = 97341860479ll;
ans[1201] = 194683720958ll;
ans[1202] = 67691672289ll;
ans[1203] = 129789147305ll;
ans[1204] = 45127781531ll;
ans[1205] = 86526098203ll;
ans[1206] = 30085187687ll;
ans[1207] = 60170375374ll;
ans[1208] = 20056791791ll;
ans[1209] = 40113583582ll;
ans[1210] = 13371194527ll;
ans[1211] = 26742389054ll;
ans[1212] = 53484778108ll;
ans[1213] = 17828259369ll;
ans[1214] = 35656518738ll;
ans[1215] = 71313037476ll;
ans[1216] = 142626074952ll;
ans[1217] = 47542024985ll;
ans[1218] = 95084049969ll;
ans[1219] = 31694683323ll;
ans[1220] = 63389366646ll;
ans[1221] = 123371171055ll;
ans[1222] = 246742342110ll;
ans[1223] = 84519155529ll;
ans[1224] = 169038311057ll;
ans[1225] = 324106902823ll;
ans[1226] = 112692207371ll;
ans[1227] = 225384414742ll;
ans[1228] = 75128138247ll;
ans[1229] = 150256276494ll;
ans[1230] = 288095024731ll;
ans[1231] = 576190049462ll;
ans[1232] = 200341701993ll;
ans[1233] = 384126699641ll;
ans[1234] = 133561134663ll;
ans[1235] = 256084466427ll;
ans[1236] = 512168932854ll;
ans[1237] = 1024337865708ll;
ans[1238] = 346590066283ll;
ans[1239] = 682891910473ll;
ans[1240] = 237442017179ll;
ans[1241] = 462120088377ll;
ans[1242] = 158294678119ll;
ans[1243] = 316589356238ll;
ans[1244] = 600286687903ll;
ans[1245] = 211059570825ll;
ans[1246] = 404676687687ll;
ans[1247] = 779623642351ll;
ans[1248] = 281412761247ll;
ans[1249] = 524172661247ll;
ans[1250] = 1039498189801ll;
ans[1251] = 349448440831ll;
ans[1252] = 698896881662ll;
ans[1253] = 250144676519ll;
ans[1254] = 465931254441ll;
ans[1255] = 166763117679ll;
ans[1256] = 328767551815ll;
ans[1257] = 639489086715ll;
ans[1258] = 222350823583ll;
ans[1259] = 438356735753ll;
ans[1260] = 843201054063ll;
ans[1261] = 292237823835ll;
ans[1262] = 575142024863ll;
ans[1263] = 1150284049726ll;
ans[1264] = 383428016575ll;
ans[1265] = 766856033150ll;
ans[1266] = 263526902011ll;
ans[1267] = 511237355433ll;
ans[1268] = 981715235695ll;
ans[1269] = 351369202681ll;
ans[1270] = 685932092187ll;
ans[1271] = 1295152055855ll;
ans[1272] = 468492270241ll;
ans[1273] = 863434703903ll;
ans[1274] = 1726869407806ll;
ans[1275] = 575623135935ll;
ans[1276] = 1151246271870ll;
ans[1277] = 416437573547ll;
ans[1278] = 812956553703ll;
ans[1279] = 277625049031ll;
ans[1280] = 555250098062ll;
ans[1281] = 1064613036315ll;
ans[1282] = 370166732041ll;
ans[1283] = 740333464082ll;
ans[1284] = 254479316383ll;
ans[1285] = 493555642721ll;
ans[1286] = 917323588455ll;
ans[1287] = 329037095147ll;
ans[1288] = 658074190294ll;
ans[1289] = 219358063431ll;
ans[1290] = 438716126862ll;
ans[1291] = 877432253724ll;
ans[1292] = 1630797490587ll;
ans[1293] = 584954835817ll;
ans[1294] = 1140524212735ll;
ans[1295] = 402140154283ll;
ans[1296] = 779939781089ll;
ans[1297] = 1510138052127ll;
ans[1298] = 519959854059ll;
ans[1299] = 1023496113391ll;
ans[1300] = 1993898032319ll;
ans[1301] = 683388232127ll;
ans[1302] = 1329265354879ll;
ans[1303] = 455592154751ll;
ans[1304] = 911184309502ll;
ans[1305] = 303728103167ll;
ans[1306] = 607456206334ll;
ans[1307] = 202485402111ll;
ans[1308] = 404970804222ll;
ans[1309] = 809941608444ll;
ans[1310] = 1617376574247ll;
ans[1311] = 539961072297ll;
ans[1312] = 1079922144593ll;
ans[1313] = 2040278902631ll;
ans[1314] = 719948096395ll;
ans[1315] = 1360185935087ll;
ans[1316] = 486912565695ll;
ans[1317] = 906790623391ll;
ans[1318] = 1807627161767ll;
ans[1319] = 639953863463ll;
ans[1320] = 1205084774511ll;
ans[1321] = 426635908975ll;
ans[1322] = 853271817950ll;
ans[1323] = 1612072219361ll;
ans[1324] = 568847878633ll;
ans[1325] = 1074714812907ll;
ans[1326] = 2149429625814ll;
ans[1327] = 758463838177ll;
ans[1328] = 1516927676354ll;
ans[1329] = 2865906167753ll;
ans[1330] = 1011285117569ll;
ans[1331] = 1910604111835ll;
ans[1332] = 674190078379ll;
ans[1333] = 1322573610623ll;
ans[1334] = 2547472149113ll;
ans[1335] = 881715740415ll;
ans[1336] = 1698314766075ll;
ans[1337] = 3396629532150ll;
ans[1338] = 1210271371431ll;
ans[1339] = 2351241974441ll;
ans[1340] = 4481856530047ll;
ans[1341] = 1567494649627ll;
ans[1342] = 3134989299254ll;
ans[1343] = 5975808706729ll;
ans[1344] = 2089992866169ll;
ans[1345] = 4025635001067ll;
ans[1346] = 1402343409087ll;
ans[1347] = 2790251575015ll;
ans[1348] = 989345275647ll;
ans[1349] = 1921435608057ll;
ans[1350] = 3720335433353ll;
ans[1351] = 7080708261359ll;
ans[1352] = 2480223622235ll;
ans[1353] = 4720472174239ll;
ans[1354] = 1653482414823ll;
ans[1355] = 3306964829646ll;
ans[1356] = 1122382791663ll;
ans[1357] = 2244765583326ll;
ans[1358] = 4409286439529ll;
ans[1359] = 8584463665391ll;
ans[1360] = 2939524293019ll;
ans[1361] = 5722975776927ll;
ans[1362] = 1995347185179ll;
ans[1363] = 3919365724025ll;
ans[1364] = 7838731448050ll;
ans[1365] = 2612910482683ll;
ans[1366] = 5225820965366ll;
ans[1367] = 10438178058015ll;
ans[1368] = 3483880643577ll;
ans[1369] = 6967761287154ll;
ans[1370] = 2345780341887ll;
ans[1371] = 4691560683774ll;
ans[1372] = 8935765734559ll;
ans[1373] = 3198780775531ll;
ans[1374] = 6255414245033ll;
ans[1375] = 11787870157403ll;
ans[1376] = 4170276163355ll;
ans[1377] = 7858580104935ll;
ans[1378] = 2780184108903ll;
ans[1379] = 5519595646055ll;
ans[1380] = 10482249318383ll;
ans[1381] = 3679730430703ll;
ans[1382] = 6988166212255ll;
ans[1383] = 2459499360255ll;
ans[1384] = 4906307240937ll;
ans[1385] = 9317554949673ll;
ans[1386] = 3295033017959ll;
ans[1387] = 6537813452799ll;
ans[1388] = 2196688678639ll;
ans[1389] = 4393377357278ll;
ans[1390] = 8649455068187ll;
ans[1391] = 2928918238185ll;
ans[1392] = 5766303378791ll;
ans[1393] = 11103949945639ll;
ans[1394] = 3844202252527ll;
ans[1395] = 7688404505054ll;
ans[1396] = 14724037451335ll;
ans[1397] = 5125603003369ll;
ans[1398] = 10251206006738ll;
ans[1399] = 3499538751007ll;
ans[1400] = 6834137337825ll;
ans[1401] = 2366794773743ll;
ans[1402] = 4666051668009ll;
ans[1403] = 1577863182495ll;
ans[1404] = 3155726364990ll;
ans[1405] = 6038417951903ll;
ans[1406] = 2166507138407ll;
ans[1407] = 4025611967935ll;
ans[1408] = 1444338092271ll;
ans[1409] = 2813538212167ll;
ans[1410] = 5367482623913ll;
ans[1411] = 1899148184679ll;
ans[1412] = 3578321749275ll;
ans[1413] = 6894108070491ll;
ans[1414] = 2500922855259ll;
ans[1415] = 4852790810603ll;
ans[1416] = 9542191331401ll;
ans[1417] = 3235193873735ll;
ans[1418] = 6470387747470ll;
ans[1419] = 2156795915823ll;
ans[1420] = 4313591831646ll;
ans[1421] = 8627183663292ll;
ans[1422] = 16341589500423ll;
ans[1423] = 5751455775529ll;
ans[1424] = 11473232956843ll;
ans[1425] = 4057619222183ll;
ans[1426] = 7668607700705ll;
ans[1427] = 2705079481455ll;
ans[1428] = 5112405133803ll;
ans[1429] = 10073053519207ll;
ans[1430] = 19367809778279ll;
ans[1431] = 7025912218889ll;
ans[1432] = 12911873185519ll;
ans[1433] = 4683941479259ll;
ans[1434] = 9367882958518ll;
ans[1435] = 3122627652839ll;
ans[1436] = 6245255305678ll;
ans[1437] = 2081751768559ll;
ans[1438] = 4163503537118ll;
ans[1439] = 8327007074236ll;
ans[1440] = 2775669024745ll;
ans[1441] = 5551338049490ll;
ans[1442] = 10755096863359ll;
ans[1443] = 3700892032993ll;
ans[1444] = 7401784065986ll;
ans[1445] = 14149254874715ll;
ans[1446] = 4934522710657ll;
ans[1447] = 9432836583143ll;
ans[1448] = 18865673166286ll;
ans[1449] = 6288557722095ll;
ans[1450] = 12577115444190ll;
ans[1451] = 24182456592539ll;
ans[1452] = 8772484818945ll;
ans[1453] = 16121637728359ll;
ans[1454] = 32243275456718ll;
ans[1455] = 10858055219359ll;
ans[1456] = 21495516971145ll;
ans[1457] = 8006010325735ll;
ans[1458] = 14477406959145ll;
ans[1459] = 28898848364443ll;
ans[1460] = 10397019044679ll;
ans[1461] = 19689781812671ll;
ans[1462] = 7116453622875ll;
ans[1463] = 13126521208447ll;
ans[1464] = 26253042416894ll;
ans[1465] = 50952336524201ll;
ans[1466] = 17502028277929ll;
ans[1467] = 33968224349467ll;
ans[1468] = 67844529485951ll;
ans[1469] = 23336037703905ll;
ans[1470] = 45229686323967ll;
ans[1471] = 16429857255783ll;
ans[1472] = 31716412085113ll;
ans[1473] = 60387954399047ll;
ans[1474] = 21529079969951ll;
ans[1475] = 40258636266031ll;
ans[1476] = 14352719979967ll;
ans[1477] = 27657526167591ll;
ans[1478] = 53678181688041ll;
ans[1479] = 19136959973289ll;
ans[1480] = 37484377599999ll;
ans[1481] = 13711348536135ll;
ans[1482] = 25929167855359ll;
ans[1483] = 49168935409051ll;
ans[1484] = 95427878556519ll;
ans[1485] = 33020626679527ll;
ans[1486] = 63618585704351ll;
ans[1487] = 22175491344543ll;
ans[1488] = 42412390469567ll;
ans[1489] = 15365432803175ll;
ans[1490] = 28274926979711ll;
ans[1491] = 10243621868783ll;
ans[1492] = 18849951319807ll;
ans[1493] = 6829081245855ll;
ans[1494] = 13658162491710ll;
ans[1495] = 25133268426409ll;
ans[1496] = 50266536852818ll;
ans[1497] = 16939839048319ll;
ans[1498] = 33511024568545ll;
ans[1499] = 67022049137087ll;
ans[1500] = 22586452064425ll;
ans[1501] = 44681366091391ll;
ans[1502] = 16187451842027ll;
ans[1503] = 30115269419233ll;
ans[1504] = 10791634561351ll;
ans[1505] = 20832809002855ll;
ans[1506] = 39961633046143ll;
ans[1507] = 13888604532735ll;
ans[1508] = 26769128372651ll;
ans[1509] = 53282177394857ll;
ans[1510] = 17846085581767ll;
ans[1511] = 35521451596571ll;
ans[1512] = 71042903193142ll;
ans[1513] = 23680967731047ll;
ans[1514] = 47361935462094ll;
ans[1515] = 94143454480635ll;
ans[1516] = 31726374367585ll;
ans[1517] = 63149247282793ll;
ans[1518] = 21947424446791ll;
ans[1519] = 42301832490113ll;
ans[1520] = 84198996377057ll;
ans[1521] = 28201221660075ll;
ans[1522] = 56132664251371ll;
ans[1523] = 112265328502742ll;
ans[1524] = 39017643460961ll;
ans[1525] = 74843552335161ll;
ans[1526] = 26011762307307ll;
ans[1527] = 50135505173467ll;
ans[1528] = 100197749947111ll;
ans[1529] = 34678285757567ll;
ans[1530] = 66847340231289ll;
ans[1531] = 23118857171711ll;
ans[1532] = 46237714343422ll;
ans[1533] = 15412571447807ll;
ans[1534] = 30825142895614ll;
ans[1535] = 10275047631871ll;
ans[1536] = 20550095263742ll;
ans[1537] = 41100190527484ll;
ans[1538] = 13700063509161ll;
ans[1539] = 27400127018322ll;
ans[1540] = 54366979424255ll;
ans[1541] = 18951767785799ll;
ans[1542] = 36244652949503ll;
ans[1543] = 12634511857199ll;
ans[1544] = 24163101966335ll;
ans[1545] = 8423007904799ll;
ans[1546] = 16108734644223ll;
ans[1547] = 5615338603199ll;
ans[1548] = 11230677206398ll;
ans[1549] = 3743559068799ll;
ans[1550] = 7487118137598ll;
ans[1551] = 14974236275196ll;
ans[1552] = 28637750478619ll;
ans[1553] = 9982824183465ll;
ans[1554] = 19965648366929ll;
ans[1555] = 38183667304825ll;
ans[1556] = 13310432244619ll;
ans[1557] = 26620864489238ll;
ans[1558] = 50911556406433ll;
ans[1559] = 17747242992825ll;
ans[1560] = 35494485985650ll;
ans[1561] = 11831495328551ll;
ans[1562] = 23662990657102ll;
ans[1563] = 7887663552367ll;
ans[1564] = 15775327104734ll;
ans[1565] = 31550654209467ll;
ans[1566] = 10516884736489ll;
ans[1567] = 21033769472978ll;
ans[1568] = 42067538945956ll;
ans[1569] = 14022512981985ll;
ans[1570] = 28045025963970ll;
ans[1571] = 56090051927940ll;
ans[1572] = 105998886176159ll;
ans[1573] = 37393367951961ll;
ans[1574] = 70665924117439ll;
ans[1575] = 141331848234878ll;
ans[1576] = 49857823935947ll;
ans[1577] = 94221232156585ll;
ans[1578] = 33238549290631ll;
ans[1579] = 65934756507167ll;
ans[1580] = 125628309542113ll;
ans[1581] = 43956504338111ll;
ans[1582] = 85409110527847ll;
ans[1583] = 29304336225407ll;
ans[1584] = 58608672450814ll;
ans[1585] = 19536224150271ll;
ans[1586] = 39072448300542ll;
ans[1587] = 75939872045551ll;
ans[1588] = 26262557464201ll;
ans[1589] = 52096597734057ll;
ans[1590] = 101253162727401ll;
ans[1591] = 35016743285601ll;
ans[1592] = 67510019129447ll;
ans[1593] = 135020038258894ll;
ans[1594] = 45006679419631ll;
ans[1595] = 90013358839262ll;
ans[1596] = 30540204941055ll;
ans[1597] = 60008905892841ll;
ans[1598] = 120017811785682ll;
ans[1599] = 41501325375527ll;
ans[1600] = 80774335420583ll;
ans[1601] = 27667550250351ll;
ans[1602] = 53849556947055ll;
ans[1603] = 106156882866591ll;
ans[1604] = 212313765733182ll;
ans[1605] = 71121666243367ll;
ans[1606] = 142243332486734ll;
ans[1607] = 283085020977577ll;
ans[1608] = 94828888324489ll;
ans[1609] = 189657776648978ll;
ans[1610] = 373181914983915ll;
ans[1611] = 126438517765985ll;
ans[1612] = 251320740690415ll;
ans[1613] = 84292345177323ll;
ans[1614] = 168584690354646ll;
ans[1615] = 58355901374591ll;
ans[1616] = 113460794884329ll;
ans[1617] = 38903934249727ll;
ans[1618] = 77807868499454ll;
ans[1619] = 148930809298023ll;
ans[1620] = 51871912332969ll;
ans[1621] = 99902038728679ll;
ans[1622] = 199804077457358ll;
ans[1623] = 390421812010431ll;
ans[1624] = 133202718304905ll;
ans[1625] = 265679811299327ll;
ans[1626] = 91369594184007ll;
ans[1627] = 177119874199551ll;
ans[1628] = 342089210933743ll;
ans[1629] = 118575517178183ll;
ans[1630] = 237151034356366ll;
ans[1631] = 79050344785455ll;
ans[1632] = 158100689570910ll;
ans[1633] = 304079298607771ll;
ans[1634] = 109293905820905ll;
ans[1635] = 210685906562287ll;
ans[1636] = 72862603880603ll;
ans[1637] = 145574161177199ll;
ans[1638] = 48575069253735ll;
ans[1639] = 97049440784799ll;
ans[1640] = 187276361388699ll;
ans[1641] = 360909513188911ll;
ans[1642] = 126963969213599ll;
ans[1643] = 249473403830319ll;
ans[1644] = 84642646142399ll;
ans[1645] = 169285292284798ll;
ans[1646] = 56428430761599ll;
ans[1647] = 112856861523198ll;
ans[1648] = 222078334870523ll;
ans[1649] = 76760603265161ll;
ans[1650] = 148052223247015ll;
ans[1651] = 51173735510107ll;
ans[1652] = 100317210242843ll;
ans[1653] = 197402964329353ll;
ans[1654] = 66878140161895ll;
ans[1655] = 133756280323790ll;
ans[1656] = 263203952439137ll;
ans[1657] = 89170853549193ll;
ans[1658] = 175469301626091ll;
ans[1659] = 60650353197163ll;
ans[1660] = 121300706394326ll;
ans[1661] = 237788942797849ll;
ans[1662] = 80867137596217ll;
ans[1663] = 161566634945703ll;
ans[1664] = 311945425113051ll;
ans[1665] = 107822850128289ll;
ans[1666] = 211367949153643ll;
ans[1667] = 418005205297977ll;
ans[1668] = 809550297759591ll;
ans[1669] = 281823932204857ll;
ans[1670] = 563647864409714ll;
ans[1671] = 1091118206337191ll;
ans[1672] = 375765242939809ll;
ans[1673] = 727412137558127ll;
ans[1674] = 255315176210523ll;
ans[1675] = 484941425038751ll;
ans[1676] = 969882850077502ll;
ans[1677] = 323294283359167ll;
ans[1678] = 646588566718334ll;
ans[1679] = 1293177133436668ll;
ans[1680] = 431059044478889ll;
ans[1681] = 862118088957778ll;
ans[1682] = 287372696319259ll;
ans[1683] = 574745392638518ll;
ans[1684] = 1149490785277036ll;
ans[1685] = 383163595092345ll;
ans[1686] = 766327190184690ll;
ans[1687] = 1516194796352667ll;
ans[1688] = 522912582128111ll;
ans[1689] = 1021769586912921ll;
ans[1690] = 348608388085407ll;
ans[1691] = 689536100292859ll;
ans[1692] = 1362359449217227ll;
ans[1693] = 478672174364191ll;
ans[1694] = 919381467057145ll;
ans[1695] = 1815952419179239ll;
ans[1696] = 615595064708335ll;
ans[1697] = 1210986177081979ll;
ans[1698] = 2421269892238985ll;
ans[1699] = 820793419611113ll;
ans[1700] = 1614179928159323ll;
ans[1701] = 547195613074075ll;
ans[1702] = 1076119952106215ll;
ans[1703] = 2080187239122687ll;
ans[1704] = 717413301404143ll;
ans[1705] = 1434826602808286ll;
ans[1706] = 495078915855807ll;
ans[1707] = 956551068538857ll;
ans[1708] = 1913102137077714ll;
ans[1709] = 672373534360667ll;
ans[1710] = 1275771445814759ll;
ans[1711] = 448249022907111ll;
ans[1712] = 850514297209839ll;
ans[1713] = 1701028594419678ll;
ans[1714] = 576379505929575ll;
ans[1715] = 1147930647482415ll;
ans[1716] = 390534567227295ll;
ans[1717] = 767377252201287ll;
ans[1718] = 1525579734171815ll;
ans[1719] = 2933495759934703ll;
ans[1720] = 1017053156114543ll;
ans[1721] = 2034106312229086ll;
ans[1722] = 678035437409695ll;
ans[1723] = 1356070874819390ll;
ans[1724] = 2687265553316295ll;
ans[1725] = 904047249879593ll;
ans[1726] = 1808094499759186ll;
ans[1727] = 602698166586395ll;
ans[1728] = 1205396333172790ll;
ans[1729] = 401798777724263ll;
ans[1730] = 803597555448526ll;
ans[1731] = 267865851816175ll;
ans[1732] = 535731703632350ll;
ans[1733] = 1071463407264700ll;
ans[1734] = 357154469088233ll;
ans[1735] = 714308938176466ll;
ans[1736] = 238102979392155ll;
ans[1737] = 476205958784310ll;
ans[1738] = 952411917568620ll;
ans[1739] = 1883039384641307ll;
ans[1740] = 634941278379081ll;
ans[1741] = 1255359589760871ll;
ans[1742] = 2510719179521742ll;
ans[1743] = 846588371172107ll;
ans[1744] = 1676012354611647ll;
ans[1745] = 564392247448071ll;
ans[1746] = 1128784494896142ll;
ans[1747] = 385283153999087ll;
ans[1748] = 770566307998174ll;
ans[1749] = 256855435999391ll;
ans[1750] = 513710871998782ll;
ans[1751] = 171236957332927ll;
ans[1752] = 342473914665854ll;
ans[1753] = 684947829331708ll;
ans[1754] = 228315943110569ll;
ans[1755] = 456631886221138ll;
ans[1756] = 152210628740379ll;
ans[1757] = 304421257480758ll;
ans[1758] = 608842514961516ll;
ans[1759] = 1168778549494463ll;
ans[1760] = 405895009974345ll;
ans[1761] = 779185699662975ll;
ans[1762] = 1558371399325950ll;
ans[1763] = 541193346632459ll;
ans[1764] = 1082386693264918ll;
ans[1765] = 360795564421639ll;
ans[1766] = 721591128843278ll;
ans[1767] = 1385219021623067ll;
ans[1768] = 481060752562185ll;
ans[1769] = 923479347748711ll;
ans[1770] = 1846958695497422ll;
ans[1771] = 671458716610089ll;
ans[1772] = 1231305796998281ll;
ans[1773] = 2462611593996562ll;
ans[1774] = 820870531332187ll;
ans[1775] = 1641741062664374ll;
ans[1776] = 3275533932696303ll;
ans[1777] = 1094494041776249ll;
ans[1778] = 2188988083552498ll;
ans[1779] = 729662694517499ll;
ans[1780] = 1459325389034998ll;
ans[1781] = 486441796344999ll;
ans[1782] = 972883592689998ll;
ans[1783] = 353690188173215ll;
ans[1784] = 707380376346430ll;
ans[1785] = 235793458782143ll;
ans[1786] = 471586917564286ll;
ans[1787] = 157195639188095ll;
ans[1788] = 314391278376190ll;
ans[1789] = 104797092792063ll;
ans[1790] = 209594185584126ll;
ans[1791] = 419188371168252ll;
ans[1792] = 817071831439871ll;
ans[1793] = 279458914112169ll;
ans[1794] = 544714554293247ll;
ans[1795] = 1089429108586494ll;
ans[1796] = 372611885482891ll;
ans[1797] = 745223770965782ll;
ans[1798] = 1398823788852327ll;
ans[1799] = 496815847310521ll;
ans[1800] = 949171704250607ll;
ans[1801] = 1898343408501214ll;
ans[1802] = 632781136167071ll;
ans[1803] = 1265562272334142ll;
ans[1804] = 421854090778047ll;
ans[1805] = 843708181556094ll;
ans[1806] = 1687416363112188ll;
ans[1807] = 573855662136095ll;
ans[1808] = 1124944242074793ll;
ans[1809] = 382570441424063ll;
ans[1810] = 765140882848126ll;
ans[1811] = 255046960949375ll;
ans[1812] = 510093921898750ll;
ans[1813] = 170031307299583ll;
ans[1814] = 340062614599166ll;
ans[1815] = 680125229198332ll;
ans[1816] = 226708409732777ll;
ans[1817] = 453416819465554ll;
ans[1818] = 151138939821851ll;
ans[1819] = 302277879643702ll;
ans[1820] = 100759293214567ll;
ans[1821] = 201518586429134ll;
ans[1822] = 403037172858268ll;
ans[1823] = 134345724286089ll;
ans[1824] = 268691448572178ll;
ans[1825] = 537382897144356ll;
ans[1826] = 1074765794288712ll;
ans[1827] = 358255264762905ll;
ans[1828] = 716510529525809ll;
ans[1829] = 1433021059051618ll;
ans[1830] = 477673686350539ll;
ans[1831] = 955347372701078ll;
ans[1832] = 1910694745402156ll;
ans[1833] = 636898248467385ll;
ans[1834] = 1273796496934770ll;
ans[1835] = 424598832311591ll;
ans[1836] = 849197664623182ll;
ans[1837] = 283065888207727ll;
ans[1838] = 566131776415454ll;
ans[1839] = 1132263552830907ll;
ans[1840] = 377421184276969ll;
ans[1841] = 754842368553938ll;
ans[1842] = 1509684737107876ll;
ans[1843] = 503228245702625ll;
ans[1844] = 1006456491405250ll;
ans[1845] = 335485497135083ll;
ans[1846] = 670970994270166ll;
ans[1847] = 223656998090055ll;
ans[1848] = 447313996180110ll;
ans[1849] = 894627992360220ll;
ans[1850] = 1789255984720440ll;
ans[1851] = 596418661573481ll;
ans[1852] = 1192837323146961ll;
ans[1853] = 397612441048987ll;
ans[1854] = 795224882097974ll;
ans[1855] = 1590449764195948ll;
ans[1856] = 530149921398649ll;
ans[1857] = 1060299842797298ll;
ans[1858] = 2120599685594596ll;
ans[1859] = 706866561864865ll;
ans[1860] = 1413733123729730ll;
ans[1861] = 2827466247459460ll;
ans[1862] = 942488749153153ll;
ans[1863] = 1884977498306306ll;
ans[1864] = 3769954996612612ll;
ans[1865] = 1256651665537537ll;
ans[1866] = 2513303331075074ll;
ans[1867] = 4799452220254971ll;
ans[1868] = 1675535554050049ll;
ans[1869] = 3351071108100098ll;
ans[1870] = 6702142216200196ll;
ans[1871] = 2234047405400065ll;
ans[1872] = 4468094810800130ll;
ans[1873] = 8577656802337051ll;
ans[1874] = 2978729873866753ll;
ans[1875] = 5764178121494247ll;
ans[1876] = 11436875736449401ll;
ans[1877] = 3971639831822337ll;
ans[1878] = 7753342150136767ll;
ans[1879] = 15168639115867563ll;
ans[1880] = 5295519775763119ll;
ans[1881] = 10264776135073183ll;
ans[1882] = 20089765945518247ll;
ans[1883] = 6891859689010459ll;
ans[1884] = 13618330978839911ll;
ans[1885] = 4834438573028383ll;
ans[1886] = 9078887319226607ll;
ans[1887] = 17865313505258175ll;
ans[1888] = 6052591546151071ll;
ans[1889] = 12105183092302142ll;
ans[1890] = 4297278731580783ll;
ans[1891] = 8070122061534761ll;
ans[1892] = 16140244123069522ll;
ans[1893] = 5380081374356507ll;
ans[1894] = 10760162748713014ll;
ans[1895] = 3586720916237671ll;
ans[1896] = 7173441832475342ll;
ans[1897] = 14279970436365415ll;
ans[1898] = 4782294554983561ll;
ans[1899] = 9564589109967122ll;
ans[1900] = 19039960581820553ll;
ans[1901] = 6376392739978081ll;
ans[1902] = 12693307054547035ll;
ans[1903] = 4320515538764287ll;
ans[1904] = 8501856986637441ll;
ans[1905] = 16924409406062713ll;
ans[1906] = 5760687385019049ll;
ans[1907] = 11335809315516591ll;
ans[1908] = 22306454539715739ll;
ans[1909] = 8204150056032103ll;
ans[1910] = 15361833026717465ll;
ans[1911] = 30087838944111489ll;
ans[1912] = 10241222017811643ll;
ans[1913] = 20482444035623151ll;
ans[1914] = 7292577827584091ll;
ans[1915] = 13931317416585193ll;
ans[1916] = 4861718551722727ll;
ans[1917] = 9529714983638895ll;
ans[1918] = 18002872838806255ll;
ans[1919] = 6482291402296969ll;
ans[1920] = 12383393259186843ll;
ans[1921] = 23884503578372399ll;
ans[1922] = 8643055203062625ll;
ans[1923] = 15923002385581599ll;
ans[1924] = 31715658300320347ll;
int t = 1;
// std::cin >> t;
for (; t > 0; t--) {
solve();
}
return 0;
}