#include <cstdio>
#include <tuple>
#include <iostream>
#include <numeric>
#include <span>
#include <vector>

constexpr int64_t mod = 1llu << 32;

uint64_t biao[]={1,
2630352897,965738497,3596091393,1931476993,266862593,2897215489,1232601089,3862953985,2198339585,533725185,3164078081,1499463681,4129816577,2465202177,800587777,3430940673,1766326273,101711873,2732064769,1067450369,3697803265,2033188865,368574465,2998927361,1334312961,3964665857,2300051457,635437057,3265789953,1601175553,4231528449,2566914049,902299649,3532652545,1868038145,203423745,2833776641,1169162241,3799515137,2134900737,470286337,3100639233,1436024833,4066377729,2401763329,737148929,3367501825,1702887425,38273025,2668625921,1004011521,3634364417,1969750017,305135617,2935488513,1270874113,3901227009,2236612609,571998209,3202351105,1537736705,4168089601,2503475201,838860801,3469213697,1804599297,139984897,2770337793,1105723393,3736076289,2071461889,406847489,3037200385,1372585985,4002938881,2338324481,673710081,3304062977,1639448577,4269801473,2605187073,940572673,3570925569,1906311169,241696769,2872049665,1207435265,3837788161,2173173761,508559361,3138912257,1474297857,4104650753,2440036353,775421953,3405774849,1741160449,76546049,2706898945,1042284545,3672637441,2008023041,343408641,2973761537,1309147137,3939500033,2274885633,610271233,3240624129,1576009729,4206362625,2541748225,877133825,3507486721,1842872321,178257921,2808610817,1143996417,3774349313,2109734913,445120513,3075473409,1410859009,4041211905,2376597505,711983105,3342336001,1677721601,13107201,2643460097,978845697,3609198593,1944584193,279969793,2910322689,1245708289,3876061185,2211446785,546832385,3177185281,1512570881,4142923777,2478309377,813694977,3444047873,1779433473,114819073,2745171969,1080557569,3710910465,2046296065,381681665,3012034561,1347420161,3977773057,2313158657,648544257,3278897153,1614282753,4244635649,2580021249,915406849,3545759745,1881145345,216530945,2846883841,1182269441,3812622337,2148007937,483393537,3113746433,1449132033,4079484929,2414870529,750256129,3380609025,1715994625,51380225,2681733121,1017118721,3647471617,1982857217,318242817,2948595713,1283981313,3914334209,2249719809,585105409,3215458305,1550843905,4181196801,2516582401,851968001,3482320897,1817706497,153092097,2783444993,1118830593,3749183489,2084569089,419954689,3050307585,1385693185,4016046081,2351431681,686817281,3317170177,1652555777,4282908673,2618294273,953679873,3584032769,1919418369,254803969,2885156865,1220542465,3850895361,2186280961,521666561,3152019457,1487405057,4117757953,2453143553,788529153,3418882049,1754267649,89653249,2720006145,1055391745,3685744641,2021130241,356515841,2986868737,1322254337,3952607233,2287992833,623378433,3253731329,1589116929,4219469825,2554855425,890241025,3520593921,1855979521,191365121,2821718017,1157103617,3787456513,2122842113,458227713,3088580609,1423966209,4054319105,2389704705,725090305,3355443201,1690828801,26214401,2656567297,991952897,3622305793,1957691393,293076993,2923429889,1258815489,3889168385,2224553985,559939585,3190292481,1525678081,4156030977,2491416577,826802177,3457155073,1792540673,127926273,2758279169,1093664769,3724017665,2059403265,394788865,3025141761,1360527361,3990880257,2326265857,661651457,3292004353,1627389953,4257742849,2593128449,928514049,3558866945,1894252545,229638145,2859991041,1195376641,3825729537,2161115137,496500737,3126853633,1462239233,4092592129,2427977729,763363329,3393716225,1729101825,64487425,2694840321,1030225921,3660578817,1995964417,331350017,2961702913,1297088513,3927441409,2262827009,598212609,3228565505,1563951105,4194304001,2529689601,865075201,3495428097,1830813697,166199297,2796552193,1131937793,3762290689,2097676289,433061889,3063414785,1398800385,4029153281,2364538881,699924481,3330277377,1665662977,1048577,2631401473,966787073,3597139969,1932525569,267911169,2898264065,1233649665,3864002561,2199388161,534773761,3165126657,1500512257,4130865153,2466250753,801636353,3431989249,1767374849,102760449,2733113345,1068498945,3698851841,2034237441,369623041,2999975937,1335361537,3965714433,2301100033,636485633,3266838529,1602224129,4232577025,2567962625,903348225,3533701121,1869086721,204472321,2834825217,1170210817,3800563713,2135949313,471334913,3101687809,1437073409,4067426305,2402811905,738197505,3368550401,1703936001,39321601,2669674497,1005060097,3635412993,1970798593,306184193,2936537089,1271922689,3902275585,2237661185,573046785,3203399681,1538785281,4169138177,2504523777,839909377,3470262273,1805647873,141033473,2771386369,1106771969,3737124865,2072510465,407896065,3038248961,1373634561,4003987457,2339373057,674758657,3305111553,1640497153,4270850049,2606235649,941621249,3571974145,1907359745,242745345,2873098241,1208483841,3838836737,2174222337,509607937,3139960833,1475346433,4105699329,2441084929,776470529,3406823425,1742209025,77594625,2707947521,1043333121,3673686017,2009071617,344457217,2974810113,1310195713,3940548609,2275934209,611319809,3241672705,1577058305,4207411201,2542796801,878182401,3508535297,1843920897,179306497,2809659393,1145044993,3775397889,2110783489,446169089,3076521985,1411907585,4042260481,2377646081,713031681,3343384577,1678770177,14155777,2644508673,979894273,3610247169,1945632769,281018369,2911371265,1246756865,3877109761,2212495361,547880961,3178233857,1513619457,4143972353,2479357953,814743553,3445096449,1780482049,115867649,2746220545,1081606145,3711959041,2047344641,382730241,3013083137,1348468737,3978821633,2314207233,649592833,3279945729,1615331329,4245684225,2581069825,916455425,3546808321,1882193921,217579521,2847932417,1183318017,3813670913,2149056513,484442113,3114795009,1450180609,4080533505,2415919105,751304705,3381657601,1717043201,52428801,2682781697,1018167297,3648520193,1983905793,319291393,2949644289,1285029889,3915382785,2250768385,586153985,3216506881,1551892481,4182245377,2517630977,853016577,3483369473,1818755073,154140673,2784493569,1119879169,3750232065,2085617665,421003265,3051356161,1386741761,4017094657,2352480257,687865857,3318218753,1653604353,4283957249,2619342849,954728449,3585081345,1920466945,255852545,2886205441,1221591041,3851943937,2187329537,522715137,3153068033,1488453633,4118806529,2454192129,789577729,3419930625,1755316225,90701825,2721054721,1056440321,3686793217,2022178817,357564417,2987917313,1323302913,3953655809,2289041409,624427009,3254779905,1590165505,4220518401,2555904001,891289601,3521642497,1857028097,192413697,2822766593,1158152193,3788505089,2123890689,459276289,3089629185,1425014785,4055367681,2390753281,726138881,3356491777,1691877377,27262977,2657615873,993001473,3623354369,1958739969,294125569,2924478465,1259864065,3890216961,2225602561,560988161,3191341057,1526726657,4157079553,2492465153,827850753,3458203649,1793589249,128974849,2759327745,1094713345,3725066241,2060451841,395837441,3026190337,1361575937,3991928833,2327314433,662700033,3293052929,1628438529,4258791425,2594177025,929562625,3559915521,1895301121,230686721,2861039617,1196425217,3826778113,2162163713,497549313,3127902209,1463287809,4093640705,2429026305,764411905,3394764801,1730150401,65536001,2695888897,1031274497,3661627393,1997012993,332398593,2962751489,1298137089,3928489985,2263875585,599261185,3229614081,1564999681,4195352577,2530738177,866123777,3496476673,1831862273,167247873,2797600769,1132986369,3763339265,2098724865,434110465,3064463361,1399848961,4030201857,2365587457,700973057,3331325953,1666711553,2097153,2632450049,967835649,3598188545,1933574145,268959745,2899312641,1234698241,3865051137,2200436737,535822337,3166175233,1501560833,4131913729,2467299329,802684929,3433037825,1768423425,103809025,2734161921,1069547521,3699900417,2035286017,370671617,3001024513,1336410113,3966763009,2302148609,637534209,3267887105,1603272705,4233625601,2569011201,904396801,3534749697,1870135297,205520897,2835873793,1171259393,3801612289,2136997889,472383489,3102736385,1438121985,4068474881,2403860481,739246081,3369598977,1704984577,40370177,2670723073,1006108673,3636461569,1971847169,307232769,2937585665,1272971265,3903324161,2238709761,574095361,3204448257,1539833857,4170186753,2505572353,840957953,3471310849,1806696449,142082049,2772434945,1107820545,3738173441,2073559041,408944641,3039297537,1374683137,4005036033,2340421633,675807233,3306160129,1641545729,4271898625,2607284225,942669825,3573022721,1908408321,243793921,2874146817,1209532417,3839885313,2175270913,510656513,3141009409,1476395009,4106747905,2442133505,777519105,3407872001,1743257601,78643201,2708996097,1044381697,3674734593,2010120193,345505793,2975858689,1311244289,3941597185,2276982785,612368385,3242721281,1578106881,4208459777,2543845377,879230977,3509583873,1844969473,180355073,2810707969,1146093569,3776446465,2111832065,447217665,3077570561,1412956161,4043309057,2378694657,714080257,3344433153,1679818753,15204353,2645557249,980942849,3611295745,1946681345,282066945,2912419841,1247805441,3878158337,2213543937,548929537,3179282433,1514668033,4145020929,2480406529,815792129,3446145025,1781530625,116916225,2747269121,1082654721,3713007617,2048393217,383778817,3014131713,1349517313,3979870209,2315255809,650641409,3280994305,1616379905,4246732801,2582118401,917504001,3547856897,1883242497,218628097,2848980993,1184366593,3814719489,2150105089,485490689,3115843585,1451229185,4081582081,2416967681,752353281,3382706177,1718091777,53477377,2683830273,1019215873,3649568769,1984954369,320339969,2950692865,1286078465,3916431361,2251816961,587202561,3217555457,1552941057,4183293953,2518679553,854065153,3484418049,1819803649,155189249,2785542145,1120927745,3751280641,2086666241,422051841,3052404737,1387790337,4018143233,2353528833,688914433,3319267329,1654652929,4285005825,2620391425,955777025,3586129921,1921515521,256901121,2887254017,1222639617,3852992513,2188378113,523763713,3154116609,1489502209,4119855105,2455240705,790626305,3420979201,1756364801,91750401,2722103297,1057488897,3687841793,2023227393,358612993,2988965889,1324351489,3954704385,2290089985,625475585,3255828481,1591214081,4221566977,2556952577,892338177,3522691073,1858076673,193462273,2823815169,1159200769,3789553665,2124939265,460324865,3090677761,1426063361,4056416257,2391801857,727187457,3357540353,1692925953,28311553,2658664449,994050049,3624402945,1959788545,295174145,2925527041,1260912641,3891265537,2226651137,562036737,3192389633,1527775233,4158128129,2493513729,828899329,3459252225,1794637825,130023425,2760376321,1095761921,3726114817,2061500417,396886017,3027238913,1362624513,3992977409,2328363009,663748609,3294101505,1629487105,4259840001,2595225601,930611201,3560964097,1896349697,231735297,2862088193,1197473793,3827826689,2163212289,498597889,3128950785,1464336385,4094689281,2430074881,765460481,3395813377,1731198977,66584577,2696937473,1032323073,3662675969,1998061569,333447169,2963800065,1299185665,3929538561,2264924161,600309761,3230662657,1566048257,4196401153,2531786753,867172353,3497525249,1832910849,168296449,2798649345,1134034945,3764387841,2099773441,435159041,3065511937,1400897537,4031250433,2366636033,702021633,3332374529,1667760129,3145729,2633498625,968884225,3599237121,1934622721,270008321,2900361217,1235746817,3866099713,2201485313,536870913,3167223809,1502609409,4132962305,2468347905,803733505,3434086401,1769472001,104857601,2735210497,1070596097,3700948993,2036334593,371720193,3002073089,1337458689,3967811585,2303197185,638582785,3268935681,1604321281,4234674177,2570059777,905445377,3535798273,1871183873,206569473,2836922369,1172307969,3802660865,2138046465,473432065,3103784961,1439170561,4069523457,2404909057,740294657,3370647553,1706033153,41418753,2671771649,1007157249,3637510145,1972895745,308281345,2938634241,1274019841,3904372737,2239758337,575143937,3205496833,1540882433,4171235329,2506620929,842006529,3472359425,1807745025,143130625,2773483521,1108869121,3739222017,2074607617,409993217,3040346113,1375731713,4006084609,2341470209,676855809,3307208705,1642594305,4272947201,2608332801,943718401,3574071297,1909456897,244842497,2875195393,1210580993,3840933889,2176319489,511705089,3142057985,1477443585,4107796481,2443182081,778567681,3408920577,1744306177,79691777,2710044673,1045430273,3675783169,2011168769,346554369,2976907265,1312292865,3942645761,2278031361,613416961,3243769857,1579155457,4209508353,2544893953,880279553,3510632449,1846018049,181403649,2811756545,1147142145,3777495041,2112880641,448266241,3078619137,1414004737,4044357633,2379743233,715128833,3345481729,1680867329,16252929,2646605825,981991425,3612344321,1947729921,283115521,2913468417,1248854017,3879206913,2214592513,549978113,3180331009,1515716609,4146069505,2481455105,816840705,3447193601,1782579201,117964801,2748317697,1083703297,3714056193,2049441793,384827393,3015180289,1350565889,3980918785,2316304385,651689985,3282042881,1617428481,4247781377,2583166977,918552577,3548905473,1884291073,219676673,2850029569,1185415169,3815768065,2151153665,486539265,3116892161,1452277761,4082630657,2418016257,753401857,3383754753,1719140353,54525953,2684878849,1020264449,3650617345,1986002945,321388545,2951741441,1287127041,3917479937,2252865537,588251137,3218604033,1553989633,4184342529,2519728129,855113729,3485466625,1820852225,156237825,2786590721,1121976321,3752329217,2087714817,423100417,3053453313,1388838913,4019191809,2354577409,689963009,3320315905,1655701505,4286054401,2621440001,956825601,3587178497,1922564097,257949697,2888302593,1223688193,3854041089,2189426689,524812289,3155165185,1490550785,4120903681,2456289281,791674881,3422027777,1757413377,92798977,2723151873,1058537473,3688890369,2024275969,359661569,2990014465,1325400065,3955752961,2291138561,626524161,3256877057,1592262657,4222615553,2558001153,893386753,3523739649,1859125249,194510849,2824863745,1160249345,3790602241,2125987841,461373441,3091726337,1427111937,4057464833,2392850433,728236033,3358588929,1693974529,29360129,2659713025,995098625,3625451521,1960837121,296222721,2926575617,1261961217,3892314113,2227699713,563085313,3193438209,1528823809,4159176705,2494562305,829947905,3460300801,1795686401,131072001,2761424897,1096810497,3727163393,2062548993,397934593,3028287489,1363673089,3994025985,2329411585,664797185,3295150081,1630535681,4260888577,2596274177,931659777,3562012673,1897398273,232783873,2863136769,1198522369,3828875265,2164260865,499646465,3129999361,1465384961,4095737857,2431123457,766509057,3396861953,1732247553,67633153,2697986049,1033371649,3663724545,1999110145,334495745,2964848641,1300234241,3930587137,2265972737,601358337,3231711233,1567096833,4197449729,2532835329,868220929,3498573825,1833959425,169345025,2799697921,1135083521,3765436417,2100822017,436207617,3066560513,1401946113,4032299009,2367684609,703070209,3333423105,1668808705,4194305,2634547201,969932801,3600285697,1935671297,271056897,2901409793,1236795393,3867148289,2202533889,537919489,3168272385,1503657985,4134010881,2469396481,804782081,3435134977,1770520577,105906177,2736259073,1071644673,3701997569,2037383169,372768769,3003121665,1338507265,3968860161,2304245761,639631361,3269984257,1605369857,4235722753,2571108353,906493953,3536846849,1872232449,207618049,2837970945,1173356545,3803709441,2139095041,474480641,3104833537,1440219137,4070572033,2405957633,741343233,3371696129,1707081729,42467329,2672820225,1008205825,3638558721,1973944321,309329921,2939682817,1275068417,3905421313,2240806913,576192513,3206545409,1541931009,4172283905,2507669505,843055105,3473408001,1808793601,144179201,2774532097,1109917697,3740270593,2075656193,411041793,3041394689,1376780289,4007133185,2342518785,677904385,3308257281,1643642881,4273995777,2609381377,944766977,3575119873,1910505473,245891073,2876243969,1211629569,3841982465,2177368065,512753665,3143106561,1478492161,4108845057,2444230657,779616257,3409969153,1745354753,80740353,2711093249,1046478849,3676831745,2012217345,347602945,2977955841,1313341441,3943694337,2279079937,614465537,3244818433,1580204033,4210556929,2545942529,881328129,3511681025,1847066625,182452225,2812805121,1148190721,3778543617,2113929217,449314817,3079667713,1415053313,4045406209,2380791809,716177409,3346530305,1681915905,17301505,2647654401,983040001,3613392897,1948778497,284164097,2914516993,1249902593,3880255489,2215641089,551026689,3181379585,1516765185,4147118081,2482503681,817889281,3448242177,1783627777,119013377,2749366273,1084751873,3715104769,2050490369,385875969,3016228865,1351614465,3981967361,2317352961,652738561,3283091457,1618477057,4248829953,2584215553,919601153,3549954049,1885339649,220725249,2851078145,1186463745,3816816641,2152202241,487587841,3117940737,1453326337,4083679233,2419064833,754450433,3384803329,1720188929,55574529,2685927425,1021313025,3651665921,1987051521,322437121,2952790017,1288175617,3918528513,2253914113,589299713,3219652609,1555038209,4185391105,2520776705,856162305,3486515201,1821900801,157286401,2787639297,1123024897,3753377793,2088763393,424148993,3054501889,1389887489,4020240385,2355625985,691011585,3321364481,1656750081,4287102977,2622488577,957874177,3588227073,1923612673,258998273,2889351169,1224736769,3855089665,2190475265,525860865,3156213761,1491599361,4121952257,2457337857,792723457,3423076353,1758461953,93847553,2724200449,1059586049,3689938945,2025324545,360710145,2991063041,1326448641,3956801537,2292187137,627572737,3257925633,1593311233,4223664129,2559049729,894435329,3524788225,1860173825,195559425,2825912321,1161297921,3791650817,2127036417,462422017,3092774913,1428160513,4058513409,2393899009,729284609,3359637505,1695023105,30408705,2660761601,996147201,3626500097,1961885697,297271297,2927624193,1263009793,3893362689,2228748289,564133889,3194486785,1529872385,4160225281,2495610881,830996481,3461349377,1796734977,132120577,2762473473,1097859073,3728211969,2063597569,398983169,3029336065,1364721665,3995074561,2330460161,665845761,3296198657,1631584257,4261937153,2597322753,932708353,3563061249,1898446849,233832449,2864185345,1199570945,3829923841,2165309441,500695041,3131047937,1466433537,4096786433,2432172033,767557633,3397910529,1733296129,68681729,2699034625,1034420225,3664773121,2000158721,335544321,2965897217,1301282817,3931635713,2267021313,602406913,3232759809,1568145409,4198498305,2533883905,869269505,3499622401,1835008001,170393601,2800746497,1136132097,3766484993,2101870593,437256193,3067609089,1402994689,4033347585,2368733185,704118785,3334471681,1669857281,5242881,2635595777,970981377,3601334273,1936719873,272105473,2902458369,1237843969,3868196865,2203582465,538968065,3169320961,1504706561,4135059457,2470445057,805830657,3436183553,1771569153,106954753,2737307649,1072693249,3703046145,2038431745,373817345,3004170241,1339555841,3969908737,2305294337,640679937,3271032833,1606418433,4236771329,2572156929,907542529,3537895425,1873281025,208666625,2839019521,1174405121,3804758017,2140143617,475529217,3105882113,1441267713,4071620609,2407006209,742391809,3372744705,1708130305,43515905,2673868801,1009254401,3639607297,1974992897,310378497,2940731393,1276116993,3906469889,2241855489,577241089,3207593985,1542979585,4173332481,2508718081,844103681,3474456577,1809842177,145227777,2775580673,1110966273,3741319169,2076704769,412090369,3042443265,1377828865,4008181761,2343567361,678952961,3309305857,1644691457,4275044353,2610429953,945815553,3576168449,1911554049,246939649,2877292545,1212678145,3843031041,2178416641,513802241,3144155137,1479540737,4109893633,2445279233,780664833,3411017729,1746403329,81788929,2712141825,1047527425,3677880321,2013265921,348651521,2979004417,1314390017,3944742913,2280128513,615514113,3245867009,1581252609,4211605505,2546991105,882376705,3512729601,1848115201,183500801,2813853697,1149239297,3779592193,2114977793,450363393,3080716289,1416101889,4046454785,2381840385,717225985,3347578881,1682964481,18350081,2648702977,984088577,3614441473,1949827073,285212673,2915565569,1250951169,3881304065,2216689665,552075265,3182428161,1517813761,4148166657,2483552257,818937857,3449290753,1784676353,120061953,2750414849,1085800449,3716153345,2051538945,386924545,3017277441,1352663041,3983015937,2318401537,653787137,3284140033,1619525633,4249878529,2585264129,920649729,3551002625,1886388225,221773825,2852126721,1187512321,3817865217,2153250817,488636417,3118989313,1454374913,4084727809,2420113409,755499009,3385851905,1721237505,56623105,2686976001,1022361601,3652714497,1988100097,323485697,2953838593,1289224193,3919577089,2254962689,590348289,3220701185,1556086785,4186439681,2521825281,857210881,3487563777,1822949377,158334977,2788687873,1124073473,3754426369,2089811969,425197569,3055550465,1390936065,4021288961,2356674561,692060161,3322413057,1657798657,4288151553,2623537153,958922753,3589275649,1924661249,260046849,2890399745,1225785345,3856138241,2191523841,526909441,3157262337,1492647937,4123000833,2458386433,793772033,3424124929,1759510529,94896129,2725249025,1060634625,3690987521,2026373121,361758721,2992111617,1327497217,3957850113,2293235713,628621313,3258974209,1594359809,4224712705,2560098305,895483905,3525836801,1861222401,196608001,2826960897,1162346497,3792699393,2128084993,463470593,3093823489,1429209089,4059561985,2394947585,730333185,3360686081,1696071681,31457281,2661810177,997195777,3627548673,1962934273,298319873,2928672769,1264058369,3894411265,2229796865,565182465,3195535361,1530920961,4161273857,2496659457,832045057,3462397953,1797783553,133169153,2763522049,1098907649,3729260545,2064646145,400031745,3030384641,1365770241,3996123137,2331508737,666894337,3297247233,1632632833,4262985729,2598371329,933756929,3564109825,1899495425,234881025,2865233921,1200619521,3830972417,2166358017,501743617,3132096513,1467482113,4097835009,2433220609,768606209,3398959105,1734344705,69730305,2700083201,1035468801,3665821697,2001207297,336592897,2966945793,1302331393,3932684289,2268069889,603455489,3233808385,1569193985,4199546881,2534932481,870318081,3500670977,1836056577,171442177,2801795073,1137180673,3767533569,2102919169,438304769,3068657665,1404043265,4034396161,2369781761,705167361,3335520257,1670905857,6291457,2636644353,972029953,3602382849,1937768449,273154049,2903506945,1238892545,3869245441,2204631041,540016641,3170369537,1505755137,4136108033,2471493633,806879233,3437232129,1772617729,108003329,2738356225,1073741825,3704094721,2039480321,374865921,3005218817,1340604417,3970957313,2306342913,641728513,3272081409,1607467009,4237819905,2573205505,908591105,3538944001,1874329601,209715201,2840068097,1175453697,3805806593,2141192193,476577793,3106930689,1442316289,4072669185,2408054785,743440385,3373793281,1709178881,44564481,2674917377,1010302977,3640655873,1976041473,311427073,2941779969,1277165569,3907518465,2242904065,578289665,3208642561,1544028161,4174381057,2509766657,845152257,3475505153,1810890753,146276353,2776629249,1112014849,3742367745,2077753345,413138945,3043491841,1378877441,4009230337,2344615937,680001537,3310354433,1645740033,4276092929,2611478529,946864129,3577217025,1912602625,247988225,2878341121,1213726721,3844079617,2179465217,514850817,3145203713,1480589313,4110942209,2446327809,781713409,3412066305,1747451905,82837505,2713190401,1048576001,3678928897,2014314497,349700097,2980052993,1315438593,3945791489,2281177089,616562689,3246915585,1582301185,4212654081,2548039681,883425281,3513778177,1849163777,184549377,2814902273,1150287873,3780640769,2116026369,451411969,3081764865,1417150465,4047503361,2382888961,718274561,3348627457,1684013057,19398657,2649751553,985137153,3615490049,1950875649,286261249,2916614145,1251999745,3882352641,2217738241,553123841,3183476737,1518862337,4149215233,2484600833,819986433,3450339329,1785724929,121110529,2751463425,1086849025,3717201921,2052587521,387973121,3018326017,1353711617,3984064513,2319450113,654835713,3285188609,1620574209,4250927105,2586312705,921698305,3552051201,1887436801,222822401,2853175297,1188560897,3818913793,2154299393,489684993,3120037889,1455423489,4085776385,2421161985,756547585,3386900481,1722286081,57671681,2688024577,1023410177,3653763073,1989148673,324534273,2954887169,1290272769,3920625665,2256011265,591396865,3221749761,1557135361,4187488257,2522873857,858259457,3488612353,1823997953,159383553,2789736449,1125122049,3755474945,2090860545,426246145,3056599041,1391984641,4022337537,2357723137,693108737,3323461633,1658847233,4289200129,2624585729,959971329,3590324225,1925709825,261095425,2891448321,1226833921,3857186817,2192572417,527958017,3158310913,1493696513,4124049409,2459435009,794820609,3425173505,1760559105,95944705,2726297601,1061683201,3692036097,2027421697,362807297,2993160193,1328545793,3958898689,2294284289,629669889,3260022785,1595408385,4225761281,2561146881,896532481,3526885377,1862270977,197656577,2828009473,1163395073,3793747969,2129133569,464519169,3094872065,1430257665,4060610561,2395996161,731381761,3361734657,1697120257,32505857,2662858753,998244353,3628597249,1963982849,299368449,2929721345,1265106945,3895459841,2230845441,566231041,3196583937,1531969537,4162322433,2497708033,833093633,3463446529,1798832129,134217729,2764570625,1099956225,3730309121,2065694721,401080321,3031433217,1366818817,3997171713,2332557313,667942913,3298295809,1633681409,4264034305,2599419905,934805505,3565158401,1900544001,235929601,2866282497,1201668097,3832020993,2167406593,502792193,3133145089,1468530689,4098883585,2434269185,769654785,3400007681,1735393281,70778881,2701131777,1036517377,3666870273,2002255873,337641473,2967994369,1303379969,3933732865,2269118465,604504065,3234856961,1570242561,4200595457,2535981057,871366657,3501719553,1837105153,172490753,2802843649,1138229249,3768582145,2103967745,439353345,3069706241,1405091841,4035444737,2370830337,706215937,3336568833,1671954433,7340033,2637692929,973078529,3603431425,1938817025,274202625,2904555521,1239941121,3870294017,2205679617,541065217,3171418113,1506803713,4137156609,2472542209,807927809,3438280705,1773666305,109051905,2739404801,1074790401,3705143297,2040528897,375914497,3006267393,1341652993,3972005889,2307391489,642777089,3273129985,1608515585,4238868481,2574254081,909639681,3539992577,1875378177,210763777,2841116673,1176502273,3806855169,2142240769,477626369,3107979265,1443364865,4073717761,2409103361,744488961,3374841857,1710227457,45613057,2675965953,1011351553,3641704449,1977090049,312475649,2942828545,1278214145,3908567041,2243952641,579338241,3209691137,1545076737,4175429633,2510815233,846200833,3476553729,1811939329,147324929,2777677825,1113063425,3743416321,2078801921,414187521,3044540417,1379926017,4010278913,2345664513,681050113,3311403009,1646788609,4277141505,2612527105,947912705,3578265601,1913651201,249036801,2879389697,1214775297,3845128193,2180513793,515899393,3146252289,1481637889,4111990785,2447376385,782761985,3413114881,1748500481,83886081,2714238977,1049624577,3679977473,2015363073,350748673,2981101569,1316487169,3946840065,2282225665,617611265,3247964161,1583349761,4213702657,2549088257,884473857,3514826753,1850212353,185597953,2815950849,1151336449,3781689345,2117074945,452460545,3082813441,1418199041,4048551937,2383937537,719323137,3349676033,1685061633,20447233,2650800129,986185729,3616538625,1951924225,287309825,2917662721,1253048321,3883401217,2218786817,554172417,3184525313,1519910913,4150263809,2485649409,821035009,3451387905,1786773505,122159105,2752512001,1087897601,3718250497,2053636097,389021697,3019374593,1354760193,3985113089,2320498689,655884289,3286237185,1621622785,4251975681,2587361281,922746881,3553099777,1888485377,223870977,2854223873,1189609473,3819962369,2155347969,490733569,3121086465,1456472065,4086824961,2422210561,757596161,3387949057,1723334657,58720257,2689073153,1024458753,3654811649,1990197249,325582849,2955935745,1291321345,3921674241,2257059841,592445441,3222798337,1558183937,4188536833,2523922433,859308033,3489660929,1825046529,160432129,2790785025,1126170625,3756523521,2091909121,427294721,3057647617,1393033217,4023386113,2358771713,694157313,3324510209,1659895809,4290248705,2625634305,961019905,3591372801,1926758401,262144001,2892496897,1227882497,3858235393,2193620993,529006593,3159359489,1494745089,4125097985,2460483585,795869185,3426222081,1761607681,96993281,2727346177,1062731777,3693084673,2028470273,363855873,2994208769,1329594369,3959947265,2295332865,630718465,3261071361,1596456961,4226809857,2562195457,897581057,3527933953,1863319553,198705153,2829058049,1164443649,3794796545,2130182145,465567745,3095920641,1431306241,4061659137,2397044737,732430337,3362783233,1698168833,33554433,2663907329,999292929,3629645825,1965031425,300417025,2930769921,1266155521,3896508417,2231894017,567279617,3197632513,1533018113,4163371009,2498756609,834142209,3464495105,1799880705,135266305,2765619201,1101004801,3731357697,2066743297,402128897,3032481793,1367867393,3998220289,2333605889,668991489,3299344385,1634729985,4265082881,2600468481,935854081,3566206977,1901592577,236978177,2867331073,1202716673,3833069569,2168455169,503840769,3134193665,1469579265,4099932161,2435317761,770703361,3401056257,1736441857,71827457,2702180353,1037565953,3667918849,2003304449,338690049,2969042945,1304428545,3934781441,2270167041,605552641,3235905537,1571291137,4201644033,2537029633,872415233,3502768129,1838153729,173539329,2803892225,1139277825,3769630721,2105016321,440401921,3070754817,1406140417,4036493313,2371878913,707264513,3337617409,1673003009,8388609,2638741505,974127105,3604480001,1939865601,275251201,2905604097,1240989697,3871342593,2206728193,542113793,3172466689,1507852289,4138205185,2473590785,808976385,3439329281,1774714881,110100481,2740453377,1075838977,3706191873,2041577473,376963073,3007315969,1342701569,3973054465,2308440065,643825665,3274178561,1609564161,4239917057,2575302657,910688257,3541041153,1876426753,211812353,2842165249,1177550849,3807903745,2143289345,478674945,3109027841,1444413441,4074766337,2410151937,745537537,3375890433,1711276033,46661633,2677014529,1012400129,3642753025,1978138625,313524225,2943877121,1279262721,3909615617,2245001217,580386817,3210739713,1546125313,4176478209,2511863809,847249409,3477602305,1812987905,148373505,2778726401,1114112001,3744464897,2079850497,415236097,3045588993,1380974593,4011327489,2346713089,682098689,3312451585,1647837185,4278190081,2613575681,948961281,3579314177,1914699777,250085377,2880438273,1215823873,3846176769,2181562369,516947969,3147300865,1482686465,4113039361,2448424961,783810561,3414163457,1749549057,84934657,2715287553,1050673153,3681026049,2016411649,351797249,2982150145,1317535745,3947888641,2283274241,618659841,3249012737,1584398337,4214751233,2550136833,885522433,3515875329,1851260929,186646529,2816999425,1152385025,3782737921,2118123521,453509121,3083862017,1419247617,4049600513,2384986113,720371713,3350724609,1686110209,21495809,2651848705,987234305,3617587201,1952972801,288358401,2918711297,1254096897,3884449793,2219835393,555220993,3185573889,1520959489,4151312385,2486697985,822083585,3452436481,1787822081,123207681,2753560577,1088946177,3719299073,2054684673,390070273,3020423169,1355808769,3986161665,2321547265,656932865,3287285761,1622671361,4253024257,2588409857,923795457,3554148353,1889533953,224919553,2855272449,1190658049,3821010945,2156396545,491782145,3122135041,1457520641,4087873537,2423259137,758644737,3388997633,1724383233,59768833,2690121729,1025507329,3655860225,1991245825,326631425,2956984321,1292369921,3922722817,2258108417,593494017,3223846913,1559232513,4189585409,2524971009,860356609,3490709505,1826095105,161480705,2791833601,1127219201,3757572097,2092957697,428343297,3058696193,1394081793,4024434689,2359820289,695205889,3325558785,1660944385,4291297281,2626682881,962068481,3592421377,1927806977,263192577,2893545473,1228931073,3859283969,2194669569,530055169,3160408065,1495793665,4126146561,2461532161,796917761,3427270657,1762656257,98041857,2728394753,1063780353,3694133249,2029518849,364904449,2995257345,1330642945,3960995841,2296381441,631767041,3262119937,1597505537,4227858433,2563244033,898629633,3528982529,1864368129,199753729,2830106625,1165492225,3795845121,2131230721,466616321,3096969217,1432354817,4062707713,2398093313,733478913,3363831809,1699217409,34603009,2664955905,1000341505,3630694401,1966080001,301465601,2931818497,1267204097,3897556993,2232942593,568328193,3198681089,1534066689,4164419585,2499805185,835190785,3465543681,1800929281,136314881,2766667777,1102053377,3732406273,2067791873,403177473,3033530369,1368915969,3999268865,2334654465,670040065,3300392961,1635778561,4266131457,2601517057,936902657,3567255553,1902641153,238026753,2868379649,1203765249,3834118145,2169503745,504889345,3135242241,1470627841,4100980737,2436366337,771751937,3402104833,1737490433,72876033,2703228929,1038614529,3668967425,2004353025,339738625,2970091521,1305477121,3935830017,2271215617,606601217,3236954113,1572339713,4202692609,2538078209,873463809,3503816705,1839202305,174587905,2804940801,1140326401,3770679297,2106064897,441450497,3071803393,1407188993,4037541889,2372927489,708313089,3338665985,1674051585,9437185,2639790081,975175681,3605528577,1940914177,276299777,2906652673,1242038273,3872391169,2207776769,543162369,3173515265,1508900865,4139253761,2474639361,810024961,3440377857,1775763457,111149057,2741501953,1076887553,3707240449,2042626049,378011649,3008364545,1343750145,3974103041,2309488641,644874241,3275227137,1610612737,4240965633,2576351233,911736833,3542089729,1877475329,212860929,2843213825,1178599425,3808952321,2144337921,479723521,3110076417,1445462017,4075814913,2411200513,746586113,3376939009,1712324609,47710209,2678063105,1013448705,3643801601,1979187201,314572801,2944925697,1280311297,3910664193,2246049793,581435393,3211788289,1547173889,4177526785,2512912385,848297985,3478650881,1814036481,149422081,2779774977,1115160577,3745513473,2080899073,416284673,3046637569,1382023169,4012376065,2347761665,683147265,3313500161,1648885761,4279238657,2614624257,950009857,3580362753,1915748353,251133953,2881486849,1216872449,3847225345,2182610945,517996545,3148349441,1483735041,4114087937,2449473537,784859137,3415212033,1750597633,85983233,2716336129,1051721729,3682074625,2017460225,352845825,2983198721,1318584321,3948937217,2284322817,619708417,3250061313,1585446913,4215799809,2551185409,886571009,3516923905,1852309505,187695105,2818048001,1153433601,3783786497,2119172097,454557697,3084910593,1420296193,4050649089,2386034689,721420289,3351773185,1687158785,22544385,2652897281,988282881,3618635777,1954021377,289406977,2919759873,1255145473,3885498369,2220883969,556269569,3186622465,1522008065,4152360961,2487746561,823132161,3453485057,1788870657,124256257,2754609153,1089994753,3720347649,2055733249,391118849,3021471745,1356857345,3987210241,2322595841,657981441,3288334337,1623719937,4254072833,2589458433,924844033,3555196929,1890582529,225968129,2856321025,1191706625,3822059521,2157445121,492830721,3123183617,1458569217,4088922113,2424307713,759693313,3390046209,1725431809,60817409,2691170305,1026555905,3656908801,1992294401,327680001,2958032897,1293418497,3923771393,2259156993,594542593,3224895489,1560281089,4190633985,2526019585,861405185,3491758081,1827143681,162529281,2792882177,1128267777,3758620673,2094006273,429391873,3059744769,1395130369,4025483265,2360868865,696254465,3326607361,1661992961,4292345857,2627731457,963117057,3593469953,1928855553,264241153,2894594049,1229979649,3860332545,2195718145,531103745,3161456641,1496842241,4127195137,2462580737,797966337,3428319233,1763704833,99090433,2729443329,1064828929,3695181825,2030567425,365953025,2996305921,1331691521,3962044417,2297430017,632815617,3263168513,1598554113,4228907009,2564292609,899678209,3530031105,1865416705,200802305,2831155201,1166540801,3796893697,2132279297,467664897,3098017793,1433403393,4063756289,2399141889,734527489,3364880385,1700265985,35651585,2666004481,1001390081,3631742977,1967128577,302514177,2932867073,1268252673,3898605569,2233991169,569376769,3199729665,1535115265,4165468161,2500853761,836239361,3466592257,1801977857,137363457,2767716353,1103101953,3733454849,2068840449,404226049,3034578945,1369964545,4000317441,2335703041,671088641,3301441537,1636827137,4267180033,2602565633,937951233,3568304129,1903689729,239075329,2869428225,1204813825,3835166721,2170552321,505937921,3136290817,1471676417,4102029313,2437414913,772800513,3403153409,1738539009,73924609,2704277505,1039663105,3670016001,2005401601,340787201,2971140097,1306525697,3936878593,2272264193,607649793,3238002689,1573388289,4203741185,2539126785,874512385,3504865281,1840250881,175636481,2805989377,1141374977,3771727873,2107113473,442499073,3072851969,1408237569,4038590465,2373976065,709361665,3339714561,1675100161,10485761,2640838657,976224257,3606577153,1941962753,277348353,2907701249,1243086849,3873439745,2208825345,544210945,3174563841,1509949441,4140302337,2475687937,811073537,3441426433,1776812033,112197633,2742550529,1077936129,3708289025,2043674625,379060225,3009413121,1344798721,3975151617,2310537217,645922817,3276275713,1611661313,4242014209,2577399809,912785409,3543138305,1878523905,213909505,2844262401,1179648001,3810000897,2145386497,480772097,3111124993,1446510593,4076863489,2412249089,747634689,3377987585,1713373185,48758785,2679111681,1014497281,3644850177,1980235777,315621377,2945974273,1281359873,3911712769,2247098369,582483969,3212836865,1548222465,4178575361,2513960961,849346561,3479699457,1815085057,150470657,2780823553,1116209153,3746562049,2081947649,417333249,3047686145,1383071745,4013424641,2348810241,684195841,3314548737,1649934337,4280287233,2615672833,951058433,3581411329,1916796929,252182529,2882535425,1217921025,3848273921,2183659521,519045121,3149398017,1484783617,4115136513,2450522113,785907713,3416260609,1751646209,87031809,2717384705,1052770305,3683123201,2018508801,353894401,2984247297,1319632897,3949985793,2285371393,620756993,3251109889,1586495489,4216848385,2552233985,887619585,3517972481,1853358081,188743681,2819096577,1154482177,3784835073,2120220673,455606273,3085959169,1421344769,4051697665,2387083265,722468865,3352821761,1688207361,23592961,2653945857,989331457,3619684353,1955069953,290455553,2920808449,1256194049,3886546945,2221932545,557318145,3187671041,1523056641,4153409537,2488795137,824180737,3454533633,1789919233,125304833,2755657729,1091043329,3721396225,2056781825,392167425,3022520321,1357905921,3988258817,2323644417,659030017,3289382913,1624768513,4255121409,2590507009,925892609,3556245505,1891631105,227016705,2857369601,1192755201,3823108097,2158493697,493879297,3124232193,1459617793,4089970689,2425356289,760741889,3391094785,1726480385,61865985,2692218881,1027604481,3657957377,1993342977,328728577,2959081473,1294467073,3924819969,2260205569,595591169,3225944065,1561329665,4191682561,2527068161,862453761,3492806657,1828192257,163577857,2793930753,1129316353,3759669249,2095054849,430440449,3060793345,1396178945,4026531841,2361917441,697303041,3327655937,1663041537,4293394433,2628780033,964165633,3594518529,1929904129,265289729,2895642625,1231028225,3861381121,2196766721,532152321,3162505217,1497890817,4128243713,2463629313,799014913,3429367809,1764753409,100139009,2730491905,1065877505,3696230401,2031616001,367001601,2997354497,1332740097,3963092993,2298478593,633864193,3264217089,1599602689,4229955585,2565341185,900726785,3531079681,1866465281,201850881,2832203777,1167589377,3797942273,2133327873,468713473,3099066369,1434451969,4064804865,2400190465,735576065,3365928961,1701314561,36700161,2667053057,1002438657,3632791553,1968177153,303562753,2933915649,1269301249,3899654145,2235039745,570425345,3200778241,1536163841,4166516737,2501902337,837287937,3467640833,1803026433,138412033,2768764929,1104150529,3734503425,2069889025,405274625,3035627521,1371013121,4001366017,2336751617,672137217,3302490113,1637875713,4268228609,2603614209,938999809,3569352705,1904738305,240123905,2870476801,1205862401,3836215297,2171600897,506986497,3137339393,1472724993,4103077889,2438463489,773849089,3404201985,1739587585,74973185,2705326081,1040711681,3671064577,2006450177,341835777,2972188673,1307574273,3937927169,2273312769,608698369,3239051265,1574436865,4204789761,2540175361,875560961,3505913857,1841299457,176685057,2807037953,1142423553,3772776449,2108162049,443547649,3073900545,1409286145,4039639041,2375024641,710410241,3340763137,1676148737,11534337,2641887233,977272833,3607625729,1943011329,278396929,2908749825,1244135425,3874488321,2209873921,545259521,3175612417,1510998017,4141350913,2476736513,812122113,3442475009,1777860609,113246209,2743599105,1078984705,3709337601,2044723201,380108801,3010461697,1345847297,3976200193,2311585793,646971393,3277324289,1612709889,4243062785,2578448385,913833985,3544186881,1879572481,214958081,2845310977,1180696577,3811049473,2146435073,481820673,3112173569,1447559169,4077912065,2413297665,748683265,3379036161,1714421761,49807361,2680160257,1015545857,3645898753,1981284353,316669953,2947022849,1282408449,3912761345,2248146945,583532545,3213885441,1549271041,4179623937,2515009537,850395137,3480748033,1816133633,151519233,2781872129,1117257729,3747610625,2082996225,418381825,3048734721,1384120321,4014473217,2349858817,685244417,3315597313,1650982913,4281335809,2616721409,952107009,3582459905,1917845505,253231105,2883584001,1218969601,3849322497,2184708097,520093697,3150446593,1485832193,4116185089,2451570689,786956289,3417309185,1752694785,88080385,2718433281,1053818881,3684171777,2019557377,354942977,2985295873,1320681473,3951034369,2286419969,621805569,3252158465,1587544065,4217896961,2553282561,888668161,3519021057,1854406657,189792257,2820145153,1155530753,3785883649,2121269249,456654849,3087007745,1422393345,4052746241,2388131841,723517441,3353870337,1689255937,24641537,2654994433,990380033,3620732929,1956118529,291504129,2921857025,1257242625,3887595521,2222981121,558366721,3188719617,1524105217,4154458113,2489843713,825229313,3455582209,1790967809,126353409,2756706305,1092091905,3722444801,2057830401,393216001,3023568897,1358954497,3989307393,2324692993,660078593,3290431489,1625817089,4256169985,2591555585,926941185,3557294081,1892679681,228065281,2858418177,1193803777,3824156673,2159542273,494927873,3125280769,1460666369,4091019265,2426404865,761790465,3392143361,1727528961,62914561,2693267457,1028653057,3659005953,1994391553,329777153,2960130049,1295515649,3925868545,2261254145,596639745,3226992641,1562378241,4192731137,2528116737,863502337,3493855233,1829240833,164626433,2794979329,1130364929,3760717825,2096103425,431489025,3061841921,1397227521,4027580417,2362966017,698351617,3328704513,1664090113,4294443009,2629828609,965214209,3595567105,1930952705,266338305,2896691201,1232076801,3862429697,2197815297,533200897,3163553793,1498939393,4129292289,2464677889,800063489,3430416385,1765801985,101187585,2731540481,1066926081,3697278977,2032664577,368050177,2998403073,1333788673,3964141569,2299527169,634912769,3265265665,1600651265,4231004161,2566389761,901775361,3532128257,1867513857,202899457,2833252353,1168637953,3798990849,2134376449,469762049,3100114945,1435500545,4065853441,2401239041,736624641,3366977537,1702363137,37748737,2668101633,1003487233,3633840129,1969225729,304611329,2934964225,1270349825,3900702721,2236088321,571473921,3201826817,1537212417,4167565313,2502950913,838336513,3468689409,1804075009,139460609,2769813505,1105199105,3735552001,2070937601,406323201,3036676097,1372061697,4002414593,2337800193,673185793,3303538689,1638924289,4269277185,2604662785,940048385,3570401281,1905786881,241172481,2871525377,1206910977,3837263873,2172649473,508035073,3138387969,1473773569,4104126465,2439512065,774897665,3405250561,1740636161,76021761,2706374657,1041760257,3672113153,2007498753,342884353,2973237249,1308622849,3938975745,2274361345,609746945,3240099841,1575485441,4205838337,2541223937,876609537,3506962433,1842348033,177733633,2808086529,1143472129,3773825025,2109210625,444596225,3074949121,1410334721,4040687617,2376073217,711458817,3341811713,1677197313,12582913,2642935809,978321409,3608674305,1944059905,279445505,2909798401,1245184001,3875536897,2210922497,546308097,3176660993,1512046593,4142399489,2477785089,813170689,3443523585,1778909185,114294785,2744647681,1080033281,3710386177,2045771777,381157377,3011510273,1346895873,3977248769,2312634369,648019969,3278372865,1613758465,4244111361,2579496961,914882561,3545235457,1880621057,216006657,2846359553,1181745153,3812098049,2147483649,482869249,3113222145,1448607745,4078960641,2414346241,749731841,3380084737,1715470337,50855937,2681208833,1016594433,3646947329,1982332929,317718529,2948071425,1283457025,3913809921,2249195521,584581121,3214934017,1550319617,4180672513,2516058113,851443713,3481796609,1817182209,152567809,2782920705,1118306305,3748659201,2084044801,419430401,3049783297,1385168897,4015521793,2350907393,686292993,3316645889,1652031489,4282384385,2617769985,953155585,3583508481,1918894081,254279681,2884632577,1220018177,3850371073,2185756673,521142273,3151495169,1486880769,4117233665,2452619265,788004865,3418357761,1753743361,89128961,2719481857,1054867457,3685220353,2020605953,355991553,2986344449,1321730049,3952082945,2287468545,622854145,3253207041,1588592641,4218945537,2554331137,889716737,3520069633,1855455233,190840833,2821193729,1156579329,3786932225,2122317825,457703425,3088056321,1423441921,4053794817,2389180417,724566017,3354918913,1690304513,25690113,2656043009,991428609,3621781505,1957167105,292552705,2922905601,1258291201,3888644097,2224029697,559415297,3189768193,1525153793,4155506689,2490892289,826277889,3456630785,1792016385,127401985,2757754881,1093140481,3723493377,2058878977,394264577,3024617473,1360003073,3990355969,2325741569,661127169,3291480065,1626865665,4257218561,2592604161,927989761,3558342657,1893728257,229113857,2859466753,1194852353,3825205249,2160590849,495976449,3126329345,1461714945,4092067841,2427453441,762839041,3393191937,1728577537,63963137,2694316033,1029701633,3660054529,1995440129,330825729,2961178625,1296564225,3926917121,2262302721,597688321,3228041217,1563426817,4193779713,2529165313,864550913,3494903809,1830289409,165675009,2796027905,1131413505,3761766401,2097152001,432537601,3062890497,1398276097,4028628993,2364014593,699400193,3329753089,1665138689,524289,2630877185,966262785,3596615681,1932001281,267386881,2897739777,1233125377,3863478273,2198863873,534249473,3164602369,1499987969,4130340865,2465726465,801112065,3431464961,1766850561,102236161,2732589057,1067974657,3698327553,2033713153,369098753,2999451649,1334837249,3965190145,2300575745,635961345,3266314241,1601699841,4232052737,2567438337,902823937,3533176833,1868562433,203948033,2834300929,1169686529,3800039425,2135425025,470810625,3101163521,1436549121,4066902017,2402287617,737673217,3368026113,1703411713,38797313,2669150209,1004535809,3634888705,1970274305,305659905,2936012801,1271398401,3901751297,2237136897,572522497,3202875393,1538260993,4168613889,2503999489,839385089,3469737985,1805123585,140509185,2770862081,1106247681,3736600577,2071986177,407371777,3037724673,1373110273,4003463169,2338848769,674234369,3304587265,1639972865,4270325761,2605711361,941096961,3571449857,1906835457,242221057,2872573953,1207959553,3838312449,2173698049,509083649,3139436545,1474822145,4105175041,2440560641,775946241,3406299137,1741684737,77070337,2707423233,1042808833,3673161729,2008547329,343932929,2974285825,1309671425,3940024321,2275409921,610795521,3241148417,1576534017,4206886913,2542272513,877658113,3508011009,1843396609,178782209,2809135105,1144520705,3774873601,2110259201,445644801,3075997697,1411383297,4041736193,2377121793,712507393,3342860289,1678245889,13631489,2643984385,979369985,3609722881,1945108481,280494081,2910846977,1246232577,3876585473,2211971073,547356673,3177709569,1513095169,4143448065,2478833665,814219265,3444572161,1779957761,115343361,2745696257,1081081857,3711434753,2046820353,382205953,3012558849,1347944449,3978297345,2313682945,649068545,3279421441,1614807041,4245159937,2580545537,915931137,3546284033,1881669633,217055233,2847408129,1182793729,3813146625,2148532225,483917825,3114270721,1449656321,4080009217,2415394817,750780417,3381133313,1716518913,51904513,2682257409,1017643009,3647995905,1983381505,318767105,2949120001,1284505601,3914858497,2250244097,585629697,3215982593,1551368193,4181721089,2517106689,852492289,3482845185,1818230785,153616385,2783969281,1119354881,3749707777,2085093377,420478977,3050831873,1386217473,4016570369,2351955969,687341569,3317694465,1653080065,4283432961,2618818561,954204161,3584557057,1919942657,255328257,2885681153,1221066753,3851419649,2186805249,522190849,3152543745,1487929345,4118282241,2453667841,789053441,3419406337,1754791937,90177537,2720530433,1055916033,3686268929,2021654529,357040129,2987393025,1322778625,3953131521,2288517121,623902721,3254255617,1589641217,4219994113,2555379713,890765313,3521118209,1856503809,191889409,2822242305,1157627905,3787980801,2123366401,458752001,3089104897,1424490497,4054843393,2390228993,725614593,3355967489,1691353089,26738689,2657091585,992477185,3622830081,1958215681,293601281,2923954177,1259339777,3889692673,2225078273,560463873,3190816769,1526202369,4156555265,2491940865,827326465,3457679361,1793064961,128450561,2758803457,1094189057,3724541953,2059927553,395313153,3025666049,1361051649,3991404545,2326790145,662175745,3292528641,1627914241,4258267137,2593652737,929038337,3559391233,1894776833,230162433,2860515329,1195900929,3826253825,2161639425,497025025,3127377921,1462763521,4093116417,2428502017,763887617,3394240513,1729626113,65011713,2695364609,1030750209,3661103105,1996488705,331874305,2962227201,1297612801,3927965697,2263351297,598736897,3229089793,1564475393,4194828289,2530213889,865599489,3495952385,1831337985,166723585,2797076481,1132462081,3762814977,2098200577,433586177,3063939073,1399324673,4029677569,2365063169,700448769,3330801665,1666187265,1572865,2631925761,967311361,3597664257,1933049857,268435457,2898788353,1234173953,3864526849,2199912449,535298049,3165650945,1501036545,4131389441,2466775041,802160641,3432513537,1767899137,103284737,2733637633,1069023233,3699376129,2034761729,370147329,3000500225,1335885825,3966238721,2301624321,637009921,3267362817,1602748417,4233101313,2568486913,903872513,3534225409,1869611009,204996609,2835349505,1170735105,3801088001,2136473601,471859201,3102212097,1437597697,4067950593,2403336193,738721793,3369074689,1704460289,39845889,2670198785,1005584385,3635937281,1971322881,306708481,2937061377,1272446977,3902799873,2238185473,573571073,3203923969,1539309569,4169662465,2505048065,840433665,3470786561,1806172161,141557761,2771910657,1107296257,3737649153,2073034753,408420353,3038773249,1374158849,4004511745,2339897345,675282945,3305635841,1641021441,4271374337,2606759937,942145537,3572498433,1907884033,243269633,2873622529,1209008129,3839361025,2174746625,510132225,3140485121,1475870721,4106223617,2441609217,776994817,3407347713,1742733313,78118913,2708471809,1043857409,3674210305,2009595905,344981505,2975334401,1310720001,3941072897,2276458497,611844097,3242196993,1577582593,4207935489,2543321089,878706689,3509059585,1844445185,179830785,2810183681,1145569281,3775922177,2111307777,446693377,3077046273,1412431873,4042784769,2378170369,713555969,3343908865,1679294465,14680065,2645032961,980418561,3610771457,1946157057,281542657,2911895553,1247281153,3877634049,2213019649,548405249,3178758145,1514143745,4144496641,2479882241,815267841,3445620737,1781006337,116391937,2746744833,1082130433,3712483329,2047868929,383254529,3013607425,1348993025,3979345921,2314731521,650117121,3280470017,1615855617,4246208513,2581594113,916979713,3547332609,1882718209,218103809,2848456705,1183842305,3814195201,2149580801,484966401,3115319297,1450704897,4081057793,2416443393,751828993,3382181889,1717567489,52953089,2683305985,1018691585,3649044481,1984430081,319815681,2950168577,1285554177,3915907073,2251292673,586678273,3217031169,1552416769,4182769665,2518155265,853540865,3483893761,1819279361,154664961,2785017857,1120403457,3750756353,2086141953,421527553,3051880449,1387266049,4017618945,2353004545,688390145,3318743041,1654128641,4284481537,2619867137,955252737,3585605633,1920991233,256376833,2886729729,1222115329,3852468225,2187853825,523239425,3153592321,1488977921,4119330817,2454716417,790102017,3420454913,1755840513,91226113,2721579009,1056964609,3687317505,2022703105,358088705,2988441601,1323827201,3954180097,2289565697,624951297,3255304193,1590689793,4221042689,2556428289,891813889,3522166785,1857552385,192937985,2823290881,1158676481,3789029377,2124414977,459800577,3090153473,1425539073,4055891969,2391277569,726663169,3357016065,1692401665,27787265,2658140161,993525761,3623878657,1959264257,294649857,2925002753,1260388353,3890741249,2226126849,561512449,3191865345,1527250945,4157603841,2492989441,828375041,3458727937,1794113537,129499137,2759852033,1095237633,3725590529,2060976129,396361729,3026714625,1362100225,3992453121,2327838721,663224321,3293577217,1628962817,4259315713,2594701313,930086913,3560439809,1895825409,231211009,2861563905,1196949505,3827302401,2162688001,498073601,3128426497,1463812097,4094164993,2429550593,764936193,3395289089,1730674689,66060289,2696413185,1031798785,3662151681,1997537281,332922881,2963275777,1298661377,3929014273,2264399873,599785473,3230138369,1565523969,4195876865,2531262465,866648065,3497000961,1832386561,167772161,2798125057,1133510657,3763863553,2099249153,434634753,3064987649,1400373249,4030726145,2366111745,701497345,3331850241,1667235841,2621441,2632974337,968359937,3598712833,1934098433,269484033,2899836929,1235222529,3865575425,2200961025,536346625,3166699521,1502085121,4132438017,2467823617,803209217,3433562113,1768947713,104333313,2734686209,1070071809,3700424705,2035810305,371195905,3001548801,1336934401,3967287297,2302672897,638058497,3268411393,1603796993,4234149889,2569535489,904921089,3535273985,1870659585,206045185,2836398081,1171783681,3802136577,2137522177,472907777,3103260673,1438646273,4068999169,2404384769,739770369,3370123265,1705508865,40894465,2671247361,1006632961,3636985857,1972371457,307757057,2938109953,1273495553,3903848449,2239234049,574619649,3204972545,1540358145,4170711041,2506096641,841482241,3471835137,1807220737,142606337,2772959233,1108344833,3738697729,2074083329,409468929,3039821825,1375207425,4005560321,2340945921,676331521,3306684417,1642070017,4272422913,2607808513,943194113,3573547009,1908932609,244318209,2874671105,1210056705,3840409601,2175795201,511180801,3141533697,1476919297,4107272193,2442657793,778043393,3408396289,1743781889,79167489,2709520385,1044905985,3675258881,2010644481,346030081,2976382977,1311768577,3942121473,2277507073,612892673,3243245569,1578631169,4208984065,2544369665,879755265,3510108161,1845493761,180879361,2811232257,1146617857,3776970753,2112356353,447741953,3078094849,1413480449,4043833345,2379218945,714604545,3344957441,1680343041,15728641,2646081537,981467137,3611820033,1947205633,282591233,2912944129,1248329729,3878682625,2214068225,549453825,3179806721,1515192321,4145545217,2480930817,816316417,3446669313,1782054913,117440513,2747793409,1083179009,3713531905,2048917505,384303105,3014656001,1350041601,3980394497,2315780097,651165697,3281518593,1616904193,4247257089,2582642689,918028289,3548381185,1883766785,219152385,2849505281,1184890881,3815243777,2150629377,486014977,3116367873,1451753473,4082106369,2417491969,752877569,3383230465,1718616065,54001665,2684354561,1019740161,3650093057,1985478657,320864257,2951217153,1286602753,3916955649,2252341249,587726849,3218079745,1553465345,4183818241,2519203841,854589441,3484942337,1820327937,155713537,2786066433,1121452033,3751804929,2087190529,422576129,3052929025,1388314625,4018667521,2354053121,689438721,3319791617,1655177217,4285530113,2620915713,956301313,3586654209,1922039809,257425409,2887778305,1223163905,3853516801,2188902401,524288001,3154640897,1490026497,4120379393,2455764993,791150593,3421503489,1756889089,92274689,2722627585,1058013185,3688366081,2023751681,359137281,2989490177,1324875777,3955228673,2290614273,625999873,3256352769,1591738369,4222091265,2557476865,892862465,3523215361,1858600961,193986561,2824339457,1159725057,3790077953,2125463553,460849153,3091202049,1426587649,4056940545,2392326145,727711745,3358064641,1693450241,28835841,2659188737,994574337,3624927233,1960312833,295698433,2926051329,1261436929,3891789825,2227175425,562561025,3192913921,1528299521,4158652417,2494038017,829423617,3459776513,1795162113,130547713,2760900609,1096286209,3726639105,2062024705,397410305,3027763201,1363148801,3993501697,2328887297,664272897,3294625793,1630011393,4260364289,2595749889,931135489,3561488385,1896873985,232259585,2862612481,1197998081,3828350977,2163736577,499122177,3129475073,1464860673,4095213569,2430599169,765984769,3396337665,1731723265,67108865,2697461761,1032847361,3663200257,1998585857,333971457,2964324353,1299709953,3930062849,2265448449,600834049,3231186945,1566572545,4196925441,2532311041,867696641,3498049537,1833435137,168820737,2799173633,1134559233,3764912129,2100297729,435683329,3066036225,1401421825,4031774721,2367160321,702545921,3332898817,1668284417,3670017,2634022913,969408513,3599761409,1935147009,270532609,2900885505,1236271105,3866624001,2202009601,537395201,3167748097,1503133697,4133486593,2468872193,804257793,3434610689,1769996289,105381889,2735734785,1071120385,3701473281,2036858881,372244481,3002597377,1337982977,3968335873,2303721473,639107073,3269459969,1604845569,4235198465,2570584065,905969665,3536322561,1871708161,207093761,2837446657,1172832257,3803185153,2138570753,473956353,3104309249,1439694849,4070047745,2405433345,740818945,3371171841,1706557441,41943041,2672295937,1007681537,3638034433,1973420033,308805633,2939158529,1274544129,3904897025,2240282625,575668225,3206021121,1541406721,4171759617,2507145217,842530817,3472883713,1808269313,143654913,2774007809,1109393409,3739746305,2075131905,410517505,3040870401,1376256001,4006608897,2341994497,677380097,3307732993,1643118593,4273471489,2608857089,944242689,3574595585,1909981185,245366785,2875719681,1211105281,3841458177,2176843777,512229377,3142582273,1477967873,4108320769,2443706369,779091969,3409444865,1744830465,80216065,2710568961,1045954561,3676307457,2011693057,347078657,2977431553,1312817153,3943170049,2278555649,613941249,3244294145,1579679745,4210032641,2545418241,880803841,3511156737,1846542337,181927937,2812280833,1147666433,3778019329,2113404929,448790529,3079143425,1414529025,4044881921,2380267521,715653121,3346006017,1681391617,16777217,2647130113,982515713,3612868609,1948254209,283639809,2913992705,1249378305,3879731201,2215116801,550502401,3180855297,1516240897,4146593793,2481979393,817364993,3447717889,1783103489,118489089,2748841985,1084227585,3714580481,2049966081,385351681,3015704577,1351090177,3981443073,2316828673,652214273,3282567169,1617952769,4248305665,2583691265,919076865,3549429761,1884815361,220200961,2850553857,1185939457,3816292353,2151677953,487063553,3117416449,1452802049,4083154945,2418540545,753926145,3384279041,1719664641,55050241,2685403137,1020788737,3651141633,1986527233,321912833,2952265729,1287651329,3918004225,2253389825,588775425,3219128321,1554513921,4184866817,2520252417,855638017,3485990913,1821376513,156762113,2787115009,1122500609,3752853505,2088239105,423624705,3053977601,1389363201,4019716097,2355101697,690487297,3320840193,1656225793,4286578689,2621964289,957349889,3587702785,1923088385,258473985,2888826881,1224212481,3854565377,2189950977,525336577,3155689473,1491075073,4121427969,2456813569,792199169,3422552065,1757937665,93323265,2723676161,1059061761,3689414657,2024800257,360185857,2990538753,1325924353,3956277249,2291662849,627048449,3257401345,1592786945,4223139841,2558525441,893911041,3524263937,1859649537,195035137,2825388033,1160773633,3791126529,2126512129,461897729,3092250625,1427636225,4057989121,2393374721,728760321,3359113217,1694498817,29884417,2660237313,995622913,3625975809,1961361409,296747009,2927099905,1262485505,3892838401,2228224001,563609601,3193962497,1529348097,4159700993,2495086593,830472193,3460825089,1796210689,131596289,2761949185,1097334785,3727687681,2063073281,398458881,3028811777,1364197377,3994550273,2329935873,665321473,3295674369,1631059969,4261412865,2596798465,932184065,3562536961,1897922561,233308161,2863661057,1199046657,3829399553,2164785153,500170753,3130523649,1465909249,4096262145,2431647745,767033345,3397386241,1732771841,68157441,2698510337,1033895937,3664248833,1999634433,335020033,2965372929,1300758529,3931111425,2266497025,601882625,3232235521,1567621121,4197974017,2533359617,868745217,3499098113,1834483713,169869313,2800222209,1135607809,3765960705,2101346305,436731905,3067084801,1402470401,4032823297,2368208897,703594497,3333947393,1669332993,4718593,2635071489,970457089,3600809985,1936195585,271581185,2901934081,1237319681,3867672577,2203058177,538443777,3168796673,1504182273,4134535169,2469920769,805306369,3435659265,1771044865,106430465,2736783361,1072168961,3702521857,2037907457,373293057,3003645953,1339031553,3969384449,2304770049,640155649,3270508545,1605894145,4236247041,2571632641,907018241,3537371137,1872756737,208142337,2838495233,1173880833,3804233729,2139619329,475004929,3105357825,1440743425,4071096321,2406481921,741867521,3372220417,1707606017,42991617,2673344513,1008730113,3639083009,1974468609,309854209,2940207105,1275592705,3905945601,2241331201,576716801,3207069697,1542455297,4172808193,2508193793,843579393,3473932289,1809317889,144703489,2775056385,1110441985,3740794881,2076180481,411566081,3041918977,1377304577,4007657473,2343043073,678428673,3308781569,1644167169,4274520065,2609905665,945291265,3575644161,1911029761,246415361,2876768257,1212153857,3842506753,2177892353,513277953,3143630849,1479016449,4109369345,2444754945,780140545,3410493441,1745879041,81264641,2711617537,1047003137,3677356033,2012741633,348127233,2978480129,1313865729,3944218625,2279604225,614989825,3245342721,1580728321,4211081217,2546466817,881852417,3512205313,1847590913,182976513,2813329409,1148715009,3779067905,2114453505,449839105,3080192001,1415577601,4045930497,2381316097,716701697,3347054593,1682440193,17825793,2648178689,983564289,3613917185,1949302785,284688385,2915041281,1250426881,3880779777,2216165377,551550977,3181903873,1517289473,4147642369,2483027969,818413569,3448766465,1784152065,119537665,2749890561,1085276161,3715629057,2051014657,386400257,3016753153,1352138753,3982491649,2317877249,653262849,3283615745,1619001345,4249354241,2584739841,920125441,3550478337,1885863937,221249537,2851602433,1186988033,3817340929,2152726529,488112129,3118465025,1453850625,4084203521,2419589121,754974721,3385327617,1720713217,56098817,2686451713,1021837313,3652190209,1987575809,322961409,2953314305,1288699905,3919052801,2254438401,589824001,3220176897,1555562497,4185915393,2521300993,856686593,3487039489,1822425089,157810689,2788163585,1123549185,3753902081,2089287681,424673281,3055026177,1390411777,4020764673,2356150273,691535873,3321888769,1657274369,4287627265,2623012865,958398465,3588751361,1924136961,259522561,2889875457,1225261057,3855613953,2190999553,526385153,3156738049,1492123649,4122476545,2457862145,793247745,3423600641,1758986241,94371841,2724724737,1060110337,3690463233,2025848833,361234433,2991587329,1326972929,3957325825,2292711425,628097025,3258449921,1593835521,4224188417,2559574017,894959617,3525312513,1860698113,196083713,2826436609,1161822209,3792175105,2127560705,462946305,3093299201,1428684801,4059037697,2394423297,729808897,3360161793,1695547393,30932993,2661285889,996671489,3627024385,1962409985,297795585,2928148481,1263534081,3893886977,2229272577,564658177,3195011073,1530396673,4160749569,2496135169,831520769,3461873665,1797259265,132644865,2762997761,1098383361,3728736257,2064121857,399507457,3029860353,1365245953,3995598849,2330984449,666370049,3296722945,1632108545,4262461441,2597847041,933232641,3563585537,1898971137,234356737,2864709633,1200095233,3830448129,2165833729,501219329,3131572225,1466957825,4097310721,2432696321,768081921,3398434817,1733820417,69206017,2699558913,1034944513,3665297409,2000683009,336068609,2966421505,1301807105,3932160001,2267545601,602931201,3233284097,1568669697,4199022593,2534408193,869793793,3500146689,1835532289,170917889,2801270785,1136656385,3767009281,2102394881,437780481,3068133377,1403518977,4033871873,2369257473,704643073,3334995969,1670381569,5767169,2636120065,971505665,3601858561,1937244161,272629761,2902982657,1238368257,3868721153,2204106753,539492353,3169845249,1505230849,4135583745,2470969345,806354945,3436707841,1772093441,107479041,2737831937,1073217537,3703570433,2038956033,374341633,3004694529,1340080129,3970433025,2305818625,641204225,3271557121,1606942721,4237295617,2572681217,908066817,3538419713,1873805313,209190913,2839543809,1174929409,3805282305,2140667905,476053505,3106406401,1441792001,4072144897,2407530497,742916097,3373268993,1708654593,44040193,2674393089,1009778689,3640131585,1975517185,310902785,2941255681,1276641281,3906994177,2242379777,577765377,3208118273,1543503873,4173856769,2509242369,844627969,3474980865,1810366465,145752065,2776104961,1111490561,3741843457,2077229057,412614657,3042967553,1378353153,4008706049,2344091649,679477249,3309830145,1645215745,4275568641,2610954241,946339841,3576692737,1912078337,247463937,2877816833,1213202433,3843555329,2178940929,514326529,3144679425,1480065025,4110417921,2445803521,781189121,3411542017,1746927617,82313217,2712666113,1048051713,3678404609,2013790209,349175809,2979528705,1314914305,3945267201,2280652801,616038401,3246391297,1581776897,4212129793,2547515393,882900993,3513253889,1848639489,184025089,2814377985,1149763585,3780116481,2115502081,450887681,3081240577,1416626177,4046979073,2382364673,717750273,3348103169,1683488769,18874369,2649227265,984612865,3614965761,1950351361,285736961,2916089857,1251475457,3881828353,2217213953,552599553,3182952449,1518338049,4148690945,2484076545,819462145,3449815041,1785200641,120586241,2750939137,1086324737,3716677633,2052063233,387448833,3017801729,1353187329,3983540225,2318925825,654311425,3284664321,1620049921,4250402817,2585788417,921174017,3551526913,1886912513,222298113,2852651009,1188036609,3818389505,2153775105,489160705,3119513601,1454899201,4085252097,2420637697,756023297,3386376193,1721761793,57147393,2687500289,1022885889,3653238785,1988624385,324009985,2954362881,1289748481,3920101377,2255486977,590872577,3221225473,1556611073,4186963969,2522349569,857735169,3488088065,1823473665,158859265,2789212161,1124597761,3754950657,2090336257,425721857,3056074753,1391460353,4021813249,2357198849,692584449,3322937345,1658322945,4288675841,2624061441,959447041,3589799937,1925185537,260571137,2890924033,1226309633,3856662529,2192048129,527433729,3157786625,1493172225,4123525121,2458910721,794296321,3424649217,1760034817,95420417,2725773313,1061158913,3691511809,2026897409,362283009,2992635905,1328021505,3958374401,2293760001,629145601,3259498497,1594884097,4225236993,2560622593,896008193,3526361089,1861746689,197132289,2827485185,1162870785,3793223681,2128609281,463994881,3094347777,1429733377,4060086273,2395471873,730857473,3361210369,1696595969,31981569,2662334465,997720065,3628072961,1963458561,298844161,2929197057,1264582657,3894935553,2230321153,565706753,3196059649,1531445249,4161798145,2497183745,832569345,3462922241,1798307841,133693441,2764046337,1099431937,3729784833,2065170433,400556033,3030908929,1366294529,3996647425,2332033025,667418625,3297771521,1633157121,4263510017,2598895617,934281217,3564634113,1900019713,235405313,2865758209,1201143809,3831496705,2166882305,502267905,3132620801,1468006401,4098359297,2433744897,769130497,3399483393,1734868993,70254593,2700607489,1035993089,3666345985,2001731585,337117185,2967470081,1302855681,3933208577,2268594177,603979777,3234332673,1569718273,4200071169,2535456769,870842369,3501195265,1836580865,171966465,2802319361,1137704961,3768057857,2103443457,438829057,3069181953,1404567553,4034920449,2370306049,705691649,3336044545,1671430145,6815745,2637168641,972554241,3602907137,1938292737,273678337,2904031233,1239416833,3869769729,2205155329,540540929,3170893825,1506279425,4136632321,2472017921,807403521,3437756417,1773142017,108527617,2738880513,1074266113,3704619009,2040004609,375390209,3005743105,1341128705,3971481601,2306867201,642252801,3272605697,1607991297,4238344193,2573729793,909115393,3539468289,1874853889,210239489,2840592385,1175977985,3806330881,2141716481,477102081,3107454977,1442840577,4073193473,2408579073,743964673,3374317569,1709703169,45088769,2675441665,1010827265,3641180161,1976565761,311951361,2942304257,1277689857,3908042753,2243428353,578813953,3209166849,1544552449,4174905345,2510290945,845676545,3476029441,1811415041,146800641,2777153537,1112539137,3742892033,2078277633,413663233,3044016129,1379401729,4009754625,2345140225,680525825,3310878721,1646264321,4276617217,2612002817,947388417,3577741313,1913126913,248512513,2878865409,1214251009,3844603905,2179989505,515375105,3145728001,1481113601,4111466497,2446852097,782237697,3412590593,1747976193,83361793,2713714689,1049100289,3679453185,2014838785,350224385,2980577281,1315962881,3946315777,2281701377,617086977,3247439873,1582825473,4213178369,2548563969,883949569,3514302465,1849688065,185073665,2815426561,1150812161,3781165057,2116550657,451936257,3082289153,1417674753,4048027649,2383413249,718798849,3349151745,1684537345,19922945,2650275841,985661441,3616014337,1951399937,286785537,2917138433,1252524033,3882876929,2218262529,553648129,3184001025,1519386625,4149739521,2485125121,820510721,3450863617,1786249217,121634817,2751987713,1087373313,3717726209,2053111809,388497409,3018850305,1354235905,3984588801,2319974401,655360001,3285712897,1621098497,4251451393,2586836993,922222593,3552575489,1887961089,223346689,2853699585,1189085185,3819438081,2154823681,490209281,3120562177,1455947777,4086300673,2421686273,757071873,3387424769,1722810369,58195969,2688548865,1023934465,3654287361,1989672961,325058561,2955411457,1290797057,3921149953,2256535553,591921153,3222274049,1557659649,4188012545,2523398145,858783745,3489136641,1824522241,159907841,2790260737,1125646337,3755999233,2091384833,426770433,3057123329,1392508929,4022861825,2358247425,693633025,3323985921,1659371521,4289724417,2625110017,960495617,3590848513,1926234113,261619713,2891972609,1227358209,3857711105,2193096705,528482305,3158835201,1494220801,4124573697,2459959297,795344897,3425697793,1761083393,96468993,2726821889,1062207489,3692560385,2027945985,363331585,2993684481,1329070081,3959422977,2294808577,630194177,3260547073,1595932673,4226285569,2561671169,897056769,3527409665,1862795265,198180865,2828533761,1163919361,3794272257,2129657857,465043457,3095396353,1430781953,4061134849,2396520449,731906049,3362258945,1697644545,33030145,2663383041,998768641,3629121537,1964507137,299892737,2930245633,1265631233,3895984129,2231369729,566755329,3197108225,1532493825,4162846721,2498232321,833617921,3463970817,1799356417,134742017,2765094913,1100480513,3730833409,2066219009,401604609,3031957505,1367343105,3997696001,2333081601,668467201,3298820097,1634205697,4264558593,2599944193,935329793,3565682689,1901068289,236453889,2866806785,1202192385,3832545281,2167930881,503316481,3133669377,1469054977,4099407873,2434793473,770179073,3400531969,1735917569,71303169,2701656065,1037041665,3667394561,2002780161,338165761,2968518657,1303904257,3934257153,2269642753,605028353,3235381249,1570766849,4201119745,2536505345,871890945,3502243841,1837629441,173015041,2803367937,1138753537,3769106433,2104492033,439877633,3070230529,1405616129,4035969025,2371354625,706740225,3337093121,1672478721,7864321,2638217217,973602817,3603955713,1939341313,274726913,2905079809,1240465409,3870818305,2206203905,541589505,3171942401,1507328001,4137680897,2473066497,808452097,3438804993,1774190593,109576193,2739929089,1075314689,3705667585,2041053185,376438785,3006791681,1342177281,3972530177,2307915777,643301377,3273654273,1609039873,4239392769,2574778369,910163969,3540516865,1875902465,211288065,2841640961,1177026561,3807379457,2142765057,478150657,3108503553,1443889153,4074242049,2409627649,745013249,3375366145,1710751745,46137345,2676490241,1011875841,3642228737,1977614337,312999937,2943352833,1278738433,3909091329,2244476929,579862529,3210215425,1545601025,4175953921,2511339521,846725121,3477078017,1812463617,147849217,2778202113,1113587713,3743940609,2079326209,414711809,3045064705,1380450305,4010803201,2346188801,681574401,3311927297,1647312897,4277665793,2613051393,948436993,3578789889,1914175489,249561089,2879913985,1215299585,3845652481,2181038081,516423681,3146776577,1482162177,4112515073,2447900673,783286273,3413639169,1749024769,84410369,2714763265,1050148865,3680501761,2015887361,351272961,2981625857,1317011457,3947364353,2282749953,618135553,3248488449,1583874049,4214226945,2549612545,884998145,3515351041,1850736641,186122241,2816475137,1151860737,3782213633,2117599233,452984833,3083337729,1418723329,4049076225,2384461825,719847425,3350200321,1685585921,20971521,2651324417,986710017,3617062913,1952448513,287834113,2918187009,1253572609,3883925505,2219311105,554696705,3185049601,1520435201,4150788097,2486173697,821559297,3451912193,1787297793,122683393,2753036289,1088421889,3718774785,2054160385,389545985,3019898881,1355284481,3985637377,2321022977,656408577,3286761473,1622147073,4252499969,2587885569,923271169,3553624065,1889009665,224395265,2854748161,1190133761,3820486657,2155872257,491257857,3121610753,1456996353,4087349249,2422734849,758120449,3388473345,1723858945,59244545,2689597441,1024983041,3655335937,1990721537,326107137,2956460033,1291845633,3922198529,2257584129,592969729,3223322625,1558708225,4189061121,2524446721,859832321,3490185217,1825570817,160956417,2791309313,1126694913,3757047809,2092433409,427819009,3058171905,1393557505,4023910401,2359296001,694681601,3325034497,1660420097,4290772993,2626158593,961544193,3591897089,1927282689,262668289,2893021185,1228406785,3858759681,2194145281,529530881,3159883777,1495269377,4125622273,2461007873,796393473,3426746369,1762131969,97517569,2727870465,1063256065,3693608961,2028994561,364380161,2994733057,1330118657,3960471553,2295857153,631242753,3261595649,1596981249,4227334145,2562719745,898105345,3528458241,1863843841,199229441,2829582337,1164967937,3795320833,2130706433,466092033,3096444929,1431830529,4062183425,2397569025,732954625,3363307521,1698693121,34078721,2664431617,999817217,3630170113,1965555713,300941313,2931294209,1266679809,3897032705,2232418305,567803905,3198156801,1533542401,4163895297,2499280897,834666497,3465019393,1800404993,135790593,2766143489,1101529089,3731881985,2067267585,402653185,3033006081,1368391681,3998744577,2334130177,669515777,3299868673,1635254273,4265607169,2600992769,936378369,3566731265,1902116865,237502465,2867855361,1203240961,3833593857,2168979457,504365057,3134717953,1470103553,4100456449,2435842049,771227649,3401580545,1736966145,72351745,2702704641,1038090241,3668443137,2003828737,339214337,2969567233,1304952833,3935305729,2270691329,606076929,3236429825,1571815425,4202168321,2537553921,872939521,3503292417,1838678017,174063617,2804416513,1139802113,3770155009,2105540609,440926209,3071279105,1406664705,4037017601,2372403201,707788801,3338141697,1673527297,8912897,2639265793,974651393,3605004289,1940389889,275775489,2906128385,1241513985,3871866881,2207252481,542638081,3172990977,1508376577,4138729473,2474115073,809500673,3439853569,1775239169,110624769,2740977665,1076363265,3706716161,2042101761,377487361,3007840257,1343225857,3973578753,2308964353,644349953,3274702849,1610088449,4240441345,2575826945,911212545,3541565441,1876951041,212336641,2842689537,1178075137,3808428033,2143813633,479199233,3109552129,1444937729,4075290625,2410676225,746061825,3376414721,1711800321,47185921,2677538817,1012924417,3643277313,1978662913,314048513,2944401409,1279787009,3910139905,2245525505,580911105,3211264001,1546649601,4177002497,2512388097,847773697,3478126593,1813512193,148897793,2779250689,1114636289,3744989185,2080374785,415760385,3046113281,1381498881,4011851777,2347237377,682622977,3312975873,1648361473,4278714369,2614099969,949485569,3579838465,1915224065,250609665,2880962561,1216348161,3846701057,2182086657,517472257,3147825153,1483210753,4113563649,2448949249,784334849,3414687745,1750073345,85458945,2715811841,1051197441,3681550337,2016935937,352321537,2982674433,1318060033,3948412929,2283798529,619184129,3249537025,1584922625,4215275521,2550661121,886046721,3516399617,1851785217,187170817,2817523713,1152909313,3783262209,2118647809,454033409,3084386305,1419771905,4050124801,2385510401,720896001,3351248897,1686634497,22020097,2652372993,987758593,3618111489,1953497089,288882689,2919235585,1254621185,3884974081,2220359681,555745281,3186098177,1521483777,4151836673,2487222273,822607873,3452960769,1788346369,123731969,2754084865,1089470465,3719823361,2055208961,390594561,3020947457,1356333057,3986685953,2322071553,657457153,3287810049,1623195649,4253548545,2588934145,924319745,3554672641,1890058241,225443841,2855796737,1191182337,3821535233,2156920833,492306433,3122659329,1458044929,4088397825,2423783425,759169025,3389521921,1724907521,60293121,2690646017,1026031617,3656384513,1991770113,327155713,2957508609,1292894209,3923247105,2258632705,594018305,3224371201,1559756801,4190109697,2525495297,860880897,3491233793,1826619393,162004993,2792357889,1127743489,3758096385,2093481985,428867585,3059220481,1394606081,4024958977,2360344577,695730177,3326083073,1661468673,4291821569,2627207169,962592769,3592945665,1928331265,263716865,2894069761,1229455361,3859808257,2195193857,530579457,3160932353,1496317953,4126670849,2462056449,797442049,3427794945,1763180545,98566145,2728919041,1064304641,3694657537,2030043137,365428737,2995781633,1331167233,3961520129,2296905729,632291329,3262644225,1598029825,4228382721,2563768321,899153921,3529506817,1864892417,200278017,2830630913,1166016513,3796369409,2131755009,467140609,3097493505,1432879105,4063232001,2398617601,734003201,3364356097,1699741697,35127297,2665480193,1000865793,3631218689,1966604289,301989889,2932342785,1267728385,3898081281,2233466881,568852481,3199205377,1534590977,4164943873,2500329473,835715073,3466067969,1801453569,136839169,2767192065,1102577665,3732930561,2068316161,403701761,3034054657,1369440257,3999793153,2335178753,670564353,3300917249,1636302849,4266655745,2602041345,937426945,3567779841,1903165441,238551041,2868903937,1204289537,3834642433,2170028033,505413633,3135766529,1471152129,4101505025,2436890625,772276225,3402629121,1738014721,73400321,2703753217,1039138817,3669491713,2004877313,340262913,2970615809,1306001409,3936354305,2271739905,607125505,3237478401,1572864001,4203216897,2538602497,873988097,3504340993,1839726593,175112193,2805465089,1140850689,3771203585,2106589185,441974785,3072327681,1407713281,4038066177,2373451777,708837377,3339190273,1674575873,9961473,2640314369,975699969,3606052865,1941438465,276824065,2907176961,1242562561,3872915457,2208301057,543686657,3174039553,1509425153,4139778049,2475163649,810549249,3440902145,1776287745,111673345,2742026241,1077411841,3707764737,2043150337,378535937,3008888833,1344274433,3974627329,2310012929,645398529,3275751425,1611137025,4241489921,2576875521,912261121,3542614017,1877999617,213385217,2843738113,1179123713,3809476609,2144862209,480247809,3110600705,1445986305,4076339201,2411724801,747110401,3377463297,1712848897,48234497,2678587393,1013972993,3644325889,1979711489,315097089,2945449985,1280835585,3911188481,2246574081,581959681,3212312577,1547698177,4178051073,2513436673,848822273,3479175169,1814560769,149946369,2780299265,1115684865,3746037761,2081423361,416808961,3047161857,1382547457,4012900353,2348285953,683671553,3314024449,1649410049,4279762945,2615148545,950534145,3580887041,1916272641,251658241,2882011137,1217396737,3847749633,2183135233,518520833,3148873729,1484259329,4114612225,2449997825,785383425,3415736321,1751121921,86507521,2716860417,1052246017,3682598913,2017984513,353370113,2983723009,1319108609,3949461505,2284847105,620232705,3250585601,1585971201,4216324097,2551709697,887095297,3517448193,1852833793,188219393,2818572289,1153957889,3784310785,2119696385,455081985,3085434881,1420820481,4051173377,2386558977,721944577,3352297473,1687683073,23068673,2653421569,988807169,3619160065,1954545665,289931265,2920284161,1255669761,3886022657,2221408257,556793857,3187146753,1522532353,4152885249,2488270849,823656449,3454009345,1789394945,124780545,2755133441,1090519041,3720871937,2056257537,391643137,3021996033,1357381633,3987734529,2323120129,658505729,3288858625,1624244225,4254597121,2589982721,925368321,3555721217,1891106817,226492417,2856845313,1192230913,3822583809,2157969409,493355009,3123707905,1459093505,4089446401,2424832001,760217601,3390570497,1725956097,61341697,2691694593,1027080193,3657433089,1992818689,328204289,2958557185,1293942785,3924295681,2259681281,595066881,3225419777,1560805377,4191158273,2526543873,861929473,3492282369,1827667969,163053569,2793406465,1128792065,3759144961,2094530561,429916161,3060269057,1395654657,4026007553,2361393153,696778753,3327131649,1662517249,4292870145,2628255745,963641345,3593994241,1929379841,264765441,2895118337,1230503937,3860856833,2196242433,531628033,3161980929,1497366529,4127719425,2463105025,798490625,3428843521,1764229121,99614721,2729967617,1065353217,3695706113,2031091713,366477313,2996830209,1332215809,3962568705,2297954305,633339905,3263692801,1599078401,4229431297,2564816897,900202497,3530555393,1865940993,201326593,2831679489,1167065089,3797417985,2132803585,468189185,3098542081,1433927681,4064280577,2399666177,735051777,3365404673,1700790273,36175873,2666528769,1001914369,3632267265,1967652865,303038465,2933391361,1268776961,3899129857,2234515457,569901057,3200253953,1535639553,4165992449,2501378049,836763649,3467116545,1802502145,137887745,2768240641,1103626241,3733979137,2069364737,404750337,3035103233,1370488833,4000841729,2336227329,671612929,3301965825,1637351425,4267704321,2603089921,938475521,3568828417,1904214017,239599617,2869952513,1205338113,3835691009,2171076609,506462209,3136815105,1472200705,4102553601,2437939201,773324801,3403677697,1739063297,74448897,2704801793,1040187393,3670540289,2005925889,341311489,2971664385,1307049985,3937402881,2272788481,608174081,3238526977,1573912577,4204265473,2539651073,875036673,3505389569,1840775169,176160769,2806513665,1141899265,3772252161,2107637761,443023361,3073376257,1408761857,4039114753,2374500353,709885953,3340238849,1675624449,11010049,2641362945,976748545,3607101441,1942487041,277872641,2908225537,1243611137,3873964033,2209349633,544735233,3175088129,1510473729,4140826625,2476212225,811597825,3441950721,1777336321,112721921,2743074817,1078460417,3708813313,2044198913,379584513,3009937409,1345323009,3975675905,2311061505,646447105,3276800001,1612185601,4242538497,2577924097,913309697,3543662593,1879048193,214433793,2844786689,1180172289,3810525185,2145910785,481296385,3111649281,1447034881,4077387777,2412773377,748158977,3378511873,1713897473,49283073,2679635969,1015021569,3645374465,1980760065,316145665,2946498561,1281884161,3912237057,2247622657,583008257,3213361153,1548746753,4179099649,2514485249,849870849,3480223745,1815609345,150994945,2781347841,1116733441,3747086337,2082471937,417857537,3048210433,1383596033,4013948929,2349334529,684720129,3315073025,1650458625,4280811521,2616197121,951582721,3581935617,1917321217,252706817,2883059713,1218445313,3848798209,2184183809,519569409,3149922305,1485307905,4115660801,2451046401,786432001,3416784897,1752170497,87556097,2717908993,1053294593,3683647489,2019033089,354418689,2984771585,1320157185,3950510081,2285895681,621281281,3251634177,1587019777,4217372673,2552758273,888143873,3518496769,1853882369,189267969,2819620865,1155006465,3785359361,2120744961,456130561,3086483457,1421869057,4052221953,2387607553,722993153,3353346049,1688731649,24117249,2654470145,989855745,3620208641,1955594241,290979841,2921332737,1256718337,3887071233,2222456833,557842433,3188195329,1523580929,4153933825,2489319425,824705025,3455057921,1790443521,125829121,2756182017,1091567617,3721920513,2057306113,392691713,3023044609,1358430209,3988783105,2324168705,659554305,3289907201,1625292801,4255645697,2591031297,926416897,3556769793,1892155393,227540993,2857893889,1193279489,3823632385,2159017985,494403585,3124756481,1460142081,4090494977,2425880577,761266177,3391619073,1727004673,62390273,2692743169,1028128769,3658481665,1993867265,329252865,2959605761,1294991361,3925344257,2260729857,596115457,3226468353,1561853953,4192206849,2527592449,862978049,3493330945,1828716545,164102145,2794455041,1129840641,3760193537,2095579137,430964737,3061317633,1396703233,4027056129,2362441729,697827329,3328180225,1663565825,4293918721,2629304321,964689921,3595042817,1930428417,265814017,2896166913,1231552513,3861905409,2197291009,532676609,3163029505,1498415105,4128768001,2464153601,799539201,3429892097,1765277697,100663297,2731016193,1066401793,3696754689,2032140289,367525889,2997878785,1333264385,3963617281,2299002881,634388481,3264741377,1600126977,4230479873,2565865473,901251073,3531603969,1866989569,202375169,2832728065,1168113665,3798466561,2133852161,469237761,3099590657,1434976257,4065329153,2400714753,736100353,3366453249,1701838849,37224449,2667577345,1002962945,3633315841,1968701441,304087041,2934439937,1269825537,3900178433,2235564033,570949633,3201302529,1536688129,4167041025,2502426625,837812225,3468165121,1803550721,138936321,2769289217,1104674817,3735027713,2070413313,405798913,3036151809,1371537409,4001890305,2337275905,672661505,3303014401,1638400001,4268752897,2604138497,939524097,3569876993,1905262593,240648193,2871001089,1206386689,3836739585,2172125185,507510785,3137863681,1473249281,4103602177,2438987777,774373377,3404726273,1740111873,75497473,2705850369,1041235969,3671588865,2006974465,342360065,2972712961,1308098561,3938451457,2273837057,609222657,3239575553,1574961153,4205314049,2540699649,876085249,3506438145,1841823745,177209345,2807562241,1142947841,3773300737,2108686337,444071937,3074424833,1409810433,4040163329,2375548929,710934529,3341287425,1676673025,12058625,2642411521,977797121,3608150017,1943535617,278921217,2909274113,1244659713,3875012609,2210398209,545783809,3176136705,1511522305,4141875201,2477260801,812646401,3442999297,1778384897,113770497,2744123393,1079508993,3709861889,2045247489,380633089,3010985985,1346371585,3976724481,2312110081,647495681,3277848577,1613234177,4243587073,2578972673,914358273,3544711169,1880096769,215482369,2845835265,1181220865,3811573761,2146959361,482344961,3112697857,1448083457,4078436353,2413821953,749207553,3379560449,1714946049,50331649,2680684545,1016070145,3646423041,1981808641,317194241,2947547137,1282932737,3913285633,2248671233,584056833,3214409729,1549795329,4180148225,2515533825,850919425,3481272321,1816657921,152043521,2782396417,1117782017,3748134913,2083520513,418906113,3049259009,1384644609,4014997505,2350383105,685768705,3316121601,1651507201,4281860097,2617245697,952631297,3582984193,1918369793,253755393,2884108289,1219493889,3849846785,2185232385,520617985,3150970881,1486356481,4116709377,2452094977,787480577,3417833473,1753219073,88604673,2718957569,1054343169,3684696065,2020081665,355467265,2985820161,1321205761,3951558657,2286944257,622329857,3252682753,1588068353,4218421249,2553806849,889192449,3519545345,1854930945,190316545,2820669441,1156055041,3786407937,2121793537,457179137,3087532033,1422917633,4053270529,2388656129,724041729,3354394625,1689780225,25165825,2655518721,990904321,3621257217,1956642817,292028417,2922381313,1257766913,3888119809,2223505409,558891009,3189243905,1524629505,4154982401,2490368001,825753601,3456106497,1791492097,126877697,2757230593,1092616193,3722969089,2058354689,393740289,3024093185,1359478785,3989831681,2325217281,660602881,3290955777,1626341377,4256694273,2592079873,927465473,3557818369,1893203969,228589569,2858942465,1194328065,3824680961,2160066561,495452161,3125805057,1461190657,4091543553,2426929153,762314753,3392667649,1728053249,63438849,2693791745,1029177345,3659530241,1994915841,330301441,2960654337,1296039937,3926392833,2261778433,597164033,3227516929,1562902529,4193255425,2528641025,864026625,3494379521,1829765121,165150721,2795503617,1130889217,3761242113,2096627713,432013313,3062366209,1397751809,4028104705,2363490305,698875905,3329228801,1664614401,1,
};

