let a = [1,0,0,1,1,1,2,3,4,6,9,13,19,28,41,60,88,129,189,277,406,595,872,1278,1873,2745,4023,5896,8641,12664,18560,27201,39865,58425,85626,125491,183916,269542,395033,578949,848491,1243524,1822473,2670964,3914488,5736961,8407925,12322413,18059374,26467299,38789712,56849086,83316385,122106097,178955183,262271568,384377665,563332848,825604416,209982074,773314922,598919331,808901405,582216320,181135644,990037049,572253362,753389006,743426048,315679403,69068402,812494450,128173846,197242248,9736691,137910537,335152785,344889476,482800013,817952798,162842267,645642280,463595071,626437338,272079611,735674682,362112013,634191624,369866299,731978312,366169929,736036228,468014533,834184462,570220683,38235209,872419671,442640347,480875556,353295220,795935567,276811116,630106336,426041896,702853012,332959341,759001237,461854242,794813583,553814813,15669048,810482631,364297437,379966485,190449109,554746546,934713031,125162133,679908679,614621703,739783836,419692508,34314204,774098040,193790541,228104745,2202778,195993319,424098064,426300842,622294161,46392218,472693060,94987214,141379432,614072492,709059706,850439138,464511623,173571322,24010453,488522076,662093398,686103851,174625920,836719318,522823162,697449082,534168393,56991548,754440630,288609016,345600564,100041187,388650203,734250767,834291954,222942150,957192917,791484864,14427007,971619924,763104781,777531788,749151705,512256479,289788260,38939958,551196437,840984697,879924655,431121085,272105775,152030423,583151508,855257283,7287699,590439207,445696483,452984182,43423382,489119865,942104047,985527429,474647287,416751327,402278749,876926036,293677356,695956105,572882134,866559490,562515588,135397715,1957198,564472786,699870501,701827699,266300478,966170979,667998671,934299149,900470121,568468785,502767927,403238041,971706826,474474746,877712787,849419606,323894345,201607125,51026724,374921069,576528194,627554918,2475980,579004174,206559085,209035065,788039239,994598324,203633382,991672621,986270938,189904313,181576927,167847858,357752171,539329098,707176956,64929120,604258218,311435167,376364287,980622505,292057665,668421952,649044450,941102115,609524060,258568503,199670611,809194671,67763167,267433778,76628442,144391609,411825387,488453829,632845438,44670818,533124647,165970078,210640896,743765543,909735621,120376510,864142053,773877667,894254177,758396223,532273883,426528053,184924269,717198152,143726198,328650467,45848612,189574810,518225277,564073889,753648699,271873969,835947858,589596550,861470519,697418370,287014913,148485425,845903795,132918701,281404126,127307914,260226615,541630741,668938655,929165270,470796004,139734652,68899915,539695919,679430571,748330486,288026398,967456969,715787448,3813839,971270808,687058249,690872088,662142889,349201131,40073212,702216101,51417225,91490437,793706538,845123763,936614200,730320731,575444487,512058680,242379404,817823891,329882564,572261968,390085852,719968416,292230377,682316229,402284638,694515015,376831237,779115875,473630883,850462120,629577988,103208864,953670984,583248965,686457829,640128806,223377764,909835593,549964392,773342156,683177742,233142127,6484276,689662018,922804145,929288421,618950432,541754570,471042984,89993409,631747979,102790956,192784365,824532344,927323300,120107658,944640002,871963295,992070953,936710948,808674236,800745182,737456123,546130352,346875527,84331643,630461995,977337522,61669158,692131153,669468668,731137826,423268972,92737633,823875459,247144424,339882057,163757509,410901933,750783990,914541499,325443425,76227408,990768907,316212325,392439733,383208633,699420958,91860684,475069317,174490268,266350952,741420269,915910537,182261482,923681751,839592281,21853756,945535507,785127781,806981537,752517037,537644811,344626341,97143371,634788182,979414523,76557887,711346069,690760585,767318472,478664534,169425112,936743584,415408111,584833223,521576800,936984911,521818127,43394920,980379831,502197951,545592871,525972695,28170639,573763510,99736198,127906837,701670347,801406545,929313382,630983722,432390260,361703635,992687357,425077610,786781245,779468595,204546198,991327443,770796031,975342229,966669665,737465689,712807911,679477569,416943251,129751155,809228724,226171968,355923123,165151840,391323808,747246931,912398771,303722572,50969496,963368267,267090832,318060328,281428588,548519420,866579748,148008329,696527749,563107490,711115819,407643561,970751051,681866863,89510417,60261461,742128324,831638741,891900202,634028519,465667253,357567448,991595967,457263213,814830661,806426621,263689827,78520481,884947102,148636922,227157403,112104498,260741420,487898823,600003321,860744741,348643557,948646878,809391612,158035162,106682033,916073645,74108800,180790833,96864471,170973271,351764104,448628575,619601846,971365950,419994518,39596357,10962300,430956818,470553175,481515475,912472293,383025461,864540936,777013222,160038676,24579605,801592827,961631503,986211108,787803928,749435424,735646525,523450446,272885863,8532381,531982827,804868690,813401071,345383891,150252574,963653645,309037529,459290103,422943741,731981270,191271366,614215107,346196370,537467736,151682836,497879206,35346935,187029771,684908977,720255912,907285683,592194653,312450558,219736234,811930887,124381438,344117672,156048552,280429990,624547662,780596214,61026197,685573859,466170066,527196263,212770115,678940181,206136437,418906552,97846726,303983163,722889715,820736441,124719597,847609312,668345746,793065343,640674648,309020387,102085723,742760371,51780751,153866474,896626845,948407596,102274063,998900908,947308497,49582553,48483454,995791951,45374497,93857951,89649895,135024392,228882343,318532238,453556630,682438973,971204,454527834,136966800,137938004,592465838,729432638,867370642,459836473,189269104,56639739,516476212,705745316,762385055,278861260,984606576,746991624,25852877,10459446,757451070,783303947,793763393,551214456,334518396,128281782,679496238,14014627,142296409,821792647,835807274,978103683,799896323,635703590,613807266,413703582,49407165,663214431,76918006,126325171,789539602,866457608,992782779,782322374,648779975,641562747,423885114,72665082,714227829,138112936,210778018,925005847,63118776,273896794,198902634,262021410,535918204,734820838,996842248,532760445,267581276,264423517,797183962,64765231,329188748,126372703,191137934,520326682,646699385,837837319,358163994,4863372,842700691,200864678,205728050,48428734,249293412,455021462,503450196,752743608,207765063,711215259,463958860,671723923,382939175,846898035,518621951,901561126,748459154,267081098,168642217,917101371,184182462,352824679,269926043,454108505,806933184,76859220,530967725,337900902,414760122,945727847,283628742,698388864,644116704,927745446,626134303,270251000,197996439,824130742,94381735,292378174,116508909,210890644,503268818,619777727,830668371,333937182,953714909,784383273,118320448,72035350,856418623,974739071,46774414,903193037,877932101,924706515,827899545,705831639,630538147,458437685,164269317,794807464,253245142,417514459,212321916,465567058,883081517,95403426,560970484,444051994,539455420,100425897,544477891,83933304,184359201,728837092,812770396,997129597,725966682,538737071,535866661,261833336,800570407,336437061,598270397,398840797,735277858,333548248,732389045,467666896,801215144,533604182,1271071,802486215,336090390,337361461,139847669,475938059,813299520,953147189,429085241,242384754,195531936,624617177,867001931,62533860,687151037,554152961,616686821,303837851,857990812,474677626,778515477,636506282,111183901,889699378,526205653,637389554,527088925,53294571,690684125,217773043,271067614,961751739,179524775,450592389,412344121,591868896,42461278,454805399,46674288,89135566,543940965,590615253,679750819,223691777,814307030,494057842,717749619,532056642,26114477,743864096,275920731,302035208,45899297,321820028,623855236,669754533,991574561,615429790,285184316,276758870,892188660,177372969,454131839,346320492,523693461,977825300,324145785,847839246,825664539,149810317,997649563,823314095,973124412,970773968,794088056,767212461,737986422,532074471,299286925,37273340,569347811,868634736,905908076,475255880,343890609,249798678,725054558,68945160,318743838,43798389,112743549,431487387,475285776,588029325,19516705,494802481,82831799,102348504,597150985,679982784,782331288,379482266,59465043,841796331,221278590,280743633,122539957,343818547,624562180,747102137,90920677,715482857,462584987,553505664,268988514,731573501,285079158,554067672,285641166,570720324,124787989,410429155,981149479,105937461,516366616,497516088,603453549,119820158,617336246,220789788,340609946,957946192,178735973,519345919,477292104,656028077,175373989,652666093,308694163,484068152,136734238,445428401,929496553,66230784,511659185,441155731,507386515,19045693,460201424,967587939,986633632,446835049,414422981,401056606,847891655,262314629,663371235,511262883,773577512,436948740,948211623,721789128,158737861,106949477,828738605,987476466,94425936,923164541,910641000,5066929,928231470,838872463,843939392,772170855,611043311,454982696,227153544,838196855,293179544,520333088,358529936,651709480,172042561,530572497,182281970,354324531,884897028,67178991,421503522,306400543,373579534,795083056,101483592,475063126,270146175,371629767,846692893,116839061,488468828,335161714,452000775,940469603,275631310,727632085,668101681,943732991,671365069,339466743,283199727,954564796,294031532,577231259,531796048,825827580,403058832,934854880,760682453,163741278,98596151,859278604,23019875,121616026,980894630,3914498,125530524,106425147,110339645,235870169,342295316,452634961,688505130,30800439,483435400,171940523,202740962,686176362,858116885,60857840,747034202,605151080,666008920,413043115,18194188,684203108,97246216,115440404,799643512,896889728,12330125,811973637,708863358,721193483,533167113,242030464,963223947,496391053,738421517,701645457,198036503,936458020,638103470,836139973,772597986,410701449,246841415,19439394,430140843,676982258,696421652,126562488,803544746,499966391,626528879,430073618,930040009,556568881,986642499,916682501,473251375,459893867,376576361,849827736,309721596,686297957,536125686,845847282,532145232,68270911,914118193,446263418,514534329,428652515,874915933,389450255,818102770,693018696,82468944,900571714,593590403,676059347,576631054,170221450,846280797,422911844,593133294,439414084,862325928,455459215,894873299,757199220,212658428,107531720,864730940,77389361,184921081,49652014,127041375,311962456,361614470,488655845,800618301,162232764,650888609,451506903,613739667,264628269,716135172,329874832,594503101,310638266,640513098,235016192,545654458,186167549,421183741,966838199,153005741,574189482,541027674,694033415,268222890,809250564,503283972,771506862,580757419,84041384,855548246,436305658,520347042,375895281,812200939,332547974,708443255,520644187,853192161,561635409,82279589,935471750,497107152,579386741,514858484,11965629,591352370,106210847,118176476,709528846,815739693,933916169,643445008,459184694,393100856,36545857,495730551,888831407,925377264,421107808,309939208,235316465,656424273,966363481,201679939,858104212,824467686,26147618,884251830,708719509,734867127,619118950,327838452,62705572,681824522,9662967,72368539,754193061,763856028,836224567,590417621,354273642,190498202,780915823,135189458,325687660,106603476,241792934,567480594,674084070,915877004,483357591,157441654,73318651,556676242,714117896,787436547,344112782,58230671,845667218,189779993,248010664,93677875,283457868,531468532,625146407,908604275,440072800,65219200,973823475,413896268,479115468,452938936,866835204,345950665,798889601,665724798,11675456,810565057,476289848,487965304,298530354,774820202,262785499,561315853,336136048,598921547,160237393,496373441,95294981,255532374,751905815,847200796,102733163,854638978,701839767,804572930,659211901,361051661,165624584,824836485,185888139,351512723,176349201,362237340,713750063,890099264,252336597,966086660,856185917,108522507,74609160,930795077,39317577,113926737,44721807,84039384,197966121,242687928,326727312,524693433,767381361,94108666,618802099,386183453,480292119,99094211,485277664,965569783,64663987,549941651,515511427,580175414,130117058,645628485,225803892,355920950,1549428,227353320,583274270,584823698,812177018,395451281,980274979,792451990,187903264,168178236,960630226,148533483,316711719,277341938,425875421,742587140,19929071,445804492,188391625,208320696,654125188,842516813,50837502,704962690,547479496,598316998,303279681,850759177,449076168,752355849,603115019,52191180,804547029,407662041,459853221,264400243,672062284,131915498,396315741,68378018,200293516,596609257,664987275,865280791,461890041,126877309,992158100,454048134,580925443,573083536,27131663,608057106,181140635,208272298,816329404,997470039,205742330,22071727,19541759,225284089,247355816,266897575,492181664,739537480,6435048,498616712,238154185,244589233,743205945,981360130,225949356,969155301,950515424,176464773,145620067,96135484,272600257,418220324,514355808,786956065,205176382,719532190,506488248,711664630,431196813,937685061,649349684,80546490,18231544,667581228,748127718,766359262,433940483,182068194,948427456,382367932,564436126,512863575,895231507,459667626,972531201,867762701,327430320,299961514,167724208,495154528,795116042,962840250,457994771,253110806,215951049,673945820,927056626,143007668,816953488,744010107,887017775,703971256,447981356,334999124,38970373,486951729,821950853,860921226,347872948,169823794,30745013,378617961,548441755,579186768,957804729,506246477,85433238,43237960,549484437,634917675,678155635,227640065,862557740,540713368,768353433,630911166,171624527,939977960,570889119,742513646,682491599,253380711,995894357,678385949,931766660,927661010,606046952,537813605,465474608,71521553,609335158,74809759,146331312,755666470,830476229,976807541,732474004,562950226,539757760,272231757,835181983,374939736,647171493,482353469,857293205,504464691,986818160,844111358,348576042,335394195,179505546,528081588,863475783,42981322,571062910,434538686,477520008,48582911,483121597,960641605,9224509,492346106,452987704,462212213,954558319,407546016,869758229,824316541,231862550,101620772,925937313,157799856,259420628,185357934,343157790,602578418,787936352,131094135,733672553,521608898,652703033,386375579,907984477,560687503,947063082,855047552,415735048,362798123,217845668,633580716,996378839,214224500,847805216,844184048,58408541,906213757,750397798,808806339,715020089,465417880,274224212,989244301,454662174,728886386,718130680,172792847,901679233,619809906,792602753,694281979,314091878,106694624,800976603,115068474,221763098,22739694,137808168,359571266,382310960,520119128,879690394,262001347,782120475,661810862,923812209,705932677,367743532,291555734,997488411,365231936,656787670,654276074,19508003,676295673,330571740,350079743,26375409,356947149,707026892,733402301,90349443,797376335,530778629,621128072,418504400,949283029,570411094,988915494,938198516,508609603,497525090,435723599,944333202,441858285,877581884,821915079,263773357,141355234,963270313,227043663,368398897,331669203,558712866,927111763,258780959,817493825,744605581,3386533,820880358,565485932,568872465,389752816,955238748,524111206,913864022,869102763,393213962,307077977,176180733,569394695,876472672,52653398,622048093,498520758,551174156,173222242,671743000,222917149,396139391,67882384,290799533,686938924,754821308,45620834,732559758,487381059,533001893,265561644,752942703,285944589,551506233,304448929,590393518,141899744,446348673,36742184,178641928,624990601,661732785,840374713,465365307,127098085,967472798,432838098,559936183,527408974,960247072,520183248,47592215,7839280,528022528,575614743,583454023,111476544,687091287,270545303,382021847,69113127,339658430,721680277,790793404,130451827,852132104,642925501,773377328,625509425,268434919,41812240,667321665,935756584,977568824,644890482,580647059,558215876,203106351,783753410,341969279,545075630,328829033,670798312,215873935,544702968,215501273,431375208,976078176,191579442,622954650,599032819,790612261,413566904,12599716,803211977,216778874,229378590,32590560,249369434,478748024,511338584,760708018,239456035,750794619,511502630,750958665,501753277,13255900,764214565,265967835,279223735,43438293,309406128,588629863,632068156,941474284,530104140,162172289,103646566,633750706,795922995,899569561,533320260,329243248,228812802,762133062,91376303,320189105,82322160,173698463,493887568,576209728,749908191,243795752,820005480,569913664,813709416,633714889,203628546,17337955,651052844,854681390,872019345,523072182,377753565,249772903,772845085,150598643,400371546,173216624,323815267,724186813,897403437,221218697,945405510,842808940,64027630,9433133,852242073,916269703,925702836,777944902,694214598,619917427,397862322,92076913,711994340,109856655,201933568,913927908,23784556,225718124,139646025,163430581,389148705,528794730,692225311,81374009,610168739,302394043,383768052,993936791,296330827,680098879,674035663,970366490,650465362,324501018,294867501,945332863,269833874,564701375,510034231,779868105,344569473,854603704,634471802,979041275,833644972,468116767,447158035,280803000,748919767,196077795,476880795,225800555,421878350,898759145,124559693,546438043,445197181,569756874,116194910,561392091,131148958,247343868,808735959,939884917,187228778,995964737,935849647,123078418,119043148,54892788,177971206,297014354,351907142,529878348,826892702,178799837,708678185,535570880,714370717,423048895,958619775,672990485,96039373,54659141,727649626,823688999,878348140,605997759,429686751,308034884,914032643,343719387,651754271,565786907,909506294,561260558,127047458,36553745,597814303,724861761,761415506,359229802,84091556,845507062,204736857,288828413,134335468,339072325,627900738,762236206,101308524,729209262,491445461,592753985,321963240,813408701,406162679,728125919,541534613,947697292,675823204,217357810,165055095,840878299,58236102,223291197,64169489,122405591,345696788,409866277,532271868,877968656,287834926,820106794,698075443,985910369,806017156,504092592,490002954,296020103,800112695,290115642,586135745,386248433,676364075,262499813,648748246,325112314,587612127,236360366,561472680,149084800,385445166,946917846,96002639,481447805,428365644,524368283,5816081,434181725,958550008,964366089,398547807,357097808,321463890,720011697,77109498,398573388,118585078,195694576,594267964,712853042,908547618,502815575,215668610,124216221,627031796,842700406,966916627,593948416,436648815,403565435,997513851,434162659,837728094,835241938,269404590,107132677,942374615,211779198,318911875,261286483,473065681,791977556,53264032,526329713,318307262,371571294,897901007,216208262,587779556,485680556,701888818,289668367,775348923,477237734,766906101,542255017,19492744,786398845,328653855,348146599,134545437,463199292,811345891,945891328,409090613,220436497,166327818,575418431,795854928,962182746,537601170,333456091,295638830,833240000,166696084,462334914,295574907,462270991,924605905,220180805,682451796,607057694,827238499,509690288,116747975,943986474,453676755,570424730,514411197,968087952,538512675,52923865,21011810,559524485,612448350,633460160,192984638,805432988,438893141,631877779,437310760,876203901,508081673,945392433,821596327,329677993,275070419,96666739,426344732,701415151,798081890,224426615,925841766,723923649,948350264,874192023,598115665,546465922,420657938,18773596,565239518,985897456,4671045,569910563,555808012,560479057,130389613,686197625,246676675,377066288,63263906,309940581,687006869,750270775,60211349,747218218,497488986,557700335,304918546,802407532,360107860,665026406,467433931,827541791,492568190,960002121,787543905,280112088,240114202,27658100,307770188,547884390,575542490,883312678]
let x = Int(readLine()!)!
print(a[x])