#include<bits/stdc++.h>
#define ll long long
#define N 3001
#define mod 23333333
using namespace std;
ll n,ans[N]={0,1,1,2,3,4,5,7,10,13,17,22,28,36,46,58,73,91,114,141,173,213,261,318,387,469,567,683,821,984,1176,1403,1671,1984,2351,2781,3284,3869,4550,5343,6264,7330,8565,9993,11642,13543,15733,18252,21148,24471,28282,32646,37640,43348,49867,57302,65776,75426,86405,98882,113053,129132,147363,168015,191393,217833,247718,281468,319558,362511,410918,465431,526782,595778,673324,760423,858193,967866,1090824,1228588,1382855,1555496,1748594,1964448,2205613,2474902,2775441,3110674,3484419,3900879,4364710,4881038,5455530,6094423,6804608,7593660,8469945,9442651,10521915,11718871,13045781,14516110,16144682,17947754,19943210,22150663,1258329,3956493,6937757,10230528,13865973,17878219,22304678,3852949,9234551,15165200,21698597,5560106,13480612,22196944,8452486,18997661,7257333,19998065,10662272,2702273,19581271,14774185,11768782,10733352,11851360,15322626,21364871,6881780,18798125,10728099,6310717,5878446,9792968,18447464,8936113,5056798,7314372,16257181,9147536,9965427,19412966,14918745,20642967,14149218,19743782,15148255,1506470,3391465,22146838,12561535,22879162,8140756,16862250,4378820,19524012,17975888,2271491,21821681,9594549,15465997,19572399,2330619,14460366,13674024,4702485,15988673,6383984,5179366,18806390,7539811,2203895,10880603,18955285,12497936,1649196,20675616,11363645,9750054,6191673,15438876,6715859,20471857,5140092,3901808,14792260,14146029,3385453,9149288,13432491,400741,3217410,10879977,15070580,10350734,17705424,14766448,6053805,23231697,8718296,2645596,3175808,13503760,18885398,10355306,8473854,17099843,530055,668210,20898420,3325724,16059508,20535443,12219388,21355399,20435221,18385048,14814344,988912,7540938,12244852,11205855,20123583,5645550,3472706,3233273,20120645,3312559,1167892,23219797,18961424,20111554,3023515,7926113,1660713,20605185,10449089,16180003,22279331,3156184,20485608,17482311,10110056,21927872,19241098,9927814,2610456,12879977,23243625,13507963,14936696,1565406,15348818,11860736,9890904,8331267,20365610,15026901,22806792,8721275,2853734,21786921,14282723,17961852,13681398,14370850,15029686,13990609,12158181,13670066,4698752,3852656,20902292,17304009,8589886,5443237,3539976,22324432,6144779,7934964,2215602,4286126,5730358,6462742,3454399,6391007,10421460,19608386,4596222,4804070,2016469,9046305,371463,11788054,12681026,17995341,20209945,21776634,5032520,3430126,17806319,11589056,8712028,14864968,19239156,7462392,9613275,20750875,4585198,4475622,12460807,17265103,22073561,9789744,19997732,12124164,5797221,9689644,19965089,19754732,4250542,9665076,7461188,15605238,8416337,288965,1712902,13080484,11579618,3561333,4579349,19749741,3549948,11994117,13255941,13325600,9757798,10449865,4190508,3643567,1232260,5685068,144705,13413324,5715603,17750968,4951488,16300644,225177,14230570,4780969,4814224,9455841,4780515,17662192,9106460,16666033,19306635,1316017,16361472,6056322,15328099,162135,11328191,21010280,14061422,8962024,1806443,13374756,1054263,4156747,6348543,2424499,11969725,16030722,5061381,61449,4469045,8114980,3707396,156472,19752111,20157038,11764255,11717104,15712833,6263592,19513883,13755444,9818411,18078770,17500146,20217035,2857119,774857,12755974,18984818,184486,11343872,19011085,6942516,20933545,13153292,6193584,3582255,13976613,23213627,12807255,10926736,6975847,8853414,17812547,4372012,2037531,21447148,11736471,9147778,18062530,16980596,4836520,11269852,8476916,21451811,2036400,22437040,7173208,7180304,7922574,2748654,9172011,23222766,21913879,22917098,720408,12648710,3789742,15880702,13193363,6586838,20755770,10137261,2265604,3671660,9782798,22737510,20705486,17829145,564249,5098973,17816720,3405269,20164726,5442212,13828979,11939481,5132215,17658515,4913222,21308691,14015874,6915275,2558621,3895481,15010154,4514436,4141770,17293365,6635977,20644597,2928800,5010185,14347764,6507926,9611085,905242,385601,411117,22354379,18840464,7109942,4696596,21855437,10314049,18962834,3249263,15455618,18568625,8017577,12229105,4307436,20280827,5897674,19084355,15869267,334475,19882036,20064232,9985538,15298521,1589225,16341497,2408302,7361217,13592242,21881918,11262353,12794902,18846755,22180799,18138533,11946005,22112601,14042594,15680207,139371,22539549,14175676,13729133,3772511,5404341,2242973,1758502,21390006,17407565,10132798,19107393,2931117,14274069,14012386,7321353,17880033,6616652,6589343,19723985,11217280,12399279,21906371,22446986,17198659,22462219,1129126,16819880,15733576,13756253,19267216,18406520,6408939,16628459,19582024,21943569,18719717,5497258,14557583,597297,18812433,13136159,18794999,18740230,11367061,23043420,6580575,13876694,6722989,11334235,21466807,8403530,11282861,11357573,18267076,12170934,17439363,22257610,13759623,9007798,19069204,17306591,12450067,11405861,18888720,6568694,6423393,17285466,10115184,2581046,10305717,21761311,8708735,20807857,6803966,7717490,3992457,11093757,5777911,8294633,21859514,4577124,3106674,22514763,12782943,6912796,12622499,4074227,19884337,2559408,110359,9732416,20479320,20592731,9546534,885376,8975331,20006841,3593627,22486599,11631367,13105463,15627128,9282315,18247610,17634393,16873864,9492843,19936480,9075409,11268542,476518,15162608,13801989,2279623,4317042,8017354,20829640,20571315,2060369,9359108,20408221,23333055,12047412,16315687,881657,2921624,8039899,10153484,14804438,1096388,4078913,16798661,13132459,4352245,7965864,18065424,951008,11773744,11242779,7271889,3629400,5555274,20298057,2839791,1252774,17104692,10314674,21508036,23043335,11287427,12618492,8178508,1311862,14587503,13598746,21308996,8645865,15167312,22003728,6286176,3406414,18409649,20388784,12645070,1944464,18729248,4941825,20560541,14473345,3323028,8256287,2042941,3107369,8516237,1822108,13664903,9400714,4496847,15725845,8448355,9637690,1920922,12871579,5047348,22720731,850835,20513754,9590136,4305088,577873,21892307,21697961,12776055,9890623,20571554,16151980,11589459,17336493,13211277,20267236,10901389,20098242,782474,1856846,8081182,13866932,16013778,23158365,3118713,12673105,2043077,18268354,803763,15546032,21395677,10321803,19374607,17914297,11408490,8313974,11894583,7825679,384288,13180611,18459011,15939958,4441201,16849348,12341021,14907032,4596344,9650522,16899643,19699222,10284241,3646546,4090933,1216728,3325906,8559182,4224059,6104061,3510408,18962138,6932665,17996768,1261305,3673800,6826739,14585752,8725041,22443047,15817744,5243542,16820531,7730273,957121,15998833,21946788,3705071,12999492,22374126,16432298,16002245,4339121,15066164,14676815,11205285,19204290,4448579,17644245,21036558,3402411,3242896,7649089,21845359,22444805,1388086,1695192,16489603,12052782,12852564,21286895,4915394,16049848,6614268,3784757,17240068,18390509,13228791,20676616,8117155,3893272,17999229,6549236,6756844,13902370,16849257,7265085,20618111,2494969,21397023,11394773,14625345,12162755,1709401,9317586,8870446,22855015,11282903,284823,10267693,21346194,18833214,18515896,14476478,13119376,12936530,19216971,5173899,12686182,22262897,17521866,20864049,22218513,6195700,22852359,8949929,9801780,20791923,3564444,3408684,16535257,11397111,18127258,503931,8617035,21452289,17741021,12728153,4413654,16589793,5958853,16032758,7334220,22034002,12458458,2392025,10269985,13914680,5461558,15770484,16006329,9697722,1584755,6272538,20657774,2816563,7528373,5610429,16588778,12593048,20612974,18285573,7533778,9431924,20934884,11181568,14599537,21645593,9632333,10589302,11276746,15775742,22929108,1381455,2446341,15959978,13814329,6525982,19907750,9817545,7300254,14713010,1055925,6432486,12829269,21615136,15400821,5872337,12587865,12954916,1101586,19636803,12868319,755030,10903828,22170784,11844755,2017692,22139050,5197280,5114800,19521431,15385338,8178007,3567375,12073282,13795805,8221460,22932944,22963171,12566401,7640038,6665568,6939451,5538101,588240,18966140,15428912,2696514,18443594,14731042,14406959,18490271,1038448,19682731,10792224,13758991,11381417,20493326,6216607,20047154,14434880,2956023,13854740,23275267,12658004,6410105,15906329,23177426,7917482,3711608,11026972,8415178,22311648,12906875,17980820,11497891,689635,5697935,10951751,19247103,10754273,13605127,16647211,19045668,22758719,5954556,15070548,16300974,10708663,4658137,22169614,5891862,21154563,9917793,3302814,11105462,7278026,20071846,11206689,16307375,6976997,14955521,22939813,5582366,16211424,17564865,2541528,18272604,10259087,15140457,22413036,19754464,1488545,20596413,5962583,21847046,16015364,12420768,2734707,18000000,20813107,3835428,17226085,16838260,2715810,11296907,13079030,1807985,12572382,4365133,22040610,23140532,12200300,15599176,15337200,10540736,21033940,13477472,6105045,10439104,17879325,13781289,18777456,17886912,16086529,16212440,17748475,9093593,545862,4356296,2872537,4651940,13599574,5234571,5727519,16986612,6261779,14666958,2850243,3836734,18485251,7495852,10464237,12452808,20396851,21502515,4575307,20608007,17332054,16340942,16481854,13580987,17964240,10281237,8232120,13978003,12144547,13358483,15805555,22579759,20318225,7082993,23175604,15074833,11484956,8868289,240959,12396357,10599695,4086384,15909532,3473028,16225473,18237463,10559320,15360770,3148379,1723128,10963356,1546100,6491580,8698653,11706696,20079756,15908281,10995059,12698516,7129124,6194900,18388482,5777157,21708662,4900630,2066292,20729042,15182080,14866367,14704683,17768615,4402614,21764035,6295019,6132351,21417093,22014666,5263584,4090139,9179185,898385,5728931,14943961,7669506,7693859,15756152,9688290,6414258,16918687,422085,16295965,20686236,171543,20165762,1110273,7700148,17913571,4851629,8750419,7719312,6582548,1704886,13808216,4924495,14598378,8192755,12442963,17192314,18316851,8506238,21803424,9236219,20161553,3478964,4283382,13364995,18985126,12267152,19584565,6347530,15905354,9564936,2890188,15468937,21693105,6146966,2063897,23086762,12978669,22682475,17871474,4678752,9340311,5876599,13928927,18211238,957187,6091801,10383154,5532301,2098819,5559871,5016575,19338906,19195572,6917641,21542535,21849656,12246962,19160997,21934401,4583388,21348886,22872495,805544,6889312,16137362,19641938,687117,11709690,16969608,7341712,6163770,11106596,8135094,19536209,8502577,8057112,18085415,3094022,345332,11102834,5580432,15350844,23316540,19709958,16658720,3932613,18741610,16212335,8528956,3149959,7237660,550366,12602589,8839427,13780487,12501427,744383,21589803,2023925,15585140,17060134,11975621,8425766,23055390,19684525,22393088,9363457,14302994,10502720,1430580,15059133,18445695,15797133,1571611,18923968,4508658,6987246,14952717,8594161,10519701,12096890,520749,2914509,449951,3317272,22713422,19422911,17270898,3130555,9194237,4801869,15254617,20723272,4922339,14411037,10333679,2142238,16184283,17254194,7129480,3810241,5448092,11856000,11726796,20948679,19631186,1215196,12688780,10201512,22753079,6605295,4600652,8923,11915279,18408511,15981846,7455970,5357207,901498,11606099,4473991,13548300,7738660,15529046,21064426,19978993,1818749,17135953,10727503,14028888,13871005,12984571,15294597,16827897,10668865,7364477,2114557,8816927,18787882,10676424,16345320,17209508,13307688,10264145,11899389,13578126,7360240,8736066,21466258,7879366,20824399,20233469,5378726,3222722,15511261,13819119,23004236,12807362,2392786,3440725,22833927,8265843,13232935,48488,4218504,13459807,18539541,7819047,16235085,21229100,3536619,15532119,2623105,17696760,18761019,7894372,13000127,6566335,395989,3585958,660790,16438932,11563757,4849654,18231024,17165196,10695149,16863184,19521607,9247634,173594,13520092,13026514,20202330,2522971,17292272,9732809,13896575,7320753,6928858,19666555,20644092,19360163,11983811,16662091,17438245,21144459,8533134,15573425,1731522,13833407,17782773,8911145,19521174,16182011,18653954,862906,1704441,17757382,9325848,6955999,2278064,13189052,19097221,21066140,1691222,781644,6773919,19045219,634275,1986151,5027273,4120567,3000183,16176517,13018827,2258026,12128194,8482895,15635631,3646794,13193815,13276610,14032360,12985416,18932961,10053201,10757783,5714020,1441362,5307920,12525872,14175039,8994068,9579081,20336593,1397921,18548444,14225943,23312260,20665157,20515083,7777659,13168442,17656402,14780079,15649158,13220543,3928466,22525738,18735729,10875365,1466510,4269940,7476680,9969354,21156699,13875230,10316196,14489403,11223427,12779932,8038430,6196426,11419650,12174395,2290010,7108990,18620366,15351185,18491088,16386313,6565601,6849389,20368733,11512529,21950683,8026891,11129119,4170889,14772245,4026634,15986312,2444729,14257703,21705860,6307081,18719465,22228390,5865932,2596273,11117617,20061657,12710746,4527615,3404057,16622228,20378038,6643338,3450785,17626355,5596029,14519758,13730802,17779514,2789220,1660162,9383303,13713138,15902369,11169781,9536172,4596939,8026847,4528448,17904188,17852567,22548685,8000396,15227843,4546093,5542135,5542396,16284399,2446884,15657825,4194531,2686844,20333237,12949967,6245123,15821287,6884670,3246244,6740326,5681701,10107130,4656740,21542217,20340072,5384239,134126,329398,19485593,22144466,4422438,6777332,1866865,19930698,21535724,10817269,7470046,11033589,21685167,3784898,3993571,17338101,11054749,20437191,12817510,17542639,10378375,2061889,10341627,4408662,18164428,14707359,15943459,1853664,2063029,624505,19283697,9500817,11905489,4295883,17943044,2189027,12620939,22667731,18080702,17831095,14275911,11880726,5738498,9500036,7900333,20386545,11751980,22213782,7654712,9234351,19560621,9050448,2024697,6141785,2248655,18969445,1405010,13951969,22430747,22479692,7587279,9454262,15930804,3374122,10024890,18963458,1692245,16017929,16581675,5330729,17576832,8486442,7636515,7947277,19392504,22445782,15114093,21140186,17798552,13163833,20957664,8751441,5602419,21174622,3472239,11120406,12908280,11088838,12347251,13432286,18920431,8356417,19361351,6155107,14476238,7760580,17223045,6646234,12931361,12052983,18683755,14504511,4225714,970639,1564964,20923190,13721637,3894981,10803734,21963609,3655023,2853469,15588173,3465416,16110231,15007756,15403489,5517692,14847411,3117451,13312249,8046722,22440014,21048556,21099185,17955433,12061933,7403343,16455923,20601710,11510302,1013914,10290094,16705585,11129061,20617749,1465834,18059202,18408125,21997682,7274654,21714048,12075332,9772876,17840109,1540814,14654095,3613787,5476776,8281379,5301965,20747828,9029902,9919588,6005479,12369372,3296203,1071527,19214908,2854432,4794305,15357740,22688826,16349865,21173552,10737666,20807644,17380636,9118340,5261665,10395457,10716069,19021024,17038180,21225017,22357894,4963108,10667788,9740609,18190790,400166,10432550,16669681,18622264,83529,9721758,4334988,833374,1660496,21085945,22650566,985383,12058253,6559175,8534940,22283158,13277959,6396328,10427833,476796,13536176,653071,19925233,1959919,18777679,10380653,23183492,18471649,15441048,19228541,16898728,6040135,9393891,17368746,908446,6262643,5877507,15551514,18264001,23281531,11777795,14289902,2046340,19985421,10000359,18375595,8743637,10399069,4547769,18693602,4287354,19538972,15217395,8525507,21531007,10046319,21380859,7395909,7543572,19011243,156945,7074435,17539882,17502565,8334286,5616412,21216493,2409315,13183015,4958611,9873757,2975204,22663661,11687923,10815927,11857987,3019179,23275321,19149076,17826631,16395059,2695226,23002321,8614084,18793267,18811883,13875153,18430869,3355117,5009099,15550989,924627,2805078,17054496,13190694,4714014,10260046,16893695,8344242,20638099,13054935,6798428,2925703,13003959,2610826,8475986,15950305,15510003,1824103,1005807,9179108,22844168,14848561,15464561,22358654,19568135,13227798,23087617,4490879,15488900,21879520,16498011,14796372,5751270,17406708,6896826,23278388,22937776,22640798,20477391,675008,7391073,14804959,13870748,451111,16883289,14860867,8534366,12928279,6196827,14110375,17450289,13386463,8864063,261274,3427060,9681467,8449070,18014538,20046851,9840540,16278581,19466380,12639588,16585693,9677372,10006239,12912128,5999262,4006506,5216448,430713,12571006,13596788,20034215,8685101,3361367,10979486,13293038,14478914,1313413,18659796,5592444,10209094,18429272,9331045,605530,11213131,22923586,4452022,11792880,8514307,6502462,13220131,12074362,14467994,2595090,8011324,960715,14222713,17408270,3118252,3837913,17638658,14939457,15872705,18813997,6202598,11687972,12391398,11806893,18149431,6106470,8376001,2736282,8036264,3842121,7271628,7392512,4783486,4385751,22164688,2224061,2937827,16358131,22984476,8691704,1681314,22929668,10121004,10967307,192415,15399386,23253117,7670367,21672703,16114697,3908420,8718689,7526217,5679559,22304768,4400271,23043899,4476260,6777895,461053,14026561,13886647,11603133,18169785,19208468,14150517,21732978,10457356,8963004,19191547,15138754,21352024,21946820,2975682,14643110,10551437,21034523,12854437,12515716,11415470,15154744,16591713,1351460,2770733,7530543,1718423,18263352,13359897,17288206,15782827,773487,3151978,19243940,16047964,7586581,16054926,2995014,13810639,14906241,10852891,22682943,740363,7172069,17234680,8160185,14598794,5676653,13801123,12530772,12893515,3063566,12711360,6382703,20798398,17335110,10716107,9309718,13477418,17938410,18236333,22124163,18399025,11713204,1519007,19555512,8308990,15998994,8607871,12124402,7931463,4166942,10175416,2466105,19574453,12090046,18958458,12425612,13937804,6614201,14363435,7669971,20343423,23101252,10142692,9344329,17956551,16656544,22016128,6825740,919021,15974041,17439175,5169724,1646662,4608413,7991598,5956978,20265570,12163102,5811672,6580878,1940499,6143335,1052543,20111747,16045424,9433008,3057223,7277985,13851998,13543311,6843673,17822901,12954681,11983773,10492447,4157564,17352403,371785,10672141,22531804,21828213,4377143,5562256,16700288,22449088,13079194,11440240,17656757,11571934,3258472,14302019,13909862,10787210,5563194,13662026,12122608,8298819,5646804,9259802,17726943,15882529,22437346,5459604,10230024,8785738,17871253,19125731,19487267,6147027,12135750,7783412,14441308,13409389,8174655,17098291,21804407,5505640,14030300,6429168,17629919,4324365,11394026,16451115,3880540,18143470,13984624,22948965,15284478,18470187,9034189,22470633,22899314,17587685,13817036,18980786,19552415,3246657,12739826,521994,15884322,8314141,10316322,18156573,12527981,834312,8298099,23316325,20272016,4072901,11026116,11201852,6935224,11608253,275579,17421169,15944681,17485284,4896692,14460482,22110236,4255611,22118650,11602980,11094742,19141241,10459254,15566649,20451544,18738403,16347067,10552374,16163633,2163314,20971159,12136414,2771278,3984376,16147158,17780676,11750074,16799855,7893016,1222957,9915080,19296884,9585607,4573717,14305493,14927480,4189873,15882461,18971072,7594970,14634029,19690263,7334380,19888598,3993215,16456027,17250786,4967919,6238206,1133583,22490548,6453252,17997360,13371311,6443023,20439859,8887060,17982894,8189997,15457174,17062433,9156264,23166446,14568508,4646775,21648082,12216190,17394583,18316967,18602527,11410362,12122544,19457239,7791370,4571062,17575333,5023464,12691093,2990297,21726743,19649220,11086926,17568629,16113071,21870454,21421359,4123746,10843981,2610196,3938898,9178944,1243358,18505710,20513821,22352913,6188415,7699399,21320352,18295784,165887,6814634,23029335,21300355,2879930,900953,20057945,15825983,6713732,3380448,9442358,21846110,6473402,19835834,1041836,5896251,2385586,17868525,7815434,8045618,17429314,4339580,11215277,14458847,12923935,20716910,20577224,7768528,20761780,4295625,5613138,3520856,16973258,14587359,2915935,22142084,16461156,7428061,22340446,12288516,3115818,4460214,15273421,6347118,7478137,2062902,20430539,17175618,15660975,11355863,10591581,10072836,17958178,12527261,11967297,11145773,6143601,4875357,7727801,12229733,13106301,12053216,15316227,22221386,20224519,3029427,22643292,13576367,942205,20243847,17244716,15555355,2763558,18123618,9899789,8143301,20467884,9436308,23324981,18861750,22183087,16636395,15389011,20760857,4917674,5959685,22047737,10343438,18913718,20820082,14351179,15227214,10464318,4931,22459894,11265887,4170358,12869957,14248846,20378784,22338270,11546982,20695311,12536270,22868453,16760825,4700842,4926341,937851,20585233,3243999,11718644,13641204,12553327,1075700,20334653,17732659,18928992,21684348,8872634,16269891,13894042,11508855,8445980,1172210,21929738,7098773,98669,5199153,2082716,15693285,8237972,22964798,792963,373689,13513552,23114262,11777459,10694721,15272780,5262075,22094224,1312724,12061596,13747334,16502869,9393762,11114915,7802791,15543847,18572373,16536132,5782896,21979686,7230876,10640801,17488933,11530544,12590368,2668791,2600221,19635640,11241537,2833530,1063247,2811018,13689176,2553347,20249268,14908686,13929702,11108834,9041989,5455702,19558134,16168729,13412708,2342736,6813980,21252160,7629950,16670095,13321554,9840862,10663658,20916219,2910823,21096305,3522847,3437804,18400395,13813196,11793019,22247352,20446454,6477731,17660635,18572181,19513131,12692310,4096778,212645,4686671,8663640,21580684,14948775,7883172,22333063,3928268,15689209,12513077,12885531,14436315,7720710,11298106,2125920,14898495,16121542,6105246,15386369,17142314,21423865,7847974,5004428,8983843,349747,17805621,8478090,18890182,20695768,892849,9430084,16575882,7631212,19637904,2719529,17095192,14210524,15210040,6732379,6423169,3464443,15390282,21002770,16930523,7703549,20603462,13742440,11608885,20985308,17456190,12689510,12238862,2414896,1954286,474821,10195925,11910051,5509362,19800655,5521171,21555351,6823374,4632003,6319937,15632975,20066987,23199661,6917341,14994912,15761860,21213309,7513007,22415973,23275881,2848546,1809329,14244969,2778304,19078791,16686516,12448933,12298314,21973020,22913609,11034748,12361955,6786218,16010163,5840347,11624594,9522806,21410019,8147381,22917355,19276795,23312697,3053245,4941165,18883782,17995916,17738607,5002039,5904998,12064698,2661476,3816788,2442538,14250295,8404338,9998711,11756526,12665640,10000823,19121950,21084369,10590091,11922061,9179196,9445262,9602806,7444622,9607361,18559210,11949843,14772696,23304226,12632971,14988222,12732304,12175615,17164748,4872083,20998648,15807222,1686591,22904840,4186797,2550160,3161554,15326949,22310681,16035087,21413289,11436924,13390774,5552185,738584,13863919,14448027,7668579,14948789,2906118,9209260,12614063,4667042,13272007,11100367,6797879,4241214,17713697,13165135,3125657,20256050,15203901,8834502,18574712,5112918,16099970,2519309,14052127,14464543,20401483,16193940,20483654,4613629,15983188,6947196,20086439,14312338,18644197,3991386,16436162,16519591,11624762,1095607,9052196,19917799,10836147,11278753,4123251,1730647,18219878,4643367,22218247,22806819,1855323,1142052,22687423,8639923,6675030,11230542,21564447,4380459,19367455,21685404,15612612,9012508,16181628,18359254,4458565,8314850,22608085,12814277,11319090,22653739,22356787,2954954,10199698,22712768,14215650,18969062,21518358,19269710,5958816,12463612,8394807,9485617,509077,9752777,17726060,13772262,738587,20764869,10017314,23222857,2366029,16716664,13122610,6723241,9950039,16971342,17479788,17784933,19533113,10643128,13810299,20120885,22691893,4566087,11466990,15936209,4135194,343522,4974381,6444619,16799848,11662015,7250592,13920814,9412087,6882834,20249646,22391134,13076489,10705268,8999057,3455949,20232541,9884874,23230461,8139747,9200153,12598747,6134725,4504927,11135657,7227997,15834848,12116461,14833095,9592769,18222412,2082673,16123298,2533619,21261482,16149531,10301300,8856216,7595876,9393662,7126089,2281688,7934035,12947052,18956951,13339111,13889080,3357192,20651594,10668721,18517347,17010332,5258249,10932039,17138263,1255772,20283898,782902,5436619,2161974,17399466,21349449,17073180,18491150,5385464,15018892,11093781,6719092,19276315,5127319,22161555,1845415,9985851,17987547,1273002,14907833,21998758,4208824,1832905,14358398,22494672,9809801,2484781,6146717,403044,9649981,20038426,20167442,19352540,6503656,18245800,157656,22667490,10367964,2159728,20523854,17624764,473298,505469,15514638,4971692,13978833,20351392,12337876,10744424,7181633,16605461,16291731,11605972,18973316,555339,6869872,1526313,22782791,4884470,19891418,21719638,15384406,19411212,354796,2416259,12065007,6367953,1743737,823616,12448097,21916337,2531941,17554346,856779,8819851,3767312,12055093,22882829,12973510,10280392,7589727,15611052,21636961,2745530,22109575,23184021,15686507,10901143,47178,4084028,8473721,23278356,14309904,2242422,14674533,13210933,620200,4271379,11957951,20811203,21958453,7479990,7262484,4497973,6984418,20102501,11228286,5239526,1749902,16757444,8174274,8642487,17957544,6758812,2217243,11238216,20948835,4283499,8568090,19468186,13323464,7005478,5481015,20684365,8920017,15955859,908364,15450423,4481842,8273880,1602491,16762311,596587,16870255,23056435,4041182,22514958,6305359,21972946,19996128,6717732,6539295,7693498,5031622,18615986,17375913,13619956,8790025,13019229,771994,20148166,13584895,16307486,14367067,15248873,17543680,5987875,7763593,16466357,12441084,14801552,13667523,22366910,8520150,9377421,18831261,3068091,19087285,13545573,16675452,12955564,8574959,21038941,17295020,23001375,12942438,5392767,2543800,7220550,18699181,13784057,22558130,7493374,8271415,14880113,14455741,17716232,16823075,21487326,4048983,21709777,14083279,16032957,2447643,23049053,20885445,3404325,1188708,20202487,14133961,2748471,5407520,15663614,6900281,1368741,6361092,12568471,6541600,14806424,4146769,2696009,18832340,9549311,17404835,15749748,4666395,4956971,15771105,10267137,7173097,17589091,3649016,19685298,8185074,8447077,12016047,298774,10922693,21412537,21970370,10128384,10811918,15398449,5738593,2843448,5886161,19124713,7701376,22137177,20383394,5409625,7901140,7295259,11145930,13167985,17513971,11309533,1425834,9210664};
int main(){
    freopen("get_bag.in","r",stdin);
    freopen("get_bag.out","w",stdout);
    cin>>n;
    cout<<ans[n]<<endl;
    return 0;
}