#include #include #include uint64_t a[29][29] = { {26426630, 14176228, 70225397, 44568705, 999301162, 613823, 57558942, 6718464, 959574529, 8573184, 134689, 2216425, 4200522, 7203856, 69022813, 7581311, 15539364, 210227181, 2244004, 16, 2206093, 5044516, 13189336, 42558358, 8695519, 31703281, 26789, 15546355, 55241078}, {1624593, 4096, 77369616, 15054400, 66564, 528529, 496474, 5803281, 1020100, 25083945, 365267, 147456, 46444225, 31124641, 49266361, 30976, 94249, 149504965, 126493740, 268324, 17172736, 4656964, 27242468, 14175225, 34969, 1, 335241, 297493504, 22}, {163489349, 134689, 8499552, 1686714, 3910187, 1359556, 4673318, 4804864, 4243600, 20684304, 14984641, 1700416, 549799368, 10150596, 174292804, 59979027, 6682225, 701932036, 8185286, 33373729, 1089, 2310400, 746011, 2656900, 8262810, 7776048, 2665831, 228251664, 52228131}, {8847786, 1387684, 12086765, 35809765, 1372589, 15034928689, 13542866, 1079521, 7371068, 18757561, 78747876, 674041, 14055201, 30177375, 1774670, 1156, 22393459, 96179780, 22945292, 3663396, 69569752, 4835601, 3622220, 14025025, 1796519, 20116222, 270281, 25921, 4641882}, {23132378, 537822481, 16935461, 2682934, 26829, 1985682721, 31888057, 9205156, 29537021, 24453909, 2085136, 34128964, 36864, 1590121, 5825787, 9388096, 3721, 2160900, 27393512, 177936989, 24324624, 26718561, 632510440, 484416, 46494896, 1602807, 20710695, 6765201, 240912624}, {6458152, 544644, 29584, 267289, 16597476, 4225, 16702741, 14010049, 290463849, 391876, 10824100, 2815002, 75583386, 24007569, 11934592, 5564881, 37356544, 27878400, 62884230, 9891025, 10751841, 70756, 21822368, 5340721, 3385600, 15069924, 755161, 66049, 34263464}, {5289938, 59431026, 4436148, 2459909, 82318684, 135443615, 11567240, 1909924, 23438537, 6874884, 10309523, 6012304, 17306338, 16703569, 12550896, 1, 196764677, 19847025, 13270937, 912402436, 227933151, 83759104, 2127319, 109175272, 13312734, 150289362, 341673, 20861726, 16442173}, {105625, 49284, 355511025, 5329, 2832489, 135424, 266505625, 2989441, 9320809, 9991921, 147158694, 762068, 90383049, 18809569, 35074930, 28558814, 23833924, 11971600, 3013468, 91795079, 58430736, 4928400, 4, 3829849, 24542116, 62001, 9205156, 486334809, 13623481}, {189127223, 14231187, 810000, 19321, 2, 135982167, 2582788, 7119501, 17847173828676242, 320510680554088, 24500379597492841, 334679191532383085, 6735482919480050, 25933343445080586, 21581617288276224, 41614577724152196, 3597896227441156, 237585195915605692, 819992478029118938, 5757151873740873, 34435069922004544, 2639126666849761, 20697314316134544, 81401057719394436, 455170744392893683, 96265958776, 20235491812777081, 7849195739570642, 17840524156980625}, {13446889, 1476403776, 3341584, 31526786, 25172287, 1158046189, 4579600, 25614112, 18858594792906801, 97157512044087075, 8583768499201352, 51493082149240384, 438751524920563634, 58952187204511225, 980182635911571118, 10075279945981636, 242043483614867200, 1619512685727048, 987654321, 3013484410315369, 996411698904838542, 75727024186510096, 301910512736450, 15674484116928400, 768397452398157811, 19963682742652609, 83431307510937961, 723951695885999821, 1863130896000000}, {24751326, 126736, 2603, 128444901, 216225, 2563131, 6058408, 14400, 14514459050969667, 65452835104725289, 4705736451472063, 81838777463450176, 10215129739505625, 24164303213566562, 60818182376684329, 166164519662083547, 54121438461461904, 10960800704100, 197320728219753648, 53490783932878009, 13052192158008481, 3514063554328, 6586200247646464, 14357311204712004, 22392822139274596, 273691129333161620, 51318159687273924, 4294967295, 66239079090333444}, {289444, 18032320, 1375929, 9541921, 29944006, 11818835, 24285184, 1267876, 1680616261902400, 682098571722780488, 42525278968633472, 1895221345539600, 18504876111496, 4971008326922884, 34238445270232225, 70336000388259904, 17753028175440100, 61355174571854289, 119486243513795735, 43017139676983692, 115787985820277906, 37923540629626276, 85227135481523161, 384899706937321, 640502598789352953, 54976877278105225, 30148468695324736, 42583120954411682, 625274180063289}, {23256069, 166627824, 212521, 7581530, 788544, 158404, 591444, 2430481, 166489929220005075, 363678664205484500, 3893172962927616, 244292675374420285, 16516049594, 79587262356501025, 200319175346305, 5725709599469095, 909850551074439044, 29884214442716, 86106059968832281, 9052519712983, 12822709891134025, 2557629320887207, 76781391744530263, 27745041930946752, 139887330317390908, 7471053610679, 15397813751724450, 8934659158102276, 6373212089760000}, {75076, 839056, 649636, 929296, 31856709, 152631276, 1296, 1874161, 441795208155625, 87294051753326224, 23955110561676996, 3077505470622361, 38052544446336996, 39483196955179264, 17052155233289288, 838650461448390679, 63849192232536529, 33386595476480064, 20857620209805625, 11482694980044800, 22413160832037, 904498782032672, 31600666494972169, 480585181487065767, 10711320985800000, 6853331223952801, 76952279604702121, 53499522076331769, 66902225380076025}, {7284601, 40804, 6403088, 1908576, 8905675, 64451368, 32959066, 4594852, 700979222216448, 72391696405561, 249235754127863009, 18034898498972480, 214540232815821675, 10493327086311364, 1211948378541698, 63293971988192849, 79079938665518025, 30002580549000900, 20213036921669868, 440358011814681, 12142518898028738, 1317773832873, 145378292978492523, 268899993881842510, 8694488293177600, 9363491351568225, 3333969266605156, 3142515396608449, 6927987983135296}, {28875783, 63313849, 98, 497959225, 99443411, 12349867, 4583881, 236185569, 4131012615886116, 88126642124697124, 46851542330613241, 389977705427968567, 5192488383919929, 9095481533214756, 44225459404448448, 8096640288456889, 863708975349920813, 8729195724488, 128278530496733952, 38980992562576, 575715187374087, 7555995436702441, 13016829527525041, 64909617320248281, 371187618412900, 458059557857457548, 151893297101051427, 8444045934420100, 2196289721455}, {101422375, 17424, 4803047, 106777563, 66049, 1490841, 13235, 37717705, 2879563665572356, 248494562623992428, 59768428885432, 33668074851561518, 12944083456996624, 373304264186349620, 12067964591986944, 497459113230000, 51646658535216144, 385560227813799821, 56431741344023447, 14503568615186562, 20987490164877604, 44824557514641147, 21249562281111616, 22898250232735684, 687089336786186322, 93010719039717675, 37942418315930769, 9149335897857319, 6774285701990401}, {887068, 719104, 13521433, 567009, 1740944, 111325652, 160000, 1, 618817863602500, 912376554654012642, 3485714869443249, 75202055056264761, 975883560728816, 54081332683984225, 28650939147769689, 269395903678875627, 24939760786725625, 1399263898173696, 315758749752103691, 86065914704689262, 54491145232558225, 30, 34952213805837512, 1145141919893819, 93202136725531392, 36619012555787200, 49638592773434401, 34683260682611776, 891461160011827816}, {36258077, 7744262, 13121607, 241081, 43811161, 6561, 12463011, 146635284, 101142234966475125, 70369247778144676, 67054732739140800, 2181050394259796, 41992642470892096, 77860086961231, 4369026725729689, 442319349884812766, 85041307549191184, 572574447321821935, 15559475510834423, 621668740882338891, 61659251010780267, 244199158881186963, 38438769139320050, 402473450810500989, 11514303747481746, 86941720193486596, 494038417687500, 517578421606074367, 1981507943278125}, {12496430, 14641, 301948074, 3374569, 1085438916, 8094025, 25431849, 28999756, 15634300383542416, 7011729609833200, 3271575591389166, 2961134977456898, 26214160354378134, 22884291725251401, 2636061467648498, 40730155979608225, 85184600333280100, 9811779310189476, 682799486007364097, 21048509037967849, 94597344048818, 7434072567060624, 28601896405386304, 1126344009980401, 1635787795694847, 14357827881815716, 5655219729428025, 43783684710633169, 117853083392256}, {224268983, 8100, 2426935, 8221786, 39106164, 81804852, 38632446, 16085719, 289651500760801, 68976389989876356, 57509482629577104, 9569637300177529, 16241050200450248, 80629740089767696, 3247482525045858, 486027415615521983, 5305078307, 19273068647840484, 376078473239836584, 471833858297169, 759108028415330539, 168580987666223405, 11416607275983845, 1400498632087296, 818920040381264156, 47647505633683396, 67476178712103529, 885711495574548219, 7330469664258244}, {70879561, 34562641, 13579225, 4120900, 864900, 25, 14830368400, 23804641, 60397750160226675, 22616367371786881, 262514612128063743, 27323415249565681, 71853425689600, 354953931130768257, 161506726698908748, 3141592, 15352404996642328, 437827184169977451, 95903827767595575, 6692224744628361, 458073500457423692, 34175319272131041, 65283664546649124, 56646875076481600, 325704327140256980, 85580428588003584, 1015381220312209, 15513415681496769, 27541931405317128}, {541716, 1350101, 27687184, 34776788, 480304, 38664013, 6021357, 3693479076, 320510680554107, 7711426804972900, 63640521214732900, 243155991349334173, 7410280467, 798994276313222182, 14848812597335616, 346161961289200500, 3179437618706568, 188262607181153967, 8738053451459378, 480332570033640505, 319809179126721310, 21990540397558084, 8932091665293228, 5791746060804484, 327673847425552348, 16957305696848400, 71037, 7700298501747687, 654046406097561}, {4585394, 4393216, 169, 912025, 23409, 2916, 107014526, 2235025, 114514889464364387, 6444427738513303, 186137373704056428, 101, 19805185135112882, 20749448323769344, 30624752200501264, 2387988575702500, 6342404796729800, 22517554322601009, 243808716399151788, 35370913185406096, 1090525197129722, 9958513517691904, 57462737073238225, 24465581212641529, 1356919184887, 199226537104, 43622417726918416, 82548526671008836, 545262598564949}, {2514932, 2856100, 3654569, 22970664, 925190, 3949242649, 16360651, 4571044, 28445577015209778, 338531447264966017, 66104653246495504, 58335142948462864, 24853322266508450, 619367882862427888, 1635787795694847, 3838101249160582, 569777233319585974, 26281435622041800, 127080750563260160, 296370435991154627, 396399699423758925, 563098692628060687, 21845133628648445, 756929056527999348, 6939328541811, 1529582713614400, 11489535756594018, 124611992446268047, 64604841155430976}, {23717148, 1478656, 86032008, 3659753, 901237061, 155451024, 2263363952, 492884401, 34616216652321312, 138935911001462575, 1757031777164, 56309785053455241, 80127670138522, 699361563546396371, 1329535273360849, 960024969482731314, 3153897190265761, 67197727645310025, 408881930759706320, 13763018258878088, 39276911332513156, 34350353280741289, 19393374894969604, 33777763154496, 5873125849687684, 43579670220100, 645424593523264, 23972129236613538, 583767613286288014}, {483, 189888400, 950476, 56248, 20915772, 103684, 9934918, 1890625, 37132469487932641, 19094389629316875, 964440414643586376, 3996248116333225, 42304996680786225, 54526, 273079343794295695, 917653059853096840, 27235567625280400, 7924014716794225, 2290283839787638, 202109440910400, 33257762809752100, 13107080177189067, 3, 36603489333907456, 2686010748428772, 878515888582, 291263422844662922, 334188698502708405, 7992151162964224}, {17123620, 2414916, 236196, 207849889, 60516, 2637376, 48782711, 87025, 893, 204492526206016647, 542205425934485500, 474927570439200, 757359645583469827, 2181050394259444, 3074805610037, 11608214876513476, 3614048134225, 80263898822145600, 13878657083622, 39002661112555396, 28983092315164488, 19434932572737529, 854151322844516288, 85368513111356836, 29884214442763, 38134795503192976, 92462224886672368, 49412142999826929, 127697463132569643}, {235492693, 28956667, 55209494, 21233244, 27346710, 38716356, 13941653, 47524, 464643937840190647, 72335929757839609, 75449813273514436, 17540331879846724, 33110907312216845, 69339424173087601, 839245612879765668, 13789290677797452, 45243154122001924, 44734576953261001, 1019002827782088, 31691722466499481, 45050869053610000, 218571815228469132, 12303992406108488, 3491729380994449, 392367542219582771, 59975021587672324, 551, 26332309569251912, 21039442803488} }; uint64_t f (uint64_t x) { uint64_t s = 0; //for(uint64_t i=1;i*i<=x;i++){ // if(x%i==0){s^=i;} // if(i!=(x/i)){s^=(x/i);} //} if(x==0){return 0;} int t=1,c; while(x%2==0){x/=2;} for(uint64_t i=3;i*i<=x;i++){ if(x%i!=0){continue;} c=1; while(x%i==0){ x/=i; c++; } t*=c; } if(x!=1){t*=2;} return t%2; //return s; } uint64_t g (uint64_t x) { if (x%2 == 0) return 1; if (x%2 == 1) return 0; //bool t[x << 1]; //for (uint64_t i = 1; i < x; i++) { //printf("%llu : %llu %llu\n",x,i,x-i); // t[g(i) ^ g(x - i)] = 1; //} //for (uint64_t i = 0; ; i++) { // if (!t[i]) return i; //} } int main(void){ //for(int i=0;i<10;i++){ // printf("%lld\n",g(i)); //} uint64_t n,res,sig=0,a; int i; scanf("%llu",&n); res=n; for(i=0;i