# l=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]
# l2=[]
# for i in range(2,1001):
#   a=i
#   b=[]
#   for j in l:
#     while True:
#       if a%j==0:
#         b.append(j)
#         a//=j
#       else:
#         break
#   l2.append(b)
# print(l2)

# class struct:
#   def __init__(self,a,b):
#     self.a=a
#     self.b=b
# l0=[0]*1000
# l=[[2],[3],[2,2],[5],[2,3],[7],[2,2,2],[3,3],[2,5],[11],[2,2,3],[13],[2,7],[3,5],[2,2,2,2],[17],[2,3,3],[19],[2,2,5],[3,7],[2,11],[23],[2,2,2,3],[5,5],[2,13],[3,3,3],[2,2,7],[29],[2,3,5],[31],[2,2,2,2,2],[3,11],[2,17],[5,7],[2,2,3,3],[37],[2,19],[3,13],[2,2,2,5],[41],[2,3,7],[43],[2,2,11],[3,3,5],[2,23],[47],[2,2,2,2,3],[7,7],[2,5,5],[3,17],[2,2,13],[53],[2,3,3,3],[5,11],[2,2,2,7],[3,19],[2,29],[59],[2,2,3,5],[61],[2,31],[3,3,7],[2,2,2,2,2,2],[5,13],[2,3,11],[67],[2,2,17],[3,23],[2,5,7],[71],[2,2,2,3,3],[73],[2,37],[3,5,5],[2,2,19],[7,11],[2,3,13],[79],[2,2,2,2,5],[3,3,3,3],[2,41],[83],[2,2,3,7],[5,17],[2,43],[3,29],[2,2,2,11],[89],[2,3,3,5],[7,13],[2,2,23],[3,31],[2,47],[5,19],[2,2,2,2,2,3],[97],[2,7,7],[3,3,11],[2,2,5,5],[101],[2,3,17],[103],[2,2,2,13],[3,5,7],[2,53],[107],[2,2,3,3,3],[109],[2,5,11],[3,37],[2,2,2,2,7],[113],[2,3,19],[5,23],[2,2,29],[3,3,13],[2,59],[7,17],[2,2,2,3,5],[11,11],[2,61],[3,41],[2,2,31],[5,5,5],[2,3,3,7],[127],[2,2,2,2,2,2,2],[3,43],[2,5,13],[131],[2,2,3,11],[7,19],[2,67],[3,3,3,5],[2,2,2,17],[137],[2,3,23],[139],[2,2,5,7],[3,47],[2,71],[11,13],[2,2,2,2,3,3],[5,29],[2,73],[3,7,7],[2,2,37],[149],[2,3,5,5],[151],[2,2,2,19],[3,3,17],[2,7,11],[5,31],[2,2,3,13],[157],[2,79],[3,53],[2,2,2,2,2,5],[7,23],[2,3,3,3,3],[163],[2,2,41],[3,5,11],[2,83],[167],[2,2,2,3,7],[13,13],[2,5,17],[3,3,19],[2,2,43],[173],[2,3,29],[5,5,7],[2,2,2,2,11],[3,59],[2,89],[179],[2,2,3,3,5],[181],[2,7,13],[3,61],[2,2,2,23],[5,37],[2,3,31],[11,17],[2,2,47],[3,3,3,7],[2,5,19],[191],[2,2,2,2,2,2,3],[193],[2,97],[3,5,13],[2,2,7,7],[197],[2,3,3,11],[199],[2,2,2,5,5],[3,67],[2,101],[7,29],[2,2,3,17],[5,41],[2,103],[3,3,23],[2,2,2,2,13],[11,19],[2,3,5,7],[211],[2,2,53],[3,71],[2,107],[5,43],[2,2,2,3,3,3],[7,31],[2,109],[3,73],[2,2,5,11],[13,17],[2,3,37],[223],[2,2,2,2,2,7],[3,3,5,5],[2,113],[227],[2,2,3,19],[229],[2,5,23],[3,7,11],[2,2,2,29],[233],[2,3,3,13],[5,47],[2,2,59],[3,79],[2,7,17],[239],[2,2,2,2,3,5],[241],[2,11,11],[3,3,3,3,3],[2,2,61],[5,7,7],[2,3,41],[13,19],[2,2,2,31],[3,83],[2,5,5,5],[251],[2,2,3,3,7],[11,23],[2,127],[3,5,17],[2,2,2,2,2,2,2,2],[257],[2,3,43],[7,37],[2,2,5,13],[3,3,29],[2,131],[263],[2,2,2,3,11],[5,53],[2,7,19],[3,89],[2,2,67],[269],[2,3,3,3,5],[271],[2,2,2,2,17],[3,7,13],[2,137],[5,5,11],[2,2,3,23],[277],[2,139],[3,3,31],[2,2,2,5,7],[281],[2,3,47],[283],[2,2,71],[3,5,19],[2,11,13],[7,41],[2,2,2,2,2,3,3],[17,17],[2,5,29],[3,97],[2,2,73],[293],[2,3,7,7],[5,59],[2,2,2,37],[3,3,3,11],[2,149],[13,23],[2,2,3,5,5],[7,43],[2,151],[3,101],[2,2,2,2,19],[5,61],[2,3,3,17],[307],[2,2,7,11],[3,103],[2,5,31],[311],[2,2,2,3,13],[313],[2,157],[3,3,5,7],[2,2,79],[317],[2,3,53],[11,29],[2,2,2,2,2,2,5],[3,107],[2,7,23],[17,19],[2,2,3,3,3,3],[5,5,13],[2,163],[3,109],[2,2,2,41],[7,47],[2,3,5,11],[331],[2,2,83],[3,3,37],[2,167],[5,67],[2,2,2,2,3,7],[337],[2,13,13],[3,113],[2,2,5,17],[11,31],[2,3,3,19],[7,7,7],[2,2,2,43],[3,5,23],[2,173],[347],[2,2,3,29],[349],[2,5,5,7],[3,3,3,13],[2,2,2,2,2,11],[353],[2,3,59],[5,71],[2,2,89],[3,7,17],[2,179],[359],[2,2,2,3,3,5],[19,19],[2,181],[3,11,11],[2,2,7,13],[5,73],[2,3,61],[367],[2,2,2,2,23],[3,3,41],[2,5,37],[7,53],[2,2,3,31],[373],[2,11,17],[3,5,5,5],[2,2,2,47],[13,29],[2,3,3,3,7],[379],[2,2,5,19],[3,127],[2,191],[383],[2,2,2,2,2,2,2,3],[5,7,11],[2,193],[3,3,43],[2,2,97],[389],[2,3,5,13],[17,23],[2,2,2,7,7],[3,131],[2,197],[5,79],[2,2,3,3,11],[397],[2,199],[3,7,19],[2,2,2,2,5,5],[401],[2,3,67],[13,31],[2,2,101],[3,3,3,3,5],[2,7,29],[11,37],[2,2,2,3,17],[409],[2,5,41],[3,137],[2,2,103],[7,59],[2,3,3,23],[5,83],[2,2,2,2,2,13],[3,139],[2,11,19],[419],[2,2,3,5,7],[421],[2,211],[3,3,47],[2,2,2,53],[5,5,17],[2,3,71],[7,61],[2,2,107],[3,11,13],[2,5,43],[431],[2,2,2,2,3,3,3],[433],[2,7,31],[3,5,29],[2,2,109],[19,23],[2,3,73],[439],[2,2,2,5,11],[3,3,7,7],[2,13,17],[443],[2,2,3,37],[5,89],[2,223],[3,149],[2,2,2,2,2,2,7],[449],[2,3,3,5,5],[11,41],[2,2,113],[3,151],[2,227],[5,7,13],[2,2,2,3,19],[457],[2,229],[3,3,3,17],[2,2,5,23],[461],[2,3,7,11],[463],[2,2,2,2,29],[3,5,31],[2,233],[467],[2,2,3,3,13],[7,67],[2,5,47],[3,157],[2,2,2,59],[11,43],[2,3,79],[5,5,19],[2,2,7,17],[3,3,53],[2,239],[479],[2,2,2,2,2,3,5],[13,37],[2,241],[3,7,23],[2,2,11,11],[5,97],[2,3,3,3,3,3],[487],[2,2,2,61],[3,163],[2,5,7,7],[491],[2,2,3,41],[17,29],[2,13,19],[3,3,5,11],[2,2,2,2,31],[7,71],[2,3,83],[499],[2,2,5,5,5],[3,167],[2,251],[503],[2,2,2,3,3,7],[5,101],[2,11,23],[3,13,13],[2,2,127],[509],[2,3,5,17],[7,73],[2,2,2,2,2,2,2,2,2],[3,3,3,19],[2,257],[5,103],[2,2,3,43],[11,47],[2,7,37],[3,173],[2,2,2,5,13],[521],[2,3,3,29],[523],[2,2,131],[3,5,5,7],[2,263],[17,31],[2,2,2,2,3,11],[23,23],[2,5,53],[3,3,59],[2,2,7,19],[13,41],[2,3,89],[5,107],[2,2,2,67],[3,179],[2,269],[7,7,11],[2,2,3,3,3,5],[541],[2,271],[3,181],[2,2,2,2,2,17],[5,109],[2,3,7,13],[547],[2,2,137],[3,3,61],[2,5,5,11],[19,29],[2,2,2,3,23],[7,79],[2,277],[3,5,37],[2,2,139],[557],[2,3,3,31],[13,43],[2,2,2,2,5,7],[3,11,17],[2,281],[563],[2,2,3,47],[5,113],[2,283],[3,3,3,3,7],[2,2,2,71],[569],[2,3,5,19],[571],[2,2,11,13],[3,191],[2,7,41],[5,5,23],[2,2,2,2,2,2,3,3],[577],[2,17,17],[3,193],[2,2,5,29],[7,83],[2,3,97],[11,53],[2,2,2,73],[3,3,5,13],[2,293],[587],[2,2,3,7,7],[19,31],[2,5,59],[3,197],[2,2,2,2,37],[593],[2,3,3,3,11],[5,7,17],[2,2,149],[3,199],[2,13,23],[599],[2,2,2,3,5,5],[601],[2,7,43],[3,3,67],[2,2,151],[5,11,11],[2,3,101],[607],[2,2,2,2,2,19],[3,7,29],[2,5,61],[13,47],[2,2,3,3,17],[613],[2,307],[3,5,41],[2,2,2,7,11],[617],[2,3,103],[619],[2,2,5,31],[3,3,3,23],[2,311],[7,89],[2,2,2,2,3,13],[5,5,5,5],[2,313],[3,11,19],[2,2,157],[17,37],[2,3,3,5,7],[631],[2,2,2,79],[3,211],[2,317],[5,127],[2,2,3,53],[7,7,13],[2,11,29],[3,3,71],[2,2,2,2,2,2,2,5],[641],[2,3,107],[643],[2,2,7,23],[3,5,43],[2,17,19],[647],[2,2,2,3,3,3,3],[11,59],[2,5,5,13],[3,7,31],[2,2,163],[653],[2,3,109],[5,131],[2,2,2,2,41],[3,3,73],[2,7,47],[659],[2,2,3,5,11],[661],[2,331],[3,13,17],[2,2,2,83],[5,7,19],[2,3,3,37],[23,29],[2,2,167],[3,223],[2,5,67],[11,61],[2,2,2,2,2,3,7],[673],[2,337],[3,3,3,5,5],[2,2,13,13],[677],[2,3,113],[7,97],[2,2,2,5,17],[3,227],[2,11,31],[683],[2,2,3,3,19],[5,137],[2,7,7,7],[3,229],[2,2,2,2,43],[13,53],[2,3,5,23],[691],[2,2,173],[3,3,7,11],[2,347],[5,139],[2,2,2,3,29],[17,41],[2,349],[3,233],[2,2,5,5,7],[701],[2,3,3,3,13],[19,37],[2,2,2,2,2,2,11],[3,5,47],[2,353],[7,101],[2,2,3,59],[709],[2,5,71],[3,3,79],[2,2,2,89],[23,31],[2,3,7,17],[5,11,13],[2,2,179],[3,239],[2,359],[719],[2,2,2,2,3,3,5],[7,103],[2,19,19],[3,241],[2,2,181],[5,5,29],[2,3,11,11],[727],[2,2,2,7,13],[3,3,3,3,3,3],[2,5,73],[17,43],[2,2,3,61],[733],[2,367],[3,5,7,7],[2,2,2,2,2,23],[11,67],[2,3,3,41],[739],[2,2,5,37],[3,13,19],[2,7,53],[743],[2,2,2,3,31],[5,149],[2,373],[3,3,83],[2,2,11,17],[7,107],[2,3,5,5,5],[751],[2,2,2,2,47],[3,251],[2,13,29],[5,151],[2,2,3,3,3,7],[757],[2,379],[3,11,23],[2,2,2,5,19],[761],[2,3,127],[7,109],[2,2,191],[3,3,5,17],[2,383],[13,59],[2,2,2,2,2,2,2,2,3],[769],[2,5,7,11],[3,257],[2,2,193],[773],[2,3,3,43],[5,5,31],[2,2,2,97],[3,7,37],[2,389],[19,41],[2,2,3,5,13],[11,71],[2,17,23],[3,3,3,29],[2,2,2,2,7,7],[5,157],[2,3,131],[787],[2,2,197],[3,263],[2,5,79],[7,113],[2,2,2,3,3,11],[13,61],[2,397],[3,5,53],[2,2,199],[797],[2,3,7,19],[17,47],[2,2,2,2,2,5,5],[3,3,89],[2,401],[11,73],[2,2,3,67],[5,7,23],[2,13,31],[3,269],[2,2,2,101],[809],[2,3,3,3,3,5],[811],[2,2,7,29],[3,271],[2,11,37],[5,163],[2,2,2,2,3,17],[19,43],[2,409],[3,3,7,13],[2,2,5,41],[821],[2,3,137],[823],[2,2,2,103],[3,5,5,11],[2,7,59],[827],[2,2,3,3,23],[829],[2,5,83],[3,277],[2,2,2,2,2,2,13],[7,7,17],[2,3,139],[5,167],[2,2,11,19],[3,3,3,31],[2,419],[839],[2,2,2,3,5,7],[29,29],[2,421],[3,281],[2,2,211],[5,13,13],[2,3,3,47],[7,11,11],[2,2,2,2,53],[3,283],[2,5,5,17],[23,37],[2,2,3,71],[853],[2,7,61],[3,3,5,19],[2,2,2,107],[857],[2,3,11,13],[859],[2,2,5,43],[3,7,41],[2,431],[863],[2,2,2,2,2,3,3,3],[5,173],[2,433],[3,17,17],[2,2,7,31],[11,79],[2,3,5,29],[13,67],[2,2,2,109],[3,3,97],[2,19,23],[5,5,5,7],[2,2,3,73],[877],[2,439],[3,293],[2,2,2,2,5,11],[881],[2,3,3,7,7],[883],[2,2,13,17],[3,5,59],[2,443],[887],[2,2,2,3,37],[7,127],[2,5,89],[3,3,3,3,11],[2,2,223],[19,47],[2,3,149],[5,179],[2,2,2,2,2,2,2,7],[3,13,23],[2,449],[29,31],[2,2,3,3,5,5],[17,53],[2,11,41],[3,7,43],[2,2,2,113],[5,181],[2,3,151],[907],[2,2,227],[3,3,101],[2,5,7,13],[911],[2,2,2,2,3,19],[11,83],[2,457],[3,5,61],[2,2,229],[7,131],[2,3,3,3,17],[919],[2,2,2,5,23],[3,307],[2,461],[13,71],[2,2,3,7,11],[5,5,37],[2,463],[3,3,103],[2,2,2,2,2,29],[929],[2,3,5,31],[7,7,19],[2,2,233],[3,311],[2,467],[5,11,17],[2,2,2,3,3,13],[937],[2,7,67],[3,313],[2,2,5,47],[941],[2,3,157],[23,41],[2,2,2,2,59],[3,3,3,5,7],[2,11,43],[947],[2,2,3,79],[13,73],[2,5,5,19],[3,317],[2,2,2,7,17],[953],[2,3,3,53],[5,191],[2,2,239],[3,11,29],[2,479],[7,137],[2,2,2,2,2,2,3,5],[31,31],[2,13,37],[3,3,107],[2,2,241],[5,193],[2,3,7,23],[967],[2,2,2,11,11],[3,17,19],[2,5,97],[971],[2,2,3,3,3,3,3],[7,139],[2,487],[3,5,5,13],[2,2,2,2,61],[977],[2,3,163],[11,89],[2,2,5,7,7],[3,3,109],[2,491],[983],[2,2,2,3,41],[5,197],[2,17,29],[3,7,47],[2,2,13,19],[23,43],[2,3,3,5,11],[991],[2,2,2,2,2,31],[3,331],[2,7,71],[5,199],[2,2,3,83],[997],[2,499],[3,3,3,37],[2,2,2,5,5,5]]
# l2=[]
# for i in l:
#   for j in i:
#     l0[j]+=1
#   c=1
#   for j in l0:
#     if j!=0:
#       c*=(j+1)
#       c%=1000000007
#   c%=1000000007
#   l2.append(c)
# print(l2)