int64_t power(int64_t a, int64_t n, int64_t mod) {
    int64_t res{1};
    for (; n; n >>= 1) {
        if (n & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
    }
    return res;
}

std::tuple<int64_t, int64_t, int64_t> ex_gcd(int64_t a, int64_t b) {
    if (b == 0) {
        return {a, 1, 0};
    }
    auto [d, x, y] = ex_gcd(b, a % b);
    return {d, y, x - a / b * y};
}

int64_t inverse(int64_t a, int64_t m) {
    auto [d, x, y] = ex_gcd(a, m);
    return d * x;
}

int64_t s(int64_t n) {
//    int64_t res = 1;
 //   for (int64_t i = 1; i <= n; i += 2) {
  //      res = res * i % mod;
   // }
    //return res;
    auto k = n / (1 << 19);
    //printf("%lld %lld\n", n, k);
    int64_t res = biao[k];
    for (auto i = (k << 19) + 1; i <= n; i += 2) {
    	res = (res * i) % mod;
    }
    return res;
}
int64_t f(int64_t n) {
    int64_t res = 1;
    for (; n; n >>= 1) {
        res = res * power(s(mod), n / mod, mod) % mod * s(n % mod) % mod;
    }
    return res;
}
int64_t g(int64_t n) {
    int64_t res = 0;
    for (; n; n >>= 1) {
        res = (res + (n >> 1));
    }
    return res;
}


int main() {
    int64_t n, k;
    std::cin >> n >> k;
    auto a = f(n);
    auto b = inverse(f(k), mod);
    auto c = inverse(f(n - k), mod);
    auto d = g(n) - g(k) - g(n - k);
    // printf("%lld %lld %lld\n", g(n), g(k), g(n - k));
    // printf("a = %lld, b = %lld, c = %lld, d = %lld\n", a, b, c, d);
    auto e = power(2, d, mod);
    auto ans = a * b % mod * c % mod * e % mod;
    // std::cerr << "a = " << a << std::endl;
    std::cout << (ans % mod + mod) % mod << std::endl;

    return 0;
}