-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSlidingWindowMedian.cpp
More file actions
54 lines (42 loc) · 97.3 KB
/
Copy pathSlidingWindowMedian.cpp
File metadata and controls
54 lines (42 loc) · 97.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include"import.h"
using namespace std;
class Solution {
public:
multiset<long>::iterator getIndex(multiset<long>& myValues, int k) {
auto index = myValues.begin();
for (int i = 1; i<k / 2; i++) index++;
return index;
}
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
multiset<int> medianValues(nums.begin(), nums.begin() + k);
auto mid = next(medianValues.begin(), k / 2);
vector<double> medians;
bool oddNum = k % 2 ? true : false;
for (int i = k; ; i++) {
// Push the current median.
if (oddNum)
medians.push_back((double(*mid)));
else {
medians.push_back((double(*mid) + *prev(mid)) / 2);
}
// If all done, return.
if (i == nums.size())
return medians;
// Insert nums[i].
medianValues.insert(nums[i]);
if (nums[i] < *mid)
mid--;
// Erase nums[i-k].
if (nums[i - k] <= *mid)
mid++;
medianValues.erase(medianValues.lower_bound(nums[i - k]));
}
}
};
int main() {
Solution sol;
vector<int> nums = { 670171779,25361138,42884260,141714653,824765604,621543621,923179139,302439598,8531137,648898857,914108711,120073717,237312017,625937240,752289674,141815960,941475197,507103461,318252662,638209204,494253441,450836291,883236221,144198283,971967143,736648250,603912795,954629843,613444564,93797901,208325209,923443053,443074902,434073765,268798074,176615008,546039302,84925083,52223304,543742352,927770657,955649910,577841457,860316065,324709204,631644601,39141886,520660598,539787639,239923745,217071727,897283083,799585325,470872927,484044894,674478622,543511088,188400256,52206914,61254200,293145996,577268554,968953579,627285630,585338865,960695726,631008736,882555644,236137457,5438721,7249251,17550834,564585977,59257924,663000107,543132644,624847958,417574854,996991360,766373626,627596054,714689161,697669834,269165996,65312768,933505315,701282801,69781671,87451813,716785121,417247555,145549430,58374655,495778484,312430228,417325081,301045265,196296523,620780269,978423957,89160220,365210512,584812058,51090134,264380494,92275593,185676995,172494452,804309892,774280626,376558940,191796871,157056750,395395087,90823391,400838098,229712447,748983070,402297354,133107922,259863458,690884255,40573034,951644917,630895741,337953748,687374899,395390280,803010720,59428223,230248106,14385648,261417472,684888720,412369120,758070971,25815593,676932013,620959263,839292468,108894758,124087618,919931645,201877693,81707638,456694942,565335816,131405184,706716950,852705671,265836066,933754080,587308862,65202022,426702362,931679379,77547507,965860067,174236974,26106088,678357028,155887673,74070771,514416584,823343044,689402887,913024822,83020470,608152387,135470814,111262234,112067457,967569958,202109022,320181778,848607111,893793428,131012209,544437066,718926973,262637189,857319516,146812620,20993937,657781051,80309401,140372291,93029009,756416403,780273559,522557531,209285865,36802916,657276032,975368234,271231287,269436606,525509166,425291429,47469987,904617050,507517168,35996692,553497637,528604833,121580592,148061447,328171434,839285742,202872298,263659628,68604035,622276384,353824998,354522843,345785523,319514857,22579030,528635338,427256705,511103945,189415615,937476451,79193918,719802333,735405758,989164799,14843944,960020912,819806651,28282783,547826472,850098793,194689038,166562216,239972271,32648209,903097256,734143174,450773403,619256183,132914319,300945131,453806610,58758704,862544155,57974413,4340709,732830743,867582056,37652062,458013816,49793242,942353120,436991215,117277765,844892056,731889806,878618004,835236456,865999200,144857259,955453471,571258478,534832587,712227014,118554498,473602048,255224954,833937397,153045988,705994857,601390502,157619263,259616490,480555304,6997961,650613589,668838377,237193841,580215433,750519982,817878643,836507032,745733562,622391220,929368581,249176236,104865380,181346051,603784064,938531573,632760196,461594228,303257032,655221071,797377059,218273333,410817233,238288504,650863651,931168186,75861344,543805937,848960105,591134067,930913047,437212534,334997482,748041187,751938949,689631826,672856723,54058359,173257032,90595139,652552606,45642391,252982136,646117270,615637658,238885338,91918101,265254823,109242636,528422223,140400194,207489661,558268277,458877796,745340995,673990014,921411020,443413201,470392695,795698836,722645361,126053473,161844769,56230412,171729804,44794260,237851370,893887101,557890673,554938309,326680442,549986962,654232224,357694706,761174367,290479568,652748323,40090716,642282301,231318016,816493842,391498164,19747940,191145942,747289860,216309364,614644955,941416615,877020856,554752362,496436507,427383132,488478887,34671328,752941359,711772589,70968111,346091001,365737731,648825781,685920379,571592757,65113868,92581731,681465998,868738935,153964592,112586756,898472241,310927361,928443176,728279930,691479257,303353413,334634313,86710745,792052058,915294700,725638017,31498984,915425504,776577198,320338898,194355657,212900112,504426482,777928265,552885497,977786088,105914172,628524019,131127740,545704358,897972216,496941774,536492435,692004939,548556199,436740022,190444308,46850526,83270611,517304880,122293682,834020351,547253866,816244339,493068537,10991233,632016545,640932331,164692343,670766396,429154469,194568788,647509182,32677456,601673007,610713504,437512715,85172255,58959461,380173269,808282258,965842931,886232222,105863209,564967456,382829605,149143401,332703136,487168542,634023030,4187374,303213045,122952984,591533674,204656955,193618769,712925378,325561433,715650453,28740371,441551978,253588792,459271496,712784532,898824936,943704932,327553960,198818459,850264259,35213875,74572778,800187154,202899764,725280690,675376458,601055211,964834367,322187672,201929217,593166437,522195863,573182730,17986315,86759134,812347403,569258242,276604487,382495832,188892953,536009383,808779494,732953795,581211951,319128832,331612865,490336668,986604115,927100896,436395018,834413021,911429037,386970808,237886940,344228444,126513290,300054500,724378344,542032765,319050781,19809708,81797071,373838217,709245644,402792789,869949379,170544077,236611972,745182807,955786523,726412501,370371112,419670378,856724876,890116375,814829623,338256842,693529885,763024926,180569976,445193421,532800599,920343050,673910587,586481431,43471087,474119229,357551433,500668703,690940953,993496320,800273393,297813568,361234797,336963110,424612631,376330236,642936037,835745802,482137765,833616224,404563740,569551778,122118167,238644815,551436756,251116218,704909571,895362945,740080664,103415002,574646769,647264602,216988690,501680224,718726646,43224947,632211543,977801492,10304131,382837957,289515465,481454731,91282021,873602989,299741584,907650073,91410848,329788240,95656773,385615855,733006917,681054827,193617457,483853172,392669193,373879520,255941518,199348085,368775275,368241683,137579174,39246755,135710234,47248302,326240902,605089123,397821716,865966279,591554012,191972652,963924370,60253622,217827217,355396562,997995227,458497119,582732175,99729836,122108992,84440590,853789110,940821094,458033997,595996731,846306887,888634306,320994635,477909181,630765287,292897017,480624373,960819222,204617292,881507797,11863526,821785958,82240827,828067877,642776179,89474621,147359403,59314739,470406165,229110548,15779743,862630598,363338267,123223626,283719983,68057941,34009114,360528896,357786885,162943173,337237264,530330193,995397279,537436601,173712303,945378826,543403007,873871605,312381980,399399523,821386186,805723764,560402144,963042113,57524330,236751738,592241253,212035326,2353709,697060095,758700858,520403098,861457502,974466618,150156704,183417481,851548300,934233070,47759204,677541297,123777216,559499016,462050277,378137987,961036036,908147965,76568526,337490507,491618000,47114569,19052596,34896147,29485576,288331953,272026439,748654388,527611343,603863338,123406044,763662153,153025930,368880051,774706846,304608961,109276726,101372853,257481809,317215158,380748652,534304682,429662267,139195186,843799519,903994692,784964497,906257558,516752782,433117184,223926736,145302408,201643195,80961977,16293819,119792764,957785887,762963475,502268088,9022306,752515161,991113744,765529276,468991133,861966419,937900049,756154563,29001042,527682181,439932535,159919124,258674671,831272547,462068625,686512823,938864477,578405361,747916005,795488722,338743010,274620873,610655108,456051143,482424258,353736781,812321949,934431442,234313761,419351107,140209542,150685144,681995395,176379726,679600600,374744385,906825691,120924456,650780508,326762363,572328140,332772645,655406305,763121250,799487444,973270607,376152650,953215429,256687161,639446682,172214786,398930724,384732334,123076421,518655686,409991429,598407627,564046666,732476182,143904848,128150970,493212005,920269193,787101057,308199479,178086989,663303852,353207565,507723225,144691622,319076059,444657054,108015018,784725811,189629250,26051180,548496850,586745026,971723536,144334117,314466956,81852803,103504519,724653919,671633074,756004664,302627127,12847393,970748029,721835722,550836329,897157864,49534661,98370969,905951440,459773428,558821068,952680123,849733807,709841699,37776008,39185522,461072272,913655706,96353270,792696208,649600446,27834574,811733819,639665120,548534958,79742535,202990017,449184283,828203754,424472202,163623680,244121600,50944008,955924459,897219206,80509655,797031131,492207309,421234119,575737521,652180643,443532613,536887954,897041831,39830255,998155077,997612422,112639356,196563285,602260487,894555276,50489663,116704054,585444445,587695139,114908620,474356265,839426769,71124371,386395665,954371705,569886492,305205424,396612132,863840814,583107178,107437963,262054170,648453771,83020672,611547401,213412643,321578989,354707202,149339942,695505498,400392843,129224828,214190588,718620144,400729480,551653368,951251877,822028471,863189524,19789314,886518760,272235012,106657152,23865575,322255614,196346764,465180756,97985943,877270399,453854269,66784939,468006039,337877090,753488962,177917975,970169201,937913183,769876279,514626556,57375154,84055775,828654346,555121005,42747045,628520726,75782289,215128552,450595563,925266597,819586430,621995730,724819092,507233460,355662208,167740255,357415852,576463905,330119718,17335156,441674547,166122328,289225596,259098811,369858939,401513355,634317189,653150393,355230265,350525195,729308644,801206279,944443041,995533688,682579017,40875023,584723099,555956221,254858250,320215632,63086220,226156500,113723957,684056625,105228915,203332924,562949869,478478179,603980085,731067804,302637341,977492669,262366911,609724464,640081542,104888571,571117188,662160273,460428135,825063382,331331173,50906518,680335098,982034036,279710788,257510633,801660126,189336404,753660821,711847119,176110174,444207430,934097616,66151120,991301850,632059524,570301806,635915459,597986872,141889744,34079238,184597895,570434997,726972949,992864638,921012254,183803980,904986052,266882841,554053751,285278243,133424928,499837428,959108979,525334249,780428704,628090830,440454805,140755004,82835459,84629666,736622148,165216481,97040596,21208899,768658669,732113178,337863914,532039930,20681049,279996885,563954196,178332892,501228279,358316550,682109662,949381548,452180026,992553896,993338754,506566700,241350192,569046339,217139482,681536299,695782773,972607896,122870755,795468027,345427214,739866435,797835493,126217561,417683069,22782287,88281952,991050834,501179484,685702632,999864800,461134403,810407776,182201958,749606062,490010732,803565057,140740663,487301203,716172810,863554813,71255665,91065207,524577385,944717338,163192426,438486563,627271484,347587043,532890439,75778861,743471312,107977469,153639768,948237082,544492787,862451242,850890691,619216842,264688710,977494611,295006105,420844390,468013159,457542930,932568250,131900522,87423059,440538065,747127246,423718091,167160563,351950643,857471641,556093848,420471592,644848114,405264167,604210132,302500439,31085824,413896325,448980220,546000560,433788289,120275305,123412817,877495964,97441577,756519134,713894898,233393475,131973481,313644972,151669597,47827790,682782552,521225543,444883666,414694186,180749587,109410429,53551880,250799067,817003655,162969245,775429368,356112911,152770988,379037151,833878433,309521687,718578953,501410921,487518419,71954828,104479513,138530323,406865313,597383543,739157476,974284884,36215591,730544414,888934777,76043438,102271079,676085731,429883218,705234996,715308557,370440171,225839922,880943383,56154241,477480963,23639949,618105304,910422367,440715872,233540779,312744515,404579396,625660748,45750855,135474359,584885893,144551332,463210745,347749418,114443417,891118963,485456963,784802188,325813842,17426291,264370354,128874035,322390069,101626880,586451373,331264859,290872189,809078529,109362677,605489085,677532109,116838147,337156780,532140674,211896741,820639261,344078593,548429758,459129782,685502403,136604713,841349904,180999611,223617925,43061803,830712560,994806773,557241916,181676223,503512505,449102355,451239858,223535849,811094118,625628648,860751224,195975576,314569912,19255717,946762078,523904323,369982539,124353486,93407827,680759588,526502878,301244906,49674094,648842822,972328466,721458039,645569089,785272757,437711015,477538130,629940649,111086611,662360412,529197014,484432071,532290098,575782262,611164052,419938363,272802899,913715726,164647185,266300959,157276143,580744522,260005639,933036675,414784909,351025979,349029322,3469828,335340727,74508961,82119904,150220085,455683370,536692966,560340740,724003663,480198717,249269771,529424478,12452225,771610394,595126303,456430442,207830188,986538272,820477595,774441778,144578379,124811096,401545931,388843443,291987258,222690389,486349780,757991978,698180242,464680086,627664910,517446884,213987616,602237034,500380705,145525861,662250472,35940503,609129114,578473749,749829474,949928922,61960256,629432375,365481503,844390501,99210931,783785823,216615041,457191000,105626612,90470393,117473075,832499932,970396919,470202315,743465823,370228915,970227624,565323475,716968575,353075286,431993719,669203304,928070989,915383962,285402226,424228631,157871755,1260818,301688812,67951295,389093439,405724158,745344281,729217816,274660083,269657578,737396854,93776919,648659313,390081419,623813420,416985286,32561641,448148880,813076131,932087856,854874574,4345366,604079520,254788202,142918896,151167726,995795059,987495542,83950378,850225545,384547677,314513516,864386723,813760084,689867692,135067869,988437982,891153929,866109103,844513333,809143286,50249929,589483432,105978013,701499706,213315290,832850765,217374787,341340140,767890421,350565855,412681264,354802816,756324440,382135065,213427856,784285302,228445428,929031207,666877290,489459337,480708949,234804407,75703841,44136663,716015404,365515818,421122706,496197808,917557755,313119178,259089496,213301734,812036495,638794780,953116107,941887376,199166395,255573670,459377690,557124865,568905135,991407501,260252234,782591546,471754325,265315551,982414485,585971259,851923449,3932794,319454279,358949653,585253548,881277976,444229273,508234339,145050032,47905635,429596976,189332996,341877496,416319547,373883081,108769823,378810142,166021817,747420866,270643559,128910345,578147170,703467162,68093577,425921944,700095935,242456210,978021689,563671463,868890302,343484692,304153886,696260720,208507115,478748479,851944891,9803419,557305961,110596891,228592382,896898369,983169490,390438412,181343830,566455717,626228468,204507729,187566103,710477903,993038401,900984770,736812971,17873573,339387987,170309655,591648712,990616974,6250474,410974971,741907423,740982457,227464424,266661086,767479691,244382755,145208799,421335310,128971011,597760632,427419936,107043715,285400397,393488628,54200261,996677455,578518163,141790503,513619398,309939824,510777993,946569870,233926692,356333365,710457719,446784491,149605256,859670602,6809376,421527719,860800358,21770714,266643717,830063977,624469105,492643424,101546561,29508518,673918147,713542351,957608409,282079445,58318117,900049387,255237841,257550628,119351022,182900456,958865135,929036857,116341909,586819302,427101690,53250487,627737857,595983466,830383454,905973172,825023152,655185563,555099172,675799814,919443493,941946686,841484496,650108777,774397681,550923747,218908543,556394890,185117192,353820019,270840790,503309537,978281404,840755596,136904712,2508647,6135767,44620913,471891988,431533945,738737696,361493365,180726770,725925110,561703741,9641353,773924924,840726367,793136556,608078341,890979692,292212913,74811749,521605457,594668745,208704077,848626588,428164789,740886204,964245322,159526592,896818866,439941147,304661008,836547008,270126547,236445671,97645547,244180699,896737254,422793332,11626648,574018215,820575759,69779057,43518315,60858803,90159558,335720171,802351906,871643207,366918793,378603414,986511615,726958465,749432050,505853273,781179416,714910601,124444620,684634740,438694554,828008927,652003529,761744909,142160727,293523225,267883994,993541624,414214074,701441791,239937885,809227776,470273359,937502331,307137656,304875582,147924932,535752545,787070522,942481381,238168773,786028381,607086770,405515071,171681297,377020758,156615987,577425934,112050523,682960220,212324325,564592608,170705141,3152395,442695237,140989982,944164833,821680548,665120026,812872925,457266839,587274107,274053315,454620968,67793150,233139140,4848783,36600942,410182661,517476557,67206796,554179206,246316781,290645429,499911925,856674989,51665566,759774374,590138756,382590246,421203982,862203540,628225402,554722762,791927885,621297667,84397555,923478443,830853210,4206254,413507783,361205767,642034478,715629218,317338657,308912698,73235418,359540595,927281154,318507577,273093246,705631883,150358847,285867588,655633177,488213082,9737634,37614622,267233245,842838,73654962,406839171,158014949,467460151,900555709,968035685,439648123,822257581,418874000,356901712,318226091,984608985,607205691,463758093,164114088,689452846,605202088,148940824,75475144,495393478,77063905,73390772,616070204,66235019,253908696,393447083,562974868,105657794,969051336,122803882,26038585,336812685,43903303,295922600,791990326,877764976,530780389,971906863,78027359,86292974,774552293,2003984,907177892,952420791,786108177,800734495,812125363,777894187,187157973,647993003,721806062,52340709,14979471,504382398,37008477,24193887,752249526,821553593,678870988,997057383,728538540,742970233,276277304,533003514,35768161,653039345,990835245,25258808,470507597,579373103,625865201,334508779,769839385,101570520,993713922,162542913,52518385,853696356,736409685,889318134,283695018,648471186,375714577,32973459,927123065,16010823,658446286,523495811,153593718,174274732,15209863,667570604,50064431,766785840,113225811,108672813,895846719,280935694,162647883,23770597,666422593,82796377,136788630,637475629,256981720,502153923,90251151,727640075,674854507,64054273,670859164,840822598,263007326,635761134,151730244,67121919,482156536,942078999,917785440,992337326,648414058,208542859,286519309,871689789,356843889,700899999,871457976,548708670,644815050,997041166,248957999,731923415,443484467,520676710,17603445,655840476,470298659,569740853,797912976,635495764,134107595,674476971,515762731,973199203,116527847,564395621,154911926,647538696,528719254,44654339,472156279,578505488,283266847,687630708,399804849,836744258,437823650,16089506,419344976,682660756,621683818,924965049,46436488,714468533,137058685,442849211,581347353,801851668,54077729,84765778,315246394,503986809,830795095,234488871,421962652,935289770,982351997,328714021,14105794,852878588,24568438,43350751,599115724,934636132,379571297,428357089,825388657,355777157,952204451,652070513,740061350,133309673,148703799,741268332,737198255,50890820,61993743,399269806,788716214,329834345,870543508,418651945,126812043,819207455,695013846,727132267,375554970,497942257,171741040,233637712,148918868,853944299,401598970,925764847,810761014,676622083,61438116,443759983,63328250,353492485,1406371,600514436,465963530,723671748,196670606,465542309,86661342,316240906,831859395,942309795,856311587,386419093,555147523,695456493,576765808,109236145,419327986,397109826,993154353,347801318,46264492,178236830,34197892,824310604,771314631,273709925,125716179,580890383,564007819,286596075,14412304,709424864,267459682,304580781,281150397,830698979,766550906,666678789,448220324,659330370,349910070,128321004,410511218,390061693,646783607,722840313,462149512,45980632,288326260,969322766,389760598,674225814,235029257,914295566,320083477,989440782,565344353,67865121,881229246,418202741,19491356,173705948,838570341,709524504,1646937,910266395,966778115,778505603,873292097,162525612,116245547,114746815,902383277,826221425,674228473,634224139,89259043,233150095,188969468,29018410,819586157,617407419,918487407,905394813,48983096,211131180,838757416,913231804,621304719,202920519,74109975,818813143,717284425,573620364,576344943,123703962,328319038,172582523,137035542,53884810,196881214,857747318,894429893,297682651,662901494,33227600,903503558,327431369,285915169,100821975,150336342,262131122,941786035,288906786,195826435,309945841,257400643,100541843,530103690,690550074,866443908,29130027,755070851,994922634,357034096,395720332,907743743,725260313,332900219,859080298,30009705,507433468,776734439,22626160,173265601,87130675,968891118,577503603,624454828,252689885,29222007,508000133,356233437,30967823,785158587,20844541,880323282,224051322,91735663,701008073,747395469,843796180,847876119,345429119,978905192,587342277,626807927,146519132,969265571,782989302,714388476,146045755,17195764,246396850,636365112,712853902,917242879,463449187,60276818,253177320,986112533,462038232,968676250,468205843,755520693,112966187,833118117,415792557,106696739,896225706,415140684,95106885,733582827,622955962,38074209,756082435,816745746,330281398,941712338,197764954,323874900,641882802,106872911,355159794,313602745,589444055,237147352,798874810,621170626,96703115,437111604,140655688,206610025,806611554,803608214,511575293,314405441,402475267,621302997,173978865,130519066,491612184,156386479,660547203,473869478,100448601,317490465,712866107,122372314,215126150,410225149,24550951,896930389,166824561,354237392,636156438,353153631,955759556,66156710,292274402,960773725,794454282,487284175,75478145,545831285,529245589,153348449,347005943,710782396,461179889,781912400,149270807,326532131,997786210,886010625,528966077,898041206,656456704,89824420,145506746,133963245,750375237,178128006,205192924,966220233,785095995,968860797,422403625,549766971,458832203,772038022,546840580,667102547,773365020,374859496,339507552,239376385,962031864,465159985,103392815,201749860,726196985,43160994,350332050,778087923,88773856,107020283,39062420,978054114,315659860,803637508,3919551,889857756,763187384,118023004,923695556,391925529,760020554,432718722,323931912,245578417,765863563,999406870,207155834,597110251,440906126,490677532,273054422,846095493,837724064,518532494,279965710,39995971,842881664,509991236,608446853,642109935,836351370,277005975,687853707,852781748,396978558,934416724,986948335,476976917,142073415,412027597,106039782,946672711,814891732,382122805,7374036,528855173,827056256,820331208,254577694,692856812,981083828,489434108,849663724,324935296,136605551,269477014,57162775,809569216,120909567,46036016,633207992,545250659,508082642,742962200,141266673,299543176,513469042,77873826,446326068,241845905,665065211,891597220,81071421,501214058,473809272,236050006,683133411,768640393,70443377,678347742,147301518,233925191,331106058,769387429,95480616,365407381,391600625,741809967,103039465,912468773,681944584,322399249,462936562,241544453,893528741,184406516,501411791,502140509,12285700,913286944,193537630,496705852,659297253,586291229,141713367,10173224,123146233,130459479,844638544,973102338,843022861,381100499,359851339,500483199,720658872,305892624,61480650,365650343,534600734,755935868,500877824,117691728,212433609,253845149,118391232,231579102,702577528,916821,376625018,302369817,776184095,155907718,410967086,816405650,56738867,920376979,451176712,162241027,628192746,798851948,29907570,938334170,609975269,560393883,824199486,844216630,117423259,788220998,951178690,384953140,332174147,540890076,234208159,791981940,736821474,367804916,32265724,562617733,545740790,362801193,893576918,994117355,707611825,67505689,696749407,38956358,904480218,355265391,940887877,580455878,496711803,966337132,956838910,26990212,91400723,159617365,481978452,303526280,92526335,104930495,275733856,782186144,455118921,639933211,759373101,288394386,173854223,390166041,46055374,397031407,675166220,215068792,446209243,425851777,875304235,768274273,359515478,505139735,673648132,263346118,887387337,45044544,149407264,472481283,391375353,103147110,574174641,509165316,612111295,307865935,807642500,596343391,437191988,344185929,204942263,48328100,87515290,429137991,65106689,617419209,323663359,233996862,742701977,417171075,653128648,344267119,569502593,88444450,220166004,8684025,716498757,253800170,509912826,290609983,904171003,807761249,799179256,88522185,733679571,894427301,254118907,778979713,44702857,287598305,472001316,121525994,230432861,972079286,828457073,387037341,208623424,640575264,605918215,92964009,18466472,566823245,360820623,965875280,429921865,207291478,729395312,110351708,48263926,570469363,157078664,763703685,58075676,120310794,74381509,880496365,985573656,995067081,637271178,908719635,740186559,90213689,683973397,853899566,4276508,446783114,480967086,278345672,729304716,380683314,790673985,228858259,277547236,401914168,135351761,464843532,872713116,376031602,66245340,427373743,685183033,856898995,669050761,304743013,860299974,54267767,545293641,82997469,221574580,60300740,655234374,227982002,582681366,600288042,162948288,630226491,827287233,407394353,692002813,512824517,189781808,442609839,853189443,806657482,428036463,86099838,261956344,151775836,478881594,941725049,411398731,274107155,566531270,896047739,364511540,722091536,555334933,343267647,951245865,366479718,441520830,84589425,853270239,17112207,989537998,844748596,468241233,143299001,535615029,977827826,452899669,202691915,526929841,680256037,7760878,26531235,26846647,240030259,214273947,765129788,404268680,52929299,110455591,439720438,890172139,752055171,495491333,928734312,119413966,679273773,531235359,383158134,228279363,285460399,47437173,353112152,51600581,253528635,241191375,47292667,278904879,744983599,902664961,58495697,175626309,901822963,791937193,132242292,536584155,879037910,95640588,113594560,863786315,667142485,651624408,832309203,705276841,625618894,489794324,461363095,359066926,408777212,518415331,665312238,102917784,453333362,49319225,565483989,119760079,615470514,931684846,169431376,69820510,947240308,971581345,49497274,262986238,488356540,125868946,207983127,616521820,66610543,477394692,366661830,288498,553818592,834949646,340550824,386758291,606575946,617052113,596331828,242852647,405508829,66772003,250590687,255223220,804794059,114719385,234345845,958586895,547624471,957056702,392453062,829311675,865431273,189642758,253080136,145719623,978346181,929462635,475436745,671701306,109801310,180637906,586892931,310079224,351685077,896092595,325427754,970896216,64930984,959312568,652087278,21830705,481933876,701821095,172449272,399474701,730397763,571655067,757852969,509339626,601277240,756013545,451890094,414634066,963291325,158084542,489626055,135254728,626988479,93110724,543843252,476113310,305311026,816959877,427192399,784818072,592776230,613459177,339398592,555569312,194529628,989347062,137675960,518445410,170849991,83141276,136550113,485214195,792546284,277311425,733605985,12172468,364701789,417617763,718162923,99129299,204775377,36453676,644093137,955772679,286714971,658192307,549838052,506006923,423112741,937482770,185397351,121990107,26802620,293047048,61733165,107681232,262730381,483135235,418225338,399279135,945508717,578997397,960846822,22995561,525294423,111073122,435650789,4036678,710927598,108611325,655396481,598009282,311513192,830065136,850969840,9011860,138475730,282299340,813631157,670475250,623809519,144399757,63173367,690836129,231719352,119297053,68822051,346009071,781718799,42902447,654404984,113788379,619313532,96778962,357367064,903967636,330234305,150220287,104573315,922081959,189488161,802252004,547095362,299751258,70240991,10287043,888618519,55662526,364688037,186487899,916456098,917901380,438952190,863129885,371941710,46907200,828769107,336425485,771662422,676582321,393158182,2383055,397299739,683033428,88226112,52547954,350662539,683144183,949685397,56981453,495531165,243685667,166669018,680488416,263882368,517227921,35865191,490843977,923011890,431947880,253292300,564076324,83454541,313649096,575486734,732170828,513808886,554202415,843411866,831161662,745908077,615002600,302883767,824207157,973143127,174058515,321712969,459025415,78889881,697798346,281583533,313459721,540144756,799538223,33734682,836096144,282389887,980949517,586574200,602639670,825033016,820969811,457181502,153015148,187666977,258383574,440793984,753390585,464957961,648437672,959928426,265394449,160969524,732878295,312283451,97927689,898195421,307885984,144606043,28233453,718737162,219967359,172046226,860910098,364182178,481471696,376412776,30185817,112842783,906550736,794723065,709752762,335990427,256598626,298922584,820597533,435734675,266425033,95104214,481669908,205773144,980559538,474648088,656150058,378476039,993203637,383138928,259989190,302073263,293989733,873054431,463040444,987489227,770792751,885385931,560130832,343563554,836608942,104029863,964175939,786385089,159827185,506434476,166545071,744794834,877575253,489589575,522135368,703926912,205177239,348097369,727026355,97480702,414093009,459680914,358443339,458547316,278909507,822766395,380576310,932719982,387092952,143277501,528769598,536280878,76828665,414679386,724984565,786349455,560926547,39265099,651039264,587728583,677001928,796020668,689224844,275161190,101828339,677405492,343291297,201247768,84492751,582975390,246982116,735512539,843370841,141654487,20577064,93847481,41616269,157942739,253826681,162504625,409011969,169008936,559806018,326865597,159898331,702185298,998641799,233509419,140182064,43367467,673040114,781805827,151076974,825031264,146029016,321820547,119605214,160138106,644137851,559797230,386187103,951058887,725929188,837264109,585024819,124975545,810935205,102261504,722180128,103838452,456141400,644868588,103875754,521549623,449245285,60485790,263381008,680804989,496578907,880237707,140297366,40785956,442279099,943914626,911418793,214799900,221908693,587792059,389337991,13920906,685928197,702989883,843421434,637465969,94626100,242963920,921169071,671943652,533438169,898563805,849843509,199098144,255962760,349340957,946151979,7388665,213198285,13831377,121676519,51296398,997618739,573314244,726353397,524493831,540425260,219001657,766856819,513191286,704596028,713591616,431100195,38636034,254235553,591965388,663518143,14334177,982301531,480531959,762122193,40721974,514417272,834906260,611362322,604778606,266908369,628597778,370795253,751252155,238608372,731917833,349667793,144317337,470919005,258477840,670617577,75437183,650361529,727433251,346247186,843255379,141546878,152454826,153248289,604079048,246855298,106071129,911995249,106339882,133959626,335045635,409865011,621183948,113584547,488476402,785884511,336547327,671977269,305460510,388875240,826399437,164087441,448618139,109977556,556847272,991345456,364945566,219810508,476313694,378197620,963287867,892944514,102721562,657418924,436491853,314435219,902954113,475822420,65795159,451116264,86753716,514265655,434162988,975390457,290228179,929642116,551511687,510481535,258967558,311373415,982821813,634976945,211272672,862308391,242972512,272596237,735314786,460198395,465811918,115991089,133038503,240621972,214754681,254891538,879687048,268284719,493097180,137889065,159638920,637231915,248826394,667521827,377753039,726644519,767908922,16017231,204619051,911071310,817104060,57497502,578832120,123498508,963199532,555781816,264095640,954206778,738420628,327498783,271458620,149760112,960346678,59526294,878527403,105484027,196033014,279930378,446171047,931375252,408535959,551622032,217566303,265182258,889642681,443389153,66217959,321686345,11555847,945592299,190781493,64446458,612840096,464901038,839216458,831394688,721913834,716181066,209334827,712223603,268247243,863238048,42353604,19935271,837629343,281061716,133215990,283183756,438603918,97668253,832821863,86123942,667072272,264533095,716578375,444456249,28052677,975402224,487996148,511211543,997815201,373262362,413763825,369536367,67991623,66886135,814302142,855796841,679522728,213433328,669231784,52229280,644180984,77712139,23819953,348465238,467349697,398660400,929342738,814832935,393921626,96168128,828498261,286305479,572816273,946889388,516119846,532780067,220756657,552875830,815312819,16881073,838309663,623276652,132943745,441002844,968733311,427230070,63449500,243857588,908661618,912578487,171402713,782805342,917540050,808529821,831666978,648819501,934877488,141074295,213729777,563704255,272541799,27396742,895542336,814642976,141742938,714194443,179900418,722328928,457236405,75769869,799364190,256245698,16734051,721815978,426020343,413425703,336192276,147086053,114593652,475656383,422694947,151048531,139968341,746292300,275682551,274408078,122155415,657650529,827088372,212621173,111266003,736939531,997483846,99146171,49869572,77747783,36931505,878009130,339309373,996527804,210817453,653893599,315896694,489139252,188986226,956165047,645814428,820739458,880605925,33969998,289063440,474205144,447019769,956438955,747397468,670371951,35146873,741448742,474381831,476135953,685871927,550238571,795078815,246392071,556044459,383369247,835993329,701861829,857065610,528886841,359300332,829643138,200900395,688645681,278586884,488387506,439293086,943096594,47656851,104778073,654439527,546868933,143631418,827580254,682725937,569697238,419380740,283746304,155929919,784099293,397159459,472831115,976034483,376954926,404682632,420285975,672666842,157695686,189552782,888337151,769161491,238602875,846551176,906453657,517621381,206296470,186165032,784997723,464686940,388355019,880001100,458610811,553091394,497834742,305198660,75908162,769149572,38280242,278416841,777958452,267259828,93118250,670332734,376026754,630259935,389380541,729058756,541800888,716861336,905214482,165643626,626594248,702699826,263400729,805234414,925831282,927334059,60198265,287442118,348955123,903890882,394734896,732411489,263631019,587772572,268841404,111883740,381827055,479154727,882799017,238561596,152775023,446853396,307691591,24926539,974008386,38586068,561940638,696201938,575063110,54773201,450188291,522697034,406429139,856541713,106663128,124304207,472197096,264516807,235804537,852503222,803737948,751552406,989959635,341267067,894257579,342063478,247151727,645702391,85217246,667639551,415878082,751136836,93420517,308083262,372311517,819802508,958651382,631457480,834661464,792043244,767157802,922340204,234844582,750925066,36190843,521626200,943296346,257405068,967891396,955045125,150638197,685935744,829832312,232864166,825811706,23510759,801314043,815170364,770123535,375290854,146890517,123187394,822252406,331897775,983851744,765158086,879873166,455907720,219397544,185100109,421211107,981953415,72197288,884537439,538932739,549499905,265221235,190224051,639958421,976056149,741095388,185033516,301982556,916960831,18035745,124550566,317785515,229320516,604249694,967418973,811987774,967424580,699203201,270661401,428780839,357420319,651540774,426672565,637902622,991002130,37116425,483970854,577571989,419313261,149626751,73453420,876016562,855452280,183453295,660495620,399892575,163671493,47714691,367884815,434665992,839444097,362356067,2278824,231446478,621049607,3199007,664576630,269950941,225497854,781278870,31928910,344235776,42720792,541791624,354139866,144520603,739727020,602171235,394496912,27581695,502058691,637170574,572373276,91373397,847832930,767035243,9974738,934675678,251242341,677175185,767488842,43678543,813348574,9048641,195127506,93442951,478110078,505252450,627586912,561039567,584287170,819232106,109323203,735028145,292095471,893942633,698238419,442460925,497875492,197105332,122509828,171818879,187372716,962211310,333625260,952921081,959052688,579251412,935109633,102273085,709800573,139549904,156072582,827331265,792935108,724330521,531250182,632288295,913267287,10646078,125963754,801421183,261367275,988711388,836816208,499603653,177536201,996144524,418502856,768556867,21126964,746082193,246402918,945371410,773267364,526533682,818967734,960990293,932323942,527804682,351323195,256392762,133933630,45614510,577364747,83680614,965774360,881243072,650576323,397013784,171955037,328296575,795046882,709694140,705235542,931506601,675656377,10686550,806176658,936762083,957712824,889498703,171034554,37607970,155433081,23677615,458179188,534233152,227457557,358268839,27714532,380145081,127505120,582850712,299002617,18228517,69502276,41132411,408654499,396440165,121075092,242057535,719941905,933708715,972342954,610452786,350592583,507393691,108202400,786571438,789806112,674902277,73946085,566302629,993740677,819235620,375404423,908161053,296538542,406709285,122504594,645377532,713257905,471891781,428054896,248419622,480377186,308336029,118577770,864734552,571776215,646503758,668890533,759274664,781447374,923513413,271110353,738887584,378672265,350711794,363489321,721525979,639953022,92336578,63168243,811738483,72558037,298173519,115963960,677081400,191244347,608204117,857413277,929675169,107033458,905989576,307746602,949496416,28261433,188997022,137613419,821823892,926818987,140801396,508040734,38614444,245877492,497449794,277828565,628221955,142283964,217283837,960227137,990862932,845099286,919837122,115218348,30482398,9533778,758890477,766867406,691126995,825336920,840738467,996501256,764625217,513878471,723717510,965792540,393815754,109756002,773651419,893400195,964396119,546488124,831320427,473809207,441978973,194664238,104253685,638006421,588068276,943771238,648980324,342862355,788975584,748603710,468844775,756632582,473131787,586977846,944267051,185153405,962451910,82422166,935370225,187075535,55436115,499860585,200825031,569486580,819313959,544564349,65193776,81090418,820496637,94480672,739217749,632788126,723992316,289489688,48220692,843835525,361663887,106227799,604685714,853156172,40450363,37397067,905753654,637572842,536335542,202587935,926821628,37705036,200864187,80097825,879381753,579642595,860249951,6509784,35757338,264115762,937892163,623614561,369729367,16775329,622596746,443181838,876842048,844493600,477490755,833709024,964253340,87263696,495564927,811123601,121149429,136934425,147389969,134563992,109711831,31269422,559165686,302223908,471375179,128438248,233547479,425351415,55654689,671445087,98495871,296169216,641898144,571747327,160983142,961756021,917012556,887377820,678070903,789435739,685472785,284309918,245677251,633988023,415824725,854365737,249277917,666334300,100844642,117257767,947259179,288746242,438025652,323191248,889161873,952383685,162467635,141826108,757527564,482708732,485418936,145682399,352722413,150729571,74174915,117281145,547194647,175455675,181460972,180756242,73777367,878142850,439257766,349473354,230886133,287202,532036720,966730579,772546629,505063841,752602743,108599349,661137271,653724119,614929981,436881303,210449006,903855811,952780246,385017421,619566336,50688496,956501569,6772388,592848981,481680165,732667612,66301564,579351933,477082433,767997180,144864368,74934434,790593674,819533507,732518869,68366679,720979964,53013505,939748677,406769232,130033823,133089093,297909524,973967289,140847367,133191684,874672814,100421183,649654717,939967271,140216365,619864374,410340799,820796854,490755428,789273916,113197271,629001033,705851097,332699829,431587793,643761032,462029816,827228538,420907488,381017598,114017879,181552738,930088826,262410647,197311769,504150615,436398890,692468303,893864006,169733008,844382240,960368304,422994476,97286562,653170745,697286329,473069824,900070774,614689150,684201980,400726753,505820679,587877127,671592220,276392908,328476295,668117275,648029340,539543443,76183798,520839374,604013646,502148953,6720361,279957683,905086182,156789173,986174320,353008694,667287044,726722452,77728853,157248504,470720918,869691856,137322310,224122223,135885123,46145500,118800511,313375245,267840271,258689163,74839591,989545951,185436089,418554604,283780434,84057898,302809116,569547800,55259921,833535321,985289244,302900469,104917671,853179466,431952621,125952865,56883269,199857746,137691692,137358203,620354452,57147157,340056068,661328787,370544815,44129405,801051620,699594297,608382354,912580311,409080103,314137074,979976970,66340878,447123753,763635818,64918654,959103680,643295378,432739048,311045925,773664677,116227401,809766993,149980312,366280784,393004386,357995908,735530509,938371209,877984673,928260574,954255410,555778652,210918292,555716094,306989633,112020315,968232942,607462875,284260865,214222058,247536434,462000577,335808665,349208339,71746322,102107887,80801434,613014912,108066256,645882877,616656732,393614302,225940954,431504560,37842579,158044319,606576672,629253995,662416137,465767089,362550086,761167441,174074286,586776166,495093516,330569865,347526266,865916469,754397342,412675106,605810379,428048004,925564356,736076071,370213508,918303597,111067437,133081572,609977586,953840771,29391920,861739208,621153488,808664749,951918227,929449617,463664641,740949971,681472222,973345703,638291122,871049267,121987448,189134229,503189243,311005215,89451707,176286649,469760530,908319916,464560267,761350624,105347320,484355621,601900017,131103280,134605138,8274075,268920048,433653448,646981196,103256411,56691479,123926863,927132498,967529832,527711340,137029270,948471306,186128261,521492595,638259336,336821965,992850841,896147497,248165668,300118180,440143035,550308977,623887388,660165462,145894363,767717714,742846600,345861120,797095058,566628398,26489319,676869504,924875569,897051197,404266039,654036943,577595655,817067723,92276474,407505384,617638605,863568284,90641340,281569166,426498621,654888039,849580598,282341683,525289958,36029867,756564793,333802064,984003684,378351441,253590120,481591192,30276979,704540292,131341733,433274571,721646398,870856577,30930265,153921281,384658779,827299761,263447380,796319193,411567225,958502166,271067815,816929996,72466079,900119060,71726883,775396614,160121502,158053001,752495046,653040939,17625603,466723491,256929324,769017998,121883318,379483544,746470996,338563998,560933483,948817029,701727428,745671650,936341305,121126497,751516301,383142900,119725172,614745721,280485708,189667769,673440013,60457379,933360978,422894489,564288700,505374326,321451775,364105151,334362554,459719457,6235540,159979233,914421565,290265023,194374155,523795998,903869333,32560853,789410033,253432043,765253278,125260041,504513605,887699457,788856668,542961076,888788229,114999918,654296682,293556665,36931496,877857867,944515779,277579029,936259119,94331464,378962540,579891356,953230206,712065622,908027870,998594086,579080675,5995099,620876062,440933261,946735477,869799894,598611907,702413332,743263365,115000956,85785192,830194807,882866690,375941707,348358653,616437827,802423839,933137491,168737196,287639132,158180705,751332527,441936929,635514377,299452639,346318752,691560072,661611118,820714638,463456185,384913626,22567418,126451032,839641450,738805713,357171437,763548294,741386433,574638115,501816824,660057777,483516215,378905257,971641044,905374720,711280045,235232044,27569381,649602362,853015364,28395376,499714798,45550216,496775489,36707734,57552158,911478356,215875241,908274282,845073276,482687052,475548245,398198159,957414261,166517656,491052351,337207836,242755219,915520080,218632383,2919642,471277791,846143201,492068773,240343214,31657691,642351828,399858305,735179250,329728490,238922170,563469878,982839923,939351715,531984908,888904873,573446910,15608634,341306704,412952991,981256280,92867578,752255724,718701957,421255502,935121602,96414646,676758993,215000839,97101750,49024177,901579547,202833197,960994190,204842243,367291960,207970242,45458556,665256007,950821945,831590866,517088764,637515717,930740736,688665204,606709945,514668237,757907721,429556490,508884794,546850404,477709446,568786436,936895633,847782605,921222968,784811953,282912775,179193545,726816299,507531735,73802839,99229332,738546361,293209667,647387051,127505386,941826443,968044042,580104222,235901774,546303256,226232667,39357657,645135079,933317628,48816108,906552580,32736595,448138533,639174102,885930020,321721489,602221055,438843074,176700920,635457217,693269588,683180541,413270656,877800994,136134915,387905859,920903568,504602025,226290750,868074991,879959666,555208151,566947642,304077355,764509272,505653081,711519766,116739244,822377706,497352650,999634426,91227301,746902527,148854574,773355041,207142443,165026292,988479945,241921001,572698614,116878222,217718727,33993848,689910390,852693155,848458232,539067722,670675539,49604517,65419339,577160465,945280334,242553032,664846818,723054785,919296769,268934996,684884484,134153246,648754750,846607431,851931442,931249723,446253703,966069575,400470636,496229554,451112777,28147707,70582718,872768282,303206564,807005395,980442960,455783867,78262398,889109800,870171352,399255572,194980307,121458074,674858577,486963832,133924285,95574517,796117841,529432877,946592796,619243974,720696234,726814336,474539594,625669978,555384534,29428007,675274839,40628325,526415685,628770733,130166291,4973700,634092245,374505301,829003128,181670560,762839533,359637119,47571306,667023258,795259866,141832581,659297853,596375429,975654654,790124933,383854461,401050439,651043987,460086622,380221685,622009970,964150772,717908389,116143655,549731618,657632910,530965839,148302788,89422327,829980636,223756918,438654929,162031552,255030068,60477111,117513055,504443792,714352366,686628632,383277624,443569215,945036346,229792588,741407788,933551600,479194796,556238700,500494087,903653488,699821232,127511605,46349176,39994327,815250956,977149632,146416415,597406021,116945222,343787727,102295837,737688368,905306845,570504920,109190232,647668195,912230369,763034428,340270090,170450669,21208785,121247740,434742333,768002215,82003966,703638835,658434394,323626967,769840165,907658558,441039665,233078789,345034595,790591265,986066866,694512963,105747696,125529181,378477222,220107740,383946046,585814465,718675407,122513299,230155976,406418963,331008612,279096154,457753808,974806080,206022175,664034839,754004192,247453997,430986987,928927756,282681402,792496250,790895056,796914909,686347802,312840177,657865561,146163902,2892393,806282426,566921212,7351992,596835174,112654281,447407760,34952751,626323935,809021598,152523360,512120649,890269145,234951366,398160107,317874297,721479590,7776746,293224711,545726490,122461093,914256225,658879290,358543098,987713182,446858564,601571589,260686247,487113449,708074979,409284026,239482219,386278833,138259928,950282420,560750201,370385171,301454922,638950781,427541267,998770185,598314343,143706125,935697156,239353911,584311346,78074491,85461920,839413244,991293343,282060953,895006720,47974383,999087456,488237099,265907706,197345335,68294377,860305319,937079760,1942869,27501734,98616389,174231595,83184882,662414733,442170061,51775185,40614416,292647122,575606402,595947257,221818791,76809145,293628168,91198770,621887079,46205382,125237285,915032091,606935848,16452664,287511963,375356391,455392298,939613156,631056501,537858352,26651841,53871689,769335145,216743428,674529084,244142275,605450155,816214177,779114381,367605708,831660515,894700929,350995987,844953778,976272882,88759625,429366357,608286757,98860110,537009639,440212910,577214455,59711686,492422031,528078057,5474595,255678500,866750431,92916216,215209521,456936477,122825845,395170726,260450289,816334637,10707023,150266369,879073489,48121910,769563607,909020615,503790125,465589332,876976903,963517938,464780517,168125080,382718686,639432837,939521871,96829506,768386563,99289861,169900108,505348293,883915144,817438909,35832282,376215923,869161093,806723157,531836188,536851480,77001891,824100052,527534461,104686142,670881701,219601957,118680684,801431572,435975198,13927800,801795655,319688660,3223826,495752407,21637736,179166118,472872132,872428624,682520430,410708383,556330201,890867747,558236945,79764519,10948614,477245503,6725954,19454165,548636811,791585906,316107555,738112785,596032423,298698684,559498949,460924208,779649127,765147142,488915936,730681508,45589988,165223493,7869858,65179517,841439405,685242918,715902543,970649707,69337868,425410802,699266929,194254250,656036310,821218472,341459635,835780661,275034400,118352456,372849448,916369168,811373939,33612901,936806524,704632711,182639150,862062487,759536347,677564839,519447610,834956215,450956007,540797964,833565422,343713104,55128498,979214029,482998442,59607612,890733960,250141061,140809979,66338059,399744820,182341924,954530977,99287349,920659502,904573479,129724440,375739953,104962822,26075167,951646359,9636504,337922712,520257916,214362206,455520223,942164984,569956757,131644210,636081060,440780654,529353275,608721982,178257166,228501397,722218543,749479357,507963444,887085061,52637684,65776071,130304248,383154774,526312912,48948569,985340960,379112703,956197250,187050249,630454313,361324293,841122382,652004651,780602363,399293996,840772475,420590065,488540178,857767743,237712868,713567634,28034721,880637154,411352154,845792585,41716602,844239470,501295139,482032570,6066084,459415888,199118651,600623909,158392594,372088725,15799589,48698673,287327604,571801972,79401657,709282990,30467011,750924469,819135642,842557824,155158228,492169116,572302946,116358509,427341993,944539361,466900281,80755207,836077723,972788140,857264369,574462060,44849155,598945144,8160297,297115427,512480892,502422305,305980131,532210799,390487616,8315458,964444129,205908547,108794112,787035365,144576260,527670572,599325141,952318935,221698032,987674857,950213936,202718191,175571995,988967565,54437175,97566603,271873960,333423482,63626951,724287829,168230807,12188728,845005031,690198406,605432195,514360457,27500202,72868065,66363174,821852625,262250871,13945253,95128226,885239592,248094906,110821246,704359573,241481147,622523377,210069055,167491717,829710049,118452150,693901437,210743380,763453757,152503074,171173847,83738127,784911704,18965607,927377093,137975772,262418400,327616440,101436172,883210733,508800045,915452539,437975865,279399717,471791277,679346393,397254630,131907887,772733105,491682326,980758004,662782503,180829510,305192643,974780443,775141116,160933910,927292375,507098924,241999303,95741750,104814156,674929352,528995610,246918690,24016826,716847524,673076198,595291037,723126064,969799275,15534195,237694078,397764104,897681395,258585590,334088180,497788002,519639480,912231658,784698651,526129708,117322588,450748570,556393021,946683487,996003964,203594583,872706810,270046660,41268509,755591360,153182809,503556688,44202389,27693708,30156113,820629077,172916105,448580922,277450015,915404468,630046568,98288666,108642075,24728084,140563917,18719897,885674995,123462186,145714256,326616521,475666715,596344871,255044926,955690448,259163623,459154223,889260868,114203934,722621967,880354162,743051482,848850669,899326862,996662048,526594136,687534465,929732395,714325771,32625045,159274839,167594911,62102891,86236595,974474087,68666765,322074425,446070535,35048646,445052622,106854031,392348703,75349962,538943251,726175089,675154922,25183306,201545483,793221462,94631258,329654426,787107100,409764180,74000978,927362789,543063375,460643875,363059690,943168703,259592814,82632772,534563042,122446424,667714342,672890419,413365609,119170996,97665699,789896785,51359741,62224540,569264847,387614722,115709881,701742941,213420063,653308351,69568146,725854,107504874,800670191,731368035,53652464,379787864,566209942,583433915,156455781,825305917,112649624,14632492,115157286,358718433,787084880,829291218,728631896,164520878,83921435,156759122,481107163,692157586,173632103,951962495,673461893,280710892,33873032,806839525,133128095,391889647,949930358,86095108,389480656,471229336,31760016,214644456,549823610,263280229,134495983,114168215,560766243,640003065,578904210,542136560,709028277,251494336,617487856,477413488,682566202,825493318,321836006,379424627,110758046,435135751,144749022,490819281,714967640,290120515,60595493,107159329,874019826,863070102,514652476,493012594,70757232,303836364,9140829,597047575,534994241,927157076,587633700,82303347,292884361,474936403,59409322,60062646,741534388,913834153,800544705,769808480,729633832,617168632,200161592,949464120,485462561,878887774,74293552,756708135,388445989,54428821,750139503,865619031,50324170,837251919,25642420,475423540,449764871,55749457,678253707,566855273,899115219,734545441,414718862,595479119,736736591,734154913,648070776,881453226,242172376,502590945,785807542,835907922,266426380,324764665,563777628,505721810,719164422,958475238,818488919,710502598,53582197,760336886,454343352,489846910,552197419,150677377,551455426,919407977,138007852,801586960,900097667,859658379,801377415,880263568,367921771,848764062,236701591,103925693,567895818,664436,15714773,563658386,649105163,86526359,195065272,47476113,214598154,919109543,417194908,53689879,215643191,155693579,106900207,20945088,984259555,176786622,75850731,803906755,441208008,914935943,345481481,504448257,143900690,58267464,634681572,334884533,642685922,927030291,397220430,350087065,955592322,402938519,171749842,174551504,17444504,924981314,319802343,559388938,113958047,323439961,567292548,451440134,294607287,514866274,938831933,31438353,103421709,894392740,820735827,612558286,23487662,413122764,539663797,305994898,425894699,449210642,478240889,556309280,893753569,461101996,620248396,422147612,541923774,634722691,232992988,843439413,939639022,65786363,303281892,73043091,860541509,966262865,501612019,365383789,349594950,920045036,314661652,59141181,848384153,294021969,267361236,4503928,328568829,868831144,349216186,203630851,482263086,585381202,672253685,449195506,16828715,958328757,504066399,20980578,433256338,769709436,857979902,863006956,246336232,617558386,515327551,308601306,489142437,449537943,536737855,521811585,557073325,850156002,8717054,478638582,4906012,850965098,76796713,670640700,109560375,987737146,849621512,969983281,960639390,684169584,210752250,705510425,49476466,60749829,406117187,908531743,84274431,1617022,845958499,682749553,759589928,430617059,361020223,25585186,306470280,973189032,945583850,841757728,592846638,796806433,10675317,971888696,565673168,151807885,17529137,199924498,112108909,871275144,977839962,656869421,938413167,583172779,62510323,284473856,646478148,31441841,748001681,87961607,694958291,793419382,273589051,241670508,657630057,483015468,552785016,643506990,694334638,256123068,103175288,840740865,682299373,990370678,807215827,222206290,940032475,88616346,168759851,313896648,441125904,682497662,821025185,33347251,121499337,368365818,721927403,151256671,697715096,29884430,342398768,232898394,608103124,307507573,79619660,285313539,81149869,819689594,208389431,648317138,81597135,746954668,25188361,872462024,243874230,40880065,23969062,707056554,472484227,440855161,634108777,652358625,80371018,614442719,482898388,732505103,837001517,112103300,777004681,269616160,248305950,717375529,957321645,757404191,556662368,31147575,658766804,260969474,952342344,822154517,41182421,456193991,528765525,467825967,606374280,168113876,548918127,870191555,945828815,870938611,616697125,72499453,668057300,787513162,584975851,301970369,505112500,215909487,336363157,78620795,470237238,330416684,713475424,980249967,359634163,352394883,733878733,301280810,653112622,74918137,516689995,377856075,517908346,734349931,630771008,389049864,466337711,570080874,70194982,798540271,441024594,127264139,620628917,375113118,307165212,122514343,247702484,105319280,13087341,915608193,906568996,101618885,452079408,94445748,152250081,7066368,91319900,510235342,416169101,992820806,391349252,811951250,146544290,392096077,124432074,828279187,692274633,786335963,334166503,666679016,452035513,356702483,471773004,372232082,277717041,901321734,957715978,942507981,892256395,274923764,406376851,770715875,593330999,347527172,526638542,433866107,73657362,447175971,641263744,292299693,385839562,197883172,517786248,622711070,10120237,25572302,882907470,706826098,894177529,144146775,106272187,203231183,207493951,630370307,96919098,919654238,981949185,1103678,15141901,86859761,356101745,112587673,913884260,642693054,692392746,978482576,719864684,990360437,635095340,53653790,609095368,11304727,19985753,686080317,905165654,137970008,372564274,772922113,166351066,631636446,902080801,37474587,622675138,613232535,825193792,582669818,406200806,166432629,209487209,918802808,556867057,530893373,77850373,52151497,336882103,210611629,489576925,102505396,112262834,749282481,346552159,526485649,11677103,629036822,952851751,793823378,621098882,683880285,643471251,93669265,193823604,8103576,343805580,609372630,169258445,103831418,337920962,136340597,111362430,210104473,555740621,719214922,452723669,392143562,129533891,675171626,98906012,953979484,420279086,556883419,805889507,405582520,512318062,267727211,505973390,652502188,552772134,219977794,140405849,302533246,227968004,347416980,29146667,241760753,233915547,523524419,427386952,552681627,53331714,638414977,805196605,290375419,256821149,743899351,66599423,497522274,703021347,17731813,311332736,299129860,9317971,633810944,941646688,448890473,185106378,172069121,452727785,254299752,316452912,100076943,513485400,559824154,631677349,235032453,968010738,20363894,806066585,234248819,475354560,437901658,179686315,418867101,240950219,289151069,6523522,119168257,406136395,24339177,485128418,705397314,148419889,264560256,966051880,103070771,438628715,514431432,279914802,538890284,983442367,327209788,856770596,658532415,616560845,929525140,732979702,16630900,928619346,187180404,24990820,699874084,15795169,121895380,582209578,53860292,577785766,71801075,460815067,885778565,716679529,790046458,419430205,322125981,958067158,402339300,838094344,299377513,876654648,49366869,780279541,623097005,54078841,103455162,895110820,4604505,871482821,173300007,458370895,608769054,762374848,139610912,826928969,828502246,146259952,115216027,552999842,752098856,436726550,111504051,881318482,125013615,657799117,176923241,77038970,8813296,534651385,607227225,618658609,472401267,401051510,669044284,195884074,924179445,82197011,91652365,655523656,794977282,687410587,640693427,651421531,570039111,722789310,752425738,281159961,991441127,825404416,975143739,438606047,487955425,619758660,988110670,684988439,88346353,364428303,323127277,961484923,655635764,531692791,481283170,502823588,400871149,578179182,886987777,919574212,636952203,49695526,9050446,225464141,7643057,193797335,212095424,12420795,36344962,402894095,425115674,241039349,994180401,767225947,67653219,467275979,159681974,567861915,430856715,886929899,946818666,327495192,211104683,393422337,147068846,32417025,519576484,646436464,330858853,702558866,834748234,895881565,73613838,70173172,224958179,93874311,931021588,113977474,856970972,85789622,343123326,880147887,778176273,633210081,580360482,40874878,582286084,399234409,193798835,237305924,523532189,764998764,349631959,749076721,183311133,64157464,257706654,948701426,551766385,703244949,835348402,245486906,582343255,360107406,509233974,766046301,568695720,412231821,597970325,11267962,988033554,181878405,961123154,224856544,740199935,960519052,809132465,222886451,634080167,964488933,751907953,168682054,360867538,606892038,634643063,687663770,955477883,627045893,58067822,781287194,24346731,173614987,309788814,120236570,826898741,320460250,879413652,322790510,389387826,851497751,84656027,972650053,476898385,615164669,879293803,101466945,252928897,105834466,436388924,524969741,96593689,538451047,43637049,908937494,106775478,426613501,438192552,980795901,152233735,939360568,680777279,823835515,376428396,938206088,604784742,370036121,877422513,69972042,346554985,366960809,730261257,631903794,100431343,820413837,850344719,33000026,373634634,228088388,16205799,433419202,211997390,364763357,659412561,376789138,913251010,737078539,38824008,827557415,298870864,158360915,839659772,46743567,433094345,194576732,426518921,203091561,8350644,555815231,825701545,526539901,923490467,32940578,167470676,121568893,951436354,627566116,211521195,744267158,598859309,920036521,964528625,271527750,164144375,405507877,50771739,769609514,533095917,441301735,697227054,269813477,417129122,95508224,474909968,762599924,627495950,825219811,19971151,440664503,370181996,388681413,70737764,769616266,646576781,748704447,368952956,21181,941946223,833702855,860570957,106690332,788543257,924934762,891907948,654004554,826212310,314011246,12669421,920034850,936444128,701789011,987718553,537128961,652679186,25588804,367278006,766423942,473257066,545058352,777967609,66656458,456109519,109044621,909394256,548144893,113854668,733432755,41158083,47145225,741309410,634617623,260093690,265426185,487335054,930601498,495975785,480984488,570821086,773519831,474779257,713223794,691566782,981407510,841611610,284525059,714068391,1806679,886040051,816507437,412967907,877444423,438213412,331389921,38284154,782639334,481948663,950346204,278262820,691316221,858174655,634231911,219883047,902498089,401361640,231926831,104407890,82246209,125544573,198697057,957344492,141393720,80317036,707167245,185384217,546741900,8587787,453531760,88827117,209199332,375421363,192871633,833691086,308264305,267617571,810737557,75358862,334020482,359987716,852109213,978584695,288695070,932482917,52213860,823490553,21103003,929326822,340311301,656062524,54775748,931469229,47545173,227805927,918356135,639568534,865676281,12524920,845911612,894719744,874241114,287290224,943556312,331686336,577680118,296175139,95951074,475438977,709214530,234364860,278172000,957883059,603154701,891224445,903787868,810862245,230527853,421126183,909140816,376524685,409051664,836162801,255210439,797005214,411125359,121994892,107224115,169899550,141464918,336479597,888144228,28693346,651202803,188844909,728533875,664565578,84199977,750268644,888608171,29227337,36054952,178168388,676871776,756039651,890653636,254640662,603676341,275514759,394790159,306711661,942133627,42939658,925305192,675274017,672307902,567442047,816586180,943422930,30397287,372051779,394848167,488673539,158703845,953811919,898981425,278848261,793404873,29736288,207081243,490942961,439152331,724910956,903708061,617029643,11657116,293115313,854557951,184851321,534798485,932053278,66700706,638259164,333931161,799231894,973209051,489064605,81877744,168182837,353440585,129123071,5949405,645875582,848554736,13526803,504690017,912193716,147007457,941114327,884412312,228901828,9811419,337256892,67239411,309360933,164270122,16948990,393833526,408450006,107009961,72601988,243879398,127738641,567175934,638992283,125065381,173325210,881957716,924179796,733591199,763664166,541363490,600942669,427846042,33177738,65472924,891806404,301859615,791153669,493951237,814144604,355539322,249878900,29637346,46151765,17074944,801732266,401793384,45797298,354515369,220170005,75928832,323571684,633677362,636996239,582787156,23795503,292039157,94956882,945923209,102913500,735837243,651198606,118305930,590886966,72853834,181687826,698524126,949371180,70903628,616830289,163103154,878554284,557272994,911025591,48704827,390757882,462730248,68992349,706218841,277943718,623136201,919867435,270183870,992851910,707092758,726459786,165090107,913535003,422203018,473132416,597549449,380055971,777316997,16722456,319917391,345517027,308891301,68121108,95656883,32959556,47960413,202767175,998846083,519426960,280870243,210096573,422965321,400257055,994519559,817982090,427657114,5348489,845225096,886842145,619420835,398231767,522263917,716966308,314973817,10731042,760975124,443791183,380685228,615821161,28052965,187264062,76525757,411650502,210655058,426509550,838571742,87576180,305032574,639005829,205249356,767189210,657235882,655072253,443676580,809057676,113391375,389318245,36554953,784729185,39314646,922249202,852857615,317570158,904782711,351319370,192105987,850380646,636825115,854189735,438695950,851471499,997943732,385999232,733973215,741756137,552823724,294072346,907026053,193441296,25103961,453951224,696307624,996822643,871209232,663035556,138923987,373703798,243044089,328107229,907675954,378909168,37373221,859479001,81538663,911699411,429157910,252401675,834748900,114096449,63605219,152016683,231829829,828600345,2031267,365723273,405830175,172666931,555680798,713769761,484720985,300121824,501387743,97965773,538273209,202197430,13076456,525642576,520029652,27401521,414336498,611538312,60653820,146998993,5881301,855756723,5259502,142599165,865394681,929146083,450114575,638257291,302451650,4067679,438982827,378045944,207047913,930765651,107411609,26143914,314098610,333512522,205617162,299432289,797274880,293929458,860012506,665244032,749558120,477228116,714502645,64884138,171971846,610805438,835163806,644970650,671748141,542452086,717106465,523108869,885689043,566588344,500785388,504582101,891428082,385852702,418727152,243332445,879539227,285845888,83899855,1085484,63860412,353099562,47021873,815615993,669875550,489091276,382653594,692915240,815599577,393971838,792597565,346212614,262203775,15381359,609441651,181810745,971445181,553967504,190229983,385152476,741952074,698453236,550901528,992957457,333537540,626094688,896529494,225938306,386999624,367692383,495428662,668401393,128233272,83483141,232802805,1538801,92824643,30647179,484040751,604847221,627142096,320446574,649561120,514366139,122997576,779464927,816781389,929333299,656191662,284735889,755499485,402018262,737375972,97318214,830640840,936892380,793109434,152238887,818928810,306794625,982004506,137905147,429929094,328789281,486022036,692049511,297677803,226916089,995234398,947379281,159816909,333725744,848777091,455679994,686973956,99192220,469310046,779486269,175476383,529500328,932758106,234864442,291733508,459902855,793638432,660195107,998642947,252803855,151737219,977329322,664477529,958865503,935221833,840534838,721592300,961631491,178541915,719310546,266897659,448594808,865337086,754125496,931705256,866967315,236096888,323595538,241612962,690454435,613544304,415623012,759142640,502982231,919700403,610360693,950269179,131187292,192089753,784557230,503772030,515971736,190978944,88038121,40466864,521750796,682876249,741485953,99787108,730174427,320035631,185293060,369171270,581278707,648118346,887983638,477140863,395525121,921799760,534515440,469883257,823508958,975930769,135822444,578656703,322748636,40116577,515401637,199259639,29747000,387117827,561351626,534095489,854217741,909392792,523539445,886950356,290639465,45169908,108916365,694257889,906664850,565153416,213292031,648958174,118070952,729557592,335802952,253189948,198351329,589144937,504838420,111435643,293111717,1141401,3657431,779374210,439584417,544529417,123586583,503013832,657839832,861220246,281872320,872135536,406062777,787041451,453885084,377671222,351546200,709470503,241535777,540689787,15434583,710998841,951487357,130268468,136305383,312499310,578386255,72296394,757233403,626690677,175898382,386608002,228152370,298572695,234980404,93223195,286659702,876769871,631414761,471188300,135046542,984500162,925701177,888142971,653061878,222063729,45998464,588028684,71327072,291202656,920786457,890822517,945539982,104468252,96750343,23851178,873263813,41661493,918022507,681755101,78220693,395195287,27752085,11298352,351314637,112558456,629855563,35551278,302854058,324887994,134579415,575947614,242751469,497988761,953333768,305148509,440041727,995109068,988441618,952264181,301447554,515116805,61560578,354495170,880685412,222424360,310167671,45235228,852244536,105474709,477898897,457922099,862810692,95210831,333119602,251283085,361959593,426686178,866696313,183354990,8283485,781578987,633544388,756607290,48049143,901073707,291114905,800460469,501537675,263367828,252267307,516888149,560746706,104623284,200384451,400088039,301351294,837737210,739477316,700363401,442789978,733301969,990521428,400408852,605309513,599927730,342614023,703205532,965845461,928753932,656188728,28402729,61770178,936780145,261280858,536300869,619838824,187943371,963275307,681848594,856578966,939795721,197437740,266840143,629407043,732705157,904341801,530879588,491660809,973626854,714123616,136994676,953007104,50336180,477577498,144114978,926365077,954386967,826394926,442776133,500609054,688420210,784063081,581522953,251172152,290487240,988713049,71754057,232110032,35983450,769412852,522764977,548347140,11031281,157619634,265851887,52173980,714753884,992490717,78972948,739400346,406728611,447316676,858609032,344871562,197979281,985606564,548151837,876057407,748955617,295399852,596099278,629352091,163631962,28812105,61228160,209996785,893312052,630460365,256018835,144309835,906359382,80625103,796903442,848127002,267052406,108965412,725612240,598264945,520495361,264638096,126825113,38874945,122129083,215088605,572184912,73023296,882352013,108678534,637494497,574096196,190740201,724956883,321098081,69042456,755388612,40564467,453154279,186954891,175256054,121398119,814678539,739450279,452973964,303884333,667872165,30454286,744076816,901770031,256814138,626065474,760034865,466222277,422960214,521445128,47502889,664622386,38972033,606403452,658407680,22128416,983573937,391023131,625802897,641870520,900449337,327725128,573650319,286820050,276771413,247558889,46423184,490868205,182728239,211897663,836135315,940736884,983178752,191599777,139465186,879700803,499465004,142229752,892099909,585325787,95398849,784127990,879469938,914284243,129777816,125346738,21167859,433404458,757173560,975414445,693394495,635008843,392877289,723865345,302971738,155252107,922509822,938130661,130061731,602138849,204690479,757056637,10289584,138346528,258284973,931090624,126781879,519262529,19267142,138782053,135702707,920742013,143852209,804973788,840457394,567474639,364359924,114343649,361801834,70197959,287048219,171145571,755987042,6454173,101103261,375921428,7529500,639749905,973516453,6097656,197067914,700646924,120015167,400745814,619157484,267058804,216496598,821024568,377482401,472998947,501819613,913953922,20523710,783083959,512310097,926838034,313440678,220089055,69907251,50591226,676189748,237634712,754504811,864401520,269474685,18019272,54710277,392624623,772275177,30715949,639858141,290650189,579913245,114097207,514818434,134785053,530116764,910284792,275976494,565235716,596508131,851472099,653522863,527387683,932755590,985556608,708541345,657562800,707132138,595340868,767657103,78662592,818214348,390755095,208867717,96935352,399856638,707161981,889890747,110645699,487381947,718732149,928692446,622793526,455496004,889621320,877353404,848919304,698370238,510459211,883768090,493385978,696749757,837817386,146533123,765938799,909393253,324266050,418984842,279360981,820755325,147282594,122890945,696327848,189243764,196660341,293018454,581153807,696407693,738220101,252208788,533359316,573281434,529420796,743547429,387275888,715894137,829370065,699308356,97539261,812336966,393843583,577478005,987207820,336152596,480184293,213867025,722947744,913237260,713003711,494620517,177831682,667326397,240644676,803362231,879327728,26149489,846271144,494923127,968830658,915857452,800897715,53375187,221582041,392719189,214162292,36027850,722665074,811874933,863884471,169366730,130798835,105743895,268667196,124432109,828867432,841490113,744513696,447456181,55785920,729560857,745182876,956946206,889851859,664076505,661306076,343346107,122439438,343279218,145719662,417475163,675989792,171941514,101015514,255662668,600662007,5727102,766122846,707703888,614808530,188632924,667690696,275472097,677769925,25865787,727563993,189122911,105946195,166734580,634905303,7185578,508925214,78705697,104206574,639190422,160220260,670395060,630561258,804243839,664127855,524345526,195346772,838184388,665263374,281660536,607649142,119883040,534592394,970270557,139414759,239195636,71667068,917569556,304437163,14846318,413963574,786255585,923715682,523161789,775115483,523098657,714055959,999883477,982060164,73349153,709558249,361777730,665082031,174290960,933448790,105772195,389800227,547291839,454456550,244882049,153929891,174861980,147668764,170799194,583901166,419608750,27964502,847950068,588289962,167659124,141330782,22518070,297059196,567406475,573232645,502402651,768633931,316341612,376941490,178863780,833928307,270358,248939612,629914528,26576033,572745211,900034001,789623917,907718206,89038532,467483943,507449275,835381266,797832154,277120410,818184174,676599255,470746498,299614916,571719575,49060347,716510159,445433584,67231424,175123424,39769356,122109231,881436041,953344081,478479100,619459332,45250846,114736262,725019006,572220764,882609282,344652745,608267834,928304896,344670195,901549984,498946434,16558350,709271496,44308775,668239563,555840109,450847513,71844375,395579589,689759789,676047217,137083489,298203548,473177716,565927971,346336034,189040068,861087541,198983032,468759023,108377296,431081216,719655981,423151341,231727901,262980096,178106524,637123528,781671154,389616579,401182128,362352294,938866013,604220913,838201775,957486683,383714210,984314107,300663508,15536143,63412692,63699041,142925881,61543199,855384895,198397247,213405116,402094122,12354992,930393941,302532580,216774542,197462082,675956137,399280507,614062852,895429729,715035705,286605323,169843440,552929217,919609550,437899391,348606268,690157260,913891373,969262667,734181774,745018534,696838928,189030736,911266039,942430716,386642118,8561404,10112679,312587840,918826318,159021049,197113675,115246982,73260527,220021067,74716582,69617335,472940308,870779009,81749958,729493673,408999966,760253093,46034401,606064687,614256688,858264087,196853310,388764790,117549934,562742654,290782968,309541182,253252840,900872104,197740578,61671115,857785460,742503909,235725846,884448654,839701822,753477917,785263238,632230251,937721779,54937967,510400315,41386665,386934183,415309143,571892229,448867409,4491152,320864019,430129716,760181010,982019067,382631874,120845778,121417940,354831508,884045815,866142759,262686078,886018361,451963607,295661988,706851736,177591748,929722953,555634077,76013561,393106918,81251232,375813888,347588367,555142907,263370312,501037317,650806932,977891953,737703580,160974929,469215061,537578443,617188572,742314594,348875935,720461813,81867883,2449010,151300355,77407015,397589601,466798190,512395417,213327627,40198724,748562619,132733407,407840794,959907181,55813381,191097884,87062701,264925609,871110232,353647625,313877057,111859967,775252822,683871583,290195315,170275446,16698049,471235433,927210873,491799879,808987628,936094639,477399751,658709865,658500770,439208399,667245832,34072368,69133805,143207608,708583016,3422228,682811174,647770428,482976753,695080589,55903290,554714800,865131973,808780021,387306015,429260048,176056463,541486653,877964632,384410065,942130857,789362846,460360134,36675644,665699175,809211933,411021480,730605608,769938688,770556041,54484608,894773034,769886144,680427611,389416380,183921182,934337841,15666823,112267805,832830078,76709800,771420400,903885861,310346949,910876927,490571204,840504795,216659599,413098728,928669323,234165265,425567551,38780078,89225905,469178307,712832543,912767235,48723055,697115878,903267161,442252862,295927945,881823741,26967040,908970341,13340076,306831553,809674824,748379576,996791931,562054070,809674984,396563627,403122348,759375129,322478982,803009093,32083234,204518441,367602687,780886568,87981559,30291555,742497702,924383375,214681227,167833807,929744316,914682018,18226231,385586543,240360133,316015324,542491437,585500144,523828232,91121102,316521003,451503802,364675363,973475981,680389821,754279850,585470709,236135609,181400807,524068156,976040123,471746406,132220918,738877828,214703173,743701651,38822817,453035209,333229048,736236938,133442952,802766796,609269918,590461508,157610747,909466656,410466624,995075404,777155839,455623597,532088155,683714977,12623342,707111588,42935596,857035158,17080077,95024019,488337612,600724628,58198249,825890136,194200122,893790661,84507240,619470591,234480859,80283546,498805884,447313078,798137446,906174338,911052820,506342630,770372996,273014587,176588648,103006782,363165592,575579970,506209702,329230678,462130474,371503897,131035050,928325753,695213794,792691009,916725922,10382407,550939042,830476677,118267064,730644682,633676828,835042723,757412316,693219243,630010704,141017349,404122002,380690731,915331504,551224267,974780889,137142107,135912627,508405228,722214161,675831083,652002998,752820392,471658798,807276909,101327817,62088248,987615341,742907102,362718234,292263583,778938792,563965032,714958613,931382304,527058923,702253564,205526236,125744076,49755262,658528329,547887443,81859812,866799713,921198790,23947238,901787077,543306260,40823354,863805863,788664299,604782587,333817036,28616666,509925690,506815231,123443415,37251481,960878468,200364814,70048980,285146882,73124248,638590052,807219905,83723814,130310269,277328299,810185881,393274918,964365007,816567318,271904227,49142373,302142563,104209764,254331243,845722149,650877328,13553878,166760964,285362613,758452940,3117635,296957426,211463154,123277140,183129781,311141694,28749191,796811140,296807288,983061082,361403734,28803622,711632957,871656734,594267082,47888624,143693099,71274243,196284231,207167203,581167612,721406906,786176758,953375362,797197445,139963060,657534533,25027247,519124095,840090551,489890210,132456872,409589412,77137427,954569957,754424209,657207353,968563928,520872214,948934104,167418237,594731689,266603885,953586131,44624734,329090113,40116744,518208406,127985988,429369669,663951541,501498353,602482974,545948413,704837307,473800475,88198827,386947537,639749821,617599596,207944021,752245856,552850481,389272176,262273270,35900177,78853679,882329910,737193413,969511326,263921224,170280713,105220518,62204545,440230304,869555413,991608456,490219272,13529543,905246266,345332245,498227521,464184372,531629231,560513897,339286068,811862091,2554046,562135338,821041191,302360093,819774249,838207438,52664724,165732282,969151993,21567503,146243734,990123748,952030611,25308927,751331139,211587391,709339683,190327684,27213183,543907026,400479281,641526069,760733743,327362941,135845773,384790050,93109233,164278946,519759027,419469371,980388943,547920148,484049100,745168864,75951591,351577128,229277399,672560853,169317141,297356512,476450615,886450289,121442915,981607755,912162031,968982731,117243294,704011468,833331353,704682715,230077800,447020000,960321372,427186930,692900589,923865289,890122991,719003313,191178500,294492166,373006205,610521842,363733128,524222934,282426675,806266855,305219415,631758869,605139093,883162437,51594242,146989062,631949562,515149050,603502293,290752248,940713789,595021087,481043708,773153048,752708317,90002989,290222144,828211871,915399690,342721300,358726424,921389617,83692980,819104653,321725701,673012139,518651424,338359995,279738709,726778880,85652024,739523878,689952357,410548877,230017928,440751296,35933369,282206554,47155433,119896688,763974330,311838897,216243199,650093447,516746371,532388929,443856301,327639807,494165341,117623238,1784404,511664126,807421672,179854489,97883872,747720258,653052540,65119963,402041818,926260242,339908769,333158141,691986636,240937678,432879551,524996199,748294717,718050365,207366993,998575917,273714292,199112348,494689388,128325157,125805620,291146692,127683156,73113048,450351652,327843136,409527128,237351661,292233948,73841925,608664087,352699548,559416094,215863870,717161885,307069162,508201993,808432232,191488655,419321379,286065977,842473453,884618478,546450143,192973760,609677350,202741613,214720480,34580400,17693041,14196801,27928168,30263108,264388973,234782146,849046861,694737090,577682891,342780950,568285396,105850941,358779180,15081131,651455527,934388461,511932094,223213976,696341901,779937604,964107718,994299811,626666170,911492880,105475040,44988505,538369,251411773,22830093,453283885,10737864,668611056,357072019,240113615,260733170,68726888,332561686,257302039,590788062,203552884,171871717,282442404,70624158,214745293,451612491,836906317,659560547,71011262,71329858,338026958,917815369,140848960,514470304,726215084,140329465,18747358,554233444,10411200,34862993,472266298,280111174,544347194,562953338,891286731,950628670,730701588,590095970,456464522,780612748,573834691,883571538,337420161,663817847,401986942,3959310,765108691,49691401,939721571,98682337,135135984,340268209,931815280,568657036,909553480,869717592,215362193,82432556,109994955,494767196,495581988,304889250,170621586,539305735,375992736,413024478,828233220,919707264,80178589,527772163,159281431,71365233,578069514,398302770,568127691,809808075,840445486,12831814,915933198,926477090,44010880,394959101,205657630,186599387,642751267,670778637,280383887,832867291,702148691,590409372,635866064,915288754,625703595,765880384,134633770,489492099,676834814,341840739,798544648,514588833,570848340,84094162,326341008,140087018,800434414,63631290,797213402,615173781,239460609,23079563,144137459,742676753,786209885,155635782,928484606,424593940,855169177,867792115,66124959,113140414,820889081,40814617,362458035,568571353,469479299,683659215,222915055,114827595,905547668,323049787,659110493,949404625,840035165,913522777,216720636,84442518,531687937,399701992,462531728,27434003,960261472,774952699,141693038,23008790,747634226,354596363,226931094,892918364,663218512,273403254,266463976,956640637,49120970,942422342,600405369,780358108,796088927,43475279,337552751,390269261,840411689,799310704,504790143,93022682,64121358,798356759,297200635,797088101,656723521,633755514,803013256,456555844,167977955,57472458,719444103,9601442,310162169,952763114,451584966,374293642,566617609,992642243,330703136,439928316,89010391,349023225,48481196,365632468,234175609,244914090,692442978,468226731,899563887,478352507,284789359,861191197,793645777,783642522,162660203,83349190,690498486,206425814,212565993,124317968,496456801,768464390,407328250,581009692,421750535,665206645,121194811,899669699,109251144,878437601,98170529,123113516,142111351,256639371,983723799,762270118,733918871,621375107,238447988,390849014,994385772,716907628,328739057,789390915,932115817,177331454,849928989,488276857,934120412,656304914,833657184,885957038,421307946,669064263,738692549,602707736,28556053,52729490,106770797,347939934,21478535,5463627,278360746,189674856,792551222,360304391,879498644,396745985,966024538,998038846,44118005,609451820,707226197,821685412,746869274,382949981,24819186,317210162,89759458,492163921,839495650,228807338,214696567,632674609,170617166,465018795,670874710,895082798,326617329,282225349,363042998,662626259,56825318,18853867,989825138,228259635,953891903,95788866,103714190,515153613,325687565,42572399,988212698,45267966,402472102,568108842,493012932,76437998,291190058,709051871,648038694,696756121,944777134,375205220,62144948,586067172,316449593,398799579,121040544,454387877,238178585,950938665,852841681,404272489,762442093,329335402,74743095,722242748,156292792,233433441,656198396,397914227,273315009,930813908,918467008,355527398,842450810,504057577,665687802,972570991,148103351,239473384,444810410,537985663,18884171,351660819,488388389,661155089,953191245,57248095,96058809,700183966,574509580,696034148,902500227,644316428,413657222,725343393,374720710,508919966,783481139,745263416,163098339,4650001,636134093,125084863,500759184,64171473,286134495,639550410,561066213,32126492,724534225,807419663,146089226,540791439,723899747,881166152,505265530,640401050,825387164,685189375,963488989,125718321,409869555,343049887,793342261,770394982,849554711,994742521,270337130,273725436,593430978,880390578,562116616,713401959,745523712,597430986,182026908,309529428,848681940,3960784,789882209,953864556,429146415,59205210,777035909,794465156,670043493,809720561,369597688,305635092,821086198,265814164,772668588,407345107,71346713,828330365,759444701,137270517,708142341,393953513,484609290,570347606,258192412,522901544,696145062,412126756,772605095,133196834,961228864,1524514,438660190,43431757,606078497,846361358,11149825,2504995,299261672,77198608,189860446,616795058,570975737,432276963,134717918,549262466,215046187,66287008,689214310,891094830,79853632,70197296,275905178,721132773,828295790,971321254,618610062,10976907,598260885,452258941,171394654,647357729,782174179,47001744,270286468,569732849,663389748,3883059,276536712,597906476,938157819,793527659,945916943,204622260,965004973,42079067,493737784,167102258,372018508,190167539,483139815,288179976,658211225,660771456,740900933,4774203,221608391,835583639,258652940,466039630,648179379,559260200,97742128,512912497,313956599,94217292,607557383,725173174,15838693,705919601,691067979,980938655,196995144,270580112,417061685,962094565,518975692,138859908,651233114,343776817,125952889,264308059,229365617,7757132,170593635,276554700,900230792,156628029,425310759,372349297,100265899,187280176,554375177,245034084,561698489,921370989,125117253,45137914,9666716,407222287,947573198,124012634,221202048,241606357,579444200,27813902,902773024,934248313,658453374,435602405,190846790,14409490,662129966,951058386,717508881,51085062,386156812,441958050,990495024,749615402,646988112,12472201,752841957,41123175,814951538,32777178,923195592,371943747,726637990,12681088,116122119,187776066,91842397,140381342,97665519,786871525,745422449,42987392,373065461,606437434,229543154,844137844,940750604,66287145,691516869,935498297,192097992,716008681,252522357,715567627,636683789,980912369,755206342,124636224,757439521,795948609,832634300,81236248,330999222,121278424,157469743,687096075,797141184,194384433,696538344,786587811,272008545,802414999,784563611,611017497,104272125,154948923,476368697,302633041,905222569,94540413,388779667,220104026,321524848,592243062,35417767,206418328,879727369,945959766,924348421,627209349,657789167,9693591,504405343,422645092,313135546,534186472,235885375,270685263,36850895,670680507,778596624,255598397,667942957,13234008,671630324,916806836,577325427,777334443,516958800,600694416,550425165,783680526,594372009,309407997,162296192,200845832,564583918,379157380,707083589,572356403,14810308,601722082,642538451,595968841,377559657,623956892,680835543,10099985,892218360,783153166,320967077,807720453,113520884,772997430,284720238,699474550,743278172,363862205,546136426,362783082,382163919,698377034,624679583,735179876,694754741,667321826,163819879,246670899,154360783,974412883,247032559,790329462,880911139,721250755,663735617,19947332,247359992,998528599,478440666,973499094,68850012,254423107,242196750,912244763,4954386,102460425,563456659,760668190,373097317,787336157,112041532,324827061,257962131,593031002,600444887,651558556,725534639,648530007,364319124,428618049,916376083,573089275,447288130,378836410,607508093,251261213,787335467,745939633,145364292,887222514,569831677,176908297,180380231,196611431,618471731,626510015,434479442,644560472,13316014,49905166,675976141,942509157,912021427,753334950,529900516,423288303,740669657,265202118,223429701,27064682,757060857,874193702,637920387,82557063,848079035,608354684,240509199,466862517,446055659,139532783,661298513,9213344,815807180,381166743,325730600,618377997,405627746,65410022,420569646,938336623,296697771,142408863,168977683,827515425,740628581,722321433,124246518,650101720,655790682,987915970,707632833,213565723,746910902,82591777,284033586,43816268,419082511,566378795,480884061,30428144,890665378,97483387,20746295,229102760,91908249,661198750,687001672,210509963,135381532,965204729,897389443,646715620,934687873,456203706,899066952,923321972,555550182,20495365,306689544,570413208,567786648,520349315,750505199,214915693,20557997,920872059,975030262,33386824,77592610,576422541,634914970,169658847,745441960,16403700,612057662,199434682,469705985,198603523,739823623,285315631,116310113,52423930,620696240,713632201,113212290,881425366,773929356,122236413,433026759,851637408,491409001,36457092,139979358,138476441,294249117,937554025,28475067,839081435,709546774,375938827,506975915,676575756,75798805,285691542,637290280,436788371,796024529,754116671,137888550,943961893,351330193,374008148,63287245,457300028,790576561,738936738,411824965,202392474,143697317,787661100,130907592,933622794,528268707,914761851,567000884,198915649,336252942,373720937,531099262,243259502,446564804,106798210,247143734,304342618,573312150,45664608,271878186,758954933,495674329,709380790,881213033,145710850,830898370,970231796,635442279,235185200,33240851,333234537,35511983,996928062,495502718,765576938,477067789,167370403,938269298,312650143,611447770,893419495,495792641,550366927,804874460,525556767,432342858,449236605,560095961,111991726,842242688,153634770,864235696,777438011,903121107,135006931,111736663,495861072,700486744,368332132,155766801,190058714,8623109,840167192,777995497,535370074,8352788,798870861,554799783,145957607,683175975,691034963,426038743,515653081,130311653,862115678,299012415,182903503,803054642,797625277,95105965,511098965,898695333,119972380,681624705,388643837,84692863,798774127,869453670,74592433,692055230,393797036,795162576,506679551,990553302,936115170,822464268,952200184,373333622,463946998,44073129,2704535,943920314,799995587,923695420,389639777,998092336,943124435,515580538,265586521,241639981,144562768,655415597,919291894,187000871,155063336,44802919,821856692,330604940,937031791,195727886,446611376,742050167,199618640,414004444,118652606,122503204,60489311,677063524,683780993,122154254,845159024,130875110,387697820,364854320,833722633,838474734,457162724,984896949,152049345,780780063,445435671,102307633,142965162,928760388,410189651,634957487,884242066,869566022,169913919,382964701,479239648,517087686,619397771,365100188,671058815,694368239,820855075,676297197,43530055,903667914,942279014,338975320,677066327,85396083,171364294,344118631,428369846,246816978,107521820,85481613,815888426,953689687,992111848,6288959,471835210,624749746,914409417,879072165,671364373,741935673,422801629,796569258,526463808,644595416,807641244,575233799,130564646,257675244,66288487,714071863,60160583,240077900,660471165,195898812,378902433,924178076,59188228,77576591,893148364,26839796,917864080,166556159,931150850,931978839,815604433,475586630,250356276,817466259,702525154,268150650,32778075,145292893,41724590,978493786,908271154,999522402,355923580,58630743,297860784,154794109,814872024,843869027,717710579,939034632,497738221,37475282,427334581,819965877,556910518,54320978,878084427,250320983,17275386,230098735,444369476,717142513,128967605,186010921,696842862,255149474,919850106,978935367,94493502,954851559,837836660,470471241,175359233,915065347,372890862,612414266,750427169,257970552,89067818,752672323,130546762,518625347,693062434,349026910,317436413,597392721,686390700,679321794,338324306,472892264,63303501,937536042,80739855,578056659,182248785,743648873,151782971,953304608,608034967,516497943,445005405,313277912,779448187,328410787,360102897,433451211,542951231,516301892,297459895,66525049,395002103,721370822,179712970,73879108,233598768,287365638,856534341,189783346,468459005,508425711,66471942,295411332,789043638,744903641,913315924,680604490,421759508,461510787,48347792,270995087,949095569,733676845,55632841,865772242,832362869,607241303,855267555,19242445,285226065,403952929,834048114,13866607,566303482,215098470,945007389,97617358,563386754,378753433,360397301,86531945,81927752,8667293,228262611,796888113,235987430,985923648,227910262,169925764,936548685,311594863,409731055,162764034,828436807,46426679,756630092,431282357,598244052,962325288,101769859,842015779,634942501,632372364,385752745,93254922,819895391,372252316,824811301,596594522,362983411,808631197,33504694,472676544,732664755,225305387,693969648,564187079,151935248,10635431,301524694,457103716,993149493,620624367,298641268,387486815,113460579,552429873,910048108,592995800,801783451,114576032,534022112,768454149,235207763,412457192,90813428,587895026,972420713,124369721,573290894,333909947,649709618,862688378,186963080,519909999,16393550,648488034,658878913,352206859,868726659,740620438,792483454,575832684,458606606,275396537,555316652,36018880,571906284,39594863,336889027,119961875,298045748,116000410,289696550,377466679,208759293,422136831,715232576,93427504,425513771,489404687,562206399,74901193,438933609,550839018,149373309,108821020,446299543,589018808,886977033,384494735,424717322,135871873,261926259,642310,643843091,693711782,525200511,887199207,178110928,711141556,409636137,714960855,176085020,21444152,427588546,409760,237363957,144387751,68409947,862228084,247757832,95090891,464771669,19416744,712680642,507250775,646675413,258928824,14876146,708261348,39599093,615004059,534426602,331288060,326306327,704687098,96721459,745419212,988583133,828718070,833151695,980138003,625338862,285285216,605125208,649797242,187901299,49149781,865122328,646676506,70277453,830125299,862129381,529318736,28225009,931323923,545849456,41667008,217734534,152178450,10185573,537717298,596419488,361649198,859349776,264159157,667231928,800387840,280862072,279787998,555179103,871716484,805506754,415103790,622513074,829885112,120273766,97546844,939784447,214977044,51684254,866842168,280234906,269405849,801554845,360340862,137961672,232461122,701323561,754834991,118769486,584916648,661450617,270657978,578271900,652320625,441705018,678248425,478080699,365984666,504095032,295193987,431093517,571893819,830095608,8607675,787789376,139358677,89604040,589063733,494547861,104185937,646849432,829161088,481999211,445401371,525827533,688139726,364935787,55454855,814823765,239801436,663413080,41518914,669180901,551543768,256688324,658993223,125931382,50323557,265422737,429384518,913518684,940908163,566897611,610689985,835207460,24158359,155130430,231989552,365581159,164803824,396943916,352188630,562351856,165091923,944056515,148663569,858101300,401354426,317702555,982495443,799148718,929775088,638888444,172821886,12525836,654285402,103973705,581854924,388157808,860443117,105567099,237719049,817451701,103343779,732106877,231963007,919439344,872214443,377747657,636189245,904540880,581833047,374976138,152425999,23257969,640618385,183169215,180930354,852594104,538213144,340168622,405540218,594326926,906203085,601225071,879209162,33410727,40856822,278818892,299800090,743476768,554181530,285376249,780611770,557397445,648168479,376063900,461594179,302433489,698835752,744418421,200674325,184054485,820256293,142964936,363435515,610187115,973405958,296491838,769238804,538002466,94270770,151857060,844013362,996065277,27060752,129482856,610404959,339742772,690730209,953510628,923129460,260463223,33716375,528410395,148628420,267352057,643211053,808467351,781733688,293141870,507922872,412212879,279612131,746866081,536306652,717033705,654736618,245110076,484390964,841404749,309800948,324172708,997669495,278886689,439264269,458769275,68912195,506554210,824409340,76265514,539735117,357186491,16560872,106163819,322352432,469061821,109557410,937904391,829130557,175886116,180453340,425354394,751217673,659069398,258720960,816273192,770979486,728873782,934931586,257320803,906154610,579484324,554694323,520975034,736567619,396231225,904387806,156601976,341943057,163698205,142158206,44131356,272315586,520402145,845440431,211010196,952862975,982465146,289947039,499489430,405273887,767574172,477819853,69891816,584153759,369972007,154363584,21489290,186222912,757786883,191610802,324762361,170549231,677740319,321256323,374110681,639075729,380058656,822443792,253554983,891043633,366869300,339753141,865001992,771673001,647362152,856511540,599545517,361211073,731212420,585714806,836685172,444765248,926431576,72035660,108517868,439169751,17688896,737510364,854055842,335839946,874948106,432286533,295560908,155483823,521993340,671367385,792558357,834727405,545808562,501845197,136922788,744785488,75002100,573351067,345237558,699801690,946552858,948006008,955799363,942214381,252688489,360264504,2096413,313148448,751030386,451799014,31336153,119187112,161505889,803125193,190397356,50706840,471830599,547252669,796126360,672611710,24070740,622980122,89626260,962515273,147364107,138374867,89083615,18172502,68520396,9534289,329005345,615420968,98965224,949155568,742080038,347155468,76365424,864417418,536672371,421221997,372003067,723629230,629554227,58942998,457984697,560390209,407945499,572200469,334489795,450775297,5593710,110160658,132253870,938197023,452429287,532411160,817492718,792716498,197635898,656819424,891092166,828058362,482857574,839522783,891853091,86528024,16027505,377294169,811372439,8402401,278211483,828495262,235901286,538101440,817264563,460104129,28966903,953908008,366465601,997234989,566078935,529082913,359715142,565925289,301259660,652149641,715460577,984978086,722740326,722130228,58147730,183838725,695966689,561695392,76341132,17668265,390765147,377811681,564756966,140091469,313715880,550441775,62844796,256489204,607350677,546032726,767380829,375787699,114451266,584563597,815668332,549537123,536239092,729036432,166601420,898873899,619142426,368484067,561854699,606330234,782337823,856904227,756984985,746496645,562625319,466217270,338807565,359596758,516707626,674180292,824446072,900641660,619635564,859698423,474396923,375282128,207254057,100460565,518569413,107484765,255676806,838279373,468697691,225054019,557173544,32548019,573708995,918482513,823141355,447099511,356200524,625282679,133996113,509809135,695358993,292588377,942784256,33621604,876056423,525396107,672592463,55091480,943009659,527002531,901956867,894978074,921026130,624039334,66438237,521909975,63230408,856545638,25146956,738094680,84720266,697809857,475048910,595809402,52373453,919812948,354420861,779257696,274312197,865188517,404609960,139349896,735000351,824961713,977085359,66180104,39962429,72119848,730487006,924078521,385967343,552519861,274992777,211773273,685974810,131909505,799926831,122618397,56075837,868755073,218174536,897819701,81105816,640817314,379085271,495147626,447018057,134686793,26144591,118455527,750658676,646919985,74483134,2550584,503949504,996788538,505027919,148861689,892936846,973845486,448209415,475982807,466452174,346376868,520832037,480700687,302966395,272473728,30811092,91442895,75423591,628942207,717162515,672162641,66502645,456931584,247610616,915798873,609339040,604711315,490453601,804413399,11934059,859750442,555701678,64699921,577825443,384147345,821563111,484334945,254398485,828374796,358712871,900625768,352538720,3863545,303069983,658972175,772177646,746017501,306608121,142399072,442893855,538700483,147962029,11758177,51185315,278130405,258795894,928205283,24979573,865350824,985020062,73725889,805930682,97610745,659263485,373257522,332417945,136414346,789335382,353277755,539922908,365906181,184997637,846447850,110315800,237736748,321940216,130882097,150623260,789394654,994957190,937816788,149765514,258159514,969984858,987144029,618522328,329410147,183498663,275511949,554583911,812764197,131864059,622073065,24588437,379473944,939628865,540572595,547777355,24589374,749727172,23517786,126438254,186408095,575190270,398972743,883924245,615894347,465111489,288320543,80258569,79017445,694282847,178650309,393604857,67198839,627467329,698691733,264353313,635444526,479971951,940002325,729368943,460146503,386641652,793707920,828079923,490728232,332190744,465330786,826561575,741657160,36800932,830952366,730258921,592642642,515729308,618480264,976945568,11680061,324246859,450946774,385618933,784738863,408994214,663579229,893522932,86774653,280196658,981076782,371011986,98916392,335457566,890738387,531567072,515807584,934064996,517906780,501008747,963609520,211020613,920920072,781984753,10802609,963801693,938883508,105280800,75364119,215353459,728618796,737327756,79930480,652771494,784030782,38673660,93637157,801668095,116249965,396021563,882587288,974999587,517832099,245845180,161403432 };
sol.medianSlidingWindow(nums, 5463);
cout << "done " << endl;
return 0;
}