#include using namespace std; typedef unsigned long long ll; const ll mod=(1ll<<32); const ll mmm=(1ll<<31); struct node { ll k,v; }; ll g[2500]= {1,3449999489,4005945601,658059649,2865545729,491819649,2459214593,2389242753,77431809,1493324929,1600611585,1536996737,24266241,1958221441,1228809985,2194962305,2504722433,1685182593,1142483201,4161812865,3022506497,472881793,1140304641,2941254529,1376291841,2414959745,1020947713,2626928001,1659719169,3015122561,583085825,3017506689,3671461889,2072043649,3920359681,3911664001,2915226113,3679363713,2241508097,813106049,3484652545,3340788865,3935139073,2110440833,883447297,854992513,209991425,3307374465,3500218369,315615361,3749640449,4202580353,2543704577,1521330817,1467857665,299764609,2107546625,4270812289,1753251073,4282502529,1990417921,4067765889,109526785,3064565633,1990991873,710865025,630325505,739594625,1907941889,2588717697,3114320641,1401230209,1539941377,910062721,3065218305,553178497,685663745,4063508097,281691905,2289080193,3438749697,3257792641,3152349441,2112641409,1007938049,2586557057,2885929729,4117502849,1781836801,1848474753,3576073473,3807370625,1264152065,842219137,726486785,980918145,3548524545,3661430913,2725777665,4026753409,4138660353,1514848897,782684929,4153615233,2833232897,2791081089,3285816577,1160177025,3725882881,2993833601,1443911425,3435046785,2320316417,1921779841,3645577473,2186963329,2710174209,3668560513,1099553537,1509567361,399162369,3737881729,2194447617,1201532289,3775888897,1928416897,2433965825,1061531521,4049092609,2333806721,1616781569,888238465,1017446913,457757313,3836535553,480326529,3069559809,393909377,301966593,3931436417,1414170113,1940936321,3696649985,2450306945,144918529,602544257,934357249,130578817,3355445761,472373889,403696385,1065892737,2254490625,1349098625,1903340801,759954817,935693825,3031391873,936996609,3306405761,3492696065,1022959745,1598304513,4208951681,1134236161,3712410241,3685937921,3266265985,2248922113,2308482177,2703602945,277022081,2340460033,904816257,2744940289,3629827969,1207523329,3595053185,3608623361,238455169,2943752705,1587931777,798358273,2786478977,3052854273,3272060033,2702753025,2482638209,1333501441,4151144065,530546433,3420573569,1879334913,4023857281,2670346497,1103991169,194060801,2688873089,330892033,3921499009,371319809,4239832193,1900791041,3081835905,2209785345,4180440705,2883749633,2678642561,1213163521,2309372033,3078441217,2510592385,1475095041,2720266881,2283539201,2376358785,2794253313,916831361,297716993,2074615169,674344449,992706177,1214615297,1404034945,3503976449,2746564737,537940225,163291521,2491888129,1682113153,2361332481,2446025601,1731720193,1892992129,2188498177,3755943297,1022146049,3177875073,4113078017,3891718017,161839105,1040468097,3638778113,2652023169,3244440065,3869379201,564271873,4130499457,1478687745,2873347201,3278167297,3830852993,3253190145,2146012801,2989203201,1551757185,4071653377,1486049409,3791020289,1386852737,3732750849,692130433,1187324673,3134813057,2035155969,3857896577,3566724353,2299344257,3072509441,2192086657,2137958145,2974087041,2348517377,4083308673,994666753,662747521,3956820481,740301441,4230490881,3753933697,3401124865,551672961,3054169345,3456384385,480103937,3316096641,1559342849,3863740289,3582365697,242311297,3839652097,479707521,3916648961,4013892225,1103835905,1692894081,1281627137,1544610945,1740502273,3007006081,4065908225,1223075457,1253357313,4220716929,3478231041,2847959169,3736041729,837732737,3612236289,1922968193,397294337,1246661505,4266597377,2541743233,3920690433,951209345,945020417,207990401,1220001537,4045016961,2036113409,3310317697,683835649,1736823169,3043582465,3057463937,2110866177,2415235969,3766100993,3543069825,1004799233,1583961473,4002342401,270841473,1459275521,3336640385,3550980097,1629386881,3272968449,3176978817,2210687489,3122412161,1949584129,903650177,4075105281,253623425,1582763265,610295169,352972289,1411628673,1971179265,2095587201,3727863809,2100134017,2913505537,863232385,1113551361,2117812865,4208415489,1006871425,898642945,1263338625,1359615233,2325177729,2881811969,3630352001,2755712769,321857409,2566764545,427591809,3900414209,3385518465,4047141377,43666049,297425665,2724899713,2826648577,2277248129,335355137,2433641857,2998926849,2632044161,3812876033,2310418305,67682305,906727553,1938727169,2153902465,2421522945,1194939009,3101516545,1762767745,1269187585,3295351937,2804950273,935687553,704316929,2711672449,847701761,3766302593,525584385,3537541249,1323411713,1463351681,531663361,1276664449,4030753537,2415442817,521227265,22682753,178466049,2126282113,292949505,3869236865,2450124545,394542977,3940470785,4025065601,2054467841,1313866113,2672529921,288842369,3085136641,387957633,582767617,1049175169,1045837057,1710458241,1764824577,1809770113,30209793,785074049,1722406913,2369300609,4131895553,1705445761,254188033,2526440065,264665857,4270246785,1453808641,2079861889,1112096001,3983183233,824974849,828239489,2177892097,642928513,2461327361,2865213569,3260727553,2638090625,1866572289,3694490241,4159275777,1177408385,3134350337,3114742913,377242881,354522497,1768367617,924644993,303236865,4263073665,1862264833,1217837185,3735931137,4111800705,3214715393,3792992897,1884064513,3994344321,1329425409,4153818241,3136244993,3709377921,300035585,2098986625,2996178689,3055574913,4220186625,1722138753,1262539009,1831608705,3650049,2821948033,2028966657,4131120001,334001153,902120577,799167745,1162847617,714946049,56297089,1666782977,1315399553,945158145,83150977,135518465,92481921,823310849,781355649,299014913,1587735425,148077569,1949584513,1955945729,1304866177,3013099009,3386510977,610017025,3337514881,627113985,595841153,354869505,3189387649,1378730497,1966183041,989176577,659157889,771654657,3001242753,2311611649,4135433601,2899527169,3499693697,4120848129,531986305,3266054145,3260209281,1920592129,2532391297,1669908993,2081462913,4099451649,1345387393,2204732417,4057095297,1866165505,1064615297,374230529,395845249,3609341697,1488748417,272044033,3781288065,537719041,2416460161,1696846337,1127195265,1039905537,3646423937,152343553,822174849,619607297,682345857,4027143681,2664900225,3370465025,1912833921,235018241,2159077505,501217537,2841594241,1459542529,3398347393,400472833,3267300225,3204422657,1886416001,2866904321,2988625281,973364737,1716924033,3404218113,1804242817,3154976769,2688544897,1811087617,3807793537,957997569,304984705,2181153537,208016257,2771035137,2954851457,18121985,3688486273,4097795585,1846883969,3710600961,1162975105,441985025,1074722945,172361985,1020090753,192211457,437041793,2086980353,3058506625,3147148289,4027481217,663194881,2781928833,515534337,3054780033,4289613569,4283998081,685977601,1612578945,4174975233,3068420481,3457151489,3794518657,117953281,3228836737,37794817,809337985,507155713,268952961,3111482881,1045644929,846288641,2577377153,3886954497,7145601,934025473,1362848129,2162883073,1787480705,569039617,719006593,2032909313,1890356353,3844971777,444525953,3295706625,114445953,1970560769,338079617,1454981121,553390209,3334414593,198340993,604373505,3005862529,3440239361,4118950785,542557185,2975569025,2086708481,3308647809,1068205569,261183105,3367462657,1861072769,1979992065,3251312769,2786208001,3869866369,3076590081,3154696833,141617921,543767425,4156673025,4064976001,3822300417,271383937,723947009,1485856385,742027009,2851389313,1167020033,3805945985,3584372993,3787489665,989598209,2233983617,3558077185,2878358401,4285322241,863609985,461812993,4217636225,2262930945,3788465793,2684188417,3309029249,3311032321,2217289857,1433942273,4246178177,2933332481,243722881,804715265,2532789121,928504833,1961405569,595180801,2262502785,1390190081,2874044033,604012289,3233992577,4117061633,2780311681,629883137,950964609,317858305,1478881921,471466753,3802026881,2676155393,3063395457,4222403841,2995918209,2400691713,3037558401,3091433217,2626279297,3585107969,1200044161,1172195585,2491783553,1733110273,1644493441,2558331649,2391104385,938339329,4169579649,2753547521,2122915201,999468545,4279008897,1556516609,1485889409,1715171329,1771454593,3060879617,278700417,2884121089,740557441,2770342657,2594988929,10023937,984990849,483579137,3938461057,1481487873,2303428225,294229761,4107790209,2802219009,199575681,2000967937,2901649793,3770890753,3062041217,1107499777,118713217,4186176513,2099563649,1707465985,4147588481,3846749697,1405783681,3599539969,1902047105,2551283713,779374721,2287427841,1770697089,98451969,19010177,1864770305,3552211841,581895169,3218330753,2130240769,2750297473,3800286721,1586075265,2882512641,3458594689,962365441,3510851713,3920259329,1180809601,456739329,201398913,747186945,10582913,2082081793,46324865,1751903489,4041555329,1342098945,2844302977,2438115073,187498369,2330431489,4099039361,2604495105,1131987329,550785537,3609207425,2049716993,2378728321,96801793,1173480577,572454145,3726394753,767153665,885499521,2266347265,678692737,2360514561,2543937665,2635102465,1624230273,380590593,1652501121,1477393153,2066713473,3215989761,2304830593,2886860033,1804815745,2075450881,4632193,2367209217,637210497,1052614657,3140513921,4012081409,2657538433,4241121793,2921214593,3325182721,3369505665,2849711105,3440374913,105186561,2571785601,972023297,201700993,2740700929,63051649,2701699073,1593800833,2440464641,4231911809,3542444545,3120380545,3298118401,1992137601,3292933121,285146241,817368321,1732337025,1751838209,1476705921,3386822401,3251183489,3012800513,2198765697,2215219457,2052383105,2579526145,2249998977,1396200193,2229576577,250688513,1429079169,728438017,3581437313,119928321,3829646977,10606337,1611671425,1985918977,660441217,3336345857,413919617,1352366593,310069889,1914395393,4081822593,2312911873,2577206401,4133362945,3824119169,371260929,2965556865,1201987329,3734450049,3916021761,1273794689,1508876545,3611488641,4155933185,1595560577,557736705,3253908353,889668609,3729527937,2442208513,2460382593,2505836033,3179402881,2665998081,1029584769,213174273,4038826113,1027778817,3055155585,2400291329,1811503745,1621191425,4040801153,275926017,591076481,4244909313,3785194881,2228686337,176217729,107671297,2087010177,3762278401,365600897,1893052673,3039887745,380408321,957899393,809792257,2147533697,471684097,1751786625,951530753,3503588737,3834779137,2545936001,2116941569,2611758977,1678432257,3139020929,4104698113,3565685121,2391251457,3329714817,2418506497,1869073281,1476942849,2916691073,1152007425,1615564161,3029147137,1698623105,103874305,2603831169,2551570433,3769151617,3367747841,337580417,4137853441,337015425,2152366849,3205419905,3291702273,4085789825,551372033,2416088449,4106757633,1929246337,2658404097,2063226753,2086725633,2255992961,3977169153,1945508225,1325246977,569735809,11373313,1861606273,1620995073,964115585,3444591873,1610194305,2772643329,3237805697,1190596353,989945729,283897857,2894512257,1637994753,4094501249,2543366657,4027875969,290493185,2132599681,759788545,2141602945,1241732353,3492849025,3321771521,1329333889,4290385665,3678955393,1438054401,1389742209,645191937,2489592193,3497245185,2121501313,2989726465,4018400129,708082689,3323284609,2532728065,3769085313,1459174913,498798209,3367837441,1540321153,1254227969,2036650113,998760705,1425748353,4186882561,3440546433,3814105857,3224040321,1465877505,214193281,3022611713,2438903169,1479820801,746198657,2717918977,3163977601,4027385857,540268673,2698701057,902969729,317311489,3690044033,2763631361,4044487553,3033172993,1404263553,2711383297,3797269889,3383709185,2071535233,2340630273,4254957441,1167593473,1195565185,1450045697,921256321,478466561,2869994113,4133270273,2184774529,1115001857,2598528129,1599042817,3549218177,2875872769,179840641,2235971329,518293377,1264785409,4002539649,1547761921,1480608129,375380481,980396673,3628055297,1939868545,6331393,3796987009,3980557569,1694748033,4251278849,3661049473,2403942145,543920001,23994369,371257473,2991849729,2581025153,8053249,2316219009,1247986433,3309769601,4002128897,704672897,1265992961,2528826753,3214960129,3925227137,2844542721,36870017,1740187649,3186620545,1487341825,4222507393,3671452161,2582493825,1288030977,1999510401,217492481,1911520385,2045283585,1756487041,4061883905,972373633,3557773057,3292110721,2118397953,3858694273,1329205505,2110087553,2775642625,1779221121,3748188929,2304058241,1537324033,3122562177,2023462145,3672696193,2497082881,3392423553,248665857,1719707521,1158625281,2387478657,2517440769,538732929,1615591937,4201368193,38525697,4223413121,3666656257,42830977,1200528641,3982486913,2815524353,2595442305,1507155713,3909595009,3155836929,3067940993,757080321,3803410817,191300097,1259000449,3043943169,3462607745,2310521857,1262261377,3871450369,2685859201,722241025,2876397185,3038275329,1271838593,3815065601,1605113985,343091457,3314186625,2797734401,1542052481,4174506753,21642113,1763888129,2485886081,1446292737,4077780353,512200193,4235288193,547057409,2396372865,3136311297,2293964929,1275474177,3366027649,844960257,755556993,3430216449,2490450817,2026755073,3713705089,2514990337,3863283073,2185401857,2377148033,2623436545,2988230529,1119574017,839526529,3554228481,3958933889,2922912257,3194481281,811072257,2279099265,3099122689,650751105,2782575873,2042367361,1446878721,1596944001,677478145,3047411585,2059821057,1536766081,2884387073,797938049,441655809,268890753,612041473,3682554753,686023681,1886958721,2249049345,2910000513,2591598081,1894676097,3299116801,2573916033,1662085121,90716289,3560917249,2472974721,1991125505,568720001,2833124097,2405849985,3377392641,3127360641,914410753,2171215233,1324592641,3270344321,1898417921,1567743873,4221333505,796344449,1288851713,394109313,3276354049,4093969025,3179352833,2743952257,2583294977,76989569,3073627393,4120978817,1940829697,1428981377,770348801,28895105,1147631617,3653650561,363157761,3151276417,2374145,2254703233,1650727681,401894273,2598697985,1325780097,136764673,169356673,145341953,665554561,4209876737,2252337025,1030914049,72700033,783835393,2154541441,759120385,3640857217,2542215937,3969610625,3423601665,2578764929,693757185,3201250689,233096705,980063873,3627067137,3943102337,3871180801,2938394753,2550884609,1698871681,1251625473,3957463681,1558850305,562199425,763038721,3835944065,449637633,331758977,2204093953,2372509313,3316887297,806223745,1078497281,3660800129,1369338113,1784267137,1479889409,3204522625,2995598081,3064562561,3206943745,802350209,3699373313,150816129,1763366401,547923585,3279337217,1431635841,1242798081,2239916161,1534163201,2410727809,1443912193,1382034049,2557491969,2886765441,2165382145,2067917953,1853029633,2658422145,3205881345,4096241281,3514416897,1524371329,69115905,2970710145,3045359873,3578253697,1143693825,2784965249,244531969,28808065,1933321217,3337680001,3500541185,3559609729,2236671489,132560513,4022126337,1084430209,1852418049,1558214785,1607960833,991877505,579234305,3118348929,351685377,3080625025,2510760961,316669057,51973377,2854378881,3150704129,1541783169,507498241,111812481,2297737217,2297397377,1516933377,3241533825,4045500929,2382185089,2878952193,3452281729,3897701377,1594819713,97260801,542729601,1653011969,4028941953,1560467201,2901485441,1405073409,893290625,2772277505,1737288065,2952559105,576473729,3531365121,1143778177,1799175169,2877164673,3636403457,919629185,2038562305,3299069569,2886065921,863514497,3469393921,1640861825,1079025921,774107521,1595376129,1996182145,2308924161,450081665,510149633,4163703937,2079466753,3985077633,12387841,3647133313,189327105,2587834241,4195731457,245143681,732145921,351992193,4268919297,2346343041,3506596609,1371192193,30624769,1159470209,4016385281,1149140353,4164423169,778165889,2060185345,3779477377,3584086017,1001103489,1731637505,470942081,2383254017,1626956417,2829415169,3907109761,360600577,2454398081,857224449,1001751937,1609766401,3282101889,4203673345,143476609,1634457601,3908741249,4077500673,1130957185,233347585,4132989569,277379841,3762867073,1500077057,3753520257,1191918849,3542912385,938352129,2569006721,2324823809,269766529,2641813505,378122369,3474768129,2332037505,2114167297,1274507905,145457921,938464129,3449054209,761869441,725501185,182687105,2150180353,2933847681,718604033,4158347137,2311186433,3294148737,4218407169,4074183041,3730745857,1641446017,2433649409,4023835521,1912564737,2069380225,3752938753,3805977985,950283777,81657473,3679981313,3219283841,642576385,4066885761,2013450497,2062426497,788115969,938836609,2846987009,134079361,1185575937,3381085313,1684296961,1527883137,1633629697,2602370689,2619021057,1747543937,1930950657,2696333441,1154865409,591735169,1876212225,3461646977,1385470721,2154097537,1268087809,402017409,3109510401,1938337153,4200218113,1906052737,1830690561,4038094721,1881341953,3477459073,1642651905,3957076353,2700067329,619942529,2344067841,1493955457,2160100353,1722111105,3733611777,742372737,60114433,2287670913,1314989825,1501001601,493750273,2115295361,3476809985,3568515457,3259681281,1003657857,1427811073,2448620417,3861613569,3046399105,3556601089,2234957185,2098220545,3747225217,1071918849,2726199169,2063142913,2904809601,2362372353,3721019777,3555054081,317825665,2931667713,723125121,2077660161,79914113,2578478337,2121123201,1724601857,1989748353,1101477633,3418720129,2294552577,1551034497,2594306305,119622017,3586185729,2857413249,2560670465,612436865,1103207425,1412590721,799243521,400870785,3234225665,1310207617,1403666177,3578564481,1187979265,2348937345,4172611841,1354256769,3353076225,32486017,314819329,2116555649,938255361,2749461633,2513863937,1369167233,2332124673,1708603009,1978484481,3205732225,3038390273,1003550849,2802321665,3129956737,2855725569,432978561,489081601,940514177,1582803969,4090526849,3427372289,731045249,3313266177,3184934529,2825932545,2300223361,3550818305,1809842305,2778403073,1151754625,2094133761,4058890881,3083457281,1379279745,3036853249,1140819073,3539768577,2781472129,1882682881,1444234881,3946010369,862037889,2725263361,472844417,4100856065,4009585025,1068300801,2320288385,3802979073,3432852353,1005435905,2490272897,2851052801,3225480577,2335342081,781471361,1043750657,3186143105,561725441,1287524481,2474713345,3113513345,4073193985,3807105665,2647646977,2806264705,4078486529,3843921025,1361224961,2063070593,376276481,1196643969,2709088001,682604417,1355171841,4253882497,2194942209,2758506881,2518878721,4224375425,3912428289,3794484097,3666070529,906796161,3365252353,3589209473,300453377,2689752705,352087809,1941356417,810635265,781983873,3261542657,2944565633,700322305,3572097665,3302355713,2102543233,4063155201,2268832897,273200385,3508929921,2107872769,965830273,2562684673,2667431809,3223083009,3756730497,1379547393,3671689601,2912492033,1850272385,817429249,2025409409,974773249,3635063937,675003649,1822231937,1503567361,319843969,750944001,2860830593,2580481,293220481,843923713,644911489,565453313,3353866881,752616193,3563082625,2990859265,710521985,275694849,2824082817,2782504449,751793793,3506800385,2521552769,4034029569,3276355713,1654671617,2454165889,2249140737,3787913857,3107916545,2420595585,1521478657,2085141633,3370241281,2219515265,1649716737,2261679745,2240319233,1649598337,2432528385,4116201601,3811791105,509518209,3668587009,3152413313,3588363009,2892915585,861598721,3463955585,1368708353,8529281,2400171521,554534529,1246467841,244967297,3788011521,2812758145,3020314881,3400903041,528824833,1447365249,2193955585,685075329,1011219457,551996545,2861030657,486092161,738901505,4220292737,525246209,2602626945,3805511681,3660992641,3575210241,2538385793,1419788801,2967736961,3219661569,92042113,1970340865,1939199105,3552240897,3652203905,960873985,374052481,76654337,132642689,2485028865,2365937793,1181509889,2216933761,2046511617,3418561153,2370513665,1113815937,3738962945,3330595969,3442339073,916929921,3066088961,1900715649,4195659521,1424949121,4121530369,3222560897,134181121,2436546945,2408993281,2799837825,3941479169,3750396801,2022118401,431219841,2531325185,870204801,2759579137,210347649,4292327169,2184578945,125081601,1935894657,433223937,3197225345,2507233793,1111566977,3637590785,3706817409,1114774529,1831005313,819199233,3512028545,41344513,3892883073,366657281,2411532161,3380584449,2800906369,2078638337,204001665,2341233153,2648715905,1458848513,983077761,1016931329,3234985089,2600928513,252466561,3501319681,63420033,1008584449,2105808769,1003137025,1522628737,775457025,2046810497,1910991361,3116317313,1700219649,4169112449,1728588801,348191873,3581545729,3976420737,254602753,1606860417,1923141377,1267408769,1582673921,2396029057,818647297,135717249,1216508417,2514371201,66736897,380019585,3249746945,1760560257,3761050881,1798989185,3186095617,4228236929,3110328065,4191299457,824227841,1126140033,2208209153,3060656513,257784321,842877569,853367553,2500701057,1285438465,3177122945,3139443969,2310106497,3705863681,3632582273,275177217,2287546241,3022766081,2007928961,649175297,2231693697,3329786369,2396803713,4060111617,1941222273,130630657,302912641,1716724993,1214805377,1813906945,4114863745,2007623425,4146083713,3883321345,746428545,436513025,1943796097,1842579969,2881182337,1097034497,2996550529,4080290817,1727863937,3787861249,2808053121,1805192705,1380114049,4012699393,1176977281,3405893633,1636606081,1570222337,2196963713,91132417,2296013441,554070785,1371718529,249517057,3157009537,762918145,2794882433,3679720961,4018267777,1995437825,1970161537,1590482945,383494273,4050303233,2991196545,2370411009,641297025,2431220481,1361693569,1523211265,295382145,1231830273,1175293313,3142524417,3439390337,250806017,2230669185,2732056577,1282060417,3581788417,31527297,90481153,2212000385,2433516289,2966475649,3606406145,1732916353,899630337,2244253057,193603073,3938449025,3073771265,1958500225,2535647233,37337217,164677889,1907890561,1841277441,2713156225,560958209,1891097473,2204134401,3174644865,4061285633,1706794369,3422891521,1220476545,1874398977,1153654657,1001254913,944291969,2388906241,30351745,3327832577,2144764545,1108513537,2430526337,1611363329,325600385,2126861569,3857884545,4240455169,3875407489,947656449,4111099777,2423846913,4002924673,1664538881,2988845441,255179265,506825345,4076182273,289794945,1828092929,1775717505,3686292737,107588993,2646294017,3313307265,293543681,2240900993,2508455937,623300737,2286543105,2193437057,1213252097,2094305921,874029825,4058837889,2854323201,3230028929,149644545,3340809601,2935375361,3829143169,4207027969,4132992897,1255081985,3690322049,4254918913,1939093889,1907083777,2612238977,91990785,852753281,395086849,393567361,106851585,672644481,812731905,1127947905,4098174721,1197440897,2958692353,319086721,3274699009,2225815937,2336674305,2060624513,1730065153,3556443009,3040318465,1856267393,3557913857,693028225,573330945,3799656065,4261951233,2024179585,3324319745,3394496641,3640850689,3053603201,2502023681,439462529,1493285633,3579972481,2200083457,3323161729,1912896769,3401960833,2217172481,3254333057,403390209,2318241665,2351964161,31649921,1058406657,127488385,2403131905,2043720321,3676619521,923341697,2169349121,499283073,3761734913,209507713,1449289217,3786946177,1112426241,2079627137,41625601,3115448449,4117301505,2037406081,2039998977,2578430593,3985099521,4176485249,2948115457,1974566017,514493697,4000570753,2564648449,1102528129,2094092033,1308336001,688271361,4055957633,4227600641,193421697}; node Div(ll n) { if(n==1)return (node){0,1}; ll k,v; node p=Div(n/2); k=n/2+p.k; ll m=(n+1)/2; m%=mmm; ll tmp=g[m/1000000]; for(ll i=(m/1000000*1000000)+1;i<=m;i++) tmp=tmp*(2ll*i-1)%mod; v=p.v*tmp%mod; node np; np.k=k;np.v=v; return np; } ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0){x=1;y=0;return a;} else { ll r=exgcd(b,a%b,x,y); ll t=x%mod; x=y%mod; y=((t-a/b*y)%mod+mod)%mod; return r; } } ll inv(ll m,ll n) { ll x,y; exgcd(m,n,x,y); x=(x%n+n)%n; return x; } int main() { //cout<=32)printf("0\n"); else { //cout<<(1<<(k1-k2))<<' '<