l=[1,2,4,8,16,30,60,96,160,270,540,792,1584,2592,4032,5376,10752,14688,29376,41040,60800,96000,192000,242880,340032,532224,677376,917280,1834560,2332800,4665600,5529600,7864320,12165120,16422912,19595520,39191040,60466176,85100544,102435840,204871680,258048000,516096000,677376000,819624960,258709753,517419506,876670706,698576619,464046052,210846678,87039944,174079888,559756674,984916319,217548604,16857327,609087587,218175167,106431041,212862082,535421074,139926156,50952999,105219839,195900610,391801220,889436190,472974756,845412639,690825271,891132264,782264521,316684054,31280490,665186745,252135966,764748573,529497139,790600338,524719291,999573608,999147209,522112609,37861883,417241520,775916997,997830958,995661909,729407917,321723976,871170030,520705814,149385219,41956001,988486370,976972733,516785610,158924226,583951250,167902493,687346296,374692585,229757313,549263416,890796057,781592107,875619122,751238237,277966376,130571620,574892396,149784785,921692445,813661707,582700142,400726352,358621292,318642155,250091916,386472265,174406757,151737975,260683867,184202887,320817301,641634602,125034947,201660251,962210566,924421125,489345615,320577061,637208078,196761361,626955546,253911085,389481998,778963996,576273102,309075370,619146484,295106277,464103226,498550267,627180822,788686761,989134263,978268519,902509248,805018489,112903872,32995287,295406792,974343106,721660051,443320095,316385239,778274799,190780502,633014225,727670045,455340083,498164792,15588548,97601235,195202470,569355054,118486597,342752204,135661810,90769804,181539608,519303442,515842850,84989549,696032419,231083385,462166770,150280772,300561544,884472740,641985713,569378318,591770736,690140664,249252882,677627271,850771381,851099110,702198213,111350575,222701150,859360900,670197303,177520684,355041368,643925245,287850483,323688011,476804260,749121574,436195097,100916105,763521317,852472431,566135419,817481112,609114726,316546467,633092934,400461490,516478899,802348580,904410955,621677199,257318500,176522245,676814987,463688019,296329114,264099706,528199412,36178948,424547801,768068647,536137287,180929498,361858996,212858280,424867383,432882564,865765128,720594700,90410365,461821767,203725504,114020002,228040004,637601848,275203689,996048794,816392758,827385828,501246906,502796187,283931071,433357175,368415063,694773670,389547333,672209469,929924926,339805954,823423911,430631131,861262262,912999218,775754185,248442642,92860619,47164638,94329276,560810218,901787221,979102645,727649351,20618968,41237936,409407748,818815496,105871481,565828513,733793480,775394695,826327221,652654435,644963335,70964339,34934197,69868394,21321430,42642860,308165968,66236679,863975191,474703946,965050168,372703124,98935522,622346998,724308287,448616567,387250563,521154852,757291985,756807708,98256492,802531326,949720885,885971876,131412209,981761360,661149918,619958299,331028217,662056434,807561987,320675293,914129701,828259395,37073206,74146412,402841690,54637455,617124544,234249081,751443813,937109749,192721498,402972372,453564416,21903965,219196964,711481873,513083746,252120578,510728243,686346634,854955589,709911171,78596230,269965951,409219288,248271231,873383775,746767543,509852147,174891499,984879786,197881406,237525166,359571994,592280493,443047391,387927598,775855196,487579371,975158742,351882153,147029129,237093507,474187014,233169083,703708683,126101010,198878663,367151757,734303514,558855498,196629758,161317030,573722496,327882255,869789706,71204994,142409988,519330677,658916599,820221123,589765049,882787662,765575317,237538730,765336752,111906311,970555905,547616857,95233707,919602856,913510209,325919347,651838694,787773019,168803670,875276542,263468393,816727867,633455727,500272724,140006678,171663917,920917448,754148927,547298078,412984678,825969356,89434825,653930388,136393590,272787180,276924235,570666519,590968903,696916544,114558109,209914977,987646996,975293985,732105167,207549775,590764498,239710087,413342719,606756472,119222007,227695505,450857281,901714562,192653364,385306728,234022344,31755833,752787939,682129837,972238124,563737250,589527825,729854221,873389836,746779665,973964734,947929461,5202400,320558679,402562062,651932087,438747311,877494622,851938578,595655182,953260474,906520941,610950283,501334286,115901200,458267670,725708035,451416063,34629651,443595068,292992687,984336996,352845142,600659252,738086132,476172257,146298687,742115388,685981689,371963371,5238701,10477402,766426619,741060152,215953758,431907516,900346034,302070357,669584758,46053147,500531147,269366731,835955289,753764439,748101695,586666665,340467085,680934170,993066655,337509515,702294178,689317659,610110893,855932510,718959729,437919451,162052266,591444463,937285062,874570117,577640930,690830665,441136051,234385594,995953016,490091986,701529803,403059599,173749087,571309264,670816347,341632687,12414678,656616799,110230917,555093018,326641735,653283470,841517232,299713801,790165940,55645384,857068605,957840454,891206655,734604192,144312526,317679024,396371648,792743296,423188008,846376016,985116058,646955723,952177710,502929334,92150358,447989522,924790847,549384151,424045976,984526166,194912796,17485470,655375515,480905089,910910739,771660846,177055119,354110238,487461754,533406064,889925808,672895377,471803466,943606932,363992147,457850989,337082821,559633947,903886732,428980584,430095367,52327251,636880607,273761207,706305042,890884144,393016175,748347757,949802139,899604271,310566618,130756774,816805638,605028078,169610267,339220534,575779053,151558099,779861186,564602992,437157814,502964081,478103459,956206918,385872385,383885002,125139522,606176173,727381953,8385703,189534611,657264353,809755457,619510907,607320752,922420555,310951652,461684174,548921957,97843907,729671781,620980721,857109915,25052446,275170024,550340048,495401987,990803974,362448559,60904426,929227965,120741193,257409647,514819294,969108899,560048584,985073824,700527244,680852420,361704833,819310219,589014097,1398831,2797662,533149213,66298419,177289968,605590036,607911651,709970869,953992856,619456719,655319030,644362951,232480867,745680583,590594926,181189845,520817003,742434671,899661005,364907082,733053610,13738009,433804341,236387921,508481622,16963237,232316619,464633238,221314587,887788178,285824818,571649636,737224462,55447552,88454246,798654422,982084080,964168153,247453861,1833862,99268162,659694667,466104507,932209014,864422567,728845127,537854091,599199290,264178678,250863989,574407941,732405085,314042625,489474931,176295562,914244677,852693813,705387619,193242738,892738773,352048555,704097110,771025308,753975129,927527314,542054326,2994361,5988722,142029115,324378674,100232612,267369886,945624300,882384522,416443431,832886862,784668659,985124309,298874953,102595581,589967510,536599545,782218536,77865166,65277123,130554246,660510295,877005583,275946488,615306711,199915845,893431699,154588775,309177550,504746854,864753530,291783330,553114672,78102633,511352330,753667006,152737422,966787467,933574927,743434691,300957143,206901132,971318792,551792353,641951914,887092590,774185173,324319767,296313969,419748261,736668708,125202855,250405710,860306792,120041519,287948500,772974185,72505984,145011968,197340762,319569601,29058411,58116822,503961279,97170670,855412437,719283733,922189282,610817142,981054324,962108641,555626129,721425306,8695797,867937276,204728691,409457382,327387384,796008217,623487493,246974979,808073302,987531151,661621379,619686012,885900428,182865420,604993928,209987849,112149920,982821831,436804698,873609396,249429664,35442337,542946067,435717873,357909594,663354277,349837771,172902187,725024195,626724406,951883201,898886813,611894793,223789579,156249711,953762374,941520348,627312415,732152146,626637375,697801379,928373167,467201812,934403624,300174312,940164327,768557112,666818604,430052749,769678528,637336196,471510530,884736131,405930623,88523589,177047178,741193266,482386525,959636069,420122608,870743513,206500587,931686480,949884867,256838150,936095622,169293108,338586216,20108011,40216022,515421399,752804022,39087839,78175678,170102,340204,946184524,167781729,835787762,903545720,642497069,768924002,848555995,948817436,408127979,816255958,800214847,62298624,211839153,598162116,649248474,550398359,199342730,466361673,327607418,129788111,60519012,181516929,291695327,583390654,933077030,384594463,248685267,497370534,574889090,149778173,508531933,813332884,744233240,488466473,623778584,4368568,996107508,578055173,827804465,735970254,633530545,296440400,68756126,969743180,876576330,723047882,284529056,569058112,955600472,546169433,803429308,606858609,391311257,782622514,544679226,242364688,879318989,758637971,578342645,882174629,300235757,203149792,186638455,197248609,4796039,513889283,888015602,188499605,180716688,503135262,412392718,986465265,744612799,335327753,188776829,910205676,736820167,473640327,438152515,953148782,574653619,149307231,898195178,851342559,30893933,76564644,524487579,530536325,132326487,264652974,436939730,343683655,215324089,564898148,437093697,270599954,464012989,329405798,476278405,952556810,152525842,639543549,539816971,508927499,355269900,826589616,330452844,660905688,53392193,5534060,69632488,139264976,254644395,744092152,539703029,555053484,899170215,798340423,422351818,444892614,151256959,504363114,893778023,787556039,802071847,381737209,85245710,493128509,945208231,475863350,279284954,813432374,905487747,730092313,198445481,573858992,640307357,280614707,780620191,211244466,611704170,223408333,494598748,968788563,176505672,286582450,993252097,986504187,529362547,560946912,386341399,989315317,14725758,29451516,215685422,95948827,463209666,847826556,571585155,357027634,71359521,142719042,128278247,45877819,700894880,39614801,668371163,336742319,338115610,570799830,972926972]
n=int(input())
print(l[n-1])

Measured memory_bytes: 3704