QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #252203 | #7708. Rikka with XOR | SolitaryDream# | AC ✓ | 126ms | 3760kb | C++17 | 151.4kb | 2023-11-15 16:34:52 | 2023-11-15 16:34:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+1e3+7,P=1'500'000'001,E=1e5;
int fac[]={1,1004900904,1440753622,1065558995,255276724,583458273,1382427052,200316997,1076762228,1014925926,822650807,553662867,1017491989,1496502875,1249673449,181877270,1220112430,1106305585,611248072,1274839845,1285461965,751938922,1342618996,1414000447,640567301,679065969,206695744,165021792,1062682033,815998728,502178029,1395744083,851160719,156178546,121535309,148302721,839180281,1464026462,677080933,163870857,202898363,267337656,1071671626,1372659144,622457092,940927633,1041600305,450658791,102856612,811034230,1119674798,147543308,327871424,680910173,1337817164,1319579229,1280736777,1492274883,694132481,737789657,855146638,386238424,21142711,1062529657,595031576,368014034,1257937890,268404539,1389041291,1404866256,569880251,154371393,1472813198,45721177,522649738,938780366,864598530,457157459,673187360,1004572182,66666815,289193742,1044504606,422765074,469088115,846385546,1379412268,1248689865,1274230959,589760708,1089490863,1389905096,732626167,662043070,297183850,1355208582,965074887,1177381626,1182980360,348529317,1287889948,1245763505,1436863972,1498714604,1057955705,119483842,259314716,652316785,1270203891,512915799,333063291,421705181,1317079006,589006755,452640348,1393991969,470283319,1021806731,29443105,1066947863,1329533473,800291193,947240089,568436769,633744349,811709503,1062687880,202211593,917777555,1283313964,1122187036,694369283,1488629753,1379050387,1376248005,1170279140,1101357787,1296027735,354894197,755931867,237015524,978823611,1482329365,855731984,936417727,1179591166,725512075,660486041,163733487,271816809,370119267,251698990,487152418,206638284,1391068955,1419471098,1292189733,83228376,541886222,1435209918,140913719,792489052,1184866964,633807916,1431595192,1202955175,1044322400,356236609,1415494638,326477374,352277848,1372717649,8720254,1454611754,727695410,62758844,295117576,426252266,404506086,849880515,1421707616,1214811752,940607972,476418834,522258145,1484610965,794364161,104040479,1499435492,510219692,736597020,1093828480,643798619,520295201,1371131709,1294133012,1114759854,1166936283,592628251,1378658194,237084841,718483382,1071307083,1232159678,912791720,1015436908,1263922942,1035262437,685366501,1004559832,272162237,966982465,612262057,530662954,963754580,81840679,1215410164,794528794,1233417837,67619510,1479601233,1368424028,513138661,445836138,1242101172,728670557,497334105,305610114,1208846105,290548847,956325987,1248069980,1304914714,136515657,1443775677,57098049,586401574,413024366,781285930,1409652781,978670869,589137161,605857986,1106299376,395482526,960999066,952808894,112004018,1213792245,91817599,353494620,789649638,1150126489,480449857,1178712057,1228664572,1136473949,1172638816,526277964,466147604,879157466,796809525,1184307753,957123273,1077658550,1355292992,71792794,1311768842,658579665,667427196,291685635,735068134,314116746,1489140550,791491649,838050677,916331031,936617490,1428240423,1134283201,279388538,738885675,763134000,745025139,391457734,147448658,876611569,839386583,320161186,425121298,503656525,495876814,746812229,66734251,417110670,659623580,394662619,671221864,1204130935,80268982,964396786,1391709225,167838253,1095793356,288150008,1006816925,645303525,144735591,1309574426,1485395388,245683591,1128352270,371597742,259674706,604716835,340642921,53356332,1002227572,434493005,479952839,540840345,172890241,592378773,1091251116,800992308,78104544,602361948,527001566,69155361,852754998,1294051029,4876339,1170900222,1407234757,1031308236,878912896,640063667,452087847,1416425823,651535188,899239468,863475991,890184085,699305223,398469021,1411300081,1479396564,43317990,531964203,1464670408,998648570,443627823,1067252025,1266703719,13981331,732230630,164100823,1352731020,49743512,76020347,125111787,622612672,1265247964,1363591611,453858132,1184410496,648442337,874282443,214821348,1167012920,955267453,50316097,383304843,566027880,125033805,1001276609,1232569194,923754997,296992525,1364881528,1438548125,1077742635,1029125097,1202774525,935167429,851525844,1447516997,1150166959,1288691443,134858713,1099199293,790063787,1252605705,148207886,513637006,158005428,191696755,601181131,1365053613,494137046,1439465595,80673609,602705793,1281928934,947027260,262687109,840241715,1008511070,617297719,1467052195,564126161,902596968,24894818,1123786484,1049059442,251677700,1037407396,690376898,391810265,818218605,963923049,610861530,1108665253,618900636,779297238,453002879,71713599,1062748652,753732062,597717163,568869268,978996079,1466352867,1045243961,437659995,990539902,220250943,472481638,587249330,412306663,219836446,135565979,806980276,152870874,1492911374,472590545,479153722,78829733,1354208280,410797592,663155489,383962054,1111109169,488046873,471255437,157207456,1006391559,1308720944,1323658189,1078616778,632203025,84798928,1258121830,118693443,1477530741,704974902,1392445519,157784017,692991644,731480138,539693786,1453951042,795339297,376973632,167005427,12052480,1370182060,1457360541,1429341009,1315916151,358498357,161901938,124729578,826742824,1117825560,517865340,1228103794,543122637,873855219,453980067,435836679,173501906,535895154,91665109,1321174169,232147087,1135521864,836796259,635853943,100992041,855093953,1429405687,1377039124,1465659408,784763199,1171679607,867015687,344838012,970908694,1149049430,205448976,521269267,859269119,677946965,659730575,1453807667,521881158,1061449684,1488641991,41179856,702206361,324726724,475601577,1113089446,345670380,969917130,1447902583,561436528,677986079,873841424,1457070913,100388857,704919584,495375232,1041043522,45349242,442700077,443587887,50374935,874871328,1339152001,185767475,90120942,1493745413,337327967,1871084,372135813,63717913,668679725,357468143,159389241,1330654917,883681466,594623843,562639048,890389385,31409981,637242009,868930685,798185572,46292110,227329918,670516441,335310842,286815256,73736064,80626073,1433254789,122639972,668194177,589679885,1134103113,1088671895,866743974,384352567,278154318,685424840,124370711,85277974,77430170,1012660993,406293433,688845917,933322231,1475441821,221467871,505159804,1429276915,663819012,730038377,1077512835,1437386450,1170762178,842688023,42786210,68972132,578905408,95195340,71600878,876328833,1441740206,942229778,1396279491,1432965216,1098274261,30861188,1396060008,1419359321,1410432532,33117607,881843585,807127329,1126086585,822250280,220126189,834606316,997853661,1077418533,247276187,591489713,970654717,294639338,885922680,1421016948,897793202,115247895,56132657,1294298335,257899412,1146948551,288681028,1230604276,266903234,280207956,489884819,1485845268,951852225,876751986,481202411,641447879,781639582,832317809,243887632,1154085637,895477,746651482,581588079,1479404588,1048291961,492995197,698774957,214339556,413451290,96030778,825837053,479635695,969561631,2439099,385651650,1330383307,404120786,389097413,1206508578,1487173100,1467918006,782321779,1378749380,1309570425,216555257,808843265,160675684,1362703945,156909185,242034575,1333316970,1005256913,468656144,154179249,920045777,1438802366,1438069678,78720634,28447592,1130057026,888270230,773995331,1244546997,625440182,875018110,686655653,527853383,383428292,358273231,347265263,877486490,1177484915,1225534973,740009551,1166717518,218719752,657492995,692800446,191265024,365946645,1159592934,965051670,929382130,676272848,321661495,1270444144,1494135459,451472079,261481423,1211488645,1466616982,108753086,1376813012,719463158,136657800,1498617940,330734196,76439010,485201125,544637734,940986741,219723123,556522999,692867076,21605584,128565686,77129917,991832465,756304363,1401840557,1205978763,1403187710,1489898104,1109001153,1171119757,981946285,302967193,1397258296,567654199,1061162613,1432326078,1205397260,1353029989,768579405,904629857,1390107302,150549730,218003476,676042155,1217545375,334217244,1252960365,624251256,938607134,1254125111,644127544,1385373851,175419614,845198188,1187233224,495074033,1479817988,841681576,1273263682,901628365,879983398,1097958790,598890407,309202132,1085871985,191716184,144580304,395145607,957793210,704353887,870947409,820932953,1473364576,314198286,867711337,32965008,1091744661,46701296,646312848,942770331,1087719733,1366317207,1181696803,970800334,1019896291,961808723,230310444,1293476678,1037710353,851701977,1228927425,682394830,90268731,1239483214,903993321,208576937,1379021453,1224304704,760151496,1304564411,115885004,545277763,171796464,1471561347,602811677,699248764,1114268025,702854946,23509519,122200473,1415108786,1485627588,1330341110,341046987,640256884,9689121,1489703841,1459094849,1453746123,167481009,670576391,11919287,905076804,777147645,1321881967,85441538,963927697,1083553721,895825365,1200397827,172675475,557165459,1366005769,1223916850,530609668,1459305805,199710482,1122103185,485350279,760894466,1314774483,854293690,1007145453,151066264,58363032,422551937,236209758,340791373,518898321,80699633,1015990205,1279751308,879919403,398661267,75929483,1431355975,1110189306,493033446,1161422885,171133467,463942139,866308103,507368780,486383642,165011063,1102654783,130358237,1270474966,674810022,1070314402,1071302223,669539947,802459910,1369801294,1480346956,1199366471,469052528,102250238,801880999,829682191,1122426185,722967655,91757888,477367866,86083487,2181722,1206703062,1020707652,1299730809,252701796,731795344,568748881,632648989,507790296,847264746,249590938,1113630108,797546101,945581993,1311634046,1465331118,172039517,1029635590,338582586,1061985544,81576462,201979019,1153005850,1451670107,1265801298,1429024855,673011038,921783324,345639586,1106634603,1400997426,318339296,1418182963,949879621,979906900,1050656802,165125797,357823071,895583802,910223495,729120378,1158146951,1013361585,325605590,847569927,965151163,196506119,263413578,1481538819,677405404,1394252167,1351931575,1404078289,253169727,110380558,543528561,1020145294,1019211555,1469695351,1183650119,845028495,1243550776,669772815,697495227,103810342,1238281695,791380201,10437315,179268375,943502727,1295110678,1175799111,1250177674,187890780,979411973,1411577124,824066672,1420127245,1041751208,960985351,36946603,1363116010,740959002,179306210,92289687,877724213,637188521,461501655,199511767,717277721,705728192,1497200403,687357830,783050272,1344431355,1323172816,171119218,429724536,1248656317,129276768,165863195,622993983,377369029,460335349,850754925,260174156,859258085,509852267,150357066,1085262784,170959975,325373587,327732005,863401414,787142332,1146400769,1161302399,1470190874,21692857,1485923842,727626450,149595832,359069484,115767107,1396323676,1020018893,776367240,1478466236,1131894522,1136477515,1344490809,1051673106,1352860477,200073058,1246149935,644140023,881463171,1391922591,1229789814,1010426062,93875945,1235982327,593488144,907230429,484132693,565419392,1338910826,297256419,762800800,1457912150,1151169115,257599942,1378302580,1407523123,1312752715,324622945,1029980240,84021600,1262799920,58138931,675762088,956178185,1016274657,842298244,628814255,1109044507,615790561,121333496,1237184815,309757795,607805085,1069641741,191034379,1295055761,1192546974,876577375,1206243895,213619145,150841880,92453477,11146716,1072017523,1021832058,1317547347,938415143,391816794,601211743,37376574,10486036,1253400247,238875222,1312929339,465873720,1131846326,1369445401,224140936,1052531540,284526152,580684624,725569086,1292819705,1133212484,1213339578,684836879,398537824,1291348661,463361191,1380988745,1040986479,1271199529,356843691,1125491029,72836245,1148056677,215872767,895329792,715492614,1171862530,1062492007,94630500,1232897821,735956478,214578701,515918472,773959126,869273183,158032951,746357963,1239214181,1389368799,250871573,354519373,225379091,1163173829,842682474,465208257,1221140400,1328748354,729488707,274485891,9641143,1372461895,176801599,190728439,1120979060,815007621,214163691,752592895,1062186271,448588754,1343780342,604474371,336934001,375562634,700242137,779256557,736869648,1250651871,721756341,340595322,458826015,290050539,619671885,472906010,679069640,757768768,160211114,301658110,811633279,1255912595,136130145,653411180,349237701,814258607,448654504,1071907212,499252325,1176926646,583400236,529436514,896397889,953626091,873822010,845298280,752925987,94889187,669140661,1292769147,1035461347,165782670,1183996165,560674000,106568818,1283867711,553622664,748195546,1252132733,1370621783,563095751,546732855,383650918,1056690849,471141559,989468650,790551472,635798244,293813889,107844077,528251627,1165847453,724079214,131970133,496957011,1390315215,77285720,1009920542,110543690,509697964,377245998,1373453439,1391308168,8534600,1439775305,876040384,707836317,1483782306,1062811846,776379318,899095729,470290180,689097521,479396305,864462954,292778587,1135318994,1496894929,512295053,283241766,624382101,561119631,799368100,368274350,701439087,1040793544,1274498462,644076876,112793872,986461589,135404837,814555575,661694644,34126390,45846693,906927836,305529108,978340599,756916092,304768056,527081101,287442521,718700170,1378354892,810411376,289987863,343750738,773361329,210750415,1435389756,500263186,958928175,1282293910,1168290414,1184956612,1196801103,1124654885,1401070942,1021985911,1153680575,507136988,289616484,602506188,107915428,1358975207,580667550,957629685,1422467628,86219690,211859736,907095427,984553650,1239782125,63661989,1002168724,1250861137,946013168,1395654220,1423542878,582430178,927686786,146240747,1447756039,484592818,694775261,1072057016,774225873,9207089,1016010510,924901562,1145871090,1413951395,1460196067,1472937360,411918552,432109007,340903172,1164706355,204476780,197898711,383056871,121379740,145948684,510298205,1184894194,315638578,1364497625,1163685797,253415168,464898738,496906107,176296917,1464786798,606894360,790863829,1484849518,1044339173,459124742,1356968728,585058994,837677581,1444092150,607515590,213305649,925515822,668303246,480350463,598510562,142523464,165596053,483467493,929653259,339149577,1064405775,778851681,117253868,394438017,757146722,811612897,524280023,31094820,938147574,1312714465,958291477,391607929,1004691856,246992449,180122979,267381969,68798492,14537658,383047933,279629447,814395676,1146041792,1290662485,1400474815,54530109,987968516,244354908,1445080027,1041816943,332491271,977366582,508200342,428781623,1248278563,745270192,1127647788,855838544,1344376218,1311889391,926522110,1160140333,496966252,707087943,633764950,898242359,636451372,385808501,213407249,1323793982,1354899176,178842210,464208993,1323314195,919349843,1465176198,813647963,593554333,505796080,59696485,475573621,596033028,706216948,897046250,622131345,726741397,429242167,615066728,292198831,1324406234,1479656680,735685544,219823544,1011523389,385595419,636740101,541865185,1322541247,1384128527,438807983,572260066,885728064,458463452,608786934,717941476,386912824,793534707,506034189,331628612,732818634,1352067313,539879121,731750698,981090359,1113272364,771715464,1277499766,349219475,454460044,1016934710,1260112393,1160944926,818970694,602376593,1201504983,891308240,1457443279,317392383,736474737,1112384400,1053967923,455179188,1032721721,1338465655,122875740,1354639517,113546766,391693851,355958886,692454988,200831011,201039376,927854033,735711251,452569627,945670817,1268350135,177788896,998363533,1076435331,1146426332,1142505213,1285337616,424292741,1040855655,1288388836,928820566,4792636,832993116,160139981,54635737,662135206,817032007,1457320009,1069802483,1153997649,181721808,153105012,124265596,762616103,962005799,1127897729,1472314502,1168520244,734907852,1445955778,658845408,124697393,237752177,1050687869,454391250,986077696,1428966173,1465207102,620957286,859089052,1087428183,995051616,128191469,1072616671,762936666,575747507,950025873,475439660,788733009,185790366,1312756349,1186929493,175473641,424420127,614003076,915686180,168500499,332291988,292014903,855694269,580592510,1276295806,1304588399,454790709,1207385221,425444698,1268959948,1456524080,235130006,1104715799,345359109,880062569,870348668,48490279,21317660,777926735,397602032,1158564926,1095466172,1265388146,772577959,18402218,206024861,175645201,402399000,142935871,1108911440,592079178,1287743601,1136236111,409841071,655486968,833699818,1034052489,972348530,1277318248,20260263,1190088679,477628406,939955095,925669386,612449663,431136805,614238109,1091453148,188865084,1193133405,214909521,265874960,1245630250,1435472011,767156154,1065625624,1111691104,623829620,528186528,11829678,297638295,760600498,1059124180,508792413,525402153,1317947436,896477945,493458530,1002003447,1027399013,1476197229,1044539827,565464006,216505330,550557321,775550010,1270617101,874693977,1234582231,1377430778,1126075121,718401768,201069100,1417540971,80022627,534350014,1495097728,364525855,422927677,1211166299,683887216,1189443748,1454023572,1085591727,638359529,994432556,1281805654,633029525,310280292,338678263,148673339,1433894830,570551775,909935134,685215960,144548025,590105831,922501839,1467273396,77907460,884391556,108429152,792857847,787395076,909694289,1498051265,1269546004,1203845730,198396711,82719902,236187998,1474705962,652525602,1203852521,475638112,1236887176,1488499541,193332331,1061525099,736704545,164576197,290317698,1057505364,1437430774,120765931,848467740,512478128,159500467,610652279,1249949281,699495161,583885136,222504284,333812928,165069253,1112834887,1438530021,459286507,830932374,934394520,1330238123,523706387,1419218740,752978344,92239356,156800071,1133731518,604350265,806978517,1214748967,1343386145,5420415,350220654,580161312,21587261,1006960146,542000330,223416128,388411121,580261722,1491482480,13748921,110410819,305853742,536936737,1277883743,1224192063,315874907,666506311,847304295,304138151,103829956,291030358,341725755,774883064,769498200,657868862,904054098,453573042,1359457649,1205239642,468857383,1131620107,311556872,158258599,1144232224,662589101,485195009,1008206332,412274711,926651843,906465313,1364002548,735480097,300164500,600553681,1107443339,846741219,1279816972,1096114077,60657548,16030300,792611277,1470465991,1328208098,987926536,90833866,879409137,1218613366,750523360,1100454861,86203613,934182789,959511721,1090617446,191010695,1416033663,248811633,559262876,136428430,210369262,1405097037,551176771,1034214911,731449608,157308690,797947424,449072737,447188979,290373403,18665638,377519054,987830019,1243526761,806241285,823281016,929195541,69871238,1453797896,1335350822,1194663000,174930028,1216304249,1357069981,430157550,1367793082,50987751,567510834,873442254,195640914,1470517064,738092065,1166686523,380268775,1421282482,1082193566,1164470547,183837102,1031221102,416216191,1384673770,1350173424,879928882,151172546,1289695187,1377815419,1005476096,1224063431,1250867222,1177550594,1184528217,537322847,391799884,589592904,1418023613,1222449903,1036662138,542599431,1297852524,1376716180,584799786,37442039,1180380276,1126051413,298593181,787469665,728542656,212265914,653008940,1037052157,1189713642,942799163,640977378,1282101798,799043291,1311925888,1288332857,1327573527,1198251478,204136290,769083647,1299148082,1064370168,937824769,1189217112,498013464,1282757129,1408676126,672264025,763127196,1205420444,861178376,1474778781,134427318,77252008,1087738560,1297077369,1184516572,387151119,494700097,201209391,738577003,596947480,250063699,1384610080,1431442713,121502423,385256016,675634603,478736597,846975576,733559518,964835708,271955083,1004065790,446347490,42382208,823749763,804862955,379414923,1411408804,1000284460,705493398,993843636,312555083,861734581,148257188,136852423,247761134,1359919674,381903000,671116408,1051396155,29665563,257399407,308611254,1013251839,1039144692,1059287874,425124492,76206226,785055236,1413498320,288566429,1470095110,453643787,619026275,853090020,566984986,1379591081,450012842,598486362,1091955158,737677988,962786792,841664233,892523074,1497312169,576019445,1146023429,300199549,1368259817,61945186,701099755,660543831,1469682913,442063153,1493439229,552255116,1212532633,1271292103,954038657,519696285,206793520,415721837,631646710,679671928,208658383,754769514,523180365,87442657,905201835,131176173,97032501,1052298242,386386551,1278949267,1247393248,728380651,1277753908,901949487,551573747,582643103,315232632,553497533,1182458133,126344961,1231949671,991074363,919164578,918612837,742408718,1051928636,295845921,816742561,280179515,441924664,443119116,477355445,19980497,1329536941,1342644805,699484527,437559355,9657566,1298621703,841282093,874280928,107467504,1448851161,133608251,757450193,101267407,288474701,1305440014,1384034699,550826216,10689653,435816819,1414055261,846063223,1478524270,970163501,1268717858,1145831942,336109878,757189332,1382132540,1186068144,254675959,750683447,1381727772,919798715,721388438,1186253858,1396507198,624115924,87420284,884884448,1175709122,1463127793,508169971,214150596,57733066,397261344,150393036,955139760,125920993,497313718,93156659,1329402155,509392714,1049292098,1312877679,50293227,27400173,1224279116,1346032084,1038015509,1154570764,937412489,581842059,849337192,680393040,849572947,514742646,820534300,1346347960,1309370362,581476348,349633759,282112661,1336234232,318165319,352003344,118138511,368619935,1453482020,437645418,28374652,1428290356,707719536,1241838941,370800136,237287753,395798308,1173173722,623971752,1213016961,1097208311,1080763289,236467272,678717513,780916522,1118962216,1474315186,1448138271,1140639792,1446039547,192917729,1217416352,488151203,13812240,214683293,683042350,43039810,621982258,1441798560,1146181605,331854753,1456872265,787605789,15226647,679381317,222417143,348720111,1298245614,247148965,1383474586,1308208095,716154795,1334876847,1391429699,776984410,615536721,96255447,1203045985,1177930089,22404134,1342689430,520116045,313733890,1201438048,716960535,199155751,323048662,1284041041,280290195,100932438,772113090,447042986,1056604582,775291423,188393436,1151361643,329025350,57540850,762494115,832012781,1040140396,852525152,663374434,673167912,127843768,749915795,580768677,1009861908,628154164,596215115,778981042,1000184956,911187836,898705312,673779808,1278896123,662621190,1091505664,1490564568,186588283,765595423,1165162170,285686052,1408911936,176414948,55775826,1202667847,217219841,1012376262,199295394,1151266715,236294481,1122904560,529743860,1327305842,925643863,1107994592,800248733,1252696064,544137197,396641503,1093955340,122752851,1464289484,364381037,492962314,316778720,1249239678,666821800,1316521396,552779719,985386250,450511607,950342340,539641315,1375703023,133345414,156208488,1189764463,276349151,465389364,474038281,376463515,107702000,1459094988,694220106,477227726,862940900,1037083106,757591338,319851924,596483808,967123996,1431659665,1334563122,426308047,135745242,788340111,628199981,995376528,413284351,33640222,370379152,492355753,553728007,1427902531,135547626,1257644516,727484421,143509581,399306491,469044690,865757170,1410898579,27398084,1188979734,1322960546,960171632,401605389,893312711,1201854463,1400967790,973652991,1321965655,886317153,1097799851,1327927451,169026465,1011284064,989568959,378550436,946099167,619674127,1492345323,1374272361,379046596,1190198173,973897032,724749323,1063422390,127503336,335081451,1121019473,1258722125,82894026,1099745224,301240375,1105686534,259281635,1335596145,1120452091,1168548941,879940381,1471194409,875321947,1103346256,1248791068,114192366,1164309723,1448111981,1192916246,87934100,34963749,1481834847,676429336,1307473842,544280616,1936501,1461545943,1286124653,1408552,748732159,89673398,983145945,87111631,399271201,1214880543,1054213659,423628033,1466299588,525015850,981945958,181375135,688844239,1123581765,1185446449,168216466,1321262861,438752865,250609692,142997617,609839656,820411148,631719725,218272837,831468639,982315577,568984900,697820508,555857628,815732513,364723486,289782551,874266925,1172941414,1485516117,765321104,701048558,1040413949,750565590,703414660,1301316415,1331536437,938111166,10922568,912693781,829858542,341842887,1080252175,820251275,733006582,151005838,689887162,1144922235,1268807720,664851834,145466647,877524816,184410800,1062901590,310155189,1282505062,970079305,175818214,1140682640,711182951,77222572,1152517782,690566879,549878694,1207770678,73254773,1163055805,1197992801,96098087,881151439,316301355,1311346454,1215371822,781699963,529474278,615037498,530961561,232884263,493389696,720324421,268279731,1491922878,816945904,1265609590,1477958690,1446559546,1185312590,280544344,1019341278,1038485126,31488620,36941135,1416528703,1233010831,620171269,1404291927,65149697,68483221,862834817,1311537177,217898795,1476775262,1253131973,895798392,775295551,453735193,634246342,580853912,14170932,1044341064,379780657,886824169,731727398,589917428,869432595,23015890,1442707714,1166373261,1154840069,1069111982,380804757,553017116,856811331,1469636418,1413133237,1417742486,1473039941,1266418763,668971877,686717546,413383464,665094706,640462148,384817965,1014131252,1046201532,135190155,790210417,7374026,135569407,1264190321,1019893888,1255772126,187495349,424684615,389993611,144071796,1063629500,778686141,1106274072,256310838,786759532,380288742,1362409959,844796473,740705993,1117948060,1430522130,968541915,353743648,43633477,995385749,1145159480,789000802,738877212,1476871963,742984558,1058876713,1242333295,675541460,402028784,175703870,306720408,506858589,509038552,1263937539,1008813998,729928491,312045614,311442960,1343160447,625947781,1242826856,446162786,353364091,245934883,1144677472,950267581,868540069,1334422389,508901385,525749341,336365472,1067781070,1098371309,252576211,1008776085,163326011,715111728,760212572,335021117,206787388,489577520,460665998,244215037,1260940779,144288769,1398467744,1489058351,526170476,541482865,1234042935,284288318,815862367,438513910,704813844,467805898,22519014,1140453247,982046077,405997294,1002068810,536502092,914953720,1088061208,454000094,255050495,475057603,800653656,662399260,1185804726,1378869276,1148412709,82167886,1350569446,993899500,153456835,1366131756,5205510,968945151,1399572063,818279999,521773952,1334382789,203642866,1046127628,26867848,942012472,861999500,404446091,1361336437,187664779,940571264,766819648,29116354,517866744,1369125553,229679089,1030338742,1333088824,1355506378,1325905034,1136575259,600436768,1270125380,984605059,1268489117,590387586,491541219,1293604376,159042271,1380275390,1469476354,1487612508,1189934875,262186579,1041757372,79995635,50689837,537623253,839400020,897853342,1391050914,279649185,1286450186,716310157,93923724,1147382401,827145978,521102659,479595436,65619438,1211202362,184606166,1056357185,1303584064,419532628,762694773,128063174,1288056901,1152963693,1255259461,803635292,262377771,937431826,1082465560,812928573,1344170135,1011694562,91219800,1089153514,1247265132,936994916,163456723,837034111,221447138,455166709,1136980530,1442720272,374393986,287820354,246856627,877143628,436825624,1096568819,935470369,555014018,240519850,1481646692,39581700,1397269042,1464820372,71537302,1166359667,1122324795,294938899,365858680,1008112217,1111807647,1065767485,314758575,1165680898,325669594,704332399,654313654,548206965,137028432,1196349907,96382668,924188328,451678647,1351837873,385410827,1212732966,509106627,39351935,176583847,1417194350,1092111014,44713612,258330332,1190750945,1014612314,420146402,743113065,271823880,170288387,958136818,891505218,448368533,1182286512,1068103086,1368190973,885732601,167319247,234396347,1453255835,1266076456,91593950,906075809,1389618639,348598294,254161253,663424506,868835489,530866684,103877536,411107913,448354922,825767577,379628657,1273911084,1370506082,549422953,781803123,1145650764,1449822475,1192403585,1095407802,1368794876,78836227,348358415,163452526,772979312,1487187117,1204848461,424485185,336955780,1435219101,75760709,838951488,250140015,1437972542,1285835359,1335835052,1301632305,804907764,924487760,1024054020,229000862,447450509,1368624982,509017012,1299688477,1042748327,166974319,473174540,18183769,1064694544,20974714,507814746,1041666568,108063789,322603809,1124118814,1090239218,1157475641,1268048848,275482719,1338172629,783659574,325803086,722641602,505272182,149975621,1214341967,86838631,412855193,360907423,1198058795,896338551,997091047,609278947,1051913718,1106531658,587905540,967376060,1483112576,1071606211,1052979454,763303058,249872296,1165019694,267669533,332600275,271971524,782206158,1044708303,182576520,1447258190,616108167,650207886,84190955,672845052,1487008385,539372198,728606529,740357332,1454427645,1323537034,351974418,1054464328,916708645,1279945860,668517737,810099528,623786886,1389514515,105421078,1069957706,176404501,186477393,442349892,183197058,156998623,350068486,486346316,1320334560,1339730561,90409892,192679507,406884002,59904886,363700597,541811235,737340763,678632920,338036375,1309116583,1219123313,105213810,541378121,857706484,27989524,1458844289,678169521,149016530,720057957,846152721,1032268965,1380625115,1241687923,1486759727,367329656,970337396,548319484,733497445,1178308151,925459009,530277438,260141843,83668654,78322650,892052684,769188566,650409963,159306262,1312420933,993965051,506139793,820924950,626083495,547196567,729970536,1493395075,1394971392,1066699148,167607486,1008917007,611026330,490787249,92561732,51528237,1211402989,1331550333,648339051,1181530161,1243220288,185664735,1363196526,821271025,1396831259,168258493,1370662520,564481360,1416926253,320963313,864365921,42840576,887012023,1105451147,483224138,329611489,278229599,422914122,983300744,260494368,765965148,1296766377,1452002872,51157441,1473136385,699176491,878880625,122901613,693338279,828664063,296159343,1111599787,291692951,731899520,189387212,643241574,212339928,1495889722,758148300,1004600399,578109902,1186667304,776963576,1349146653,849883550,1034795709,416085533,1331111375,902293732,404251038,1040245786,843522505,450983354,750105743,1421519978,1266277393,955295754,292350175,632787932,371459256,42036535,617603100,255130975,1166757554,1486386960,674399526,1386201073,317864267,185049686,712854659,1252343422,820147769,1412111189,152028736,1195917813,413571615,1087171215,1040997189,1244086168,942502180,1327586961,697427040,1162177737,595214229,135887796,1303698661,224650809,1406527487,1413400319,180607244,557225901,1219320872,875097396,1358870267,528901652,241800473,89173163,513574415,33781816,108776509,1488486546,142415836,1146117694,360277241,944174407,301372117,311567411,1426450401,1057643103,1157412459,1016067691,840060652,490194067,897283207,805511849,1117160034,687781500,555345837,1363777861,1481227834,1142315489,618558441,221182991,18265684,496532443,952699740,141715505,1143757872,583752364,1189904118,1058494561,47168066,815139753,570103479,1170929499,813084040,718502634,837328497,1305033309,252925243,71888409,980324722,287676255,995393247,432353208,1478331321,488880601,874620959,1053716504,565510972,77325326,974243119,877977211,121619527,1374945779,1337739100,39705949,1074714775,357626299,969847329,1150935282,911856251,1377028675,668302094,175547044,166824567,658586276,1452206455,1283355274,448376611,548541758,404617999,391242980,1425923301,139425276,1023168654,508884508,795905020,155928786,211791413,1419664162,691101799,418597123,477628430,318935117,477968780,1234166672,817519083,1449238931,1267048854,804394253,748650093,324751528,1025921026,1104422183,545695847,580708060,1425104503,428416239,371906730,1237779386,1418317078,1043216871,750193862,996810400,135750379,564451318,774136840,1282765085,1228740455,897818619,1207012832,287031332,809239428,1463924277,1277067014,1375060981,775190934,822616392,559010992,1402284889,1056982963,797758739,1095173570,10431842,297258391,683023449,1103456532,1292777576,54984687,693024849,914385992,752261278,11753826,271011106,263064321,1321042521,562288055,363949917,1051061824,459845269,161066952,668187409,1246796984,362189394,862491480,732939119,456027944,1464551051,1146268523,519093485,588994366,836776135,991313793,395962320,283838183,1050644197,649982429,505855280,725590439,921490171,216072516,1434094320,1401736102,829459658,1396786932,1122798696,744546143,83377454,1468711908,274796979,1346502592,636205603,1077644829,231799185,146261571,1452706160,1118649826,590956327,1316942111,71189780,421108518,1221611387,601412648,479877148,1015660518,828993858,1334066919,1271914938,392650804,228550238,1438027735,1085695244,74383563,1350329235,542866489,1430770601,148998704,921888091,1039403488,1275784317,839208143,320704187,78010827,468627090,1349881952,1240678781,391172330,43764924,146443438,10626273,1390577614,936334931,455398610,955833259,1004896503,828384647,244945006,406114384,1318991020,282136060,114726378,1354293188,92129089,29640630,224597794,17485251,239434356,801126715,487463706,1132546602,1224292670,253573325,1265338288,280681369,90225989,1287336573,1383892371,913252043,301411312,834416530,785868225,612886484,827288186,953233206,949007684,315784847,1428039911,1498954735,568668369,205730971,822045063,971321197,689300779,140307987,367552066,745929073,1225203542,1278772375,292141023,711308734,820784127,266724220,715569542,746358157,415300922,519231567,265491118,120416219,441709528,1188027262,318876556,271720001,860228872,1270158861,81333209,272906434,193507907,1170610616,15800249,711662578,1246046205,433438507,1244299670,1480088665,900014488,868793017,181579723,881063013,767718460,479983566,1484211551,209246720,378435901,1282608051,33218056,664908939,590507186,856580042,1240519234,859201940,742424065,766249793,46237297,1377456180,92689858,346233407,515760731,810033943,688789722,544358862,868702455,850420040,598483673,867163444,468163061,745499749,505919021,958336793,1231802162,131555885,406322166,1327926905,1440430191,850566251,72957919,1406548113,562435267,87610829,414495378,199564117,545253922,1365527665,1340129163,344498532,179351786,1278985201,568529864,1208167709,202182052,1295856624,1310172943,1291211352,1072431259,586508441,341737771,1328792442,391869179,1241961780,1153969090,587360575,15012677,748829,243264804,1201770768,499536134,493786686,591124396,904121085,579893804,20064031,1142108158,1163253483,650638792,1050504244,1051922256,1054594515,1450144849,1135655149,540350193,308397069,1274048389,920081622,530350594,238801305,380434245,1034590117,136642539,1043052941,1187936256,831122234,8288207,192659927,483545808,708896951,855120291,252231429,490890759,172688420,1262315285,47926509,1068641220,912382419,1068519135,1480066701,222921247,1381711352,607645033,949537868,487510640,1174444706,928872505,745352511,1451541647,1333522771,697203420,821540484,1384394784,962972094,1353471433,725549310,1353285547,308872375,676636904,205716326,801243983,784627346,510584347,514069895,710809974,904988829,647626442,511476276,636861041,883890340,864269720,79501667,1232565209,1244234573,461509816,363854391,1196655342,1210074583,1264630042,457100220,858956860,1183602244,289276630,560677102,1224331854,123684449,305252935,1087170669,1170958307,293229358,1470355084,393373204,1075821755,284354541,996382352,857249624,771359934,268043808,927708568,1311697553,264072992,53446118,1150434193,933300447,1344021320,858668768,1400429606,1209991324,932743157,1239733785,1279096064,1261643764,461745499,103157934,1463611918,336567250,931093095,718945126,1180016808,13818270,808204345,556477874,169490073,192035585,640662091,1129502327,895191391,286594481,248994721,1018741809,479360991,454965666,662233610,99139100,182671136,118257058,225127110,651716516,1464084742,1122602414,1150031670,871097189,1450586667,358007685,814242567,569683875,694370371,1467011231,348084874,12428842,657382918,249571765,802308145,246959937,1017586511,1361946348,772788688,1221773973,1181740316,604175432,1259374402,319282326,946124176,693826000,235409209,476671316,1482349546,1371892961,1485520334,1257691053,344036165,968901043,799673356,271549527,516463053,17828389,1162574468,39978213,527101618,1198857048,1148173874,1167576615,1484583739,421453410,470190942,1150370622,483476061,1352250592,905637686,243058509,206000622,679435623,1491317026,1258171459,1496931663,178010610,1215492154,692314443,1496052710,881081966,187756483,208614347,366477959,1258265560,741816099,608272865,439635167,114909413,751134555,1218653401,1349453426,506237588,685915382,454459436,443069672,296405507,1022529573,1393358689,964170030,955285783,1052526128,1401409880,1029927331,585951742,407776644,1308028897,857346037,1351229068,1449848566,500064576,1132972232,786004375,297030941,306477634,358601302,662903455,431827969,602384237,1220012209,80086359,277360830,596020426,1218084741,1036676845,708358904,1194007941,22806213,289348469,835938597,110349505,1212713987,1132439097,1263132206,981952393,993666209,418147706,699309290,120647667,339488155,741863867,295167468,1267567809,170397106,868840035,1128116932,980550252,652368555,1328643203,533480819,698643966,963296791,860369099,1127849326,470329602,1152242382,1348173567,999376612,1419831010,1100537015,454794260,1220781892,1301012999,234874367,506729295,369703003,1231638274,1416971159,5992407,657641481,1406056035,392932770,541117823,1493471345,1240205394,480735393,1183471117,1413364077,151237529,1186461795,27486192,296322133,623398659,637244267,1403665840,313177083,1213464713,571462711,1165783491,1344220732,1277784844,1090299231,930132737,335328506,1053526235,370578315,561100909,915139651,1044185424,1339357082,540943540,1190028065,321341960,195896954,1083023725,800995202,1304020747,958188940,272824109,444401167,1460025421,521383710,93577507,1204072314,540094353,1268381237,806908046,1174874534,85608031,167762214,31248455,184757802,1103859939,1285717920,1002870171,699108527,647846863,38435581,362673845,415199214,448545164,93906804,1029752949,736682254,201815959,1239515087,664250396,796843555,84773472,1303923020,1260510719,491050702,29421518,696262337,596505811,544224427,1401934559,677500762,842317972,169829506,868051326,204261885,790528958,278597441,472977505,1182173494,377151996,791206934,339401131,109504176,1154341877,948172420,680325692,380499389,817943434,1397392236,1017940681,1041759478,1434122471,82345391,119784995,1066480204,703373758,796573749,1184500199,555703057,1216719798,27454139,1414483915,1218219042,1134203650,1113190095,348992809,1344174008,1159596412,1287534720,820030906,404956097,849819415,369881991,1030402801,1413773668,281583674,243140084,803615171,1127431312,840961927,620529580,1194354484,738548559,886383035,65876033,212345611,1245799832,1480053484,1388660607,359370259,1217401841,480525044,78351264,1004641046,722051504,1364305945,1141165841,1477194909,1161215413,179005907,429633140,1232800293,120413906,1459030198,1400928484,382278353,860733705,1014513747,609608019,1171884894,461798302,936058562,379509278,1238406002,802655662,1194879350,1400276150,1313350105,1378253371,941864523,1339149566,1485478507,1074884225,932492665,386885731,592350964,1186559737,148781106,373586786,191748363,1341232375,699818008,1418519643,722049591,464959639,1310687539,132284834,1184273136,1174316918,783737447,1214009726,62886989,1003581,499678575,1455781612,832333448,1369539317,1042754468,192624746,14130896,1393641360,1167671125,1333074395,632253026,1129699504,1367338267,1100295927,440816856,294602729,378730525,1066117098,514138985,385857411,1472414192,1450052597,547517385,1166922589,525147337,903274233,597789655,1115699014,1304455417,645634194,1414670692,388429868,1221806588,176701534,36881284,771013186,167395206,84693550,772484407,322961598,621574692,447156325,71012925,743491789,1459372225,382514934,1272482468,414343609,694712734,213566759,383240284,681609427,108724701,13812027,1007278757,205840081,629444749,675895471,1428912362,199089654,606207432,686477601,1033533416,1451339242,973783630,464479519,236248777,1247506392,418596146,813018581,528553127,175299647,1291934257,365700640,494292022,28149905,1055492661,1495041147,1182433431,256103287,317547070,780960807,984894893,1027392574,137711863,1111266760,635538482,829078749,732379788,1407906910,357925994,233867472,263113988,789266776,826404320,951331818,585480575,1446551125,4254196,83890913,1144295967,795553921,383640313,719497461,1260542117,1183532691,1119025797,465482976,1208803661,461713880,782391923,500869680,50813242,126105318,307820231,1300476955,998725106,393378580,1179597479,1129026589,1485203478,690025923,400346691,817403737,898689537,112147982,363384388,403243524,309404949,454788669,661027861,841045318,685350629,812874235,648015970,688433063,1394039942,1211735835,1220599571,438702754,1253012199,838370118,204778246,599156056,665506308,160383620,794726286,838889275,288870131,1284886069,1256191034,1338240757,819146850,373559150,632861912,318844027,687123051,1240396743,1495061771,1002274418,1306181461,984766277,998917702,341940530,569485285,443257898,176879254,733801153,996533717,108226479,874958309,1269158319,1351767856,894947359,264662360,125966972,33482732,1116138800,494465030,564600827,799737230,928174480,1334972315,990053878,697346079,283455847,662524125,635292628,1168312049,954221412,344951757,707011894,800051935,1320575050,1080747209,361888118,108524482,1049803897,278322784,198005092,842448665,1233100315,389944328,1163334908,717787578,785034271,612400514,423694954,1038937717,700682017,79890886,543292211,704729783,186870313,583574856,1289451848,490858940,305238712,1114133648,825577441,969236635,672048497,747094174,1080381409,617400412,1464767756,952031935,425620302,35638217,1045174187,236534444,46576125,1101483754,45053032,1401324737,959609584,85782823,325516930,427810261,579929727,1325053852,26114018,289518554,750009980,1307258056,539455287,1116422370,457800162,188093447,1235577967,996942808,1343351794,627618852,965930198,655590229,485514027,964404588,831071812,464279381,1200515468,541788515,1006319855,1241292001,1397570293,654725122,562556573,1308756167,1437107503,681223520,768591652,630099064,1095119849,58060498,829100222,1062983644,1494018486,991116492,1343843759,1193055889,309955311,989848014,1270283032,289793703,371088472,1476972244,168317367,45008292,874508941,1135088519,289753282,907793463,1415561034,1375478343,595901981,200736359,207799224,585482911,1357557907,1475643467,547842261,1036838955,138145173,66171623,600756135,1017635965,1335547940,1395269362,1064718613,1027158134,1041521612,1185315431,708993000,81942554,101873419,952515240,597217916,281333658,1290045342,644383607,871961780,1222251606,154434951,475778142,409642521,1113983751,1277235665,890485402,96767764,726738817,1258944332,123731287,738058604,468322589,155832625,112252172,382412514,327504524,1321240604,884605094,1163844571,1134898553,997659979,582568368,1157526224,446676364,155414583,667377191,464436413,556879945,294497807,1449072665,560432682,983891990,674919647,116322642,1137814481,304201022,957993944,222885403,228318115,180898516,1255619656,782352789,317596053,558956438,85419621,1164365897,101801282,513949414,474869112,18648219,1214853377,59200027,446472486,1035408395,734824937,648533533,960022220,370866726,195306270,875126585,1342559505,1006279967,1274752423,1305826609,552400242,620261033,1108672012,307199836,894607005,854552586,822860851,1456320777,476268801,456123824,1000305808,1351654509,1362481039,372283989,242832917,228318615,1446139185,1208712302,117451659,319567052,937615159,275680986,929301099,310228739,389238973,582246942,595550767,42915870,192902940,1289031026,65951626,1289686825,746487793,25195720,1147097191,735148517,1204432337,220322395,1172101639,775645163,378052084,627127905,271907472,86979335,581571239,668794251,319380053,187622109,308279663,233554177,1102059558,1175780886,577949620,169406168,1167886982,621987486,909115619,1489882055,1056920624,494466950,212271134,1288901499,1058390358,1105482108,779673833,167517153,306934524,374028346,1486794420,355334550,1324613605,287785974,459613056,1063192513,136255007,1041919518,761651286,859492397,79062407,1378507432,561814120,1210284589,1307571055,1070287264,1286086046,850795220,22282728,124945578,107109739,7035447,310064122,305647322,463665724,593483136,766876103,731787379,401622896,1213305588,320181497,1323753927,1292634963,241232198,1182044796,1429090629,1491869599,99483152,717212900,398143277,1125681285,943304641,1054881972,1201658988,583029131,51189805,1051064235,242384582,823676162,1177342570,721051964,1156962342,858574088,1407594598,734525926,752409326,1357826050,232498639,729439808,262347730,1032111036,1321884669,1201797692,542369108,1052947766,1451500775,1124128658,773501949,1475888501,887014112,976134108,124362544,536683628,508554790,988745431,1380960289,427149949,168318149,1058272878,1309493063,1314300740,522460502,462796179,69906517,288442136,1135482901,217888693,527180395,970955694,819117750,457776018,641508523,1043206035,775890604,1052930589,389627698,1153565221,150083007,83127259,346342165,685472800,639257680,1273700769,110273321,801576274,963519218,1286083071,426556272,497810209,1077720216,1338601748,590053150,887251005,948994109,64354267,728460608,105163628,1376572892,440182760,372892308,536900282,1074315207,1460275488,985066962,1233754012,684996746,297466556,983022223,781024295,1384984386,139992932,660166858,1133124519,840787985,1081265146,776825634,897910434,731721414,369902781,369531620,337623430,1041616934,282852565,1164393534,967726831,891274265,1041960161,122134578,866101204,1033094665,1471009361,913749496,906767982,788042948,1024889473,1442621027,534444676,715333979,433334229,154031916,573141010,510125835,1462673514,529575849,650622202,63616222,1473802045,1279871486,356782141,245701072,623905869,948847280,1084997340,696927023,408456970,914702530,1200225274,36565249,1412349621,14492627,1032747078,998772197,362979833,406151233,511032603,76058346,141917871,986241118,1033184196,266621111,1414501446,42761285,347676540,574169856,55482384,633767771,1045991682,393929779,755964644,567478291,653648989,733757136,1214095799,908937746,408797678,197905228,1061538773,1483478390,827024047,642225206,1322758154,1316162632,420274386,835366494,243706646,409125930,1073620234,435119368,1482625640,1101120949,1372054605,515600387,838941451,1157563181,727477792,1491971379,399808976,1266580497,1253386506,1085759720,1200569652,304731036,1404266882,1335184309,1473556724,615051933,1417424544,21034631,504591121,823554567,1120957983,227644413,1430424204,378595684,757070649,1222918750,1272124844,1277147772,328789888,288162424,563154705,267210925,673976321,1122834838,1321140236,424773923,284055799,248568197,476054873,1269980767,872426254,61236253,1321446753,345433830,10508540,975314524,209856072,1134730747,916352427,933473465,1344970191,884128196,957580417,661388341,860173066,886802982,603765716,150519857,432432972,785001806,1316569751,591880297,148100740,1048642581,1310284241,190913441,1444826095,731003984,357195417,667940519,629021434,637977822,1408001828,652993352,307297482,1256559137,1191783726,777638975,10912726,83742318,995367410,1115603407,172481066,89901700,1049525267,582920999,1347537117,390863450,495024644,1222668222,1023505547,274904488,53080183,718630900,467790855,455989014,922915004,1353262915,513243653,1055889098,241722122,1326993324,1422981763,144221601,888909598,1321945647,971947213,762955711,1352216170,814145328,560313412,21259472,1099660288,363739634,391267516,983316973,1207040761,916130041,1315127482,295741897,19610040,733626382,299770784,1113017289,321949099,490651524,657579356,1295408233,1281017510,824146049,1136149331,483859220,844103962,679458677,1397102038,130518842,1243928657,1358123278,578945027,697007190,1047271199,47553205,800980464,665840292,639138181,832788470,788698997,1387621074,257256368,1030730901,365014516,970237090,370850123,718682319,1246025904,503918540,1475734590,29241966,757172900,381695559,1168702297,250701524,109922015,709412024,1282328057,1235483981,325733250,980837643,131951334,1363913399,787839182,1213113386,624545761,10158721,79458697,1317075080,165855132,245079301,508842743,1386618831,994258333,1012368801,1065149691,1208013767,975598204,528903970,966878695,101046163,629368535,916127274,1499064559,823914773,751421528,71440918,1168514650,842670216,1293399688,1035751468,95521188,783003855,909342158,911455901,1044198477,678209801,548110662,6985570,452860569,809304866,30947168,1421130829,1433152989,299042332,921663428,1017113233,153280934,88414720,1411389399,18610719,632284861,379163816,708410612,839984187,880136978,565197037,1337179367,1025867883,1358379336,1057706657,153927690,380871346,128363878,631535968,386507387,1346033442,453790014,229889511,437932070,1238163368,729872289,458238457,709929462,1281114803,609460031,1476846029,883956143,102264865,118020845,1265529121,140079509,35349211,1395615498,1291971307,769757787,76585820,101816506,412208884,436142647,1030571888,517274494,879603344,1212014241,407898963,909721460,172727410,660193350,1372903460,355630526,867210860,854385395,409111451,315724682,30761777,1355361175,297093370,131220647,868296955,1374832771,1100862682,1193090292,930782946,712916377,168000753,1304898184,559056323,1321145458,734200995,1138315144,1179433207,288972623,1432947486,49522003,1405351577,1073120991,995618997,17013629,1240602543,1149161780,705540382,969670238,309864155,1477633648,331953684,769117763,839200020,291703668,650721710,97751142,1339720451,1033776772,367441791,580436942,1236408934,65573857,784375795,1442173284,726283869,276952840,615055338,1096867135,381952201,110921008,1116741768,664205061,1384589127,346752313,1129179956,1268642280,203465047,226559188,1367288693,907617678,298410875,283908776,630363426,409667171,1105919914,1116533714,94000891,1075410332,219522027,512986831,276318012,1443690373,668625104,1136079738,1307769996,361995155,1251582697,686717334,875822757,1054255594,231509412,760649245,919422249,890326447,1101599829,395562914,1126235480,1104906943,657064197,515905867,1222154372,921248298,264879450,536251376,411007145,1378950590,393392064,1390804630,205761904,158651603,492090710,1477921885,497627470,303065855,381384785,1345073560,1216814976,38238835,193334939,100931448,702381339,1381126747,302619994,897835021,435568454,597848674,44855180,1251264235,1285128046,266313682,664165668,1324469118,743049769,126915685,155924079,1069831018,759905482,704115731,891925213,992876938,31533997,112726140,1130708970,428849207,950976593,1142659960,1400504977,29571464,411444420,849452162,1415003860,110046005,1396801584,108885769,202668455,680115879,1142684877,510093314,96234154,906735565,899532118,1062375964,225677375,837987753,202400532,1273578911,888736803,1035039781,184840234,1173078095,854779129,1136532514,970142127,350666201,578423990,177201077,256776140,51260902,1314895805,973671022,1050733224,1087971868,338336334,572421312,1362228086,973517275,132224106,1272459239,846847325,1324100609,509276203,1081386749,1019445934,429210318,458519847,151899055,1366720940,331747101,1137907862,279290460,1125289082,264690339,656425974,585421274,165189747,1152079648,437206640,934765104,239252579,603707247,1176552085,786013153,1128594322,159560790,72240673,1082826513,705440207,128805743,1074189940,279169342,6729362,318674572,1361214818,1366700997,510490498,58564800,585776251,873994229,657867960,1017199380,129619616,104890815,458631019,1366192665,146409553,711917758,187598811,947800620,880543495,255616508,1359319482,397063040,926906779,1141266017,219497928,517986056,898677550,933142686,342669945,930806217,1184448427,278418927,399228052,698347093,981144977,126835997,896490754,1237576056,1497455438,1000619539,97727066,1253185674,1027346548,59663330,541036086,556431266,514837638,948911452,1308382646,437837020,1251269643,415499266,854105581,499079731,991954053,1184320148,1195057180,694643304,1288091668,111829291,402408855,655322009,1082102528,241032025,1278728470,992303098,420383868,1422401429,22869202,453185527,341881591,180099390,334541977,716385740,551202731,464968052,1496430699,370418111,1148283751,1482075811,1167749999,273930514,667873323,1440820696,1077928686,647045026,295166619,838216651,592655981,1223184959,1393040118,113214375,1228131366,1033085324,789092560,829273145,779058489,90640308,791837790,972919106,1361450977,814553166,156563585,1074584667,64659907,87398026,731535474,914883566,704404429,43399043,544220031,1300384393,770228760,282636961,220635948,908017437,729601359,439862739,1003856225,796442050,586420342,1443085349,855298905,1413054931,568137428,136389780,595769550,1346458713,1484062303,1440784626,244337880,1368369629,463050909,1260699391,1015094472,641326742,1225252066,1077882205,126316276,926881919,821878635,1041937423,397451145,496764039,425143661,1492922334,1106089504,549394560,582434510,216786399,298072974,506670698,691237487,1392291664,749033018,260302873,746218336,730932704,1117080126,260999761,405659230,587348642,1184331276,529138324,986477048,778792834,547724197,549173090,1462652777,1218915596,405030715,631157471,119991437,400748709,763566378,726622942,1153492501,353251499,128064198,928668288,1303899604,1276853590,25382297,283897696,581644143,1136805448,1397613058,250529219,768598574,498813257,58619973,1064162301,1156479664,896078471,887491792,470063125,1123200434,474007835,218384971,1287394909,246214964,453595086,81812140,902423847,249301240,466120653,10536484,906411647,1476605297,1443623658,852557106,1083358956,890904729,172998969,1078968494,123784841,1070489030,1175918872,1246754970,1096800502,97941268,617880533,421886474,358972921,1358773966,1339814407,1462659382,279538745,1129394071,198420757,375655012,263541502,287771237,83113911,805556387,497528323,517788535,1475946589,775741901,43962135,851649378,303866289,461588747,82798195,1266988868,226264996,1300986657,337691258,579743571,871642990,171810097,1226533067,606292994,1153269263,1417164709,216215423,153157084,46423991,1042557937,67500117,576990299,526923719,1096218317,1372227269,1089404381,750344289,1499819363,579433436,1431537826,624059303,1283949011,557657551,2396567,150106443,748392276,461720459,1471318019,482498694,954180184,932551419,617830479,1453070603,174084849,1478042793,493821207,1348931525,236471151,1390417239,1413687780,563068160,972292594,55846425,401823834,965723504,406169117,60092612,123068381,1109867654,549198226,515212739,1339723027,717357050,1457250460,579907966,824034579,1087056837,900179287,1098122277,1476205050,1097681878,1221671066,770529440,1133862554,446719401,729979685,914319916,612658434,1471969366,522535607,807824966,167854888,606176856,190293602,1114294262,1100165276,646176104,1172266095,490975943,489137464,181715708,336168515,1350453712,165340742,1131843503,629273033,876553477,880904370,943424373,1384655268,1302185417,1345492787,1263813989,1323066946,358578892,651054457,24978259,1391394974,203479254,879344256,1482227289,493338074,965002860,1497903115,384163438,152212025,223116361,969779926,795588600,1299379752,1169806084,1103832694,77794986,226600747,204979357,1103004385,131261878,705216963,1338425976,780531994,312384528,120229037,1394445110,507824268,580106808,470168743,345994822,228935030,1331828030,117547616,367105757,716234726,597430454,124208708,1169474214,143734180,686012621,1482048577,999694968,21348289,1277728624,330381876,133267569,768239643,288289571,134592027,640480246,1371947970,1065723331,530675229,837236312,872817607,1349892185,1316979968,937985097,420424927,223495884,794803511,685843817,1302406789,770047060,531533888,756766568,176471512,1281634969,1182180313,1387809523,359999005,1323527818,702614397,98242710,855202504,186300688,80770483,138716815,1174108658,1496561826,1455121173,295808866,651884975,317697360,962821814,1308184339,91100269,297637361,739197329,1190791988,523909175,702414520,81129311,1112979217,1422496348,964866576,460752016,146434633,576132128,507238573,101248329,345774407,1424253352,911466032,736952520,1485963871,334436821,1452099582,523945260,1245154640,1425253605,966227166,1452599405,1469287671,1301242287,456662329,1336145262,994824403,843406242,434168206,496036895,1372295931,433449599,1287077532,268423356,729294562,11641860,95301567,616101888,725246475,918752055,1164834226,474516893,305066202,83548581,1346896876,353225072,1318828248,501691363,811975461,302459680,518301595,1442392194,484911627,1186887087,641000777,449956379,1305836119,787102848,318664131,668732015,96867857,1245768964,351694353,499951161,853555811,160944559,1083756088,1409982409,332240153,300882013,113497171,136463450,658422011,358946192,853820629,864275345,1339230041,623864887,66130618,886075947,964307560,1390177078,464546399,957718033,508702088,941073421,84460599,697612297,1033682905,1298266780,732929247,93955843,645788135,1293177678,279333699,326080698,693339547,1180393769,1159732412,1471202135,1444986101,954329167,449651757,435007115,179107263,917584838,1129551870,1060958306,1276636546,611524005,123947042,330279563,554876876,1313292234,105470043,230232407,809579198,115410152,267316971,1185710316,831624842,817990935,1096951230,943283102,685710561,518101923,1068353600,799598099,650482350,326105681,119176359,804508437,506617062,581776304,1142436048,876824283,1336321409,60749161,345774436,889454171,762703393,750287260,1123872806,148430220,1425017339,977728666,1281160218,773192000,316098320,1284045127,663724965,1300249502,988362556,923064935,135822869,1381424298,460894140,1316131623,147792049,46295624,833534906,191378360,462873834,221465532,510189525,752048039,1426854433,779104809,638099258,371969112,844718477,1203886496,1387205828,749770416,1398917276,54069456,81574609,849651705,186598300,1371762187,843102343,29297047,636125640,42320204,961931990,1013043534,74610648,21997451,1104192862,425480988,342333634,1013007967,252054906,1303667443,484849722,1390365919,1107952305,1271268188,1093658678,402511819,721253821,253765131,493618698,811837735,1460196213,452156141,74398973,210029319,327594864,376916604,1308226056,1482783929,129232711,187039434,891730612,286830704,654456831,366380642,55089336,356950211,465826521,609141414,1346206618,1137466692,231611009,1194998969,207091725,1399751653,125897411,1425119518,882004174,1274528293,1073819816,350215388,553327632,1129842842,153698259,15786271,1180120560,693269802,787772690,97817437,1499010566,1135030505,422265454,958549985,58526430,1385199385,183162853,810299769,731106699,678954696,507952996,408351238,873199641,859391335,520287292,432353354,1016517474,979960914,918165441,932422909,1393365684,263979190,270070719,109658693,696074321,31799147,769832744,270618840,1213730303,1074186482,446228680,593670715,1244336162,875706036,1371666741,1033222819,632642006,486758912,343082394,1487792590,429584347,759065767,427922784,1051398328,1147043565,120769053,368771023,1177640018,113756542,858052128,1397262239,715781411,1113729875,157844967,1124380256,888293211,884067505,1077270076,1072939296,401688750,599419105,339908391,902470273,457946174,843133677,235608201,353810321,424365674,978681406,225172891,766593336,1229387710,426732490,1190853555,159793947,1183751525,96588290,128591346,943960585,553704503,507615025,233914975,526737738,1000296989,137715014,201128418,1258679440,896165053,908154356,990764231,513927106,1442455414,917126992,826393838,348335736,114356920,1361854634,1282892797,1426130028,596129048,605606796,362990509,27799555,1017890869,1359706862,421642393,629205243,191007029,863404887,355471011,1302196761,717172093,878984693,992829465,821764909,484574661,884555910,1442035819,136243972,1449602383,54668060,288367555,404185358,954636021,529679249,838441938,724792975,1191284034,1015274442,690920176,1443157261,461460827,96040904,1152492324,94411422,1433707492,1236099356,720466365,1369054439,1022915712,1454874737,1388851855,803273032,971826388,1246678360,625136852,1287335403,1172646965,630250296,902418163,1206423874,1271870574,910622480,146304678,1396782180,1379691898,835117044,1421805250,513522508,1154429923,308905002,750289201,139654787,83774348,230779732,1059399448,1158095779,555009364,377948170,95218836,400653448,593265829,144275897,1117967766,316539762,126323294,347258392,279082613,1201579,1495611137,1300906606,607272344,295798842,81102596,50017360,1199381652,617555233,827430596,810136718,891867626,1050473161,1127206777,922304040,655629150,1035055770,1433357599,368949671,1292897301,835522665,647729956,437669548,105226677,931927385,486022427,413258532,884249019,1217044756,702176664,1249264222,432933879,228604721,938180921,296813873,827161587,1162072521,419431994,245557297,35511341,119572774,377973520,356636653,867771011,1009073876,1027946430,206881586,1054093232,1473465477,335942310,1196155488,1297740485,552767522,2764555,813881726,594343720,1175581850,1149234369,93551082,881580014,255264166,545308221,1326337602,769724857,612225300,798210414,1395251580,676824783,1379768347,1455709006,1318350452,1234205092,1271613642,1391758309,334486124,1013685545,481975845,379911450,1090039943,64672884,1046640332,921573151,61497211,1332374928,132349040,236636922,169244792,1402212176,1313825499,1491895537,400064621,410848396,700195167,1280237657,1352228991,237058640,149321520,706288368,1027009818,252841606,730944275,1209865924,55485372,353039941,273527076,1230152193,62172743,534627617,252346351,15626840,564315934,938684461,442816100,844938526,1167594901,695380595,26242180,1217980535,1253310780,54392526,854900554,811444177,685996675,1344040692,901918510,30536980,556368370,595501442,1212177879,1057767185,1284148788,557537808,468215438,1347613583,605929091,494310837,1018852604,1003947488,1077669386,588980817,1051828680,892210309,1001218456,314636780,453515555,730589785,272578988,1205657747,574438347,679036745,1177327339,1282135727,1299183687,24738201,1234119664,569268545,39399149,289415065,377173964,15549869,1303607444,454573654,524232709,1082006087,267933557,725743265,1143289784,73260952,1315979519,1215759720,451888070,1410639985,1127977442,143109776,716088518,105711019,463540749,992719149,942119604,511312842,1031371819,1199593021,238359647,1446321380,934874690,907437973,161378840,319784931,532851921,404976428,146559433,818357790,230528917,167721517,21450996,969171043,7154984,469237680,94580694,920512349,1251322306,879302617,332739458,696148152,616098633,204083779,9598777,984015655,1109913058,684341646,620817165,728277687,469634471,629849260,114288852,900240655,768829712,294055034,977006669,958267448,550500828,10626421,1321984946,554029890,905311974,1369942859,1405740595,1138600594,176560478,594526764,500048543,196123947,581050195,1115391627,886212290,806278663,1259163094,1240727616,149133784,1469337563,1483221370,1176778765,320581894,116360096,195818652,1024102655,650890659,605275816,352406615,436724405,1487588720,1025874564,1051371359,39564809,739220772,1462892640,913283912,283767142,405544305,1301408552,890245540,103848461,635029860,548354141,240711401,846010511,344577815,497398448,31662556,1070885804,1373399612,394852646,1226632079,431691946,1497453907,267429135,1421493247,1214111817,347451753,636723588,922552996,64656299,1382201540,1226360404,422531802,358890605,1435716412,1499903567,1313520511,242665102,710025381,574849119,981088128,834284641,1326633698,276429046,1017725691,1156896818,935743533,834493426,939776191,178584055,902649491,966382066,425158529,9067958,892943257,579738615,1308880676,76582243,725818594,93687607,1361612360,962397834,1080481441,772240210,155232054,460754193,1347333512,187768728,1271038680,361246749,1096683615,43462232,259368331,1216368747,950233074,423230634,1428320319,34616670,1388402685,1378933238,387321201,1379251583,1110447514,694612014,1051425836,37604363,1405924536,1126819328,553506472,1463998243,1255987998,498721398,130639007,171560012,859990542,983770070,924902365,547931502,331390779,1314001372,168769130,220243906,674197174,959699990,468306088,532797581,133674565,295547694,828132274,196072738,1334391947,934932083,1499037549,665213597,6441258,594274177,216245516,1419729545,714674628,731894316,76692380,790242646,245371037,638724770,1380609758,421455670,912038904,225287982,546239876,619677069,693915656,673990327,1274775108,944939250,1063918585,1123466930,1212594042,727210889,52792574,440869686,700196556,995120386,269927855,1331466486,314417529,80060283,404315708,603062069,287906871,5376259,1407761579,607337750,800121854,1390330043,325178798,247973479,13920698,911865790,1427352220,505621394,366432560,1081395905,1421140324,857352381,54831476,491386617,1007923181,925385884,279560027,90347903,209710654,665031914,1016288473,180102650,1249445236,475846243,249376855,1309344194,1247527984,213698734,889665032,651482909,38510345,143821397,1256214292,438928290,355738066,159518143,66229242,753875613,897514698,1476676769,246871867,1222741412,907755001,1081032994,612659400,622856025,1343667043,156723390,1424369978,597633556,292350807,1211547022,551050517,57356613,455529134,250780635,802888455,1000856047,694551574,400768840,194323908,373826990,1462608508,1135607960,355538672,481591963,47589005,314911255,956260676,658986304,651110217,1229549883,732482603,187920749,1355219490,729266260,767378558,883041958,301033333,1158111152,231046060,796860565,135726507,201031711,1480944184,390610610,1470261716,555311813,1206253143,534326015,1188532019,1130330231,231002640,1110036165,420024319,105257867,491558505,420685084,96526675,351786166,354650297,1389201507,153584837,150119057,1223132701,821126354,991631721,462842494,1419067772,1213783180,157199592,374848946,914311664,610665810,1414547643,400050767,385112002,1333946169,1140353438,71020207,682420412,692339897,143222601,1236901959,614095653,1273515774,1330840440,686512938,892504446,858322023,872436901,45018246,693110961,869101486,86236170,1241701677,1109859438,1349800217,311703419,1494664722,868341175,531830231,174852119,390405131,1473922576,992480606,372033742,1278728424,310323567,244601166,1221264319,459574400,734321570,802949764,258558240,601185344,180049802,812498104,1278051697,1278810914,520752742,676318602,1067394551,132525960,1447926681,1196737077,17928434,1324282006,315128086,294831093,627147050,916785126,430515645,715003654,965366697,821387049,314113840,621007464,1304273615,430165517,512102608,1350531065,518426609,421733858,399624231,944725049,1130853485,87072344,38125879,860374375,85430905,616005267,989408398,78732293,572163006,1224338596,269104376,798508899,82224815,792753070,1485282615,1050777322,354338346,971560731,346743345,1202751432,896076500,583977923,1226629521,231360310,369701840,1120507630,887582083,1026496328,852392631,745492139,1251383495,399617263,862161681,1102910862,861597958,869272686,777423127,459831754,808083395,878437004,425895676,998954918,139976704,910393064,764610724,1024393437,672926701,1146978390,714833685,1309727779,161930324,467478024,508129905,578225984,1481846787,1159487580,514091584,486547877,832030119,1444116346,882631304,704474741,314530884,680926890,1332281244,918176856,1445436945,1032810638,1202104416,1237614775,421010456,218059243,577472686,233446006,771643542,123256751,505582049,860348798,504318216,1459831743,185941142,960922397,107409962,1245428356,1387625635,858007011,1465169397,1056996912,1044723374,1400059366,934629975,1082586451,441412376,1420587506,688882122,880096745,910335434,1444342284,1201813276,1435636096,1239434723,1061495898,602524087,883865406,1161384769,234520765,1423032465,180542308,1230088890,548879985,1062429566,1174527067,187368634,132064361,1412220602,106255552,792605180,910342856,523026096,1389506675,190149140,1370684953,1429924258,50619224,703088863,379407531,771615623,1096993277,435828847,1394634543,1377448500,656995752,1181305208,46941895,979310375,280159714,138906357,123945796,532847101,497294831,443296764,54494520,1289642399,1215698212,184609307,347693902,965098183,1143734945,280310031,274923315,498448265,1037423756,408624194,1233294762,940335861,1211217495,637534328,475653538,1499881739,1033146996,658226262,1395696062,572096755,623861885,872831405,1312226769,357521733,1170722146,620562813,249069779,120595487,6705348,438272029,879436420,324207507,221349729,1025251477,1136134194,923739654,139499906,155878484,98032347,33721137,733638029,1133691079,1381323914,1364541039,1371277820,1346809424,911483630,138128525,1191063142,1099883094,255791401,717392479,724399459,650337463,286601481,1360949542,900951933,718378008,75677186,1045642696,152819207,571627341,1350340082,766170425,364670208,1230678324,87600922,1025262235,340069462,1219923468,338011214,1214262454,766550877,545186765,1372778552,641626728,679244278,663152973,1256957423,1499585334,116359622,554465939,1102280165,400870330,307374879,1448633740,831554568,427709197,1100016023,666338546,533632859,724061015,1086761545,578237885,863249116,999594716,1479317921,314702361,296230193,933037199,672729763,986575015,1097432350,658664755,1256745662,1376597863,927183320,1027960620,1365132720,5237868,1150794443,780230953,511904028,213669816,594236607,1457810135,468845380,729067018,1160554978,690679177,770331109,842512239,489870645,779209385,658859813,326845244,1469067449,241905346,636116072,917967074,357909070,1060945822,630692593,1268905567,525902844,423134062,634490847,114539673,223144960,753665960,1104044007,303375492,1166916346,1481177213,1254828968,989303975,800930551,141181140,658788136,532433338,485437259,734948917,640731220,346362708,1433192558,1340632505,389951385,1069305981,484777211,1279953801,1213642116,846195297,852554762,462037878,982210878,348271709,448280274,1291056691,954192974,1190422229,1366450060,207822486,125352652,638772444,828171993,1348999925,933644239,1361098617,1161356307,65586882,1242347874,59258252,307288028,1422194040,818229455,808839658,596756747,607562441,331811040,206913469,1456451879,36906006,760206129,1018785279,1442153023,582618943,770897882,344388100,389613782,1191045098,326827743,751645614,1118352375,1032361018,263454702,1001731166,36162832,1164053259,920976423,1150909206,581971250,728360217,256888352,1242813744,1444178167,13427277,946591515,585402501,336849232,1097545616,294951968,1451008012,923700398,518346691,502029449,26484230,423574935,317944744,1426357567,865675457,515472191,895543389,380456759,81483944,1182098815,718842795,105439281,371094897,1072430099,1043774644,936439630,959578742,1011148378,1327121766,303934475,961396113,1237907854,1381259524,1484214393,931985513,227940959,386242705,1259304528,1401647998,303310379,574803635,293152929,631313567,1296486280,1207054682,1186102399,513715222,1439012459,370360057,1170188788,1139152280,1036711236,873201347,638581487,1184842627,1232416742,1028299410,131247417,562026686,50536164,391939217,492830107,819150620,1005945207,262582410,564902054,45800786,445849331,373398767,1167468766,117165972,420721622,1266269773,666576421,124640458,224834224,1119081772,1267795122,158747302,1094114612,1014950984,950163686,1284788061,1008338659,554299360,433337059,931491013,1251416406,1278807561,1134408034,869100749,109511294,1432665297,128522469,670250231,1117389817,202346426,497234410,1073258592,381091235,204542011,864428344,29055275,1316161083,1478341679,1286624937,1242710250,973367120,55295380,1467810918,1283009645,1358262286,859770843,45745808,28533968,1133125908,1315018585,625142244,1173372985,207860129,1456202485,648544147,1447136076,198539719,573327898,1048417645,576435943,280839376,255054,524292724,665277074,1309450630,530495280,1223244276,352749961,1270598017,821682820,1198878634,530248815,234696179,45728262,854202214,401685538,1369122925,807685019,184785420,782331302,536812162,296025429,1343871720,917996380,1163865363,824296256,18929438,1205094165,585435036,1282801395,812388788,614337734,419747485,96568328,1098540931,766253462,1294649411,810063519,186477451,265491324,1176870589,264643757,206400217,613101555,574176708,58020486,1426044336,1112965310,484714011,704183967,48378428,263116138,1381619456,1227329745,1371944871,323964564,40717712,1430327356,717949998,1242275796,1229093924,1382124120,364803379,1221173009,1150043595,964724926,847134291,267885680,935040123,687377068,130929951,151910178,729217340,470619772,766791495,75209403,515102865,1136577444,1013802607,52953682,1130564387,1320184704,989133492,1394536500,1389129571,1338896260,797787084,1046177373,1160187412,1081652907,531083012,1424137593,44212205,1138632679,1004678402,123322050,1239216034,40362393,315741772,113586361,666625322,298428583,485260934,441086850,967817135,970023319,433992675,898739466,509931817,1364797500,1087020127,1309835974,1056647894,1277971487,385177924,1039781732,1204864803,1177308172,1187834070,1407419230,984051035,572203656,682955331,341666298,218082550,840088923,716670980,311190488,1246521696,470139419,518918139,520744446,1160821215,1349184259,720337338,996628634,1369201787,1459677746,174235733,561305387,618808277,72033351,156312074,1102043963,436846141,1376167955,518458736,216784802,903401161,192653490,650714397,765170509,154989193,585507306,1243882831,173379483,83012213,637605809,1274580586,1110090376,813431255,713670733,849016344,895075647,243200603,1357957446,186997486,963833193,1071214353,677080730,658286533,44670324,524608592,393511213,1389021219,273233425,1070260303,1019913436,1375119424,1319312545,923742230,1255337365,1156091337,1205002657,211937902,1147012167,963666856,1343039842,1336605068,230904964,1342204102,1289566140,346909885,629423703,660853547,1460521901,490523375,1069259681,1309935520,657411401,991032754,486985487,571455929,1264970392,1451799483,348277562,770631860,421764226,187748836,18198468,442875569,1364076485,233454174,874720342,499513540,416311262,1252003639,534955653,1036793689,563614793,105183324,548489213,55540357,751363073,846309819,1451436318,777015226,814990267,692797977,800465101,141469266,1405995872,634748791,538202516,592539847,581084135,1309621787,690604346,327165453,174114349,210563812,1314503130,231608678,528357812,359124040,1131570982,121005894,883992451,97671639,137277594,747755046,188605828,1017753091,22449315,577303977,606634661,868784407,94199673,1154690070,365548267,1315035756,983810932,205971548,488578202,1223290585,1226354661,1093508860,989395761,1096132384,656005277,1320867693,584697015,706404373,758698196,105182078,808894433,1465554410,1454159855,1191353147,181057305,218967989,1261326180,378182776,887719019,1158769709,203438806,831553192,1074179868,696987344,779461755,135259505,693861936,1415526663,583741257,104042306,667332413,1227476943,1115536606,855364448,571392635,1218213803,283973712,1430796908,271092161,658085051,183033274,710944142,884745455,1354670428,577596509,241716703,2191234,1367560884,1167653192,1281544212,1009227219,1075646793,592611748,955043756,1183994107,903982950,306090860,726046582,366470265,1340814240,1256890127,910281271,170907103,957144685,1036418594,446334210,1488012620,380508427,251637594,199145993,1362361198,1454853938,823756859,1391021184,765061473,1117400407,171863050,1187108357,1310731380,499664796,733060700,389382222,1231319064,728058927,860561168,451019082,1439417294,867933977,1391011197,116178443,559521357,160336728,1421538222,279874929,967438229,445820421,162223028,87902118,757904577,313254018,285272155,230878015,927561161,847207567,612378538,515504332,256203911,1298112624,1260514082,656337519,1292773923,848078069,1154736236,951165837,1479214228,1281161834,982992863,1340832655,451349793,1261800028,147534431,1376649592,1300056116,709487348,526787757,708686663,501724882,1103477451,758418134,209846716,888621863,1467852854,1447131870,706800998,950343780,554098532,1399620788,143079709,450987813,678065180,372076344,221285299,378122323,518606147,322507547,1379170055,106766633,418489658,1042360026,695836606,417813712,1249136626,193731219,922140260,384517763,667451745,312630197,662150819,1358375743,635219713,846543846,315918383,1154057253,1324464336,672627610,677513586,1278105426,1105526308,1395083273,684167182,594831439,888338705,745292574,349448525,1093066823,444221095,1100247938,1438006082,1483909141,274351356,496268327,973669455,627547892,955100884,1081422852,210938964,1382818704,88310812,905223447,312339043,1134095518,1164606798,1176085945,252913558,578480235,825669819,567797423,914221153,1293184484,672473312,374774384,53675556,20776009,976548480,1417396243,132365587,1104636507,302254229,294194506,1426599679,501250113,926843204,993088150,680259880,42266932,1444965929,1007906723,774827549,749345537,656714770,105854913,1175201710,1359479765,180948402,83931841,255958017,988890510,1487503603,1078488096,218622863,1237116464,1266813585,1237775159,1202218231,1138220559,721929123,953619496,1348027011,558180523,1469956646,893859694,441484130,767629175,1174271299,378328050,304548182,56157163,1097395268,1005678276,558026997,496626964,376560939,594358047,1406501527,575931952,92547561,228725360,399686910,779409463,1212592909,1443571442,1231763832,489488916,1066885491,475458820,1367486428,535695160,751609698,1029296783,1344760973,1007619579,87321288,289545303,914908447,679958728,1499123601,423880135,164288583,1451214144,534917237,936270629,555557867,485818957,674206927,300537988,536346103,2807791,23477702,254009111,395032285,222927893,1251443510,1048826440,997202825,892687777,378143830,1386936431,1368942788,1397178627,968798058,142326639,1290464510,571365898,1165690641,96242710,982719187,1249797045,327601724,1088378347,52094790,1445480331,315163137,300717502,1227064271,516539370,417051006,535359841,468992584,1281275338,1453208316,144875805,1144958675,897709992,19137933,286793932,645417876,1106051106,1331726073,1405847917,228669416,570120127,672596613,1349389284,224712016,829014742,1051629056,1068163627,573689043,785751155,451112192,37276522,1213232643,351150758,233344026,753510505,118271002,192028104,461979711,1304336224,59325775,73379393,947966574,202944701,841917651,568630887,916636971,203521849,295182032,1417058975,655973390,1328388708,979301122,879037339,456164228,1192209723,838140931,81776121,760305159,285660126,583109962,1383191105,888874577,775040529,565955691,410966155,311541862,660091649,1490006922,1019824503,1458107674,513345879,2114688,1266662142,1419346388,819647836,1371304310,51287440,146213357,754877408,551163226,645488785,614491358,1444869236,1444275572,1207828959,839828696,708384944,972867411,393163548,556784489,164120378,1135562848,1173364318,693705759,33655630,194030713,177237277,812865432,301451856,233921007,711630307,836053237,504018920,770658962,729630238,529433694,1023769230,91610808,1120389307,991641470,489270580,893212335,495695965,686855149,991641936,344862723,329431475,1394687183,910651162,202356582,550928196,135251288,93036161,1472157139,612351533,256165650,1035718540,328371910,1139255911,173200678,1097117585,309772276,1289506107,823190407,1235427445,1276786233,564493254,158819945,590283708,581140738,303969077,256900518,416079269,416053376,995602225,80839499,119904938,260112346,373034289,582357259,445539231,1021026435,1225856256,813069820,719756198,1218114639,940689888,1051644550,563947197,410440553,1187473693,1182074459,552407895,704845296,1128404592,99713207,1363398030,398029426,501034036,885015207,1158576630,622156770,890630017,256237029,427318007,962773721,376030125,944139674,1253976578,462225315,882358104,1213336753,1361765051,767429,851034287,963552051,160444589,581924350,70435842,776908579,697494893,224080221,258423290,282460378,1228797607,305161529,279737830,583177744,891244949,178920659,1489682369,825270546,873849269,708881250,1052734567,439644137,411577455,374240041,25213648,601126822,306680697,271380924,316501038,688048819,1365920821,1076745405,174110131,680470293,1215710418,793900418,43430054,432211644,911477662,691144132,349086199,326961380,1467557868,26480371,1234719467,393369408,1213026063,87020500,803108835,1016791497,39948192,1486240316,724160157,1082523671,1036495870,890072108,921453737,1134408873,1113009942,962994767,346857388,569599079,1383199959,309448854,1260312235,1007472206,68329963,610967751,622537889,1321839386,968737787,456917905,993622706,789201196,1477447728,656324284,388336302,432861087,761333127,890621280,651797375,88145536,280976190,1345361494,1382342064,346180961,415300269,975065114,952350594,893145772,1454648162,501354959,963494687,1047792117,1283839068,1353600094,579218916,1109838641,37602032,865839685,809917463,520986099,1128170460,930158780,1105470161,1190746947,779003507,119433273,907878661,291959572,957254696,1314756899,1238173629,621699419,713660783,1310399463,836959180,854231644,245630334,1304727019,895189831,761482838,1129030318,1313681545,723123733,703790779,704383900,1439616031,1469760997,670609673,525859353,53303242,360397457,891513438,153785685,449134453,766412001,159386449,273522580,1224041444,619692023,1176858363,146126609,1387846615,419084925,1041052650,275255248,1078083244,1018809274,881950736,828691331,958359616,1258729247,489652670,330543226,1252567819,331336645,1412101399,1126098596,317223147,1185634506,676944551,1190395110,1137381443,769564837,959365596,1094955233,338535493,82113051,526852161,1009225898,90931495,274186968,516716662,1190199520,391404925,760075048,870409485,1041858052,1145523700,1351018490,1025139412,938526407,497082422,504072419,1012430948,385123724,50839091,182165564,1002225392,313308792,1158359689,216167008,288914520,844103449,396450395,1315092679,6696966,926978287,1316898251,595606662,1014918106,1126708601,1205935976,88532529,729016902,1445536171,641323431,522191148,665382733,416741616,613224820,265592668,632785501,263598910,565300900,1347565330,986095717,992773476,366175289,690771792,978029097,387572277,636398620,1376778766,1268443816,1014828663,1149503163,700155916,1239591040,373710921,629668001,459704669,1229282350,1267852591,494125377,125526394,1353322256,425088143,761154436,910880607,1390213947,1037708595,496688023,1123110275,816709560,449507179,1441200314,1140071129,824159343,1462087643,434350144,1165748412,444889097,1017378947,342747609,1043804476,892799245,665450040,551553977,1178597850,390886870,493572362,1010772436,1133132707,1055676980,1198225602,659709889,1318732595,389875341,1013008216,437290724,177709658,878897829,319736182,482561130,1165367994,539324850,134158793,25069427,596630960,1358081805,1320567721,306208565,1306955249,333611600,1135860759,1421115379,524993939,275875478,1316365400,87374647,1011489187,391297129,1298111421,827768566,56895810,122300113,84826315,813774265,3527476,55140829,728516909,1036479847,411833473,437080611,844124721,1197885356,678509893,1175205768,1386309543,709082457,949266527,471465170,490950271,768153246,583369777,717230299,1348600940,394449277,470973848,778672246,182101503,595121652,942187847,752580545,678748234,286015589,402185129,401182762,802730145,110476472,695778842,914210318,1114821067,1048612113,1044328036,1113067233,578589311,1374118833,966511920,1002781545,993218738,28942942,1181468749,260822305,1064145188,1421853881,156303077,1121875180,899347702,413009582,1207375771,130691600,1218794524,617107515,642230963,1427148930,464336325,107281021,413502891,420570767,1097202209,14838914,995596809,1185291161,49031545,720809381,344773481,399180859,137265095,1365892936,143403829,541519377,896375469,1050403326,207365247,3579377,670545588,522589601,1032898877,1345606989,340324843,230516212,1133201056,1029443343,534232103,44053831,581434186,84710988,238630803,346450375,1101723997,286302188,890060993,1051155277,609041083,1152258524,1429270979,175605729,923201926,892941780,1463568897,1396582934,566224983,1378931368,94370615,170386306,473279432,1411305746,443264653,1211234643,719026806,578348309,1422706345,1061137229,148495752,1053857074,1427404827,1108680184,1073703710,1426883036,8969809,991248012,526348906,34177237,1277696724,1344405535,1273080880,940369801,1356406424,1465682776,866247385,341015806,412346888,971534396,1233986676,573328344,1350765621,856445812,1020364871,941550448,669197143,281431904,322810672,631204653,115909753,1183374282,434170544,1367656823,464631895,1168501470,1237745664,894711533,992055013,158483462,1081254487,1485865758,618443898,547716497,1129331683,737288558,720240893,1014548483,65103150,477762449,1262262731,1466179298,1208127680,1150647595,1194294361,1257279609,522624202,1289328548,995003185,387034650,1214802231,343583405,503754866,947594369,269471180,984059463,815882225,1317116501,572676327,951108811,1183812543,1270857300,353007669,917182846,153282280,253037596,1001762289,755779901,151475662,1245763954,783938061,259783223,469064246,239162118,948389736,324415851,314992700,764798788,1466861500,237283649,1143558582,1482264106,350207293,1217678539,972813380,930515651,73474646,179295763,695465493,848864959,1469130678,740589420,1473751343,313377280,1092488232,1359406315,769637968,18551179,206007822,142892126,881178768,856194041,366848566,1099256184,905624765,963642142,974852861,1222780183,1386532059,392168738,650009983,554301401,276253771,1046410209,1389543087,1232471580,491231269,451878520,1059497492,966834512,1050738082,303326661,696869340,1217104044,169258880,705519273,1257826336,1185266120,66534481,1278935716,799273116,954879921,829801858,1139863699,1428078641,344472255,1366110723,414136407,1288911476,554580298,155922675,478251632,561962983,233483748,1069706050,735267735,470704963,512990295,368781436,1351829597,1289560471,1413624221,1020395286,1459788080,818678829,1424832258,560567796,191834234,706328683,1184855228,416343980,1401048411,450859086,926165565,193489046,266846095,1171814672,1290696537,579194261,373464609,1252368349,1079014178,1389215736,459831032,627764105,468168362,914556640,1339388699,804782663,468037324,343886788,1338985236,549426358,80240873,947798502,486395238,963863342,1029937527,741578853,165438175,1210563113,1037239714,54794876,1304813066,1411514519,1366257844,657329457,1242414632,1145843603,1176966598,650418463,1275957446,677595650,515448664,561259058,576249371,869041778,181463305,342024425,1367079627,476527364,4170286,1102807041,826562801,1336541438,851261038,37127366,135309333,8644523,746514692,695710786,34508810,478957791,1169205081,1268830304,1295693256,448173465,287532228,1167875366,1058228913,246581962,153320496,26583907,862471576,382117264,218597547,1357129412,637434755,1321455229,1307806001,393138650,258519460,901822932,1114863318,379872442,1237751299,250687464,63013840,1012207840,138656981,1197557175,1385178586,778541846,752229624,1080942106,839705175,1098107861,1434348065,244148611,530677188,621997137,462305796,1209259123,19370229,751978318,1144501940,1465388270,920381637,750407170,447833652,1114088550,488355546,881032124,677259662,1491749851,171484106,129335264,305643634,832718480,404230787,146403598,62413560,1273894338,1274094049,102267038,262341356,417356375,428406505,905165241,65439385,507391114,1233785789,134980194,1194737268,753570073,268243836,650666625,1030640148,1458329133,1179456622,1307150038,81535550,370034691,744423665,62370852,1288446619,1461331593,585551804,1444290025,1167859136,774263376,986491229,881956553,1035771659,1353152139,1017526333,1387318633,592513174,516974712,1398403101,1116010284,1153738277,122150375,1172616245,1293751995,679886241,825335294,1450917422,857775191,1055064382,418300796,562613607,96173627,714501620,1091016615,226755401,149809379,216687482,1090760287,510290696,972837490,1461345550,69121051,51471258,1014622031,474435287,1197448954,709976761,493074160,292404835,219799640,810626942,1372876261,962103915,1289996504,282160926,373496771,490143221,1283062786,541202860,164124495,438364514,86477316,1326597640,980731651,290130690,1034665468,1404925022,1263966666,176532883,626217454,1204517464,1477980236,95820648,220171554,1249264504,1337198370,1001591655,1294724800,821300765,463492393,395021631,480781939,1105000939,568685695,1169888201,1265245254,93902323,984884838,93162029,201377675,603645977,1347257692,1132149369,403935555,792417728,1118785797,582669693,891347898,1259139495,1474124349,1401397874,345026717,835066125,321310644,862910381,607002140,728463957,1078704733,504512265,414225072,412715383,637423744,210018716,590901884,446963061,1403517027,641393165,765603437,503990473,1081683234,1135357721,396406521,1049583923,263628470,625326301,1076044670,973143530,494746601,265422521,177871543,1427875109,1434746477,48748622,827649259,98234646,1265131553,1074425340,531060233,644128763,743568969,1018287613,1449667563,1493666350,950478599,1085317639,1051974980,1485611226,969907039,1087776906,1273289405,332270837,46544342,566441888,228507158,398909554,1430733279,996859205,162099769,1329558970,1343231521,595120051,292222818,1286740338,982376157,783377966,1425540115,42582541,198582665,772086513,1303398651,174707269,536052529,917979055,1267268770,1371677503,54292052,1007646856,759976877,1055095225,690872982,1108105830,1028045731,942635011,816816593,1407676734,72067699,459912208,440351033,1292171187,854485413,952764142,770743946,673552902,128728491,147086596,552397137,1082423103,1222459924,1145026415,680467818,1028038882,261275382,227825223,1308014085,1018961100,1364351640,1333164114,1075650291,829222417,1168800917,952237652,998453869,830486729,489212237,980908934,320757530,1123145977,914444390,294036512,1491786531,614698133,1359676976,1307500951,369055560,1226015640,543348452,1118344415,170065479,582607944,229512032,511675715,1342288805,1031355922,20982884,665635638,1212594957,1263395742,902346409,823038714,947568035,922026623,683621194,1146671617,689752070,636800845,984703305,320291660,34878865,689960944,16822645,969836310,429413107,869038396,607928090,752036555,574232355,541248692,1095633783,948341353,530625450,518602516,1347514986,729602272,342132122,925930341,1151561968,960548076,673333809,207627312,1119939484,597533661,210694058,189565995,89752829,292163416,1298723621,1374991563,400198824,701051259,532278096,1011362878,861899907,365041692,1180661807,142999154,181994346,1483977090,717439327,707204889,265100098,1389191316,759961115,1444594334,111734897,1143791507,499838473,1105573956,225802144,1312312448,1002513346,434520765,344282254,1085599566,1444714213,1051532995,80315403,46473486,119923329,340076956,1375300184,947783278,262254734,956830843,1217554653,32448130,241297907,154929495,1286792710,202471598,531247807,544267911,421800114,1248612886,1447277772,261092857,394819572,1417780338,901031021,249589590,1009130120,702528726,853996677,661266742,1236898587,1070995535,1275738124,180406919,1137723396,177049289,192573995,1046065802,1160899174,720222670,133934754,724386306,214526714,1183096281,1272614033,663787405,305438570,400879901,1173297704,1454996033,1077895465,412055818,911636424,1012282987,811675350,342985359,572860066,679134899,1040996637,1169257399,1279379233,1223346796,585719956,192161804,719221086,800501455,590926016,1254421847,1473699830,1072759590,1102891234,190357786,490168851,1050337876,790564581,693406867,382175110,982109367,387122459,516902575,345250409,595708019,576008298,894440592,1081871686,451839586,134172901,164842335,360274499,655253080,1281681767,1416468636,431988836,1332185815,901240095,987367973,1257669465,955100312,1233723499,795475094,877742608,940141402,119641092,59329519,1025175074,1290387148,9675005,1252448718,928954993,693983281,459164107,1071189585,571221967,203324232,373123193,1277326653,804095646,913640072,1480885113,313439961,923779413,671533618,1079363641,472087627,1201173227,1074186810,342873197,88828720,785803975,1362224955,525093841,1179306509,671204794,893148088,984786723,1092625418,922971140,1252035332,692622061,1012669203,1052302963,826361446,1053263428,207499168,476207828,334860559,1112569955,1030511694,1138327018,322898299,117633786,261531369,1197346456,1152114206,815703716,45118156,1489537647,12401606,1411282563,1118247018,1268529458,488119937,373108095,499519727,652916295,28581584,832417015,165713719,757374609,95272501,727071108,74712047,235914596,1493674417,110545165,486539106,899625300,925257207,1162801367,486680010,1220211983,32239609,440275453,1408181980,728900888,578689126,1469543089,698883741,30887415,1183653561,1474887990,52465584,1089952996,930189975,302080056,800391582,1405015140,1005968448,688357524,525228858,252119971,105545765,1435939391,998797544,1120544629,859482044,1453878467,716117202,1320415143,53841414,1227439603,529369451,91770841,902262616,1117100054,1211832210,1177514527,397607793,1399904411,121279123,665034930,418584950,372348616,883430417,616399052,1341729445,238703744,985369749,604052841,474911070,289180642,995518476,1277978957,1344893702,1499008722,285040720,1448750353,1448731115,167409198,586577210,784978655,171720173,139921736,1487177791,875547539,1193516124,1324591142,81673470,1136086947,982727682,325398243,1314837351,637161775,452197220,1263255798,1221925339,322851661,1011158600,245492450,160541482,335226606,993715048,155646913,340248235,538335120,102229759,1394952299,403711250,416911641,278635032,5295278,1491209648,62884960,1384495120,636470717,783412264,386795462,1476454715,1387798587,1385858143,443668431,603904993,964416860,1451901686,91128600,1043122157,1098666031,56548590,289911301,1123335801,448572316,487724524,1167067636,387346381,863869815,88025727,567805140,133720606,951724144,644223975,1263600215,984191261,456383215,463642498,1033247549,483308962,1419622686,326058510,920237159,1408898387,920611007,1225150609,137802889,1420160295,1106509619,586705432,583068238,131133057,865318337,765877143,407175577,1172085398,420618552,367126540,87088455,637628507,965893969,144983179,812924951,375420734,500181057,334468529,899555097,917849831,1371335250,488402396,1270048937,281957087,1342673372,114841788,1258505347,654718922,1452600019,822203822,899662784,888924134,1286076115,1174319582,954497212,650780395,815644734,641521449,384422644,1144035078,304932706,961358550,822918314,871735419,211844563,1218650688,283548652,347543112,195501439,1213391992,1370816598,101126442,1112920231,43082991,590712913,133139747,1257189212,697201088,267996034,1121069468,831020908,316732168,276254315,1133207785,248229137,454291434,879509204,425894819,1310249890,1352060110,769193758,781682750,560541397,917860203,526103783,726516507,613576842,422972174,794296326,1391456289,1309051175,453768845,296530884,414606155,162431551,723443903,443725183,433302092,1188146114,587562264,322479483,1016069238,460910930,950674211,1431157211,1227125502,1302675999,155394733,89264573,731603581,974803513,719980175,35578032,1410265891,834986442,495414227,1154820900,802698681,762580723,977717736,17810647,1432371484,1329695494,1053050705,1333871256,377452955,1159818788,391386931,962767699,1026833982,704344711,1030438936,1371696533,490121265,1382530869,997919438,1343955717,193548873,789026224,346765277,425944859,61216211,24936901,1129126512,1197903619,845671060,1065299348,1385915151,408023039,99451091,175096127,58133301,431581702,869091873,86167848,253931383,1332291820,429964075,215232152,1371752594,654238859,1074159011,1252902559,136687791,1348790110,854954696,303595906,1085003493,162856573,993066778,793091167,209458259,926641786,800372227,296432228,1235927514,1390559952,1390962797,1426844776,76955728,144424355,877774357,1380644786,553646465,1043756023,941926558,560053825,33015548,133448424,770932296,744970604,818187044,1232213823,897425808,914980332,1449112305,1191574159,476128276,1491496729,766040270,604362839,1040414608,53803440,663082417,1388335196,309117520,1370547930,702341300,1364922187,936841217,51336448,1407806140,564197324,1355568493,110602785,673996735,1173236439,8098828,991639488,896894937,509753520,1234008522,188138300,960744869,875163397,679405739,188759725,1384138429,1492636925,613618466,1449721878,498777923,1140935364,1114906666,1264308784,1361426436,1423970316,1252655293,750573720,423320252,652293787,1342147944,1241805447,1001334278,1263596315,1425529693,545998497,303743156,1440175504,912343178,1357506914,720871457,454331464,1316096008,267268833,1093046980,100412067,126633384,1465351994,1395048915,1224297175,922541677,1367219896,1469808125,665736745,799874162,730780251,270226447,1360274227,870265152,384743779,623039604,1183506415,632843094,550182179,1372427280,1020532067,831404056,373039311,251624270,759286761,232036685,218191573,901452062,859044641,1021285379,1467916150,691983836,1339341611,985448332,470820608,930522366,733679950,1077041727,948560544,402148526,121546851,548453344,1361190062,982430225,393700189,1358924000,1426563351,311414406,1045666851,421234643,1187617402,991914261,634380453,201816927,853666123,796558594,1119511653,393002017,873658217,782228330,1303110820,1471626197,1065722840,705509682,116994384,757024922,501425510,738068274,1010263048,1302665135,717394130,1040839434,1011289551,1001965563,918271631,710769748,801445858,213036178,1056253853,658012064,183535618,1217232934,838327843,413417565,1191906026,1142812683,1105960986,614582767,282948001,1035556312,1220912788,1094628335,346962461,1469959428,931655129,1289785521,698606952,1494754261,383503488,333186147,1263321443,1256562329,42185666,939932523,419298043,190585384,886395449,255171544,593511169,961276129,539558247,1411758393,953243493,863093362,232473212,204118921,523596875,303860653,357232296,297348183,1190582284,275308562,253207283,375499599,1373884301,235296881,103970182,566053087,624347053,545460023,1149559554,63801049,666722877,848213347,1243493803,443995094,119134411,301894230,1462696346,1029055342,519249867,1115279061,221537703,292488736,36629847,626330143,1453615058,649308704,813007190,127088054,688554297,1064430483,389245129,1171333050,727374593,88708186,327234114,350016387,1186513296,681304885,67746535,289371322,994011365,376675225,463511290,1303659901,1498222534,279833906,505031659,1433700768,1266462485,1422692562,800656810,254716684,1482301669,1184761854,981888797,1418442197,724570491,1432243970,544047991,946393830,7681753,4067393,261930417,710169679,1238427556,1040252278,621024366,1380483501,1191167748,8448475,385062562,270427682,285840676,811963606,620273380,513443197,1233509004,443264712,401409357,627457178,490322347,658701199,638532144,713593836,761652863,739567129,1201130655,548632692,630473756,1485017552,524941994,1489579646,1127869027,7440534,1419044644,1415703121,125580700,1249916017,63226610,317107934,966607015,293444445,40926144,563960155,915695408,1228614479,896081380,224154224,1185528494,287982026,289315800,1018554728,1339454867,11842762,1414587187,1094326889,250128314,270239545,1106408560,1380295142,852655218,896086397,382171579,956366477,1004423967,819386268,733882263,1272988755,423969275,1027402105,1084639372,725283006,523834997,265733300,431579509,1163510200,1183015490,103080647,1255810810,1391307021,1106175697,445807233,145539901,915663108,920802535,986565063,265693358,175926880,1014864560,709413423,809712763,455379642,462458086,1296721905,1083451129,31153184,1117912943,1234645488,966487408,388597180,961602247,271856706,195469128,30810562,808608900,1443273219,895995313,139854201,601388523,1303216759,851504755,183109566,847727271,56582164,687881037,768274667,233629933,1416810531,313847418,606912645,1274717914,346732094,1234092070,1209442266,596231153,1413830527,905918459,467300790,982027884,1188336857,253888392,975290125,801779723,777453421,1307747221,269965366,219242950,1340737895,1244314895,709630784,86034438,1320485230,493818118,382111558,1429940420,742562941,707238262,395545247,565201781,1360778674,374046982,1401546361,332076498,21674018,1138294150,1307237538,949408164,427233542,417200314,759155611,766590973,1486006053,158381249,967487783,74626705,1002260663,709939643,1488914440,658655959,1445679466,242745379,1489110879,229119418,194607823,1082664196,406367021,8125564,450398455,998855137,1162086725,1180450497,512219438,1383452623,1005703894,43079869,1328639082,692956241,490014266,346978604,170252701,1175590506,1081954070,51104721,45296799,1167694469,961272792,1123694053,561707835,222038039,127568648,407724759,733070225,1128140751,1279429832,82992251,1040060788,1216848599,197181309,1106775683,1948779,506943457,107885368,1133793447,630255642,1494374378,1022272225,744124966,36966519,213200562,561117683,281741437,916822172,795787144,944991131,274625855,1369279149,545519933,55865191,684992215,1238888906,975452377,431853802,63873436,300907666,59326651,1088872450,435697222,1498183370,995109699,1449491350,691683692,836126205,1400368171,912259318,1185985027,1385802671,704218605,1150951553,115384802,534974153,1128820638,1322715247,1474941705,838267358,1262557166,43927270,1269576757,578915125,187777282,387517444,645841869,105788936,273553364,617490256,166385293,280268478,1212554863,669344456,37557387,66080807,196969093,453684215,95245906,917346476,676531406,795784796,414533899,355449356,868858043,717715325,119751625,931479332,343944503,467255271,1374962647,15546953,920008116,1076242917,1038833176,312232962,1275457559,11941154,176947581,1302535988,98786458,319909879,260795610,1032865874,1131783374,875728738,1359683940,8566218,1064269742,573186024,693237512,745350842,1196349320,759626316,1121595555,1241030935,468433241,1295318851,52000761,647161546,679486127,387542393,455395488,350898876,984676518,804194323,126707427,795356277,129374313,694831624,346828067,646112717,330335330,1281897081,1082241863,1249923800,187215306,145261710,371035782,605630132,695522877,1322298011,1131205719,91023828,183493417,1203951952,546623083,933639414,639576033,1316810700,322953692,1365737442,1415360781,1289188030,1149529490,785425472,1490126223,743674907,1397251364,870307883,1438425746,1025586050,1348109015,1159056280,939077520,435202231,1386075519,1486028437,202528804,895887480,1228324190,1381026363,899697266,733086160,7038327,855089490,139425157,1437048466,663552424,213292228,588126028,470613524,372277389,28285064,623428182,883782571,153693539,1354424363,1468027374,1226789092,291289733,1169399693,176659876,835125059,933726313,101473326,779939172,1446155529,1224697660,233679418,266023404,959448877,891877368,968246895,1139003509,1487398511,494870251,1321975107,381341379,1295242869,1473264874,143899275,830907358,1242441262,628530268,56406519,654609009,3968728,1169474618,110606833,607106894,1457230820,970721121,643146612,1011224821,443795148,1093873434,500708672,415141880,1021318346,468975555,845800493,1482814341,743058430,1099386593,1228781891,765441378,1309819839,1346055645,585358547,629334938,1580778,935619345,541223331,655323225,1305450333,1191322485,1315765266,736068214,724352373,1358535335,175445690,1311206560,1482536607,108825500,910246137,632504493,1258182736,408435645,630810444,1290585670,308133249,171511655,976551676,657724174,1081301174,1339003484,264953565,32038243,528820986,322198615,1304632491,1024324055,1053004301,21129983,1266186009,86273861,1168503787,786774402,219314959,1341575250,904409756,1281708862,117700727,581072244,394230717,454498993,477361307,1448131848,973544753,233240130,1423714054,1221719927,1433803168,304855455,955807036,811551311,560637277,23947571,1278524659,639751057,909086711,1217061238,89003457,333053745,764883326,640841227,810272553,720545647,1461851026,746198029,28506371,349730251,761810239,84718678,303987895,386177909,700005670,1238139447,586096125,352758249,1017944885,763530084,511586634,657601611,939475620,1349689128,277510168,1292550227,1426052476,1365290667,964904302,1113578218,1189487237,665647862,1393646094,555269869,919827913,289443547,14185539,1080949666,193316818,668911375,839738630,419816862,63985989,626069647,1061627894,1121213933,850029868,1132773630,1133153669,1490379484,952503984,931003363,1196650147,96955531,75811661,219841473,311829336,290657010,1160177806,839260443,358808462,1325831592,1010158194,592248888,271566381,1280935619,398722412,1053845291,194332641,363573197,1222617583,642419743,503729633,16499889,884918014,989458410,1199636674,611854371,253323253,276828227,1142252490,1396791839,467876395,878075589,348283296,1238001254,418908336,64870070,1294196751,681065709,783510449,1279211009,743461304,37105906,85436282,1276540433,798805722,1089897248,1492403079,716829773,1242554772,1204193028,796238031,45156098,336182686,37383860,823086091,554657765,1228038393,1366922204,1146568765,395330171,332827421,194302363,639121137,965071808,1307929026,1345177466,128395290,1379554652,1340326996,1295632632,1151245824,1046198769,15404005,1222946819,394714648,334687007,736797770,1172862947,945691203,307749612,1415892016,282924185,1054219373,577115095,1171934776,776122125,459841603,11248332,623800668,940610635,233549740,854636232,1176207246,1042133404,39749595,413678278,1033085953,1205873255,1176298219,101561266,372082398,1123221717,855446729,179188508,535329968,606039484,673478838,923843244,903812036,1306644467,1040814233,1138760551,804876142,933261699,732245042,685068990,1028447518,793019016,102871568,865448009,1308618353,1313401110,459879652,1237204715,106004892,475640076,1361928763,1045674821,483618292,935216082,913360447,66552843,854776368,7722304,528420499,867614699,1435275619,1001442869,693461120,1470153866,998242629,101458731,590653135,980256413,929674854,674879906,317062776,567011198,1362116631,996311804,281984954,127017382,52151176,929405311,709845228,502469231,371970698,83629598,152821018,935876996,164922114,952738869,282665573,557628085,1067535871,1068008506,1374024199,584551528,997437097,1001712703,512980582,1213781645,1429942780,1498541100,1177161266,822363541,1113484787,515679010,983315857,1402139165,1043017324,584323706,421378669,194123421,609118376,1385849649,268663896,1356264983,317852552,572938949,494066741,1498910736,849767831,1196816150,1330194636,648709801,1278710390,1433745207,1484213727,106730370,1393317836,1127328109,1367004328,1074627706,149266223,1482183714,859596091,405792841,1035543131,624944141,1336883441,53841914,1414422643,438548602,347184529,59132283,12617802,437088418,898875332,285305615,1179103436,609811660,683548814,353970133,144466653,156230330,1388743884,945332484,25605768,1182345028,306309429,1028673963,155038079,472008813,1131371850,944665914,1310983252,119541524,90071038,51983483,596958601,1005738527,696443529,593589255,429468299,1248814429,170153818,512511066,170910060,1443552639,528771789,335097615,469967601,873671041,1015394102,46837508,357915382,773544069,717176027,1107795519,478874758,746606102,787851466,1216942085,93104118,1045092350,1292486143,1078834881,1217015628,1244434507,631885114,20652168,1441458942,251069067,816339771,960601634,855159861,1294277772,704473386,838884592,843353458,1314595632,1360265350,1338614820,181379993,675407258,24550553,8554570,695546324,564876301,1488008655,183005626,820182417,638670469,694004666,706408187,662446881,404534962,487194760,475655842,116284947,1479602306,1131053379,95024007,191670927,1070543668,870107471,113802083,755736503,220164617,278083689,783834932,1221593856,317492983,1122649653,566770269,970040189,451005827,1260503485,232865861,475159366,1352026003,1324334141,1340358972,39473980,768352361,1402886819,1130988606,1484158607,360660467,104219001,1412328150,114811665,439551713,137647153,1191735484,926260434,1000827697,558533015,466159353,448862855,976010204,1428244754,264617751,602654837,661689149,1401463518,1281959858,1422192973,759984511,1433482254,549230704,780987360,1498802557,999048996,1064168784,1121910791,84144342,55952067,881450389,955128706,1051170938,1089482144,1234397966,727975582,537994925,916384904,825147306,668635448,1095940976,721168313,425511597,538133534,30405836,1493100171,1369738555,325941846,876425573,1019755705,87721589,684969477,921923166,673477434,255248393,1379766758,678988188,82808680,1083260526,1442991636,1124934829,1173618198,778726340,718781318,896485420,543410992,910497591,698922051,530979255,404559436,744732115,813156924,1119894132,1102283809,15263359,627594243,1280596490,793363281,663229511,799829967,320736815,1067612403,1299884225,1198187150,841125097,1157094292,344548466,1056597726,902424117,195040584,1031269470,657056218,295113230,1139308731,1139316063,514271958,319551643,1252383841,950539756,1054552131,1261210665,684663743,924849451,90506675,1288128885,426667685,1225027723,1410694523,1328663140,981093117,1276032436,902594025,664301365,375872137,792780302,605082939,11957449,647236005,398275776,832445380,357776385,717663136,371847968,1216547958,918803585,1203309384,1397055955,272112896,162855299,883479330,972977403,788399111,1432624582,1273339184,236048978,573312443,36583845,114919083,1082536078,1122763748,284264046,1202345320,1016700961,192656297,1284525048,1348928512,843920822,1394852727,253091271,971704793,306266933,1309349130,1294125425,1423227244,271350707,589347215,633647988,811232188,1456883733,1198512552,311211132,661943911,1036001038,1044069643,364802068,1038831274,957260618,1011296651,1425451182,798950562,3565438,1486092894,109268927,334835003,692396930,1418815729,1440077859,1224856815,304694244,1218403209,604722171,661565616,881001452,1251103669,287847456,122677098,1298521651,1400366272,1361973605,1092727735,252789564,1211059642,162368469,733881636,358606517,323806043,705588821,914710355,1316861133,1340907877,1214468431,1326839745,1333742601,918227049,1120546416,1176590191,599217777,164368400,754048959,109563151,383428680,1377931287,1210517079,1236040368,845193818,356263189,1410248290,1162922361,736095720,207708604,1256524943,269154712,104693642,473592285,718419108,375130789,297539023,900303435,781887725,613746632,5187789,266245845,382535795,1369830727,1470380853,1120284675,1123939457,455981321,180058111,563080173,861353672,371808751,1082408750,358000293,122764623,968819810,164872607,1399813162,1155471100,954524313,679402104,229068352,353332501,48584405,25470936,267043226,469577777,1241140159,684523167,866036701,1354665600,966213002,798479285,565303322,1402814866,281327909,1151194681,731937311,1374864876,724320755,863514248,830187679,1058855669,1329324263,146022737,986536251,282417052,142843862,1126723124,334702210,1421424766,983351819,79384833,159543265,1260268295,901534362,287270541,1366929252,1104946019,62999679,122875469,1404824794,1162225526,1284069812,1275271895,701638128,1273371320,1280348973,263178323,970092502,1257505679,592972929,493564397,233396276,120510352,582494633,540378542,102657280,632344954,1456732898,802369116,1023323911,493109226,647235795,1233539997,847732278,9712695,806530418,190889851,1252888566,424105154,320013757,398109002,443580962,1234264982,869234719,1368975022,542786386,279485438,161346458,316515663,935134143,1019163732,473528561,781427190,592120747,196286721,542103148,540226645,749401151,127921342,776769331,894356645,540752894,93961931,1410726363,768579170,1452561707,1098278622,831655133,1332404832,64203973,761420687,1041861106,726969609,128398283,1493742069,583202639,827856380,27189542,1015542301,17638685,2239869,603700868,1380588,1202317232,579963248,348245136,1442705749,1138952743,211304022,1364651441,736119202,1062666813,209332446,688218275,354859310,1198566244,1058822313,70667076,1350358342,80948098,735804331,332382305,698568198,192051669,937818894,820990046,1183642067,77962087,253797223,1229323299,798453424,785479394,724153768,722685865,1332322532,813337007,1021341461,780493700,1214138761,936514237,397418838,984724197,771501013,1096121441,1435311511,428497033,1210601528,814234542,365363389,393397516,157765343,468823017,1394091399,1405135329,1150819790,130055938,413461085,1183484016,13299291,367088136,53669431,150069263,455735345,557209859,1131617771,814577137,673619613,377262011,942736404,680053890,223868549,851397159,569699057,1008898566,547455255,501445765,175060075,785914766,714293353,1104695085,1084520556,714054178,216896174,1117018417,1056134034,97745015,59730730,1233301096,289786831,338901614,355667664,637965364,780608008,1173786744,951870011,1290333548,153536632,515126544,1388110621,468979763,1033255345,431555301,29110172,1311218445,580273022,857588330,458221926,146015700,386738936,204686540,405864952,1220845902,1421602165,651266442,295222614,608239488,1265542540,897788126,989050814,1247153687,119505834,1196164926,1286820204,219294658,42760786,649471153,1439238338,101080769,143781267,712513101,604485453,1186825308,1319576122,1252460606,268132020,1248946481,52896251,254434171,1228842472,694749503,610092377,868964259,796895523,337618207,464022819,1471629165,145772524,992724797,1498491537,628671461,897793753,1169389272,352805874,498126787,940841101,262456348,890514249,918242193,1380832171,1041178632,325151289,506642421,1047017949,385279947,210659569,1017998301,584852806,1317016241,1035834654,404025276,1225160126,140706207,679156270,686408721,1368731261,100480819,585177096,636250773,781342261,1007553241,768613693,947607388,702218542,725028774,900816215,433369913,1344805207,931617712,848823883,1352972250,1224273799,1281637120,1006138307,323776034,1106535844,544481459,1043806628,31343283,1234372174,769890343,949527399,315836125,6776444,1008562390,1105965112,1125251953,130750929,332979725,11130508,780758338,1047533014,1424498869,505224870,806562285,159117727,656784697,1274648467,582782219,712824504,816985893,863515408,1184651318,1177965539,1312636671,1010018254,566211124,1375009441,1395712293,775439554,154329228,1312865869,383119906,480016422,540528594,988516643,474463770,1012606862,581137884,552848849,1165270337,1186740753,721886369,366574150,1477462591,259117263,800874365,36027607,1314132573,632515584,1045573553,1178060337,1148598364,1257203659,1214067825,1401733775,1207804716,461946494,1423981044,131429854,546394712,56351719,315356707,325370044,19447293,153943608,951061607,1073590353,917441716,521115453,1336761507,391583205,1473373873,97924662,256000574,227566184,1018999799,1083899580,137907781,1255345180,451808490,913893414,1283220087,1083623994,799795282,1266528361,1285730330,272102346,1402765152,867645843,869642016,431333347,656799910,191416307,8879156,313931096,961255664,864320866,1089344418,1384837650,1474844801,143311571,1037671318,737275728,155413956,315617767,215054177,735278066,1232768495,1401233687,731169601,120773665,703993213,701690650,1270516434,624741151,634899087,964798901,1223747860,1216615242,164546996,370146528,1233738425,838275092,242752017,182946279,477100245,1306246997,899123643,1256972443,602942038,1274602964,128137222,1386801878,211114070,1157857994,1301800746,214861648,551127448,1135231610,746782980,29333131,603940932,1299265070,178221613,619898372,190527379,898806091,1291643509,644326743,1376217900,1203737154,678560207,105279497,519304449,424806820,115566579,158009892,1356166736,277196105,1370683920,917376264,1315058740,313682650,564581030,788483772,1244951565,819079315,1060429242,987819830,810748014,610828549,778945559,535369612,453410458,589733955,539652725,429657225,148088387,1047608256,1465581931,861988397,272073822,1155178069,1207476826,1144547997,1466161693,1166735136,382055924,785033797,633002670,417739776,336429420,1021693509,339293819,748726326,654776447,210009487,1174750088,1185009468,822950162,55398142,803273771,465271111,471613845,1426886012,249729135,994749237,153530911,112644630,10988703,78837204,697135053,607244691,121286392,332623604,782118420,429312774,638650946,223377354,951742771,745794190,1389288968,1198034545,1436642566,1354206925,930894320,1226734842,636841066,1288144398,990991722,829715924,640685823,267807270,1367359339,906692870,377244510,1100909521,328617897,68061691,835935014,1342491635,46626706,1056408783,102304013,198280935,1133262280,331262794,511641039,188049336,887796210,1467226512,1012826177,1261305232,1261697077,661734810,584820549,1321371613,1428086749,546230229,913429205,511397209,746649999,628766231,735587181,265591879,49650440,641467863,1048562466,443611177,997820002,770194719,1269675911,1107642611,619007076,906078529,261483217,217238879,891251373,1008199189,1401108326,1111609161,277766465,428885305,1429534726,845809173,1441866756,1384738612,1460105504,740743007,773675568,546632381,970385634,1262263913,13252333,1019423527,839198087,1033320038,935356334,273451383,551103139,1049897790,280509841,1180817737,1157999468,807429688,1295206032,268029723,1349061723,321962774,1411045375,987193383,551682892,1346187901,652394609,881781229,1197896787,800235213,407818247,860232914,696203819,1205122116,929244005,599185647,1157454649,1178535236,1222512821,1221046327,758001934,114831155,1052543266,1273122207,960490150,636238073,45240340,953127010,1091759713,996700127,1357589386,1233180696,491828701,45322871,617698031,600881300,1480615467,448538678,572250964,844138098,1450297966,1212647773,1335400866,187218117,490168887,693162412,721000277,340212881,62626830,926005724,407459778,276804713,433770645,957744898,1499073880,1048522040,687867099,261673685,1164816122,1424388846,871498388,1265672242,846112586,859846970,1375528497,12515280,350531383,653980130,602310446,200391919,847506275,613832192,145129081,349142308,1483442439,688295904,496647392,1227893577,299448742,1271124078,522287987,61988708,1190238430,356366060,796858582,359705530,923457097,1221520788,1321910412,1363711206,426369062,1257192214,500848305,991808476,285718953,1177431385,223308497,104779141,7062990,1378742185,310083923,281282223,989234931,1480510569,359250362,189057960,419616373,1196129959,1025512023,663116730,917465021,257460534,430808319,1380597509,1414460962,120406819,771576933,1304683314,442704002,1043134007,1103679403,7796155,958960573,302750811,77566026,404616197,1120178940,676952182,950242792,1058543288,64257676,154627201,749242847,1324015124,102821818,1064682518,964594926,723710214,708063456,322278992,1157297879,326660018,1136829231,563563191,1191649584,1089239191,1133064657,103442936,522888610,895181539,383606104,1486755397,489150911,1416487173,688562074,922921850,444254665,1462444375,16358819,574584898,911877648,1334710536,1317002312,314114142,678959441,1115989248,208592959,502634200,690159045,1127009918,1148582215,789124540,191907338,1231519184,640994711,1271456504,803017376,915589178,29140079,552655997,484998630,986111202,1101377058,900225428,833562923,209410059,852785714,362405411,1048631348,1387899445,1445503506,145130431,1466026270,933514215,184295196,1172460013,478749006,162524174,1232059495,1299969122,1043486136,215000813,226792178,1400521014,702078281,527227774,1101324178,720403859,749019318,367807821,959249292,1023894336,1110930652,232141801,596316350,155531307,270260626,989952534,413022504,1266330643,235941093,472151727,1404713210,175025004,356469321,87249554,1479113440,1329686995,254927958,940046995,1141662831,480509357,782570679,1126824957,385124485,938188922,175484041,299346928,659572668,377968028,1313124749,1230134732,521611068,527547509,1120112058,601957905,1101176284,765451758,360432060,193471524,1174458274,389810369,29325473,1217276167,1207883814,1247065176,866952531,591841733,475720763,633326781,1187953908,532789930,119459593,236530534,114403020,528797754,1158937356,849678212,1486603996,1107823228,275421815,333364694,1205566848,667512422,1051560786,172858810,1405637936,298924287,212547683,1484705225,788092680,474081895,310705562,1173628131,354265931,424357909,686067734,133513785,1039352607,680018273,1351372410,505124446,1354216860,1021348864,754198333,161087244,792451947,871978322,651805854,392105478,175746386,1187924091,806773973,907764588,825758364,661851557,55953784,460507334,960069983,890741720,1484166691,1490309197,415372666,994356384,1285558104,169207111,462992807,844145382,1211902051,1462701451,929175203,526866254,306735590,288482841,605626978,1322015926,24995371,287217475,980696644,1435631449,408843218,1206624011,261612991,1041282180,389929229,1359592162,232486437,124858124,672545355,540650540,811908527,87320739,326172457,295044469,442674521,1304503834,764324045,16849526,982803413,1145924108,1461406200,672645351,225122121,1425923662,953499359,375955360,729558300,951200199,1134869640,294465665,78249289,484741085,299320436,1084733751,893184167,1261870113,700593442,989649651,474028813,630534673,284310722,183664189,1181524085,1429645270,1193675009,767876935,1161053674,887406559,112575492,1324017990,514172194,776355169,1205320826,1385106923,107917746,708536754,883196328,877394589,983014213,1405862868,837361758,1009432039,561690199,572601135,849745791,278531733,1408937704,1478531092,922738067,1225958787,399703563,1483984439,1059386888,1394987421,799439761,424459014,665199047,1123429046,845994727,357599490,1069763599,1183270088,168818814,1050823702,1357963836,805623342,1383661124,1081860139,1221686509,361069952,776867277,1284398323,654274102,692145812,820254659,198475855,386621432,1431373831,973591760,1146070700,96791982,397448356,246457066,1089656667,1243364778,1449971173,572363272,1196484207,1436560559,1384908082,1436012825,296080457,169933238,864632696,339339189,1293340702,441154885,510379557,1065341239,197380844,332890197,733481012,1283522267,1266235269,845629168,684411847,1417078646,743578247,60710712,181483832,1033041405,414591055,109403424,246453632,1132933004,1183054573,617295912,1313785741,777232652,1231490663,1181801811,763650687,144830331,1104083456,987451250,562429299,219714603,1429367751,1374314668,961610291,1231360826,935108691,929019202,747587785,21542036,483679427,1095906652,1126888997,872297751,1054723664,994266918,848625076,219408857,1291710167,1340629868,456520147,1490057800,834002894,819428859,1027698847,823699265,660797068,1256342485,697586443,517448835,1248379031,159058339,980351495,922424713,113926026,1461970051,1215027221,429469939,1141753324,1472711486,1172183644,293344926,182157251,80517557,525306639,1341735121,108717232,945551660,744859375,117778976,418560211,46426467,320832415,802125780,1197574838,1211268928,511572750,286024087,598550771,1107081312,473557556,1111568064,1013247171,657021832,740712247,1375058581,1458004920,1403617965,960970359,831516321,411141553,1257547852,150595630,609330495,26054717,625410670,1372066051,28823279,1170769187,471545372,455728035,1475333735,940408997,691824103,664564588,1427168653,1111634995,621110474,441235662,730389210,15099963,520738220,350231329,1476802652,1170838667,1204889057,1194916891,155027751,1306609597,1490675783,589832785,523376646,233278970,99797600,621781899,835423793,216917078,854338585,1162067039,900816043,225640634,452879126,1263096416,1409399402,383493018,1112746329,585924397,1026336454,84361903,702627218,930332070,1115458096,725861707,1434371599,179781813,277972419,1335534254,387300193,777151251,1373473060,1167747816,1432896661,92906299,932345701,1292932219,269097546,208128380,1252832840,1310103895,759439572,717939877,1121058369,1473221890,1478407869,1409029787,903077102,93563812,1421822030,1436196343,13080042,236179996,629223048,1134138548,1482327822,31231881,454391698,1248912274,1064362926,526755993,1318277495,1480001595,959457565,743065138,195376433,76329953,1406468700,1244818183,915891942,418559101,209308398,1488359566,304843377,986900503,657417375,261107077,641591828,13990327,189195231,1094456613,1323307567,91201326,1299340425,567100111,1154354089,636739512,30065411,172880273,1462428706,783020895,250640246,647364735,643132037,293655923,507117262,81926738,966773523,1307019249,29504672,202198576,1346557791,553134633,1028382228,1109052939,995514398,356729248,1304442792,731837510,462344183,22119366,231340211,267618985,205463415,193440091,1436230995,227907960,218515718,1109313565,884770502,1134262779,1343006322,552496255,188872976,506421942,901405968,272263047,98631316,879155250,687698536,138807052,843842118,684826486,787480027,974999865,1420464372,1039351484,482646540,242066240,168824842,164880099,444058791,1236031047,1008787261,153522561,58907676,457043049,812354242,1366463757,1011090491,1295610645,143383485,1491113232,379661533,231448289,1072698938,1494311757,622877871,1255348401,366814505,179692228,474423300,322413856,91025121,1450414404,35152883,126532310,136470699,1246986871,1482656364,641033850,1096071400,1366044662,571956040,211867249,873543589,1284834920,1116635246,154120360,1270610857,278958696,1434744359,159296018,1360342368,1013088316,575271584,388927733,1053447750,877700214,18493779,100955734,49309908,1215329717,703875408,805965734,1330240909,754782417,1460738243,354034771,619330159,815709968,381697608,674567383,712932102,833926217,1148887439,143820973,401532174,52019725,18583967,1239746464,998438054,1140201700,375080718,397187291,1323163608,104799917,1461249954,812401312,907386089,1055114252,344760981,1234733969,1472893373,1484110478,440165929,324819628,190091882,1495288037,736246242,169945263,673448847,148101478,1498605283,324248937,42152798,613076857,68210546,490615354,238170238,676241674,551483150,1139502268,1079299688,720838323,677244547,854985423,422845793,26006879,948355232,1149981843,310881356,675720326,1099950819,1133445383,274091541,1309352266,1253348610,291057721,96274589,339692748,1092907404,152266529,188791412,647531878,1255647611,1028602477,199491901,1181022277,392994874,1081216585,775119287,1014533810,1197975476,1180484020,1415814208,745607621,1134390715,570467924,413908450,1077075467,586898846,587063227,440219119,396906871,712957261,76831695,245705836,445751767,1002662771,397570803,1267945021,129763186,682056465,815188076,110537245,148686307,676035553,687452985,451251040,934223557,204482058,1325464047,352586597,618778538,1131799816,88328987,1189999825,440537476,1164772669,161998021,123592558,1017482509,516227350,15529017,1367224406,1341795835,1108744466,284172430,903765984,899894786,333910930,551761531,596919839,326891245,64406042,70426002,286288098,610337714,912309296,1240320553,105717620,137889920,741624793,709017068,695150903,609989715,926967467,1103226445,371026859,1479725129,577501375,1463630076,535729585,577961852,1129385695,839926672,632343258,1198087053,1278086045,946641816,672605334,150634474,1366236932,1229614559,1158915298,328392289,961491546,297950680,635309082,715098933,899849338,1283608704,1082928807,975015480,1020466318,878427770,264104527,131406219,526968636,1094169581,489743609,366440042,802945156,321197312,511548116,1272480601,391903260,428530380,1386457697,1334857339,582896156,1157433650,56178480,128639907,1005052749,221661648,1365923071,1097901501,898739589,1118595462,1093628873,211737634,23739807,52338199,1487667805,572029899,266961334,138100849,572729741,240982559,760172041,62080490,418595412,759244746,583369349,1136365170,284430349,291863850,792107423,1244610984,622638058,1360408480,595248665,1300589915,635328870,586230009,439385594,1408199164,1463959561,342916167,23498150,287881825,237324911,21351802,80701418,489485696,687342727,609878281,837627145,1169537502,662062721,1129877486,218921353,878834868,603320472,621363315,682217021,895823954,1355494284,849933066,386226946,620468785,1011937941,410404976,1369368994,272363718,680629090,1453853371,304493994,380501676,1002217268,107581111,699781358,152923029,1250291865,1255485132,696372638,1364410005,556601276,187184073,356900811,1498358748,42940912,743600465,1175774021,745327694,756163030,30188955,1444726723,894561488,836239328,739498342,1210932501,1315825702,1217957720,1150785637,1302483726,1106133894,672812384,85491192,722725455,1021360771,767242781,258619476,351925697,611549813,503463754,977037672,1384806616,305432705,856269851,261025794,376236790,305757601,1392690233,821213615,841572933,418201339,155020202,830942776,541067480,1024985434,597412748,1371045024,888993917,40984386,790324259,626119924,404895130,287884655,830206162,970534387,264723059,532874137,961812338,310357243,62713276,1106003590,676127136,814369091,1415606351,599051313,1465274746,1431238805,1309014561,969969103,166567172,284645510,362160476,47889345,1076988307,1046303449,1128067974,599240581,557341377,489345759,848467710,1155853884,1322252254,1002041618,463197732,1219522438,833838923,1097530594,390463,346469490,511566155,903504026,468189221,1230936196,55204480,1378645713,595285402,1186276327,38090888,282997669,1031735890,881753235,676072320,1159677387,497590131,1486719435,664401585,662009417,1264802314,1361066168,1289736697,1329435189,326015095,227256022,932242394,421661615,571561465,963185199,612377675,446915925,922879430,373004643,1275489493,878214186,809826342,482900105,471680536,833601323,155114913,45671862,1103552720,622322146,564202801,341968387,45296231,296545678,492241210,90377125,970626451,1372125709,435280962,375300058,1145292256,1442988338,785060100,996389053,274432711,1497778569,384447270,820600192,429618549,50394465,196410656,352107745,537052737,1411744790,1419002289,1068799550,1279915093,275922991,491039045,1189490244,1474510456,1060694565,1222636756,197559743,1231876814,715546516,675162755,194212713,1400354185,476000006,723277281,1023448064,830226158,402712073,1314806749,918199157,1413223589,768474619,324546475,734358246,176825644,148627880,1451485936,725648956,36883862,29514889,595772419,152902209,1184376877,58142275,358322738,1218920590,1112944012,229411356,227995503,825144274,420732402,8141085,250336052,471950557,1315901950,564717925,806160936,929913677,830509820,1062585711,526874548,1066395933,1315457942,277316384,461733387,62888913,1404293598,1065505712,1103271263,1466288451,1088991550,912775924,1442773059,1242509458,347118123,1467989365,828217648,622540478,403504590,1229944552,994485588,10111317,905750331,200098366,586849283,1359415327,818631029,1424377035,1018190370,462903648,1476861598,961373488,128192597,516289895,1033943755,373856671,966335010,517752288,1352688971,28073156,648317109,1075274548,1124909473,1045229771,672456960,704938601,759783672,237259728,700460304,667994071,160431107,139008884,363259652,1433402418,565821253,80706191,1423545841,66053008,34617306,184813998,1339793569,1068642869,1070525458,1156428378,1074168721,574760583,119156842,1204843600,329177907,1070090473,97199183,867339013,1322412401,1123222978,466574836,770792606,374234294,1210030786,1109544024,459772939,1425785996,833501983,795655537,265457501,634220484,1188335781,418886062,605190933,831018996,1265968917,62520883,671405534,825755183,471362139,1112628047,1339136462,135875634,871551545,1019898214,263592624,1368834365,849631390,429598617,1329894134,492385004,1342981539,696611345,699254285,968063170,995761369,1013776092,836614428,1246859618,1498290125,5273824,210550008,1188839689,1017758829,33942988,1289048808,807544246,1160534932,444976449,1042837677,622394464,353412346,617930104,1140820799,719346123,1212460605,1455657659,391585412,201788283,1032295994,528044886,1016601458,836892871,1115796410,390384643,773534654,710836677,777451037,1057113126,944729599,1248723952,1317162301,604976022,439523173,846017735,478930159,1149813305,906818998,246449115,454172311,486550404,134814996,552447884,1338074685,974337734,336953226,474513866,858262450,673998627,898939280,321314862,640128707,1317034178,716514879,81437046,183728384,1156987258,167141060,1485795113,1140494753,803404186,902214877,1345634789,1410818172,1230187544,992759763,530471624,1069526607,1325935056,1465126652,1111793446,470120178,497573003,32725390,1205089777,424154958,625266321,71650027,1168603097,1089820598,826995018,699478514,97156427,128998064,868710589,896974779,1484061867,505711538,1486012034,1409795890,198900243,982681761,507543359,986470250,405597478,1466303312,975979843,327953478,140814662,463261825,770329870,839743796,916959573,1145969275,468824246,1030504806,1026808031,1143500455,1057287405,284499765,5201096,827769051,1300855707,633057648,1229948335,27475380,1022750859,286505843,217561680,856804407,788214485,1341248296,998560692,410696360,654087940,473119852,362107957,1049888245,1260731760,1431879317,183801611,1260489896,1096911263,82764701,1059929532,65311166,84609271,1235481564,45177786,216610720,1108703938,614768281,519221373,1016867014,1210110941,1375607462,724419762,974209648,1405630695,432715055,1116681063,1202101085,831076915,679355094,395501664,1334859034,334971503,108956081,1068761058,49919987,1273764061,997453952,534709228,947366578,1214931526,1301433931,188414408,1142281257,923116437,862029529,1142946569,818923567,1400854096,1410106971,464575057,676175757,929489515,1320698130,852046,1096271637,1694055,1306379721,1311485285,231124885,1247822426,891916126,1125158999,319532523,288554955,316557075,627190676,511216408,949730280,458761827,799111664,775961379,112822356,238037043,320683938,251154758,1080749605,526510228,1330457590,103327004,1369296137,1289226680,1289338474,814733446,682560122,1249870057,269023285,1083269567,977776474,760492949,19168360,1057963310,1332197646,361232931,123723111,1145061582,73601563,1041208801,353671751,988712751,753926046,268743744,148246629,1106050807,838041663,1134031614,899250870,1111632439,765124402,173196549,73412539,1083802635,1096200923,13102123,1227329802,766318082,1302976756,479427874,1092709659,764186318,118649908,226206888,1011920181,1452511405,482770898,1165942395,19302846,606253659,1252267195,142610705,1306973901,7591839,828264287,380852406,48114615,466387452,1357961191,591495171,878375956,431316376,12443995,594120466,761964294,348261002,1148438089,968868136,496439473,397213227,12442532,1264961471,1273729578,1421875512,953864042,54091737,986827728,275222699,325182755,1082906705,639787556,389876977,298033561,370088117,770015038,1278457965,1160198593,965181260,381878305,1352874345,1247408383,1322597925,562355347,666154852,896872173,359788525,566143956,357965280,1095094877,1231832686,724155184,54024613,1498542142,242128311,666064784,836139667,153312192,1085565128,473743930,229325580,841487261,952065447,603724363,285462516,967421465,318153970,728016641,1364485193,532455418,1134218731,807221069,1104814198,627620160,743390784,643832616,870331844,1218319279,837501410,1312590238,144225291,1490780358,1161010771,134914887,1327185344,23377995,952310849,480270841,333144283,190545538,930169672,957503125,1241064534,1108541008,1120209425,1348954156,635607042,838913450,313287996,799015086,319940184,389906517,1393406694,507579517,1313893467,37711446,292636206,457585561,695539150,407605478,609594680,299133852,164950894,287940842,1043737161,218574745,295645985,695483394,570048618,127673556,1065184038,257932884,1340709706,83588935,1373913670,736141336,94409246,1125128720,1275952865,783195941,262276321,998309642,131541443,474934229,512440125,996368666,1435104728,990001747,464707734,244689935,239096464,1143769630,1192215503,1198064939,656039208,1010382640,161834227,261949379,1477623647,1323227106,149244862,515474840,395343259,1365101517,312116844,1140712990,1235891548,1007232280,545506377,984917637,885902976,14082304,1131768490,467996824,935951205,967786239,1072755976,355279163,728282065,456119746,1071280830,1255835762,1118591545,623307649,941702399,869306866,216029042,611085639,1348828769,981490966,1161292589,1471143118,116751976,881512871,659510066,938973537,450738390,1081168833,1371718353,610330473,518270399,724588710,575123023,405449025,581229295,207450877,338207580,277889233,994115135,1358870833,1047694257,207859225,808613924,1247572954,873313290,324236088,944027962,692462024,1241748715,227010101,353401603,216902395,586026846,340942953,218662874,1244039504,390170550,168263125,940626360,1439775932,1187502579,753030719,657513484,481910258,653408807,1281920904,1015095572,386755939,1258301919,618501538,1493738063,352397170,1365653854,225643763,89817465,330309895,681400269,338256794,365657944,1250964029,315219629,1299455369,721527128,1284806448,1210502540,1073344559,389617056,920499933,901166829,1086118217,989028191,147959529,195680723,484653983,1020861,568202747,95029504,388936088,394162849,1380212825,998166017,217800998,1299724802,258415078,957147360,1470349216,50477753,298968500,1135300496,1368992392,1198368178,1149232756,403970010,1062789846,1003060692,1298909971,1048923906,674884376,569053200,905932297,630699639,160034272,688804633,881152413,1176996970,1016938288,98881975,545288581,1111337774,550677954,980598795,1041985069,950843754,643870434,523693959,574057080,585399701,162965332,1013511618,240974227,55628485,64994422,1380198304,975453442,907778696,578548102,1187317705,85453048,977119809,4633449,857509530,1464111334,29157425,44770119,1379353542,1292261902,218734812,1187046669,2749787,628171952,1029050437,1358982903,1113699222,1436084859,546231461,10861312,1108052599,1202594241,1071756586,280819338,1287103051,29789625,810764507,741777449,240104398,1453604703,76845597,595244307,529872651,253702533,2292729,10910611,521597893,1491438681,149310382,578677688,157184932,1341986976,1494105454,928694519,770072116,896919892,792482289,180390461,101709066,961617345,68642125,1148988089,1143014783,526151445,354335260,1100684687,734466634,401862682,1058210958,1093992972,1330683768,291310113,625405667,1133013042,1354961721,1253272917,731293590,385098870,755608707,335455303,1041914092,288971153,125610489,444131513,880097186,263854683,324957386,1225288887,160414742,330145795,471230517,920727915,3979925,616218995,716742224,1337233499,1158026690,662722624,732765285,366122285,803228455,1434561256,680364242,895456504,1184140466,1192005991,73584428,149362826,195245015,1479062723,821890765,1376982269,1210479600,12766050,330261151,646511552,117061415,392950049,560896740,1354479573,310984044,782686293,131941265,1232518041,562862993,524464261,717424737,781791257,64488984,407598230,1417402471,630693239,1498597560,1285696103,1167411429,1124782699,741707955,694360300,931302889,978862787,1006096202,921508454,1126727258,669431189,1018843738,1407034557,1053497064,1242094074,739378898,331236264,335697735,408732078,725779017,412623385,1280370046,124443504,1154568092,653489842,904174361,555623215,20297114,550083137,248857111,549008216,1192095185,329176028,994075073,1256332144,824694972,927467273,566950019,1307217108,823970209,1226408111,306811870,189283008,1399903474,301591704,412184607,1262045855,293630812,797678700,956735740,359122561,1220108006,1001474539,141652829,1063951567,1312573124,868426797,391610962,507519777,674213965,264495245,736852612,817598674,951959555,1114002026,742868524,93690017,303034326,1153689915,645937525,641636417,1319240786,613359470,1323681413,975701742,616863548,395621709,811804048,1081111893,58663838,1050657945,644246596,1311917979,1165106314,1309191424,1097657736,1200927676,294733404,825189882,1472879996,427842226,885399400,379852631,1124115251,815430864,479719008,800328385,690325262,177329296,248538227,642122176,684658247,777701937,294660830,495788414,989876376,374405777,741078683,979045590,467887443,1425023618,1400837720,965052416,1067336221,1382700129,1226607326,699411134,376455506,751285837,372849113,896382146,1279038062,1027167937,666378368,78151859,81743605,978629931,1126332856,1404654989,312245177,1273530539,294633043,1358014839,967267631,1297747415,496908775,671771509,299978007,730284792,1349571555,988722335,960663691,208935408,1168418017,1414639777,710686587,1131845255,650914233,972331321,710454059,272214780,1466341420,1237548782,1010525763,23262300,778348662,522089146,874120692,853940162,640323030,594366352,937573437,828031176,15355419,1107939143,686670703,69261743,503911525,819751829,489442896,1205326089,879617849,79149566,589856512,671881108,865751071,1238430218,1182257417,644880083,950183789,1484879499,1368169133,1232559929,486532821,171505549,295602020,151733630,1213206151,515600985,765402679,1066353341,1209038749,698785895,1004062954,702203952,1275021295,327240352,816883337,1312966367,838696725,82951741,1140618817,184191826,744250638,798337767,1300981980,226971481,250002040,1199689618,63170538,294702420,1426697261,1414030987,666545905,1415638554,75622732,655936722,1023198842,1006644396,1483395166,793653763,1340477053,944106447,1176942495,28995485,1424998350,84962516,739327274,461302951,381401275,988706976,1205847723,308232103,695438614,1117656142,1394035276,354219194,333162232,69108458,193525936,943424788,87895626,344534898,515168309,1238934798,720228462,207911484,491053821,1022694844,910882613,1378145899,1236084556,1489007637,724837231,609994042,1046507226,1188948526,55782397,190634669,674420665,1307717739,1053063462,469669171,85244137,144365149,781819676,680644166,9171259,768389757,783205198,600814355,854542786,139599878,1319940192,3558597,762046969,404781022,1002990360,1043527089,1384421093,292081251,1069412617,558000833,1154082509,1283824683,808439096,454425996,433025434,824702413,1090974854,595066231,409510652,579961224,1387910500,484094483,122868390,1465784615,931612171,498791521,1422780598,1335159957,1073602979,1316865089,72709578,1452534175,1401803683,816695334,640523109,1430028245,451512672,447731841,1102781703,1002807265,1052704619,995700702,784098358,1449702476,1380390456,1118343083,440072917,229832203,648986608,1016848708,207251252,783399100,714372220,1449855796,25097329,720605080,384826833,994360753,1082071662,669932418,841437343,994788808,3632558,239085811,1468049290,1383366846,345357942,140732413,87689696,722786967,44471700,319083485,747267189,710590702,148651722,1411589000,1302173963,334386738,675723508,17239786,1352679796,314441636,1058819156,7394267,911456233,1082996804,307345195,404304333,901741786,279130728,651511032,1222365469,129311365,162194713,708622026,871652654,839155902,472573594,772626722,1341742727,823328930,1394615254,70972837,648133098,737887343,1244546798,887254012,483623274,1201060245,1313683027,865369613,1340174644,634218947,426518709,1066073976,103069408,66174940,1222751854,676602759,1146868565,1135771374,1105447775,211010025,1012906454,1166842777,1243251189,820806420,22452253,564835251,1333028939,813347306,743315831,339293365,261209358,65967398,438371695,283060792,83939288,1416686042,113037715,408523964,995928899,575436019,1367571673,305614454,626173416,724318753,547405633,973228635,172349716,888306232,305815564,1104828615,1327759511,178323908,277747134,482882579,114716941,71992008,642651998,150053662,1392288165,337656300,565774519,8203897,318283338,505887198,646779479,1059517935,647612899,1343778651,1134330364,1147755165,349721727,1095731872,728782557,522361804,593826554,43657707,177274878,871669618,614565522,1206654475,1363781397,177191947,748220069,172625485,976886970,39946799,921069638,99940147,237106308,737205747,1287485861,906146654,1396820159,3720914,1237126392,1400866641,1086015875,318744348,1294945024,292643319,218425673,196443163,674249018,1354881131,1109878710,590969001,1237734968,848765361,124298483,555504077,111041835,236272034,98429097,1175474292,318059485,1026631921,1237139471,860852986,211828027,469241610,1422084557,1368457192,15963760,625531282,429703512,1204310089,1482836552,454851855,1496066898,410406600,532174310,872498773,355171155,739341345,988279833,741045076,750176874,764690233,1189662766,128691301,1444335324,127918852,940857191,1296010583,1282372386,585819526,466841099,1240794439,1264510179,1043943069,949733650,1481683916,1443718133,879954805,977461630,449059896,574883443,1371576014,955992472,535134037,1408651433,390154589,1088527228,235171285,470740819,990662894,1123609211,1264061966,594134219,1062683592,1246942601,769845758,1288543648,267303654,1486379334,824743393,471806134,603007769,139080792,260727817,253588307,1430328940,1048231706,619835265,1295578003,157896723,460225073,264838197,894454627,288004601,296310158,1032041377,735544796,1072953235,477732302,33088896,206713429,416627610,1413059868,964822827,983422872,322305677,1161451354,931114537,1364016706,1496646456,967281795,1285121284,277714123,1072101409,820281809,104319311,745865787,671589635,924384128,929206692,933352584,704435859,1442432236,255580190,943965990,1112955105,1215805996,1050010127,56886363,633478258,226876755,1073779679,212579879,1007100037,267113299,824612218,457987740,462956215,24208183,667567820,1066038566,302753372,488106885,441682920,251542086,492925313,458401729,290496904,1156287744,639967976,813325877,694962165,825481728,71616775,886333455,543272442,86316541,1482339754,574472198,389941674,414213435,237567063,1098149415,930376742,118157485,178803776,1158561319,153863052,842522780,561029440,903204193,541748621,1151735128,1254846376,1043770878,582278843,619614824,961213218,1403623117,527897393,808280564,998912808,1380100649,1323335552,106596706,357970650,11465351,711945361,836621209,864455383,528552711,956450244,1263334692,998043208,592127356,779085940,837615157,1273081967,812301942,1429193198,663395891,625370282,36560340,988045793,1215220211,1125891507,1056046860,1311198013,426276113,347353833,520618007,689721428,187701477,1360114893,1239960422,130559198,1328043448,1048016760,277763517,470531713,625249515,1378276527,1146443402,189938489,983996409,847551761,307822065,291391555,1426550522,313831419,1356491541,1122775498,123032355,499110212,336531809,59811010,919846777,1046143251,1261230414,585737563,15991251,1005926434,195703345,1446689561,1415739514,1289611961,23758546,175257146,49113580,494381903,1387875773,475715725,210093756,755637509,407701024,327415368,452636851,231338188,345969955,424106242,48714869,1358038595,763798306,439335890,1255407149,759526472,884436666,1496811791,665560395,221496240,798709889,421992693,925513928,1194570238,471419044,196005447,1018121457,1084541646,523036946,1020322557,738963121,1225004700,110253581,343555506,765684972,640564234,1479206580,886019608,1457632113,412793856,1031719870,45347657,926984798,1256086639,592956216,1006892210,30045744,730242699,1370454070,10545294,36118961,316745366,824926422,37607545,513592579,1299595831,1147611416,883870016,501511681,556195282,832617512,1475087925,1218694057,34344842,1136897588,208084360,900142480,400648839,1020337646,713210034,1040794711,896541943,1077039231,1409205998,421111743,105712510,1176412346,604731408,1386140823,489187424,1071833974,843598112,744158023,189636384,762911977,620120698,365031183,1370229590,1461721035,571677484,1366895717,94437606,18422383,365259266,1461061089,845902219,19851010,143658579,948876962,257674244,841526081,1318555838,337607167,1190355045,635154284,1292497307,1204272736,765550753,20040758,18115642,176619746,1376548825,1468047390,462466266,1347699779,864774352,626319004,1421788808,1028474142,955244459,1126669052,1170934085,190585326,34730847,484561035,1163126314,888948226,1440864624,657154335,755690577,724907760,748104625,1463972952,382301205,1192592473,1190345376,1486911602,115008991,25875203,1183082519,417683885,1121202736,713600419,587962768,420601950,1104651381,692238140,532322391,913453926,1122334842,1160904141,111759540,469288017,397230777,176453413,528318782,851234297,655574019,1238935158,452823501,237202676,1298231101,181355682,139927229,508154094,991072410,1286960002,1056149750,782680451,1127686807,725710408,700624403,188739687,851085295,1177961773,631764756,590021735,1007030401,249487407,489592930,1367310683,95911582,180485005,110583967,853195982,946943414,1456504100,1019293902,409522296,1093827996,457840979,1233924317,1462906517,751990845,534208135,1259574421,879267644,525600695,1196686724,1322522593,1056498391,493634948,911753428,220006344,1073562530,893675121,781777152,244643883,649219737,1237397017,1323273237,1016478342,776763122,129831436,923439351,541819846,1049890616,1285459299,1225157389,662940023,522289174,774538633,721151432,1061420108,1097559292,755160603,695384430,959034804,774193599,102247232,1124297991,461957133,359437348,990631421,449129863,928278039,1284905775,941956256,291541258,1008089981,269282736,1420193839,637721542,694985554,120580148,173478596,1068789440,1253368235,277595897,252599085,128369857,201785198,1418590159,966487044,359448491,279013246,32429320,1312483334,1369310728,212200147,201886601,127693815,960020249,330161144,1181187416,318428860,1199717889,869467306,939024458,965934639,1416543668,473067931,169019495,1448171627,488400842,321962830,211160705,947436668,34863191,198371915,197912596,250915601,507282624,1405920396,971758897,120801249,184083856,517991902,889893846,779737958,1175805496,1186022462,400698132,1050203909,1102616753,637719614,474494412,564173756,1070368706,545307702,691946140,8603596,1425431121,93795835,747508282,253939217,211129438,1163219663,964914165,403367049,852119223,434356038,367437069,1076239611,527033260,1125888013,993760907,451859235,365378583,442065859,137625012,338941503,144517133,1066221318,274128513,376268860,838849566,341202474,620865869,778782837,1406324527,453633398,977109590,197702126,1488697365,1115081347,738902570,70708395,389560088,808500045,864146912,778369642,689703388,230753884,211521934,1350121457,1006807805,726847762,559092367,845462731,1179848683,230662191,280441752,44753853,117048681,47097653,126663239,609433888,85667983,1246391627,1247395845,1304912302,213542700,191157686,1051713599,1217107654,1209757123,858102117,543854730,85421950,1367760224,126916701,990205634,632882486,48282117,327339166,680838750,811063476,276896719,1063552022,823861541,310592863,102706795,973066396,297390220,202319788,142358065,433872418,1215640912,692993570,1056469629,1110475214,706072499,953661108,1375709714,176382182,510871927,391503501,838407268,701083518,1060083094,1270432435,437102854,1412795694,258673446,1010417273,41930483,730855041,663921875,608991035,1248133099,1417559333,620476015,136422444,1010991880,1410167712,5412289,740703421,1243510171,335268814,1381066058,1094953623,731929755,1390601883,161438732,638454960,530693711,226058822,162626282,914988453,1480848229,349907737,669406130,1087239517,165849737,507256161,618116748,1288627787,155573004,1335400819,790455032,480971558,350671792,1261412559,761304022,816262443,190016505,775101337,89984220,346356251,1077101306,773790320,1110781587,39735446,309563357,544390117,377305945,666665566,959863283,59104432,1095577518,1177732422,1060990760,1238293195,373722569,853774994,1285868293,154639127,1493066962,754343928,810081773,296608709,1475927869,1377677933,1322283124,111731513,759311188,688193330,1437479787,1038460157,735656346,162100706,1175988100,204705438,317989679,1076140323,627792116,318974260,265247383,1414061889,1220784885,670163566,1055468392,180311561,1280517632,926020028,938710720,1116048640,1108695322,573805631,1445017322,969236082,399603649,385430607,344752030,1294940209,185811091,764949313,494127150,478485495,711764833,933015262,1792377,748352028,75779309,599006722,546274498,1019086327,689430864,365928914,661318342,25127562,1184486358,242956669,397043338,499013152,1432208491,543413893,606033525,403296432,689652022,229394294,1345139670,869944826,716568667,903903649,1050597139,88814478,1406591900,1017236459,1333159046,713861982,1255801819,275369188,934017543,357704424,1237675794,418487293,1193150467,363091318,1329275847,1054942426,1262837888,1333672354,209078715,66727711,151657591,366669327,621656779,825047001,1402225800,56661187,1230148154,1386806857,348032992,293856152,548613458,1327885870,1494501480,524170490,27009011,659432850,649199206,720329738,1316962521,577828571,235522228,631866415,1254014066,358102050,1427938224,1037517796,906901825,165138153,2025315,825055756,150869395,114979245,653436980,790061194,1379575398,254060137,1282060454,1323971114,214655861,351391466,1349699445,436797016,189476606,631109141,837505054,299862256,1458119419,333436243,459196877,466416312,828186965,685972172,231512519,909281308,515849285,1259361738,1149335079,342965018,245617464,1198424766,491403221,579056451,169887514,563635289,105260072,266904639,266571315,1298884160,1115491353,1222661403,1419487431,12589889,1224702077,1181907217,394459470,1077652732,1425477459,303116097,763512464,809595177,1406794820,315838666,943023212,1321248462,772200677,1316546471,718221303,75891186,997398171,1282605823,673910863,503329419,221793027,1368842468,259444340,838773874,1176347010,1044069782,520877767,80341698,1152828165,388088562,773797253,972753119,919405908,914811041,481799874,297785595,870996256,8535301,184413287,371304116,1373582786,835054050,517814198,273612152,183676469,1284601289,952429014,4371580,182163278,1253312702,1213946418,1351650598,909831020,656084915,1060566438,873289744,555803770,257690554,1062385403,743912112,554566961,1405242619,263374343,175185819,47836319,1447775220,1082397668,1200808234,585171607,77182000,293416491,1304337641,198968736,446820878,1404606940,1365247649,693135314,1299041730,230455101,617416143,1379544619,433489581,994463198,1206165859,1249540932,1178586518,266389159,853680043,278586524,942278873,142222161,990428064,1424524315,739874346,932308079,972626410,398055993,93469016,906669336,1186810284,50593015,1330536045,57221364,1384813050,1210099353,123258160,237417806,25203165,385379807,620079134,486800677,1459313798,497922690,1492325823,88535526,432361914,126870549,970302644,1015085762,128016542,1078054952,979281794,446812587,1119499472,317548557,1197960202,1181574293,58953042,225556533,1031895922,725727654,766137287,690994005,1406550417,825414074,1352425220,667133355,549813963,549926619,1248594260,1079575376,798021332,286294071,1348138165,276143734,481088277,1111463444,1028926149,1358995284,1061031098,554124225,137643015,552935139,6755047,1377659194,779520515,553780039,692662850,546548711,465097546,1375505580,895165656,417040534,1174603666,536617198,1134497015,933329379,44290607,1009744256,1090126494,1233612267,1220223432,475928155,609365188,1413982778,1338472996,945516906,1425434889,303474111,280827117,1399231432,43516148,73334124,542388272,1456242070,1264433124,172116037,750624368,137816725,865124121,792637801,1205453073,97122429,606541833,76982000,1302835184,875999933,1371327463,646077672,129118414,1307856247,953653488,659405859,327792550,524196308,108518508,177244655,512915562,1200463672,97449467,1339575151,468864480,706599201,803157671,538127445,660030460,1448218346,1345417025,409728586,767079854,1226581018,597868795,1462045931,809559762,64107476,1107032031,127795624,1460833283,344888062,167271065,1021331920,819830392,1288289981,141456547,995153606,1086160534,513438942,1478330313,757852168,1023092399,914727506,385793231,832503424,873328215,1015557947,1448919582,1174459918,1417552979,700225898,1386151155,1286890526,1231436372,1075231740,120220745,159468518,1420612558,242756053,1467722094,224678064,570812014,1127108171,412258927,1128874274,338563749,637116809,1289589077,1249416916,617179408,944318044,952959044,1200122093,25146151,243100941,1007833925,994353379,132305510,392880465,1226695558,817471754,255843135,63333058,1434000334,522840063,402533469,301930400,1428897298,251342022,1042271902,938612752,1125463887,1210558440,657969708,1342828759,79224831,478279155,1372688593,549982261,660368499,24077047,1159188615,1413997195,1287026103,1024839041,293785396,1289928246,367325558,456134907,756338040,1057347044,117093079,1162635159,63672840,348494393,782939720,116542638,856672778,791395959,1309632518,155243504,563023910,1091813880,192834792,1027990288,399170518,242619941,960750437,68790158,376089655,1346028796,1329858982,774051064,1076901193,61884494,1103043607,602458776,657704472,1338967508,1106919680,487763640,562896179,448418075,1107395954,845431745,136581184,457776734,339667850,1000618963,1069839086,1131727443,392329767,1264853237,268469687,332972219,815783834,357714551,806256130,1353480318,969086273,664628,821285385,480700429,794676418,1075174510,482753933,70572890,1249802456,274824068,843188596,810000744,451626960,707213351,1209079771,6970118,104281342,1495754110,829528447,1075138444,58140070,616590839,534076753,1415568610,1354106329,504524085,64106627,620534564,556485200,1012392057,753419858,1147835261,1335931803,672089591,900115138,738087867,115949010,259711644,47545443,448508741,1226006483,1150424884,383344672,878524361,271513056,221516235,294306903,396863239,340412785,1063921328,1427322923,1297789573,465837577,477989301,1485613668,106221837,1466114875,132633647,619108671,1403820180,109055921,1078722821,326900574,1352321237,931400230,835446282,651664151,1453525025,1051094325,240164666,52013733,1466762956,1035556037,880447114,579017104,1048895861,988278767,1196565995,1227162612,149115383,1048259725,1488382929,1165360046,939057850,69789878,728076911,403236396,480701686,198992066,431320760,24959265,278638827,1261550204,431024403,652467406,898117791,144622852,280171017,967054099,1338198091,318420921,572414636,543399314,987683026,957888449,736053135,722991228,1085278056,1144068151,1286709068,816774250,535904204,863164561,323756274,671406839,110263534,537597085,1269484439,957161421,356174862,537797471,633801156,806217466,806412408,465538621,1319591856,1361162504,1204892352,1453755486,8441434,392511209,588763501,53144615,833341575,1500000000};
int qpow(int a,int b)
{
int ret=1;
while(b)
{
if(b&1)
ret=ret*a%P;
b>>=1;
a=a*a%P;
}
return ret;
}
int F(int x)
{
if(x<0)
return 1;
x%=P;
int ret=fac[x/E];
for(int i=x/E*E+1;i<=x;i++)
ret=ret*i%P;
return ret;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
if((n^P)<=m)
cout<<0<<"\n";
else
{
int ans=1;
for(int i=30;i>=0;i--)
if(m>>i&1)
{
int k=m>>i<<i;
k^=(1<<i);
int nk=(n^k)>>i<<i;
int L=nk,R=nk+(1<<i)-1;
ans=ans*F(R)%P*qpow(F(L-1),P-2)%P;
}
ans=ans*(n^m)%P;
cout<<ans<<"\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3700kb
input:
3 3 2 7 5 654321 123456
output:
6 5040 1230647278
result:
ok 3 number(s): "6 5040 1230647278"
Test #2:
score: 0
Accepted
time: 126ms
memory: 3760kb
input:
20 667144597 616359815 699804588 611193378 739486857 661506815 661779337 585080180 957263733 829085971 934825680 813222663 806544392 533383430 775224639 569837029 747555415 500162484 889383096 657370546 745364298 641076715 607446703 551802468 590490821 572218629 840118223 535505618 820772696 5402693...
output:
1339997131 115875323 118024830 1479012327 776737197 1111284901 67543231 630719933 1141450631 35331730 1432153008 484035608 911568152 81845018 1443778244 710040764 1434804142 362767626 1283025004 1385992323
result:
ok 20 numbers