{0,881884276,224432428,117569315,65973860,517470973,558995133,860051261,155788942,910520518,120304438,154582539,519742130,627424624,845041807,554328605,656331368,691227914,840211063,388741362,529978561,897343109,93875054,197837413,294171160,218059710,992370950,608415075,127363831,605748785,874956379,695700236,302540311,434730736,585400383,704261248,297528324,326818180,492252413,463421375,387370501,872587234,361055436,992982497,325135313,801394116,557360951,403960409,547993698,775785847,299703623,472678625,403957663,380758761,540946595,374446961,228705807,892207521,718954981,57611608,776424610,71562850,896393406,90704811,271738138,153293323,339320628,153347307,896068049,632403841,117739701,466237359,504300280,315016389,391019917,945735692,935020357,882658738,739835603,933165221,989769439,782121533,249519096,193556131,703222437,419413446,431786435,631744438,949953078,999174487,347817442,181159585,782823623,724333362,992209009,421432125,717981978,963213881,949213181,905975821,397787437,979828694,480573495,277991208,549719751,567216451,47229125,193523226,562775516,198426247,701258838,658499361,951483459,798815837,289824405,212292772,298288616,228285400,82003167,14644418,667403141,637219612,776881735,746273961,470673094,63221052,396553805,802421416,664109705,330618733,80898868,500911712,372936810,14763369,164434278,800155067,129543226,522371293,885734730,864146098,190734195,760467956,53928139,773945403,355892699,893464662,613233574,649265872,750616222,542952833,174676223,49232709,491571581,636833544,18734469,128738923,344556596,869386371,926461092,866124411,189177380,528948452,137544262,899481695,604975812,982588373,880849435,858716632,680329826,787961996,331778750,91643473,471903941,35501904,297918764,875624473,698628706,177359323,96043834,799943555,132305296,274017167,430246600,803909020,885071333,211359087,908310181,163092501,289723843,862932058,335517815,160745095,353121184,396002777,254876617,299997699,148894905,282450851,892767244,141750010,197002259,189488125,336988739,5912479,377980801,779389514,730269025,863910892,80416580,990383116,346918584,911285900,970687314,196919273,814269369,981721633,537167041,524124890,512141421,129452529,826629961,844552662,858326199,316201725,216345457,217177043,170644387,330742436,110465947,479850415,454012664,334245732,482115882,61454438,582477184,856049964,2773859,622296549,54916186,135709872,344915784,568517529,323549891,255018380,244220213,769833837,525761676,966219748,267020701,139057568,863807780,28693094,330606295,8320903,214044553,393795758,665964664,882496045,8450322,993754156,955916665,247561367,308068598,842596232,397110730,314934564,680815816,628852384,952681019,535841432,216765678,780975103,376023889,261389176,801658162,265596593,91699598,764918198,511700832,106145258,911267454,739393971,814157941,671802787,325919370,233034201,715878648,625378598,730009499,378907903,198286265,462512669,947151033,523579938,536898412,262628273,142820273,539768489,602447994,235455284,538198972,214191280,445514935,493630627,531830910,905192318,896019991,740494128,942747711,669511348,641305799,80632706,456548728,267448502,552369315,8751051,206840691,17660702,359904237,558390866,110359136,182907463,351902724,706703575,509166404,805761316,868781538,215982087,20607414,561336803,665695075,332434198,244445636,296096139,146919848,842092888,918082161,917457352,830767799,267667178,480488375,429939239,980195946,652990300,168766941,213746668,860340545,70455831,471021753,924987880,953037667,613453099,3429459,716134815,939302878,666207894,611865600,265886799,641182721,98208049,388621721,393532945,574587123,127861156,994167927,838670046,695283917,79683927,295133756,485611497,635797092,794413528,773300455,96883968,490174758,448813356,464292047,300836489,809512110,845031071,582250339,45343241,600429650,752724813,907896194,128127479,743059668,670965886,472836596,353477407,221922189,823162423,325363437,103238070,895577196,377600299,724360516,317927778,696348496,480835757,822088932,173129883,100903109,509872002,30509651,793096382,912265097,635124790,329022335,792929990,593861074,724921103,364763007,323091544,105177566,446841838,69674243,301701567,775945591,118967946,357062752,879371631,881226630,637838809,956684052,243147555,625392356,75278025,889180150,838429372,229023163,163264861,829182493,889667661,102035773,411031724,273947779,21430378,208075884,680853499,49495696,27721949,840654300,411256694,891010280,970033134,34676307,825939,317514406,968573110,872439661,391075505,795407218,652489241,875070467,679206205,228223288,272752045,283364033,698940617,641498780,455485924,331410012,614815198,903969475,948700634,173366382,981988015,9972884,265040543,584278645,898235586,473365059,625076457,156934123,540091039,167257252,257419317,237528245,566697660,225807662,156540145,593965224,527434258,338543393,259063313,444248903,516869051,313817985,305869681,493528919,734963854,197766490,798226158,896336218,354472923,371412817,489817232,616040351,596732314,486982966,402379357,314004690,537330486,30977444,947304195,124325062,976014973,450850674,901262181,955255717,440111488,53222380,450538058,363670182,493526521,725077347,399102326,630022204,276349041,533417615,572250039,922645861,348873742,866756797,651127832,726333652,319491323,421305744,505167105,107977989,457483343,212077938,967327512,33490544,745899187,964625899,685294202,408869465,782873514,512264754,753534275,890050157,466432933,670353054,440383757,502057106,258292363,868869323,188008608,726741755,48808113,540603499,739327008,192533803,457969670,441344936,165742244,180260478,566022731,351764771,977290752,421266407,559104821,599861657,750170433,247611860,871398198,259195465,996025972,831435669,584275727,742548687,845495362,257654985,224329231,300658145,992710638,924189496,877491804,618429094,518718248,766836529,181140271,164306906,932182776,6121988,591810437,719557720,911253527,805303356,738655543,685492181,82460898,784368931,162571769,911673042,438361881,6420342,114024001,753275805,880133902,83592767,293534685,671472330,494237566,690558980,134465071,738646042,749876495,833852913,242199917,174401287,857380225,29074626,716972112,918370289,83430985,889243891,699046680,636316098,446175190,790878300,548150047,304957524,456286197,274092515,566099045,913137157,771321639,436076267,962257384,42178612,988077852,596232835,298408887,560446696,3912078,656192864,826721597,627399847,576975132,656592501,785536396,138539751,427295347,165638733,902893714,595128242,904728539,160788667,817154218,979079552,323295238,936483886,539909358,273836774,71225520,723246366,775865813,451764301,400794681,925756070,766331866,90720390,721793982,208089255,729347670,194035908,206850102,798607097,643655693,748442012,393014716,673681579,814199119,393662717,742796284,464585146,137521346,324835914,246407282,590352640,702247251,279262443,83647804,363769511,946611338,824426917,838569581,383495983,746340889,226957248,927388262,785444453,658864507,803920002,415735258,815789669,921909856,812133339,576655831,660536671,635831015,501334000,658815022,975331884,309816261,731626913,369296187,961188455,53713173,621878087,432284479,955949273,42021113,259734068,824646990,281522273,462404170,902214464,798284513,723028008,900842497,324378424,31243697,410523198,616966886,718110650,228773372,911980928,228660174,933496938,561473393,147112856,371964715,160335324,932011166,925054467,14948071,489255251,741546464,47667348,950135025,471242403,478020176,603963882,693694411,102330997,778460218,602068215,292503186,793426520,454805497,379122601,258055056,369867007,699008212,944251486,60398046,787242034,799527110,337398837,705918891,783630643,137602889,361516628,89545275,202557990,373566327,225298631,554742575,366543172,710718080,868963785,610251883,502926489,644091186,163493553,813415264,994924108,434774307,318433738,242574397,702991705,57526831,586672671,440416879,87596049,572671848,729512740,771374890,542698661,302683255,606049149,569537387,182146137,868529356,789129142,243079097,731329651,563329076,808571737,653366773,395406418,833598471,29318056,317139270,409025531,562631959,627560387,531514690,103524186,143258325,207509362,191628679,137929026,861259567,57924370,188797797,336997649,476012756,152663007,741338990,262294828,420458654,866909380,979671928,710467521,58011431,705705059,873168245,968561226,525481154,921013575,314593293,185794685,461664578,277226950,222473208,344310275,164741562,205122217,914862108,969034915,191542875,302316228,465063693,399140014,464419894,688420298,528631763,112402264,490921942,151491026,200484827,111571174,250475091,722810866,935509511,668624876,939723686,144520355,504580877,93769428,806874801,794170657,679630385,74738395,762160779,65866925,777576606,22111448,415308584,135029452,799083566,953631184,972533318,658976380,49939295,892850702,109774344,373162740,116476013,274593180,711768279,303926936,914630948,212925783,529848655,192901914,985052818,578155565,605777218,699637142,228885201,828823391,57521826,387205131,410487464,574352165,682685261,615748262,379733355,291377225,47444855,535136576,370476359,209382736,892709245,915667077,307405918,533807867,487154669,694159220,997868324,624218138,363386280,404338312,218959588,618522582,612900277,985368038,123144193,545433933,569624187,48299749,142786049,777421606,839188154,963975440,183825221,805714418,367873472,924257051,449294689,806657966,638182780,55800762,962983911,183930350,949783426,880068416,564374056,224984765,265676925,275956497,396679834,368641496,754190920,252080293,210397673,209873051,951400423,669724648,479962412,410045432,477146710,593244473,178494482,130920516,668511900,256615293,229349869,271882058,659238085,577408535,563035954,247225826,640851700,807040045,573836850,751242666,40189818,846681441,152406455,707949528,322288153,241406619,671719842,271537091,130872560,175988967,538229443,631514013,138810550,263473971,761853121,544104102,241138305,737424861,458829333,649395755,288171817,662356488,762767804,844443702,567843845,524979882,827600166,650000007};