const js:array[0..5000]of longint=(1,48282571,85018218,608209706,100113432,169466058,704909939,727978586,815498688,340143996,164112089,907909364,931729941,306074251,898261456,129542707,971144241,236989405,754874400,280190822,483156199,542154235,871518173,62285128,372909378,307058638,998079747,376672519,913088303,675965676,688647461,41434123,750147110,466902215,819785944,999742733,138631388,460737148,139086503,797822079,228824085,329122419,572393076,143168899,771324102,954757381,190231791,58747640,978539490,305803987,95569611,996014970,527091913,109549012,162001842,133665506,58320353,637043892,424500564,632686688,309445193,214543261,213261601,832962386,817480494,756704926,69104544,428399312,936412106,835312860,26823131,207282278,305850593,668960545,738933305,396571283,822202086,719999837,598565094,9379872,819041090,929426699,2241723,92819711,477925950,668967079,443050596,701647868,117000509,814473779,61736181,573227332,169579974,118746174,460159882,10412767,807527919,176746763,312953980,433545709,865674075,211798050,651698240,96760674,556448436,569684351,786893972,243307017,54599279,506089135,139246482,534834372,207345977,641728687,967394652,884651254,152402741,130397096,32220687,816100565,289391112,733522350,936368740,472375329,265186708,781513186,506969688,830410175,364371943,928822918,600576274,805403162,165878959,528683244,134293992,578804200,674974647,616820052,399156704,542388361,199662135,939887615,515652878,755902245,48867657,365668266,367434024,628201081,807663513,415324433,986433875,995159020,259394544,295631361,432652737,407465965,297535374,279326810,218437145,399941841,968609657,517008131,657468327,84399348,862906218,707916071,791888781,439356928,113037504,797740359,90174576,576809857,568669945,591258991,279786258,601889329,638181539,244700748,658768517,832605925,875522180,627864323,431037411,463205669,107726967,712412963,136427322,116578178,597385300,655899199,310873995,647935500,693858641,170400646,136304532,344637513,569586759,875695511,966169382,718825342,616964754,950756496,827748627,481203729,928594957,937653059,614250662,419226342,652443066,90139822,726417621,874970796,538174881,628047345,987244016,57235327,916148979,371877313,481614924,50836654,613059849,211409364,240717753,901178399,276109642,10432206,605079516,570686298,427088708,687749674,180435040,982797996,969255897,754405774,742308070,162324891,49188669,243630008,491651778,561387885,741665090,870082597,932152586,549075673,470433326,773800395,322706792,374609057,988566995,105165925,390832290,531147514,769221867,248302008,167595951,271594025,487837166,995884721,321717561,434888572,20689194,292555136,314744379,98672728,43458026,943001446,182688361,626960167,639655560,562152683,943801301,789540103,147036896,615191984,212855869,994482434,562616956,270056834,712478107,588940377,81013035,553493126,644958445,882799312,119195245,689013336,929946684,866736596,615834315,515756999,236377561,51007455,650960372,121897393,488147141,498517813,481423615,765875630,938255541,92205661,164121892,471845330,487698674,137419238,368517997,796689169,564646606,963312343,309300907,783100868,339732605,240952681,253872283,77007986,942192030,902431724,109790650,276173721,71106818,41565739,264686444,527843517,102039972,925991005,532562501,247432452,866838344,753959940,131471414,109987391,885674343,766075224,559222371,73801188,400902978,222690803,40553872,900156769,679825413,636492574,460659340,335977444,580049492,583575412,637397977,776362520,456794090,481003012,709123473,693173994,456973011,223936121,588370062,492914038,934938271,968739694,569356366,70636675,217230886,251135328,41281430,536056295,234647112,240235811,32446216,418042748,779012511,932378892,509799863,734527888,599336038,618072433,924695537,759174277,423135189,702077613,714767144,296905764,606587928,981246566,179234278,833557087,875898827,687249390,62436887,328327195,482234558,166395229,437001029,12682734,580910126,869366609,890816013,887047925,298612697,406955880,939818429,394356716,706736983,533344188,193238332,885944924,869069330,1551055,241285992,518001116,9367868,429609907,232960552,871285323,712716710,563889589,978810890,265859727,235941793,318653980,51666617,356144550,336618926,914525198,740453935,112955355,905231915,369832201,488064177,820207382,975992497,812385532,828411253,910862618,734382178,491901128,736600012,460875457,359423053,15166631,866186305,597449850,106647565,454195764,812110934,223708246,266024367,77244150,523813865,454164263,832455292,255838084,170960622,921167494,496332543,890986905,804354873,64488468,183966706,769493456,315880727,91421716,887866920,755483214,1260415,676723634,908457511,52428744,134172210,95854044,641181705,857905589,812952563,222611214,14804494,589457690,633028524,329260344,254845189,344481535,761399715,466055676,697904602,3516171,192426671,640027923,755538657,544001940,683821071,712521033,334769644,374093474,968979008,787317645,866960421,868938731,3808942,884841460,567291274,191845083,368427091,84455280,716743858,450303368,670492106,683759123,464398584,440142720,787909565,203315269,111030585,339783919,108991476,541952932,959674815,68487426,326695824,645967941,767487775,310792483,186077091,805454778,408754104,876815387,428859242,13410818,96435869,70041441,586589530,455503567,740457166,381695306,198806676,936176462,296295273,899863099,153923089,326890868,788937970,324478844,815949851,205970090,264768811,736798084,557721478,412329172,4613770,882037129,282926133,964752942,319008197,539814817,326288066,687735195,294479223,491889511,836420752,125889639,349116222,642619299,448745169,948014287,649547796,31250428,522335325,8998865,997100496,491896657,307666191,400265961,985605053,909175130,882809666,987353128,534335272,788476699,543419219,650442446,851749115,558903967,133795542,320195938,486846292,766728624,811311468,68844024,951894658,669134235,634518285,556122072,409663442,922136934,469181596,632512175,628577181,500778048,640161648,785644583,846117388,539634193,430765692,434924431,35058378,725119031,666561984,916259498,700629222,342577060,457447194,279057163,633995541,926015993,288489736,677677303,442639950,111313198,963310151,33411949,14060804,426718195,63097456,344690472,299398156,446239781,573129887,626532710,158994980,705544615,550989273,306234219,733158979,672035282,461090791,596460950,535594242,880661839,247169066,424775306,849386605,568062224,394127317,395640256,936674847,344509461,910080579,165483659,899287914,18492363,288363591,682383027,477256956,232299946,998547226,772096186,480153738,855361887,37858629,627038072,712376923,888355856,647422056,552603283,876027605,491846111,270110282,363130815,635737203,148017848,10628285,120682620,458948154,849486151,452794103,427851209,719450896,546097548,648686202,915035791,508412820,544709260,382320910,656285170,503691047,729699454,517878946,869054975,827014861,413215356,15899881,613845693,235001078,612699672,23937851,691060563,986248845,443159996,487278611,893911228,884467088,882940415,999582982,793399725,624244170,352534851,485121643,39028309,169007218,964239210,546528674,142199312,930805764,829851852,460920612,681884166,334656408,714611383,858794172,525920855,549692526,308415013,386093634,906737045,964750741,532682221,429414794,997098870,80200252,805487256,424269271,557855866,531245581,798018572,403484763,43371915,621835798,856681317,182456430,261631167,500477023,978372471,376489065,678685168,190602713,746631813,997082586,781149116,893397068,313437023,71879692,610637287,275830804,293061003,528446850,364552041,327484591,543758079,281890806,552110821,870367747,10719905,752407113,169219373,475461970,775489245,121614261,736099678,785628751,329211538,624999353,785680489,304497334,189960149,927605448,691496070,537035413,405122339,150200230,218629,705530339,242382263,951628293,988414282,306867360,140169854,665347884,135423546,74483855,88582424,941671321,681327030,364822623,12788649,89821471,755254635,351846814,297173017,670877108,169850124,735485963,613812878,674486205,422707130,771047016,665247390,154956805,4097708,866079414,257804884,167933867,139067329,446562337,479445371,745844619,195696002,230901560,496117579,931358729,379176295,758495825,158093679,712938411,122503788,853017941,652834192,867807987,515143556,370022528,777221383,992100465,302010105,206692292,850038879,369203656,861834784,641633876,77516287,361055440,309007001,656810219,536782890,427023200,703082910,100799472,138251465,526161981,854937102,519993591,859826031,857473634,145930913,221098568,641151881,783996845,195826216,727312055,837510025,883803952,658498041,884555009,587685092,201634891,142101344,365449743,605430454,930970640,112080263,509410062,164295560,490144805,620803478,820536329,278465952,825754907,363263067,991902187,823253841,416286040,307645795,222226907,903582326,759471380,793733723,569493152,20873181,438285734,497513629,426109249,467268896,722492904,58474867,107212797,117359107,697742908,898790424,34891822,150388973,577450721,709363018,472735892,309245981,973388837,835670800,961183535,438555122,787084865,690309853,967196744,768140952,944158584,516779478,970947613,336982183,921235469,182198503,346059186,277053641,562817030,674222522,29459277,26429091,738447017,795313409,729032653,553200652,584530199,973132855,740724816,220193968,648800376,967684296,890451843,411127145,615189046,557376843,184208464,426509243,737238222,143275994,492085842,453970031,480225780,951609625,457699820,391080577,994326117,733058957,56439962,222269287,720955844,138728942,937728481,731082005,928929549,570093956,727072843,386718788,192469842,166341312,804185595,526332649,482424308,831409262,552325157,427499278,757745721,835425311,855369831,3706649,87146431,334485790,872557428,461462208,579756911,886607412,861957051,149845399,512136680,120471307,558215387,13257470,469049893,748481936,752195903,572519593,358015373,936201402,944052422,839052219,951046313,894822383,13809673,744504302,92805030,515324851,276080987,410591942,178582489,419671982,612655745,847077098,600927558,807178909,541476675,262869355,655354990,596158986,376333993,790135084,399880535,815445114,195106074,84782725,710349280,192899302,340376022,972617405,190943995,10823756,740170124,729351268,227541296,170138313,918482230,563860013,782161802,309928741,12806875,757497299,178268423,734649068,770326628,147369859,933634961,565544024,656076180,96058143,519672424,520470351,207368903,43418716,91837745,418943118,752652751,165007170,776068379,870931886,393706865,691360789,673767461,313993065,82663532,725712143,493073937,753333826,130783553,334833620,953881386,211054431,843446330,631762599,85861549,394360929,78558378,392013377,909353351,88605845,609975225,650855484,21963018,62279245,29998316,390030954,853624314,785268747,843084214,930078724,277516346,941363236,104716276,605123384,753677651,755889475,127485450,35820768,600298696,340479995,654900987,718245038,26081410,588191864,776876108,472652880,881070051,552959798,414446777,833348330,648018624,657592074,676619110,523738298,538376389,584284056,157482456,855624101,280445219,203276538,807909037,582272972,815426220,64145612,662454632,5701130,981244790,303167447,666103987,211310381,608817650,814992705,984169790,219480079,4512468,88716782,572102777,400915884,668740121,648109523,694617738,388631480,944887858,419563338,347762074,744757797,92272940,778380809,292368887,35811433,426317381,939326768,406609420,335014160,108842088,712421032,189374814,63787656,767405957,943486727,519127916,793279533,263225838,795708957,896663432,832848944,863383997,255103548,581672668,571719221,633481956,775385508,532857017,654653319,794922857,946409249,793028160,595855855,470516558,284195181,144878682,906511529,765248036,32753906,100956752,434971325,694641015,974905830,550903787,230441073,964505711,115225513,685788882,222609433,463024073,385292346,41890053,238421760,873582853,998562166,97965461,476977489,817940866,781675883,985976788,599373101,727670793,338871599,38984578,196840419,465393721,122706197,448727489,304315853,175822409,818255570,662596026,747096226,196007431,980317155,182603742,688754178,556897770,412089924,184130442,194472445,345456849,380341705,639878187,96592120,348821478,834022239,530955855,851899367,703731709,185737110,935307660,166154530,905337111,657930689,464180234,981971367,443753845,979325814,296608244,454447022,648485718,861431582,204901283,373970691,386447540,81909233,948822378,571142387,819956869,708005961,602497871,982148105,515504647,153150575,240879666,216015116,544442175,131256298,913437394,63778350,872951102,379118158,730940661,723724509,945517031,991560405,270805396,78445999,179078009,29249610,826823852,54059229,727002509,678747076,512511824,323506160,744236090,149158715,300231113,651306547,477233614,910589884,13388187,362722375,844699215,824505449,64526395,66620460,738215818,208416459,191709936,279972198,239284324,93737016,470354733,807994114,568275410,918541833,339950537,833383893,467410763,750219079,400816048,943548457,333032754,266769965,140669881,658191424,639513,137755912,305317847,150761397,414331392,709491108,584262204,997535992,281934746,936908697,148461782,256234804,786679183,562670099,590787278,710177221,440039911,207339699,343244673,502751326,369707355,226713690,358186625,130082330,404094304,979648672,332893952,813883107,535783736,793639796,905799464,265221814,732966207,649976889,744490348,59749564,79845027,455930738,805090778,175770523,374112951,394831060,247778846,124422680,358416463,400874380,936429484,418626778,860419522,99946534,841080092,304751520,6430494,32910197,687344691,894169516,263353206,306691429,13866244,395605543,772634051,387431514,530244548,516043041,490547100,728963691,316696479,287173557,279599895,650164841,814475608,99106148,420158172,639195432,760492722,732830573,780077822,887121466,465360318,922767133,293732951,386314710,626940455,40371792,673547887,892108952,203447236,539957951,52466822,594406779,936422594,779409101,628661891,410025332,707614490,543380998,811900716,48182919,882454611,762700732,10060456,227264963,466698618,415529624,923106647,118147922,556684753,162450904,484861515,472243587,417233174,876650046,191048316,383910998,649569453,510481612,950253003,842521672,764810784,104232772,58253341,130246780,277151092,853096969,122266693,562258894,756520244,505753533,131849002,306283398,461218335,182081805,640042214,844891889,79604455,669916934,391532044,324004907,316636024,697406258,78039697,62968876,807482442,582529836,654903492,645929437,899904170,778779290,745708257,885460937,248942795,915545919,954930349,853377354,703531737,705014437,346272675,690789405,184836726,697806503,478533743,532637281,407127984,996934825,346686042,548135160,765942400,933657016,193044592,437134842,70465577,368879691,203286011,400628145,969402144,87233108,53586076,351901593,861801971,965590935,157777546,576237903,865664494,687258845,47733438,418084812,281701037,738557295,779053933,304568296,532114164,412173364,320897149,863489134,373305422,633552785,889812890,168503336,434627838,211242191,927851579,614936003,16569617,699206926,736507685,397035158,903211757,440705427,715617560,612372394,229567681,266661262,435522292,200176528,84928269,195574671,966586370,523014139,195166660,540799747,440222895,89764275,427291076,747192999,428681577,231514074,551539517,850110981,535685004,119680018,90501935,873430866,26236466,44084025,320357343,707828720,963059910,940281847,563722697,895217040,184272120,668843999,663595238,75996223,871355856,472306161,981409109,60703902,75486282,696747403,731490959,982051833,171394898,911710305,775942676,202597561,589191850,795327523,677934945,12617918,137108358,935199280,518220977,116587977,682683443,147836368,279931006,685488923,68815628,64071148,249111,273037997,908067814,322921229,422762728,227090135,749963904,568727681,806780476,899067831,854604941,410663181,173024913,876391214,555253141,374034278,341294995,418295052,544429064,401636797,926482153,223764400,348047352,4170610,903219819,143084772,342172787,616120027,27246776,879816941,452679550,558138102,130315754,219311447,10920181,781366606,418626593,50442742,530080840,536122388,99827770,635120330,524787685,108069911,326808157,685496753,651715091,465802418,586477250,34520847,248028557,384951719,241662121,61499161,258971783,172528295,202694969,637100374,202977144,140446730,353128622,215890965,96378092,57479914,818866544,497369638,33877403,640174285,796387998,686331280,705462639,142382808,566570797,589164945,288064839,385891484,956282930,256213029,626100151,697642496,599419006,142968621,332527576,642416477,901938758,414825769,144458027,196686319,306753424,880043016,792590727,263886450,814382072,509410448,40946171,108789533,875617498,756117032,59410,579152769,129267799,633423653,540794375,18462841,676577261,676017628,759266870,748182244,652434838,482076487,654157008,241722179,998113460,252492854,127322674,922111837,565015483,48227657,831613942,813727126,751320855,44295213,404554381,658682340,837874630,570486079,798694531,91541826,321826660,637576159,962544045,714023960,417018084,758335330,597956836,946147586,659013117,315899389,142601427,739010552,202009838,352624425,244916106,795161135,820367416,934789385,9689997,662283914,22890821,961269481,627630211,697840384,778754063,726293481,164039247,998516010,871672945,693352845,396835953,623179072,220902433,173369628,205616506,84809875,316411189,413390416,365382768,834238444,227018509,606790023,34734777,772382567,45774996,218255237,488498583,402901334,601452090,815468661,378119229,93399250,988321123,246628596,15358458,168829272,131157961,789962973,726530351,143389167,620080452,780182658,328208438,580344546,992798006,593436769,378585282,722485795,137959762,936163856,586587294,313451290,233013869,362301382,589999977,219546432,439633737,572908493,94618738,892856994,208794479,625046548,748757220,597509297,380918127,214012165,717753869,771813783,457416299,671746683,33532876,795824027,195903442,551461402,342423035,431189067,518716085,696521992,560176572,630965323,557416202,323509010,173224789,828724729,968140304,988964940,316173144,341504264,277776038,36386466,688232181,907501394,970641914,582585429,41499562,428262935,873814102,894965584,70031653,34608458,758650174,819003233,97675208,310457053,556931799,431435024,148274527,954015047,931035697,220246718,78348924,193773201,726556759,193601577,212555541,224399717,649163719,331830856,226979171,47387453,766293175,766864502,32326195,857668845,288084612,675487924,241875121,303629562,311049618,33939433,92842842,147727423,932581866,582294529,30247220,598677509,818518519,530461868,462030436,107537726,717701973,459407340,713486367,787323230,427149321,275759208,156070354,715543532,218504709,288177102,778659746,568125939,281127120,285482612,523912088,612484386,902593481,775066724,767173324,127630042,12632132,848390954,645505424,537766523,171564214,539521790,933042297,22847005,420148141,292784844,618159945,649409140,37848281,596772455,707286944,905971364,953390666,214613322,149419222,697477148,667033594,847009175,272913955,705901835,482318500,638704381,530378109,5643697,88522112,127178085,903771790,635411197,413881100,983778581,599501600,879394954,216144911,770087630,53708332,945232410,868933334,574994607,763651799,503202781,741181251,714808605,500554412,629435502,638061456,352591847,31843999,262305525,575865729,293804357,640198163,960488618,925794515,918424438,513038978,486204399,281767509,262799861,512517514,959125582,956090313,30823940,793756933,893174553,426286107,325926555,944403455,932055930,882316068,288647913,463611349,56074973,931336344,657923637,727391524,765937094,73383914,392603595,16642143,393967842,82030124,827796830,577732842,782637746,177555370,188314883,102809457,58457044,940072204,891807819,860497662,293942862,158428699,128707222,932026400,826978343,934583262,611199426,928759087,429957844,636263547,647176360,356851584,469700120,201935331,881124336,498262193,401818531,181724018,259842609,313425780,425986162,8071027,400799612,139461628,1547408,563014948,173512404,108526969,504340148,561559398,69850654,268426467,190039260,465924314,691014363,590432325,696811224,238191256,411880615,10733612,75814368,718358205,707088249,432258153,419894988,430369216,451988501,623547572,316613921,186894572,262942596,906475376,846936278,118522161,74411275,132630645,960286714,72870746,833102870,501691613,539149565,100276581,268789611,439529842,576930883,933143763,111058449,685475841,119449191,636963376,808834338,284063565,967980332,922483776,37037270,52955681,247622649,606701577,783700136,438473902,95970436,644151384,323931349,717079757,730425839,14459255,131884509,649752449,404358217,846888563,612684669,925097512,135496193,121027198,296970540,487925012,280211918,516799799,896944677,919664120,492289865,392518599,630073771,415972100,985805886,32499738,973754440,341740497,473306909,425772299,302237892,364631001,729564318,709053902,887924885,824818816,375676387,435581480,693020242,945849226,247289016,595902817,717070280,207934656,318412495,316122695,277266809,436980718,153636661,940214786,637785865,930802821,390845195,770140801,479178730,662209078,232708202,515128158,552815956,606841481,518891821,550053460,307640384,616986593,92000395,47290518,531144248,902052679,808081917,168021011,122596137,228835771,293376006,376364912,293153993,446268515,542667386,680896947,49284078,760638209,163882924,707794270,649533853,402578028,721161955,300613572,639073498,196935262,317293353,148764572,956629016,256155409,193971176,537079947,770502024,944729817,660244220,222206232,123028288,529241381,823756261,32568715,68595097,335385241,51120203,781489474,943029213,458273788,803061824,778143854,200069810,674878570,922802457,42979240,297311374,91104634,799554447,599504154,243605288,965783966,996900904,309141519,327382373,94367741,560262254,730402636,446291524,961305147,708180791,789351858,987692797,931408751,751497020,761571783,70072264,435104379,935989642,494922960,225443021,920409488,732168291,85506148,820453413,779670112,851355023,659912223,35839007,829404081,465123272,627466966,899391085,77908645,266282639,90149912,149404370,365309816,432192216,675345148,763339193,888094729,891394029,58760808,241121364,456088283,497066229,841914057,962324749,886259141,63129295,567249017,265344789,632563407,285786420,430619629,269071972,260403479,11689849,661107541,104156141,123148731,539656122,596969721,983085131,613155479,638837437,186907871,310123900,278242086,891604317,807035658,501077169,990826558,471583663,198533053,988850304,240558020,568701395,110722754,58026856,964103431,524610656,803655069,6674318,492955750,2561039,209923837,487943222,57126567,268241809,615992754,731855482,319369835,160757637,128684388,181705605,644760544,274864727,144846144,305756258,451923039,716710241,332770924,943596793,917783239,624715790,449624888,896508748,186048445,745256677,880762491,731606582,590628196,441697875,209303777,945912308,856208668,522083215,92419648,395583585,12287870,411448830,319681767,279205673,42238937,81900509,408074677,624225165,64898309,898963698,588468423,518527602,565345039,406301427,362655560,661030923,159146529,369617045,680068439,861789147,592688027,882511526,376463549,222555938,636789593,118533438,664315072,510317286,360803671,246897856,133952986,181015672,712301235,632324047,183999617,117652986,995819068,30740678,379459416,978705529,480608964,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);
      t=maxlongint div 5000;
var n,i:longint;s:qword;
begin
  readln(n);
  s:=js[n div t];
  for i:=n div t*t+1 to n do
    s:=(s*i) mod 1000000007;
  writeln(s);
end.

Measured memory_bytes: 128