#597383 (C) No.502 階乗を計算するだけ

• 問題: No.502 階乗を計算するだけ
• ユーザー: tails
• 提出日時: 2020-12-25 15:47:30
• 言語: C (gcc 12.3.0)
• 結果: AC
• 実行時間: 2 ms / 1,000 ms
• コード長: 61,058 bytes
• コンパイル時間: 406 ms
• コンパイル使用メモリ: 32,464 KB
• 実行使用メモリ: 4,348 KB
• 最終ジャッジ日時: 2023-10-22 07:30:09
• 合計ジャッジ時間: 1,930 ms
• ジャッジサーバーID （参考情報）: judge10 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,348 KB
testcase_01	AC	1 ms; 4,348 KB
testcase_02	AC	1 ms; 4,348 KB
testcase_03	AC	1 ms; 4,348 KB
testcase_04	AC	1 ms; 4,348 KB
testcase_05	AC	1 ms; 4,348 KB
testcase_06	AC	1 ms; 4,348 KB
testcase_07	AC	1 ms; 4,348 KB
testcase_08	AC	1 ms; 4,348 KB
testcase_09	AC	1 ms; 4,348 KB
testcase_10	AC	1 ms; 4,348 KB
testcase_11	AC	1 ms; 4,348 KB
testcase_12	AC	1 ms; 4,348 KB
testcase_13	AC	1 ms; 4,348 KB
testcase_14	AC	1 ms; 4,348 KB
testcase_15	AC	1 ms; 4,348 KB
testcase_16	AC	1 ms; 4,348 KB
testcase_17	AC	1 ms; 4,348 KB
testcase_18	AC	1 ms; 4,348 KB
testcase_19	AC	1 ms; 4,348 KB
testcase_20	AC	1 ms; 4,348 KB
testcase_21	AC	1 ms; 4,348 KB
testcase_22	AC	1 ms; 4,348 KB
testcase_23	AC	1 ms; 4,348 KB
testcase_24	AC	1 ms; 4,348 KB
testcase_25	AC	1 ms; 4,348 KB
testcase_26	AC	1 ms; 4,348 KB
testcase_27	AC	1 ms; 4,348 KB
testcase_28	AC	1 ms; 4,348 KB
testcase_29	AC	2 ms; 4,348 KB
testcase_30	AC	1 ms; 4,348 KB
testcase_31	AC	1 ms; 4,348 KB
testcase_32	AC	2 ms; 4,348 KB
testcase_33	AC	1 ms; 4,348 KB
testcase_34	AC	1 ms; 4,348 KB
testcase_35	AC	1 ms; 4,348 KB
testcase_36	AC	1 ms; 4,348 KB
testcase_37	AC	1 ms; 4,348 KB
testcase_38	AC	1 ms; 4,348 KB
testcase_39	AC	1 ms; 4,348 KB
testcase_40	AC	1 ms; 4,348 KB
testcase_41	AC	1 ms; 4,348 KB
testcase_42	AC	1 ms; 4,348 KB
testcase_43	AC	1 ms; 4,348 KB
testcase_44	AC	1 ms; 4,348 KB
testcase_45	AC	1 ms; 4,348 KB
testcase_46	AC	1 ms; 4,348 KB
testcase_47	AC	1 ms; 4,348 KB
testcase_48	AC	1 ms; 4,348 KB
testcase_49	AC	1 ms; 4,348 KB
testcase_50	AC	1 ms; 4,348 KB
testcase_51	AC	1 ms; 4,348 KB

コンパイルメッセージ

main.c:4:7: warning: type defaults to 'int' in declaration of 'tbl' [-Wimplicit-int]
    4 | const tbl[]={1,324433771,266627774,830325768,143398913,453338976,261812299,159242414,242403290,848707231,571624523,896472930,853955644,511680662,188085513,377485740,499068954,758687219,628981142,25029286,992014811,187936348,428296160,946903047,618528731,670984002,615735236,305727387,360747062,312757388,98784756,673862316,677867054,585794267,504619813,392218114,535124551,758638376,333701,536048481,454247860,749846616,280474045,723912803,471630830,115695991,791328836,362219177,98043818,695110284,612237083,931444591,817525007,44728694,265063293,896899192,168955095,422415850,242264104,626510636,509198437,104471990,634734493,799688208,699421653,978168021,115482284,263028001,420860026,385681570,47835225,945608277,568475467,513640322,140209956,519946071,139524250,827375520,113325442,710237563,30760690,521379079,550668600,55925753,892650367,144064114,389123151,799629879,177919430,900246777,790440649,703631857,757754923,297983078,190701292,208831513,961631507,32474831,344128287,34688847,110699143,871300457,914570133,678361846,467750062,274950104,781284234,236576522,20544681,740186734,999785362,124387434,913579594,767819151,46016623,460503998,681202998,576197483,866339629,188377097,738337272,371163316,737269114,905129081,374399371,655071146,252900814,630904881,68604898,372081851,943588073,984016611,932582897,447049874,261316272,738575040,357288841,66807520,838556552,929708503,525777338,614427180,665593661,554920702,14179475,235228651,434924926,868900960,652833241,172139783,902626430,686084808,543997210,928575982,511489782,997779212,216644668,414868877,191040002,192441259,310065911,484185684,25900410,283878020,283188100,885350061,922069499,229176627,151099095,780150763,23804226,667956575,288072194,486781978,62386924,97673333,769913391,423714345,941885692,692166911,187490645,573776054,575642313,365418142,414703500,174588250,661125687,53289949,135778768,371612627,445740488,97613815,30475

ソースコード

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

const tbl[]={1,324433771,266627774,830325768,143398913,453338976,261812299,159242414,242403290,848707231,571624523,896472930,853955644,511680662,188085513,377485740,499068954,758687219,628981142,25029286,992014811,187936348,428296160,946903047,618528731,670984002,615735236,305727387,360747062,312757388,98784756,673862316,677867054,585794267,504619813,392218114,535124551,758638376,333701,536048481,454247860,749846616,280474045,723912803,471630830,115695991,791328836,362219177,98043818,695110284,612237083,931444591,817525007,44728694,265063293,896899192,168955095,422415850,242264104,626510636,509198437,104471990,634734493,799688208,699421653,978168021,115482284,263028001,420860026,385681570,47835225,945608277,568475467,513640322,140209956,519946071,139524250,827375520,113325442,710237563,30760690,521379079,550668600,55925753,892650367,144064114,389123151,799629879,177919430,900246777,790440649,703631857,757754923,297983078,190701292,208831513,961631507,32474831,344128287,34688847,110699143,871300457,914570133,678361846,467750062,274950104,781284234,236576522,20544681,740186734,999785362,124387434,913579594,767819151,46016623,460503998,681202998,576197483,866339629,188377097,738337272,371163316,737269114,905129081,374399371,655071146,252900814,630904881,68604898,372081851,943588073,984016611,932582897,447049874,261316272,738575040,357288841,66807520,838556552,929708503,525777338,614427180,665593661,554920702,14179475,235228651,434924926,868900960,652833241,172139783,902626430,686084808,543997210,928575982,511489782,997779212,216644668,414868877,191040002,192441259,310065911,484185684,25900410,283878020,283188100,885350061,922069499,229176627,151099095,780150763,23804226,667956575,288072194,486781978,62386924,97673333,769913391,423714345,941885692,692166911,187490645,573776054,575642313,365418142,414703500,174588250,661125687,53289949,135778768,371612627,445740488,97613815,304751648,70391685,739226065,853777159,852115762,192736441,618710662,584650800,346355986,551332901,638450311,930562061,53961777,475444824,447150590,81697110,325422761,740033834,900057076,782733667,772458763,861611254,517596352,230858611,226570408,666456829,509508556,442821119,176355494,307057787,999000333,820600140,799057970,568856408,703695721,926222820,57843405,24624221,237833530,415930940,185123041,154099576,150454919,202866641,725000676,197877018,14867475,796826102,593572225,921343160,988743437,457068873,243544982,438531549,447193621,469837882,998715769,216012875,6015546,70223107,150991806,781045561,266292495,500217471,661521818,820623147,263858485,153422047,342464348,424046699,816329584,949583085,17577568,571681107,462861579,466667296,674682451,197463026,916880971,453934159,383686012,554887988,796494802,361243513,432981840,98165431,235813774,536316737,610398706,435239347,949889445,674290114,907098938,3717999,507297639,260693881,544576713,645185814,50084618,986134277,985453385,631324749,870593629,767749671,718012799,723795566,252040503,345486471,252565947,989326553,217450711,813488949,358470553,382135258,823772629,745776500,467077296,931905460,63375940,578999159,445687953,283180516,193294805,82518333,349739748,919888149,288892429,921053035,935785718,568269187,19867527,985627161,306581870,418023313,447522703,742976544,21571371,729401598,829551293,152325957,865201736,483964661,47855253,139774744,801434353,856573866,366701645,719465465,581295474,422623183,588511460,949147084,963661846,731804603,286449173,872249539,399021988,907899886,391508508,395299756,355714393,5666594,216873815,676756627,80141870,919228081,26780144,821790782,927727651,683207233,82713305,196765151,516245542,851879921,598808017,101125316,831129346,634801401,591816148,49846307,686879299,925060596,30690095,929381274,359178064,727596461,587714239,310045924,89332899,110556233,157920447,742336738,200891912,127095759,112914042,353302130,400968754,456017908,220998147,730658822,421192465,755136291,880770941,390234072,228022618,875981227,702900932,91508483,490484751,154618077,733261545,153366607,648388045,278533479,832980851,535618907,765250333,532259832,513174599,219882889,134495960,638890321,898223968,578570868,330868212,824582734,125273466,774733660,526633695,763649866,387759220,820490332,722940905,841933433,293092816,551819737,697133540,837055022,910434864,140297338,984581831,21736467,844163143,36859236,85889080,933116606,741885064,166091777,554899824,37406595,612360011,916852033,82316639,249567532,891924110,372116049,717470752,744749879,452693190,516385447,754743960,407593449,194014854,974219216,738893453,9769800,881084046,597007634,318172487,733842998,892651237,179014112,433118818,539967623,41704900,502270496,136070233,773859935,286924865,222162311,642082453,773459339,997047905,310256768,380077125,944342183,766790147,608187027,92612134,863695447,720454386,316247894,723312114,642109532,480777183,889451947,945330897,682454905,309726525,687074277,834218827,258943538,123035328,126662857,73425086,35998289,651757749,850508264,894833240,54343092,571833365,160527425,229952461,431034103,641830176,280420238,348885565,950618649,684378596,548468477,774984247,429950577,632992186,836407389,357286852,345632664,422766362,491878296,122146344,428173510,987806495,784093071,111844206,55955551,170127945,240283009,789787495,173686755,191270088,35524515,792492008,216053923,674656512,658852249,40800632,551477740,988626439,126417570,656105815,868203370,109881136,49331419,278396878,540938554,217445957,926469651,327718530,109059369,857383892,516273606,134868761,389734149,297741272,217448817,41893644,568523902,253737981,542389497,869299419,948737815,335140265,151635848,279314062,820293345,136209946,659815236,339599383,772120634,355960708,978180388,763100519,765545585,152690367,907438349,791867040,267474654,212114357,179760931,766033531,137786086,224297761,516753599,848103299,546769992,752765506,249558132,177388960,149263369,824898512,118764844,773247346,739422771,52745571,575075505,237045382,41502890,378341026,756930685,65608629,616299796,602768678,301922697,365068656,767787334,207790362,792976170,170962113,92387040,499055830,545474823,68409929,771603294,647853986,56930144,93061591,762900421,882069463,958856737,708421216,270515969,199289727,832460156,893512177,110424728,347552404,176895195,288999653,53244135,76467976,89395528,330563836,819512923,133589599,713790915,238209894,889418521,418053268,212358738,567328309,166505852,330004012,266764862,516644908,90631531,821500672,717910450,524368709,480795629,454562286,661929375,633341023,754488635,868580743,15405184,651553978,281699337,503385150,216183513,404084548,507879294,314317729,5371093,204187057,536772964,229524569,206894948,544797357,299231622,377499571,730481459,156110635,424496666,612133234,364119338,150568307,784466016,615755911,794203225,832290542,19955252,503771910,601600176,250666310,780786662,882531180,874596731,408619485,789072885,154170349,551814529,37054770,51848903,43656503,813350586,768661449,786431302,636273493,906144345,95430639,487049959,691452728,286261484,135277835,497212906,96332723,45889133,139356959,966102673,298623821,431165893,145045204,876174971,50061476,602123688,553476433,643289395,278596158,279389249,117865436,94724503,897486524,457141493,447833360,80345387,800861349,556532170,849923055,708122120,163367078,66073149,196468310,641370083,822766409,375738687,445587811,352008547,591381572,484947883,951314792,267087421,735120282,719639632,792676541,447094752,117985,473605135,367808178,354227095,239566140,959182643,163278853,909940298,4989808,265373043,186166613,461507767,309599675,720391388,758682372,167480932,444856779,880464642,957113162,175182299,74010410,747040094,717213282,508706756,931972187,492990433,581156930,896045363,730588734,367383797,305683218,142317857,210323246,512049213,12072895,926588229,13867100,389043786,479831629,365130312,275772816,874031461,904058035,499578544,267859587,916361468,328057104,955151879,320240002,737829601,491749157,510917339,982322558,761795227,324315743,331737522,242851900,826054600,542142829,744828298,731769871,182011037,665718838,921334626,863981013,777856927,792702029,436684542,40196224,237460278,46637327,826840179,406486635,684706984,8785943,685477506,460961686,422457945,686686421,824563405,652250827,474704249,572302475,849710423,43269336,267426101,118474328,906010780,290187336,645703688,660595505,367092501,994981669,178431920,10193066,801852513,993530801,27333791,276076773,662745117,852371995,666454934,885405076,597569155,248955042,855907221,797567989,158851418,593503640,506437674,656300165,160024276,531075192,351774841,108383099,466666981,309952502,923448327,999306917,112617831,460627219,359723786,869515160,247988825,40754697,177393035,280286477,431576346,125241787,125138465,211299482,154486469,922723633,252816423,415786952,720271168,980436350,829994881,464784027,713980368,37011852,960772030,673582743,135333409,16401146,1063392,132717461,671225639,246787974,425971748,802878396,536921906,991710112,321746781,190482139,434547529,867295523,41447549,176687097,861841199,995780822,367408952,757603657,475028815,256697540,873103924,510197841,294330572,634549431,732910661,561623378,627362325,752005248,692876978,383060201,626407180,201534710,910504525,807229932,467957751,75150833,995972876,749302094,571238654,573684289,171972460,475993831,14526354,281519763,270016013,649307943,967664373,333359292,570973641,731295311,818429992,934051065,80840112,84216407,895411138,813213589,507695519,105082921,752112861,931477401,297656174,761233790,961761638,932344844,910136945,965318211,747415345,256205708,305408921,576460826,948056364,601558269,339759108,604658359,610151832,923998253,760841813,825479232,650702970,328544008,413910285,361118506,311779994,859276806,704675638,388527750,376455920,389651176,693241239,530164374,30604837,187326069,780877656,487536646,320496672,20702003,633572254,537434238,625779739,865542827,706278123,241353704,610051436,399052613,304071154,552334127,578392030,662450673,882375439,527295862,215335815,502420374,252178659,979583459,419522883,506265564,927948478,862855945,814475559,514848008,551300483,250402710,450876565,407196164,621117571,772870492,450072056,609661996,799404025,893432059,786792584,454279735,460264877,212131504,289988501,885670068,914512137,525778592,233275414,20054196,321895847,116692518,602588862,180358932,433275011,370516680,192955482,148166826,360734922,508802256,788821366,476597301,106989831,453016674,700441239,880075262,426933452,268852225,863812496,39386573,630174447,744556792,575937988,139253871,634989721,820374390,994146827,199089787,564879598,997188165,968454325,250138479,914892358,302573839,869811302,266098561,701510004,190729143,876128779,575645365,687365131,607012328,594070898,327035228,877912288,332286969,418623309,716223390,772398762,975616757,548725324,954410281,990990409,673398247,74608136,788849147,588120039,155137408,995807710,452617759,920207961,648810744,750953567,745093106,441038757,69153047,809607252,938775042,22946834,462675640,123696475,832656893,296813497,649659034,741898393,958287384,621287602,328066494,410044489,147984575,721529150,567759830,490217768,647843587,290375749,755922720,432573931,823907584,697743359,128882960,682362816,453635408,504500917,787774989,371107468,359921780,834712408,655993764,513875193,523783617,737542278,791976725,677762289,406019199,447701038,367293523,624104384,361064436,727080023,343129653,917929595,219350853,370928441,287164377,414993604,805440357,459388043,189189265,74570498,359196453,169399831,422288605,798837059,973546983,740714329,212944900,615124330,234232098,807148181,6554585,342558791,630728204,52886706,410947189,24913529,698212513,990817363,544757347,394525168,718036783,513391612,642882383,507813257,745103170,954779001,925249711,20819172,79908151,541729119,678544171,195340424,723359619,398858573,999917875,722309735,409767656,358673479,318018528,821325040,454328913,542685527,334984678,287407674,480493960,518790670,865929589,907272231,979528451,533628505,72904940,26938503,179955696,73410898,593845596,32675944,906431815,722745004,400069212,88215020,876866219,751573986,401516843,49043521,268584272,690268562,401702717,445300030,614768178,772052393,271389397,980540978,947988046,678295554,362809151,601577015,99532302,209757595,547313745,321417189,526864114,481925006,185619271,1668137,544473067,459678814,549354756,398718964,936448400,100744963,118924773,884772426,405236687,476657591,894808329,164894676,829260037,847401420,830230036,456729464,546967731,364139717,420394742,990564870,978407351,626225456,382209958,387034809,7648103,272426948,176226131,511651679,917863025,153053899,170252332,22308096,762574666,687690506,583146497,181604523,431168384,716868293,44833120,479351701,46795524,857592483,817938146,767086004,570451998,332338802,496413916,179796435,6720755,766240576,309203507,280463659,811173226,895722270,962245675,440140297,977095329,176061277,978412626,614463717,392195319,532731242,479888131,687970290,889348988,324035613,637176452,432845230,741896560,289439718,990098615,125902265,683343879,398156159,988939004,385609761,853276491,28846037,721236321,445086278,187529718,740084869,185032590,602826718,365288971,122207932,699567476,632720935,997742082,534042310,492222740,40386514,333196197,340390623,583782254,841626824,100052199,957507430,852021113,103960965,44565512,954397096,910472094,426690168,889752105,473298965,175448231,68665302,519939043,184196781,921613963,858617555,841335754,65073231,40576521,871864299,885498472,120543185,751978573,310228603,826745371,685536671,884196209,733546256,585395492,538813924,677774860,713344825,167377430,54296508,918629210,564242602,671500552,423032118,945089827,95347212,211292634,414330011,742090687,244220246,597472069,591278302,733616106,235221346,583203146,550662268,510573609,517209607,781516509,804104320,748163873,36488892,375686463,427004532,443659664,499717486,136168388,328666008,332296438,952022339,340828776,804001376,593716969,302183912,560464947,754036244,457624678,213608482,979067414,217964546,16062671,769232548,391431090,576646499,803328680,201644343,170205948,584512279,27640145,147832760,346253315,852832690,772862845,917263174,289450571,532192143,941222843,717751942,186590121,702817345,55194229,863271174,948386932,641422305,400231302,264666477,38231102,963102860,898981922,148464812,705435931,135979628,516967156,867023918,353042574,320978196,671589070,191225932,868426795,862290151,482020973,661804455,831467210,786501741,79362797,454583005,402669536,629268390,925251391,54648896,165899146,629734726,154210000,213692855,896919328,398272031,143038479,645938149,518089362,193547085,145215758,754565700,589581156,404227319,651924338,571242034,335740787,76726291,860591235,514544953,380670203,922448134,689569009,834041348,332347055,911517224,31489850,762777097,513771146,589387395,2589712,813350759,307301094,753024536,912922658,367988804,946597530,340912459,281188646,760281683,125590642,614998679,615842008,85725939,146467184,65537180,236249451,400877289,978034915,774800743,333538978,825335529,533501704,588136305,195488665,924171234,907897504,715145648,155198227,429605507,545132523,482579743,308106421,471334641,142455881,854966645,515382620,607840144,480565784,672945843,60581655,39259054,705083317,152121617,525357816,946929333,796229164,220102867,588074947,815947634,922672781,184789927,946983274,690739830,339179708,956271303,654185879,391971028,459966283,22868003,155950777,66818294,873122097,937406111,104713099,122483731,765508497,67439738,878404645,371679610,68211362,807573551,910316073,115232614,281278874,44007513,691547633,439415545,900233523,649672089,189460370,430041724,731082743,13006026,425042214,210346283,906891720,537853410,236680279,293502121,196649927,929455965,636935438,520558836,923987113,545015043,360908856,708375760,883347495,292512228,555623692,68137434,629855686,394941178,520275220,283043144,637856229,854679096,517854420,170727046,270322240,330897006,932059842,184399103,261836335,992243368,512378200,300569781,768758081,691526709,104444090,495075833,908748695,844882251,625176316,167700314,577179506,152494620,358401151,66605732,159918851,219543884,167580913,38527161,613983307,22286440,427749655,362581602,69410723,882085657,160697886,655397706,954171978,160023867,660366387,747262519,719868924,914677867,241540609,47720938,944370951,940089315,429334929,623977945,973872888,1293955,631153037,303826292,917548635,363372281,848975557,552310930,950440141,548691056,781313414,865439671,584723736,591508684,9291406,515742934,335876272,343339359,939957273,111327614,645468640,581250816,65825616,435534587,344114954,500526036,338440254,174589404,954952545,836354944,192269711,162780788,254683008,346634960,96384826,765349467,755554847,266292598,424036698,111708213,707532165,160054140,80965694,265653883,313501777,972354713,821869835,75412241,699834368,27173981,632456750,240480162,647501768,419314230,210130449,977202688,733508716,102418445,282048390,485766329,905511606,567991320,998462408,435655068,310951334,600176032,531480342,702736759,650671919,649216599,780513258,862706810,972525171,52108484,493292108,615037948,933948098,604801567,55948866,117545549,497892022,891688748,643313348,330734073,758593860,350097509,352196815,925460861,231682638,657908280,576616801,378949390,536372041,515039491,972998371,19728306,749092408,810356162,844431588,582264821,720860130,814024144,565251275,559136416,296621623,460381226,351825637,72270562,799633366,480550045,154413209,576063733,131156653,54719097,84307534,510865497,8913668,378071897,980996740,210233872,122832819,977837325,967380492,475055841,692211577,890849470,797809211,600453133,430229743,137652019,417728458,794306480,828989456,500873765,98720956,626751556,772284356,357061788,977271782,964938839,363262117,129520922,187705033,300268815,684473985,982945000,241210908,120756409,440456682,43412070,171236719,615828660,536609243,216671136,78040824,785393640,276110169,172114324,100784370,658503556,201295259,195509059,103387802,458643758,614081610,603702472,831346357,622094251,401900997,271299746,995136376,607330130,21669622,298278923,971473418,730597997,856039907,455026720,400379993,917181670,623910969,877964800,212734083,533616972,804862517,895997077,95353946,688622038,531986780,543630243,803485186,788417905,154502214,360908067,505064630,555592513,244680237,788241924,69669486,193308108,235567215,284410089,178879654,34727115,670636311,581477924,680086491,386687581,242495048,843381996,125623107,771109181,799675041,539580215,735686550,520532545,732185008,809270854,533068572,265739834,990354176,985529444,306442544,73963055,644113985,807006568,434993169,384212092,682807033,283282937,49044895,508258671,469649664,871717196,352462669,963755536,599728586,285806889,65320873,59893232,738704843,316157504,89931009,18372418,237444862,137740224,946808216,929043323,264361914,673728129,200714935,580164305,493408212,544332117,16651470,880947429,87861532,485818890,904873218,457414972,18111515,379798351,39280150,886824586,659395076,880753625,312149531,599518604,644850107,786785786,714032320,87254108,265861697,79356497,756903417,33240401,501827405,418756289,653680370,132639684,943675677,238416179,626185157,350142614,703090317,533099387,906870254,463045550,227502160,511514005,683737294,879962358,259206772,770216300,353210849,658027272,311407607,474867146,72709843,137886614,31052409,345207493,712589626,607795222,45126143,338171542,64535990,333254528,30265718,15095323,879528526,182343539,762960428,438134188,107595206,694967989,8484449,977586386,93325060,356186878,152264203,192811867,4557964,343867331,394636531,315555047,54248130,977425136,674307765,634618090,587554352,323582428,494720977,193365785,12332672,454070310,62053433,807506298,958241053,234881203,794831448,631628336,429883571,559230213,729139110,835334930,710027943,704067496,133191163,641334853,74966122,135478643,64732222,332005553,139150234,721199543,186939755,60565523,506873203,490223944,37154412,3504059,556467848,133415702,199445384,544851136,173209084,402359900,54112307,612259214,59707733,827747857,854074186,1422617,62654835,999569178,252497822,849554084,980890590,158394499,80194344,405391990,239588657,360522473,31175465,367938592,423598393,218106512,661690563,374078902,725611524,956909054,661266813,109580910,770097329,979392412,13891975,697541843,19838905,583181439,586961253,50098406,716126893,712274408,957538874,483785663,307962063,634707228,176956607,865137932,709912685,711668671,837141395,525110644,310239583,171361553,208662612,151766011,975564715,324041445,931446346,9915704,199050705,126683268,173219581,168284633,418801087,364467761,61920800,206731005,885943531,201149577,953426112,942476138,235836655,606288389,631571133,703822625,715523472,166397608,990991938,150440713,988887285,601413029,76922120,565825606,918191950,104342266,246811478,108534052,185598578,336161141,79817760,373092998,405288330,664331190,762432137,466364628,150340047,77599982,227545771,111600912,311737950,851605438,246684906,775804240,435299491,289336094,443752052,365398578,334400791,543604532,696116245,482749836,273046452,201676148,366830494,907975223,833882940,205409581,25162664,201616264,110641791,235046546,129191857,395571884,945839249,85377259,644389804,625837972,907506220,532413027,911360740,388725631,194317988,472564145,848921316,913594066,221426356,59990219,694305339,286861449,986394044,99553933,296255752,715284665,887424400,745157100,124820261,642455014,525815681,379643812,19921588,125259348,877556358,886621742,429273994,156464147,569687111,781137992,81891088,138529778,639401681,301435617,497474075,501565496,392823918,46025690,672957655,194736846,260228190,939310025,711233278,916579672,916657392,413383050,494612074,799009695,699279305,902733733,594139659,270973288,872090980,889327900,565772256,53103251,779698217,254495088,575956469,758197818,753657929,669749983,617770591,655849222,283503178,598191477,715793567,450295233,186797376,889022528,647862736,995100148,383350685,982914017,617197541,643073376,415152249,683435574,463916156,563524570,307678299,724206058,78339666,894582739,413597066,459279385,643552957,51236888,964179880,666752324,549718512,655485891,961709670,139698034,964037790,554855036,973272639,846560674,44556588,156666969,606270718,294428982,562447609,724223483,641159863,665478503,594751042,279044305,693337764,705656932,947178071,848116838,153017173,706293966,28324540,87850419,158964778,911725800,400147726,208678168,372640696,252387925,241243998,723493946,874233446,986562887,213146024,321103062,676742903,727114554,827370451,198333658,478934192,288970018,467941028,498964210,884212829,407185580,578021799,254143864,216295451,760952831,714293972,783073909,896761531,241588052,383053022,143924570,357397679,912877095,206696353,448603759,676255820,528709551,813131783,642596682,852726328,432387844,495044027,791504147,25620787,518912345,848678336,582026006,219280116,144057395,41545657,158292122,459876669,256098975,697433977,615522840,358290689,313288937,784418390,127560406,139941702,425571801,20437015,218442872,68733747,398129860,356516549,321131234,705714686,959453542,243106346,511304718,796781953,209486307,523055659,297010056,506664219,679870427,866784711,545026399,140183727,895353173,474419414,833248396,99452288,595798768,353521645,302597877,888953338,312165689,655890513,592197821,2235727,562907766,843046698,464276064,417045121,868998600,696159215,467462486,457717342,873875104,978899722,17537249,806058606,492427585,122052519,698721976,443992942,960770166,204933257,826124067,894368398,366154425,552636765,448401407,552860491,70281824,603250005,447463387,78898475,302315396,856120978,202464572,358232497,760127026,824485022,104072798,345152598,520003053,464312638,411122928,106964338,924148945,682006352,696421152,302073798,849710144,143323531,947097652,98482249,632043675,270274708,137937639,953988955,917905775,889778857,872878981,337015887,402421375,955638443,20112173,273917193,873233670,152955601,356465033,494676038,473368938,260974959,529581022,655996985,900711690,571808635,802613815,797992430,199787010,56966095,118598570,500949440,85232999,867718123,922313598,889870436,365200413,813078766,909343078,167844783,437307203,305027449,478102663,484765839,489131565,797710568,808644998,246242533,872321234,740821676,623564556,216677699,177871407,931065888,751393916,501089368,211629065,555536328,707517466,286659709,432639370,457654775,475698946,827262327,405956511,492632714,857861217,996956238,621273648,716620466,393008912,936342285,79518112,801969366,273561714,430801659,810995539,227856909,147426904,627493498,68161886,552040928,940286884,243895835,176820702,75187207,103178872,97343697,674320394,146152003,127281879,576099876,836444628,69250643,103373669,236429589,814456687,638323218,906778192,354097703,726421642,365146638,503463151,485788119,19155746,603299084,41550600,161217366,9110503,452994007,88378651,382884210,125478736,629875832,854543340,613411243,699652864,875553048,146447521,231162188,239086522,539942065,750271545,629127704,764821229,251833165,13945518,227104380,676845415,293246919,409569490,766670254,206498610,218596715,344347906,547856832,59399068,584787499,826152418,71001170,531368787,479072081,371545259,630468386,273578962,814536688,929719961,220697711,863391524,640006219,441570772,917379931,342304666,752528459,964168377,206474111,993975453,406218663,997583954,252840142,440341837,813976839,571783244,781825090,63011019,630087752,593862891,1976916,642868585,298975630,689282475,469981945,579402075,36987349,872251181,627674020,567096373,580286890,370902357,585515687,342255768,575837830,92359451,704366324,154746824,477677752,486694699,138108054,652326098,689243395,786516067,662890724,925954543,291819820,25336056,363910627,443958978,861448381,474075289,717163361,960850529,209532209,599586845,428688423,747265497,649866562,193387388,886672846,862240241,682969102,740116834,764870155,145550408,768825622,790495310,706418453,333085580,716579556,432088118,130786741,142514801,92290111,806351734,677773505,925673653,605241333,864223965,104274383,850882984,230959925,637289214,560770810,534028551,851443611,518710272,471293197,636836491,243536967,415807104,567144567,324812015,853267731,693647171,985335993,193281568,786506054,403520623,387595399,672930111,905241432,185583873,626370077,301946327,871900963,894780644,76077347,882146871,33484831,978542719,873378188,533114657,612523163,639824702,192869907,635936074,145068176,51830388,808795058,850028823,828300879,269703267,340871581,620787916,660669987,809123475,43460505,383430201,242414219,313704906,53848627,540611979,483946647,212712693,936559501,644917820,399807021,992866251,325992792,73590192,337768191,244680179,781584171,889216500,281074825,389532011,77354127,462986946,759456165,24683805,439627575,403418700,172296915,353452410,38692550,275958324,964525109,102983027,310513812,327243627,637062191,894851915,622694977,239062363,743379744,692683734,623287057,821078738,413939633,951902744,36136127,722842066,427121443,197437089,502836498,672661860,548856156,832003209,220264425,99266554,174602253,449237298,968808186,693631286,342233637,537466771,436586654,849542284,958446871,189744243,312425857,148067605,777803798,193531371,123884300,598211235,914139038,678698973,265826916,591615041,449892292,862055011,949281910,263031304,412110546,968490808,810341606,450649673,380787486,667528686,867989316,163410218,700953706,128821332,10104168,635228886,695757085,708912768,194940725,396334283,907848298,610205317,178192696,373521282,60683054,730722428,728249892,613903881,825083350,992811521,378498036,438675961,992046441,86609651,779728927,264932440,417721244,686522461,653998648,123754893,311474172,626125127,946552702,868297395,766358716,688351283,164002877,274935294,126385064,476070488,817399132,311004396,354467560,118164642,183369218,227302664,258340187,356157058,137594553,448371155,494471605,187069134,371272624,277064636,832502578,744598001,362257231,633255422,406663797,903696191,188292620,443386841,132604122,574992142,528928852,836527821,967155369,402867188,689256374,763321995,287022719,349252042,749445662,584889639,986787675,382845889,940110791,657718101,868593546,968031467,228983610,941959924,667127938,790096117,677257988,672533194,485262987,72252607,291958649,647888358,102717243,245697849,574265631,386021503,191223799,27373478,621725777,596425392,642249733,945252161,202969528,503649126,337383346,622419229,765514258,613678954,875287324,968902085,36154354,402356959,357345602,930799336,502930029,633767634,808276766,792017485,949475749,167298424,464920862,837560303,359183300,711632785,846935197,733490203,727152560,314772829,182998946,620461336,591259782,82233608,700398776,399778435,559860167,244662408,884849109,835894556,969247811,906791676,226569390,110672644,623973502,480060530,824150336,459843224,156753086,287394397,379808448,455585838,291197998,707749384,673045896,434023712,565376960,666967849,717418573,611813612,264098773,198797397,692480990,678062695,572430168,923028083,305956004,251620932,162011204,790650810,37931156,544901989,292013127,841012261,4314036,571626591,972022368,510507277,1674903,572498317,510704769,453021135,790468431,534480325,873527395,54373627,131822747,922240680,713575655,689229550,899189587,909452855,797414450,723318738,446948022,480734615,877733809,675266452,139275054,65650840,628200985,554551090,533960578,427125755,129281676,732995562,765072000,173515799,542920902,465561895,995514625,439590182,764443063,837051335,396722088,996146939,213578668,70251749,347448332,414092164,105728181,663572736,294976167,491750071,219515013,133236919,409761819,811690959,814513115,983643929,940820720,182459821,683664181,835636328,775695772,704960786,31911365,702575881,368112706,408395590,940743062,958579446,375332719,9754764,556604147,29146656,168031298,17290743,178434667,747954433,871808424,682951869,846429417,45687129,168686696,865606391,947451914,210768190,682742039,431892242,538384134,101179445,829075731,94012684,747401868,840492141,975683411,126723012,76051275,491424948,853597096,573195434,870103700,35007305,283906608,901170787,174820242,952789113,911459818,963908606,747453596,979691393,148720317,378235758,62922849,957695100,470664226,256824163,831384042,889217706,632805378,531495777,35706095,117568666,98735451,269381776,4385228,705095576,163414475,748443892,383919822,414034775,571443696,293369037,612414824,201438194,725747870,516468202,345204414,658011355,137311072,215471330,747920376,308066713,349661477,53372608,143081448,223824394,544568612,972639473,202089505,519587047,410242656,988230844,394477755,588576298,293136198,900609259,985939714,659522046,303566782,844660806,924440192,148977771,363803017,403485033,667220314,592020590,948436151,946302918,785626474,664358306,460334454,700239980,353061062,376130171,227175057,449658679,432670064,48198500,902091583,920905926,475883093,220286491,600844542,338640284,872181498,260845297,129324238,37672083,732825405,689750425,228715641,802133714,717704923,707452252,120678301,779555345,98865979,575372769,710153840,547736000,132480071,944190835,668604740,481820406,712819934,430020978,580131673,879246203,458485163,614551037,868206328,987113520,425550698,989113854,384977916,890215291,314865111,108312174,664157873,314863188,161668444,264134663,696433322,90108342,958958845,957779088,958897836,506350432,875218552,662014158,411403797,35648590,377209244,742176555,857934903,559733745,151519959,800719948,281101140,520676058,201524845,650995728,295857288,180068406,480404422,751083659,599314709,710510046,466866624,766522898,997183238,727228489,708518584,870762867,969426197,947585296,396418588,730330826,377966079,54872385,987523804,359235827,727124708,665042578,570319744,804726973,231810839,415715586,734566407,647673384,32533198,382298658,394619980,411531208,208408853,459139214,338188714,899591697,132479472,573975116,347737565,408988906,292444748,753358627,756856247,482812883,612693885,547697077,330516968,919155959,144752000,767898629,742633209,158809325,583533436,390248925,745269260,50355403,61461833,633297398,93948747,633415274,694245093,117106181,182210149,601924090,791913710,656257589,395980348,508553050,775537368,504422933,587437054,82764068,907691129,606218067,313652437,194864469,958209659,267323690,740131077,892539602,78663136,269856484,759470919,539246301,880776965,203223011,210876282,243118880,150983836,496260083,357576096,326829454,402834880,635792912,506562711,152608117,992249921,584287762,216115945,619108954,587441437,75837058,244153267,266969040,119218968,534844516,26982928,764731508,729693334,85132025,230295500,760780089,965856156,285446315,733461058,119838885,933721435,139986349,237273235,246787344,764869295,361855095,493911713,781143656,716253499,986682351,236163129,715977839,698555166,103998057,131312077,536611063,607599599,863717340,934380240,377697653,337249036,917453943,867185173,436789390,132409935,321089906,428188705,171306349,663614819,759027663,555853709,892661750,353286636,824549296,740214628,3306420,214135234,902371114,624497771,20174315,927452056,215132728,977974484,478139213,359065163,162355298,602206423,168157649,156673013,710925657,664876915,439833810,11067334,313580818,889076735,827010503,144774091,764753795,370242620,418398745,429772612,623721746,866949601,737037180,656571927,807955449,332010971,342526149,299156612,767393496,93757653,418203704,320730806,416820400,991759892,405283273,413214173,798217627,949966945,9746144,413172028,63181195,149753259,325009028,978758652,874241528,309707444,250070626,986882876,207586885,18053589,470257646,842391627,336806011,477587933,206303783,537517261,212320549,640062172,662971937,644256698,206061160,202256171,690691179,625972676,479260588,904625652,164001905,862515533,864804643,362397567,804699791,920236349,39391345,721271584,259383432,853952842,64240428,644639211,77428944,481787920,73342824,176733759,76358635,808241571,782426204,342290061,203416907,217145473,209535527,393067611,245773723,524930629,659073924,914970178,99342524,914791169,897142697,15249604,899060694,502006982,464773441,791633404,161476041,587096071,393839945,417143559,166005757,575668320,799338774,994879349,973441592,991234306,320234690,394253707,786276627,510019218,16099798,130482512,146858158,469314018,370635590,484144331,548049036,811286043,26027162,826625368,592870529,472661299,608317672,821680831,991954976,358484656,514353500,671893755,990163804,31719852,205932250,810975160,700301027,392786889,967308852,828404795,28794734,476585781,897730465,786301792,649747621,879432104,645454009,925729472,966460508,441185385,304415689,4522262,104175875,973108831,963833443,194181166,434867862,529131550,827411587,630838494,100081854,151888568,411657855,497871651,931402289,856039002,548146529,693611351,467896078,526094813,360553129,23994857,688381429,764649118,581814760,960147653,316665713,941741913,820611888,873799509,437587070,223176820,709693721,24437941,937441355,202206536,134556006,207097089,447354912,450061226,592653245,244468798,958018399,891489142,775979632,755267989,314182349,258289538,757710357,485558344,537346981,412999178,332641615,518369996,478499708,52020101,195001705,735965167,452818219,351844266,55262258,80497756,963165762,613545885,936404407,854757418,957407648,69655273,450028814,804719516,657541399,39757346,101671461,919857262,349822525,831179138,985012610,601842343,918305667,884604929,58057052,413250720,981877345,777935356,1415961,638420627,573085610,454358484,682891905,388197890,476345866,453610886,554078155,300950886,941923169,889434720,833979929,599995278,234982658,738934422,958443388,429615506,942737051,59305448,585440872,847579175,396169034,384767469,137022170,103150167,833291343,510837671,195108327,993054318,714429845,617993810,611796697,965629354,305939218,158980007,74767746,51614168,890920007,950855627,326818008,432422968,614429183,341723494,862598644,254443799,531864687,602068323,381760848,947293274,718399714,69138387,116443882,20598535,716241091,27221602,501415969,87443069,680400323,531359446,407997307,640794953,301030308,112657672,454624815,852275002,255044546,158416664,137186202,55090171,403188600,916295964,184777730,703082768,722480492,187337340,790719381,659065169,142679223,844486848,223205097,779084399,199698498,831333539,222347152,559760038,249918859,147014774,427833282,199076765,119493649,586355157,919569201,304640107,53631423,296247593,852725942,843488482,367899052,126757294,596198228,482827425,787470151,578281856,35495671,129640287,527972685,47102744,346497300,443938222,506829022,431028912,935633400,997929208,833252997,721456848,183477176,795194728,552311318,97068151,135223576,116555201,466466589,357936411,770918288,755595514,715369500,90377906,145484792,828749376,846164910,80714216,969098451,611299948,240104371,959209523,939138956,127958501,112433498,646994310,220022491,972690306,247445941,558288719,409389779,344766034,159847179,228756531,639549606,989268286,502462529,8697773,225033853,780277170,703454644,774107694,871421934,869425867,982847638,983552382,662726626,887138204,14617265,92828018,240552128,699945787,723294807,530570260,459699063,647149348,898297707,486571724,753704498,194060910,840384509,753356869,826267945,899910812,421777877,196016534,610458398,399899782,489826104,286743787,838096812,992762860,701373088,782494653,115493186,366462446,879765272,583501003,525907215,705757792,904188903,615325071,336292449,253571186,537632132,233897032,602547034,800456223,213763222,683245938,721225165,608045439,972862829,966879926,635565029,689725830,884747070,580078074,428900764,646882540,221583788,583994743,204650754,903374507,106499627,396640734,590347839,843787359,394144791,313494813,71923544,914234571,700767699,997701000,795436061,990860613,560336934,112585509,278000431,836988638,849252654,266206701,841252173,92453359,549876251,420886961,533892531,393201776,628488940,729326285,351144850,855929122,928177748,860500195,111777864,870259171,234249437,678833359,162732068,675172273,854891632,140811506,723963121,838358000,958584961,323890899,683759180,19037011,4377731,177781581,881685907,729986992,648284008,191725351,171472310,620095984,698108466,487205866,230035726,895311521,882778206,727922779,21722093,966291751,202722989,522169998,894183888,104771131,209406172,676880187,766371687,84436009,471692372,297136991,791300567,175933838,879210713,797411618,412351341,652380523,759533849,213961196,561296923,10436780,398002042,891597678,767434154,692532916,3801761,198546206,971330657,531575179,210174837,776893239,369014535,820559636,369686950,832531003,248429891,997094539,436651797,821033496,961118933,743247143,126386425,337100222,293828834,65405842,401790168,589526659,240838760,608411401,798599422,371822681,655184740,970808980,76436566,530042563,468453534,706765827,701883994,260169344,982732383,494447612,623933420,750295894,631188231,614167722,514696723,16282865,503756847,113555273,471073082,852204296,314656819,804851279,304762969,11105543,784836833,123768400,980698136,538045043,216701065,84346150,816082478,467939862,687385018,764883550,458735007,216303799,67443798,693549866,979591736,111479635,89243447,169577431,308173890,230525166,141042575,983026866,719644416,211339709,328042514,847011901,144366591,598217244,428368746,238236371,744099975,685616528,205204339,89961035,596540901,477419131,505381652,696963427,330728486,119018520,684787551,825078772,847278790,755470798,358971371,364557406,268860299,133924008,464254109,419214980,212263411,972160246,257782978,644617227,562010368,914708482,348650878,626048082,907147596,477574769,461156455,24965520,699945852,377452626,582286855,214055066,145213060,123862429,350717346,510059929,977630170,955332237,826130401,960259381,700860053,51070744,304099331,557097123,757395734,116125128,767192215,422234484,96828878,951591678,312747118,878086796,346055981,645664793,980321282,11311527,702938320,652876863,255086802,654121361,329691268,577944550,118745679,127077408,379098945,205379821,827540532,41087515,861586746,6115784,895558885,674273249,250445898,175975133,371551183,15721605,895168452,83823393,565604647,229619500,930223485,41372650,75920947,814213330,762214494,420245432,982350290,998858593,531697558,93943984,536062512,431962301,507160005,610989135,80629981,509223661,34228933,380150118,116990357,33285106,584294801,576651317,487770731,584915231,362941917,439066998,477615517,765662582,232086814,700059504,483061669,153519858,833425506,310771257,435582315,351898440,812612121,740393499,802801039,770508284,546413238,825736379,938452085,104885848,637782006,61472326,270180174,264035689,911566572,942029770,661976673,578757456,929017709,522095403,198292243,908799711,662746884,82631550,909758731,755556791,724826402,203691404,229038540,187648082,695247259,884491059,864710950,67710465,565390657,968091366,150134934,955009692,238463371,564945833,144429977,249895760,738037200,438159914,47846170,336851576,347026517,834808641,776452124,376050129,575017700,385569613,969124986,988122582,706817133,374455383,204463131,994077456,862946140,788361505,926780405,401882613,514322042,574653330,35731940,952496411,88920003,149184894,279846984,771802288,508596438,447809820,651830014,376640256,464943631,604982768,840871182,669474227,731099214,4363116,962010813,79524426,324948654,687538799,390554098,184839894,358615399,218814554,234798934,162367928,667365699,776784579,556757702,560912026,999214674,599597532,385969447,861050169,328618226,111808055,573508606,114350502,992959290,715658595,330769781,473240297,302694819,405238761,735516313,456086180,76033254,722036024,154065737,402232392,180919884,991650306,686936189,208655553,229494563,521627169,654081062,724927852,26351608,781320046,667721580,394829884,716082706,580086073,503852533,774582150,769543319,445619760,807347934,486541857,671835238,988632506,970466448,788693291,170209323,587266890,815792364,178135389,640015344,263985407,542781854,809295142,382183778,757945866,444223826,498995507,758325167,766290598,311526474,979192618,495212662,589150872,989469947,61631695,449741278,63337894,898399427,274170578,666730461,307262879,532954510,138279862,153323308,886909137,100882894,505394997,228198454,616913563,391429192,584765959,955576491,729657958,176428212,61359672,594369081,403595567,836556118,168206574,478253721,928723256,787136530,354785355,954111851,962721120,440803298,285606488,851147499,577516661,316494813,977379656,763161405,804860872,878980476,847347807,653479310,534878303,773107666,966293558,480570822,829125457,470987681,564256917,655211897,364099092,189072718,231186822,393085757,287598827,172993964,91457343,937055159,105215238,232666150,434776502,51696288,416328843,11778740,715572341,519751356,382010654,46502131,897265897,709322345,26200977,464241873,565942691,361275047,911137493,343749110,159050304,511783429,642149023,501061829,627296722,567872471,849748435,845687493,563522454,253527253,38810341,570120094,653448585,762780351,535940299,557834186,62479235,513894385,402515265,446722654,910795861,298359029,407962518,807553835,600096640,340650684,96063388,598207716,311949097,493166618,729121278,55609661,669774970,580081511,760250465,317320023,443178719,139567345,862120419,33415536,772579852,631707777,238914405,330729267,892860888,339026839,876875576,540282910,750466909,212425441,117423801,465752378,630415423,206800508,190646428,793620343,112238516,951604830,706613962,494871360,785886973,801218486,332748708,155663944,48329173,598250661,351818894,343546749,950887936,44402690,365224651,463968710,868157545,177142800,183100078,992022321,467977765,955734716,715777961,349207672,752105282,768789217,489798492,778665971,333610137,970620697,876048435,757516907,656801283,53455118,418765241,842710294,787604759,54132666,90002148,804859018,846505112,542235598,78683079,967445876,880862146,4838674,233317142,331426299,302420080,163572414,902542539,800863980,908056287,24297840,903736561,144962385,447671492,962953309,434307123,410189854,987477690,883510494,934799671,791375776,343412277,26771230,71119731,171288838,790172219,493346412,421663645,114617817,737553379,511463390,999769497,726028818,575833328,203649522,473192206,526685172,928815016,719235458,672908448,639340631,303478168,600283213,280756411,557823941,394478057,814376237,109559937,687606397,409749045,742339459,801471138,367715802,514919584,488020363,627388327,53930171,237642100,91899977,924218462,597330208,412972670,23006053,498601031,634154397,513225096,416460109,983489207,15454359,918624796,582317983,817974736,553507104,241710052,55647391,162646517,136236513,704687916,381305359,688782999,370038858,25846995,138531589,176581998,427327703,684500325,206721970,258394430,565458457,918224362,624032135,833268537,908709593,137790186,931463393,939988718,985832046,308179191,105250826,806640684,235448664,324592508,997716295,163849552,778795619,92186650,398853379,309973344,903524822,978101645,3626234,114125028,935630035,437600100,765674159,339511076,255282929,532496305,153193404,5432275,751533777,959398638,847801332,842278073,561476621,38123423,601330780,202545572,46411445,463240285,829125405,183258737,712485078,680038457,598712009,505244721,204905769,685701902,927237056,605267634,862891900,272582769,247783864,671972273,570100964,147978784,997322615,981838908,441979694,464502712,938464589,825622185,29912503,480979863,291801298,63879593,137898567,265427966,425254113,165607452,21159116,589001546,448721409,812680443,280617913,558423660,540551017,325104887,158008633,369494295,704261640,483312063,584985195,10105700,905038727,793725900,424285743,38700902,525243682,876851452,504240490,473042178,956148509,113751313,102249185,532868322,1560210,42162957,201589680,461676515,784388140,155283684,850716181,285189976,776445846,287908980,599854388,292222641,41355348,158578540,756915877,904808929,351145984,648908935,84577180,354399914,461338131,996182171,804868542,143476770,959764655,15807566,571564462,377813594,551379900,226549900,276501919,627632139,893217646,414941139,873394628,17820607,149505262,584278781,282648750,80699269,538870514,253197029,671455379,204062111,512894742,669325315,976097787,400916139,956777139,997250683,462874482,971257122,711804176,940503917,891242345,583106575,835496350,118588111,22233923,727236669,647572235,21618557,926595494,969354412,193321757,430448830,58314907,216452332,329880936,401547151,506012988,935370958,5117757,60752241,740341640,719877756,792589234,100531430,490853002,352466237,396786547,343306683,372633070,380644395,786015761,256958753,353481720,948905968,30960044,961005693,429184715,412931618,417679727,172902379,113406148,4295955,245283252,80238564,834361297,100567660,901188791,829001200,522219494,944462825,391464239,71051865,205352701,842318443,359198040,683176662,716389250,887662440,602494600,687553459,921184226,436987061,352843650,927235593,751814471,263732178,254522448,649736238,523073171,508971248,412879251,132772545,980506211,365636691,571712885,976922474,123325033,736796776,144364224,92319720,339098062,474006444,516011079,619503163,355439193,6902503,168223543,531750927,705539226,180296458,737977581,956158950,816435025,228162889,543302586,37037897,261283878,491033578,97776693,960944398,724676447,724472788,370567574,131507601,38043162,160324219,125207984,668108529,861256227,279989664,539492013,893598417,653952516,386737758,321015389,381678335,809889400,768644776,952845089,430575313,606531648,399849157,770286819,39995763,231281935,553322198,69673418,929921472,274113572,857270838,737264875,134447757,689472294,678407410,145085536,287178656,13679562,559881485,855199923,356283196,959392968,319670908,727850359,815577817,697206211,819169251,946739848,166511933,947141168,877908568,943151555,568738790,430308176,279985854,530898985,202400842,300199639,764368787,867525813,447672682,768245188,531186492,683578014,621342975,599993608,525569810,960613034,565700425,473455882,60230386,255432340,169594176,689084155,843011709,157717502,471280114,358116618,238764582,914232010,516009884,916240331,808195822,209185574,577785190,674590656,587781485,415663634,655540519,462866268,269858221,638880490,8883490,85962119,594209244,833726130,171014652,919425743,802710469,244890934,143169272,372675927,684558917,547558245,413119068,403170820,193290545,516166581,680289854,248637967,136244337,731962488,140409185,529984915,597478194,422008942,753361210,626958745,974666902,753048403,671559436,681534979,801016203,44616064,799421997,222030368,937142046,80861319,800231236,13020860,755655753,991588848,210606678,797580588,611267423,945597393,949639269,340336624,457039645,667755593,897704191,577626313,295878095,548784340,20509205,676631262,920392394,4501491,266555795,667922730,354008902,166045949,413772103,520917270,125072545,257472756,928996012,514724089,984742423,620892245,562964005,866517488,320667083,374518635,474142526,636034696,908015781,806376884,387644409,473186140,614520152,254464524,118719884,620552895,65627444,145333601,610177165,524204018,178947034,417400363,536870770,138426806,525824981,932539743,878345790,131412892,755928856,888167786,797369924,720154416,745068103,139108181,166283296,544704721,422149651,517897608,479788358,332225140,631140413,416378940,295850834,187917772,218974342,67958203,969071372,259474842,764904474,477579977,881654304,618907811,393970256,536521427,424017083,775936984,332515431,929760520,359375415,178646441,629390579,268900512,988347425,788805124,732244987,789816084,363222095,771563577,435550811,130978051,509913767,290235097,935986300,498694883,332290199,631844739,114665777,571351323,323604888,208957098,387793765,275724579,124490558,4002438,798737755,39431504,826387796,746272373,685323762,798630961,205363171,642610503,765083473,156265736,478011026,612239014,670444005,105595399,148920181,780094143,383373319,705428979,478558528,547378066,473966377,263924263,388123846,419052278,372592115,840623346,823653066,733561778,140697736,839125578,47142952,865530841,948573484,935566657,79274285,269723084,58684392,613238167,844414264,662910544,355191160,54692677,466877509,446854154,811327365,759012792,461656905,911882640,504450773,5735115,851565408,492255161,653364713,935068913,438158414,374611129,119994163,811070797,283960436,687166204,837743517,129394680,837738005,462650055,770299753,533864444,455736117,170012404,928867061,211880948,885144162,471997332,291699796,142498705,254908944,567858062,951983363,60005918,916699251,468267303,347063942,16443741,631213831,979458846,651399187,11783999,633353068,819940529,286795546,409321017,529870203,840135789,357632927,835317562,964170833,865512941,96440585,71963681,158134439,674082327,16490486,851012751,550690152,959846414,476170689,958279169,614898022,464084368,967371171,259637337,716443663,765565362,695987265,645473855,153176176,370187294,572467073,281157132,899899972,342218310,853255716,179271024,434837659,359987574,313268280,252393420,810816404,75274959,395356937,569823519,786337832,145610039,738048410,444501915,535433706,338373099,765996424,963946116,325367901,908038776,560385635,468390747,35390203,406284835,16976222,301921194,381518420,247950761,919767209,604652842,498738605,377086381,145395379,402499874,720730733,742497110,20298438,557959606,619588722,107301279,537642224,271321089,762662235,276138679,516388569,763443346,836473810,738519626,410313938,718755921,687102803,780407933,614004260,163306777,912773455,178693787,609044786,970922222,646735844,492865228,263940799,785105201,194661899,709476052,326377996,894643740,599030040,751896071,565747843,690704061,27150797,430561235,241000024,753984090,286394631,813869594,924063343,855346281,596943291,811365024,565719986,514066314,568884158,466854052,586574876,443985998,919920021,966964221,941114568,693651380,574295579,874330634,970281560,295797659,635745855,956430994,311911899,2865678,850152535,1344018,210146765,226812431,294940264,956997667,654655199,256094605,697671240,721206279,112170128,617187486,196675665,536652414,101379963,469998142,659621906,989262899,653019737,994489580,758161583,123499475,794062796,666854146,411074524,873961301,260683170,612924632,21540590,875582428,949751397,340803102,112451311,201206781,861734868,395894373,748361932,581050803,652962696,868180578,925217297,223778594,204840415,27356796,743603337,284675568,983015743,421662007,995912859,898094674,892917319,114731752,644624225,55841324,58235825,758525977,879264220,144636031,484977011,525339950,173257684,430839640,920386911,173012085,101089103,492672499,490587407,484731336,369957685,423708834,193265664,58475518,750860313,846363882,538225430,421167267,447831931,570957427,928440520,721966704,92944739,666997774,700251010,66525234,76630434,253881072,93772299,437245930,838792238,192909414,320437147,399969092,509745212,701203474,126971332,190775752,147903865,79228693,389801324,122097970,45239833,397676222,631100073,850638633,125963234,39521917,743021254,188710779,374475381,2620627,636489424,72864549,854883309,995728433,476344850,576177882,655790532,399441136,858357003,172232755,512422121,264317943,497005405,751391795,905232900,794366308,519494173,355833887,569998930,844183161,571580621,628460814,145979264,176453638,156065636,18587282,728385787,404600552,175217286,323417002,151005826,62513189,646190263,168296466,767125822,823622830,831206037,259173724,773208680,541575558,133810617,296961409,121715955,954216080,432959621,332603888,703457609,386674661,292489039,480285168,906671210,126999678,601452284,294817608,289108803,445718227,159931930,536441979,541778113,295315324,661466799,662218247,412730755,348027476,74356875,635075735,433598366,124870061,890425936,64829985,93739888,357090470,48915474,743284592,142886356,189750410,584445373,586578111,300831624,366971512,636273990,629574795,934333841,496907802,578867317,763801776,795368252,676414443,634982716,655502016,742552988,850548172,264612104,964436976,463321111,257056466,511395393,914390698,929994040,920837508,825297752,75622157,170902594,526999242,271348973,590033055,761775726,743302461,709549427,318694270,954924864,884291675,68950158,957645006,3193827,213981040,761485338,587749718,658165164,389483802,720023727,789465585,765102983,274807750,247768234,680539271,606002855,452059472,931313059,808489499,628266312,75631078,469929875,740877572,353898549,34556757,828027445,626731561,358983602,148642027,110442745,645376208,512463843,468178502,867804965,430568074,275517357,62020583,386350355,743770234,263461422,535691050,572178210,122608553,437212166,968219082,610355794,392866258,769549573,736444168,981326814,491639625,359379513,756810008,534356241,701224507,947316972,70920191,403380765,113764506,93888032,967546475,924887920,537684532,176515482,51990714,878630855,320665257,289540327,638226762,483970965,203530901,673489390,429189860,691155123,24170478,481104472,73733856,596846316,7650375,976618920,75101583,999115821,504302770,467474440,868651185,826222724,460160896,627217566,562242589,220347057,817667297,262337723,821916123,664923877,511276096,867321097,834129146,662125333,515648122,664753818,438668876,228169816,591612997,341415770,90005287,199312793,456371120,629047690,878912349,539012567,544349969,530970760,604615493,272918270,294935586,243910342,966073641,944132588,305296399,407513567,983309272,230492737,947067308,933669192,798552746,731605044,236545821,951207867,316620669,929471837,724404375,116386107,814757999,124777182,289989729,241654242,651651454,722314960,689620480,783288103,821585198,373065010,561576937,861533958,392083920,178570584,742094205,512044967,440714045,545908895,838557677,35516205,113994660,53847953,760052792,769027624,369119267,247864761,194565657,200104327,334583636,615306572,908795820,323656349,776461591,835953038,48050121,793558230,217459534,491717993,522962445,308139016,435797344,242191138,599647928,583134768,451901553,288037423,272645087,191027727,17092394,852751886,275164591,697083873,547820841,941459736,695532345,332083864,806078409,402090309,980740455,134614768,203731452,698349350,286106705,278685987,407666392,27095591,450456609,652805266,128469121,782787772,456767664,729746255,85815241,944461191,659778081,576054871,207234888,9339296,62374308,976928937,635670672,585845473,948683832,67611806,227914154,954575385,398135691,985533709,559943660,579279427,428326412,595064636,861418891,537797614,832600727,983684851,869409780,300395172,151904385,116645614,500123639,32198969,423213874,339986069,872632492,763258578,953003785,547846804,718591587,416032071,785987672,988307447,86733461,680782407,695170656,705597955,323774441,61480777,123207258,615810481,279120419,199537492,769698038,851245874,589487031,478115401,3893433,121878448,803173790,647587959,149627275,996135406,344363024,521423670,941046445,958013027,883270963,449114782,877024464,671584791,331212679,546066862,773941196,37021100,931799259,230363916,180611376,34157868,596788844,616379418,632268944,946050943,97352964,898099214,753065952,552285318,184296472,851603115,281231119,325490119,23865885,204205893,882046073,22475854,860891555,313197057,967927388,418403749,45574153,502074113,308394758,637783539,113124726,398176358,874396389,977087383,501019891,736356344,433335696,539872035,557746595,250794889,9555146,717580212,371855926,959196524,19800140,826162201,364585022,337426958,809233039,731454207,399388664,576250851,207638927,204386167,458834839,166530808,607649724,704552974,966622217,473465871,906089129,798856127,943968832,504911289,295142153,632496923,933257207,238661402,64342046,167090726,172521638,563204133,537636847,99854296,550084484,273711764,29725545,321050212,239419995,722613839,327093431,672321842,441401630,370809852,456411139,12553375,30788726,846882220,901698887,921896958,271637324,416392863,923481892,937007318,2186762,720162080,120215442,175925265,705040790,939851560,966361896,472424648,135866593,63737187,601346594,120258472,724230911,874293813,77744063,194441253,320599034,472673134,114912905,423484696,420890231,453873931,794986466,872030230,827637630,456857124,80306213,716635318,155101079,174640789,491257970,938480115,313716001,461216071,909207064,805887978,350281296,499723788,544359003,720121419,994623084,908532574,358504129,885659331,948482935,78605502,109134349,511947840,658177840,879700414,123574336,392951972,381533128,302779720,248419041,663094519,173627251,698787713,756879028,182059672,89644188,397618185,525835939,174604119,824162769,250454770,384108458,64723341,970535243,764130235,595513,801958815,802579283,388397253,780146446,929649124,555451927,924616248,343427680,165138099,277188729,46385948,695084937,484653438,780690641,964479543,436620971,448542646,42922976,661884560,569344288,675956397,980554576,100813613,121446770,448475740,249482259,828298451,95436108,171975496,593786681,118714092,427805272,510689944,623084615,203261950,762858862,522239308,433728722,232275629,711194405,945561945,415692256,689831371,590797965,323974458,46798390,218179557,24593285,448602994,759886689,891609133,866020122,726648464,885857506,809645601,387323326,364593406,414249563,693022283,766839198,220357419,722489346,873421924,485078812,250120932,838640395,47005591,717601448,394779661,874682328,502367172,873359016,507282666,366543366,146343440,411160720,153004131,504176619,318552492,348305811,886086725,367679407,594045571,959495976,278294567,783849766,907694187,754819121,705847347,696007205,78533659,918589188,974956793,233826890,697687987,363608124,62383381,554392424,387919342,680116842,453694086,448339624,919698574,306364477,161184787,332204682,669937875,34109429,296217069,593193565,733427640,848917968,94520630,821085259,801962626,852431196,306797076,792990340,42160512,422830003,231623298,661787533,703685159,985190597,707046921,758051427,655130837,2577657,513321360,626732212,332090769,607090078,25709024,775522549,884743272,601706678,9744095,947496705,113168239,77629912,195892141,263131958,463729844,195747270,656581481,317922303,749496174,754377546,378628094,98514328,863780380,351555227,479510832,162628062,225873131,806238867,582300729,485613512,946129703,708241846,465071050,349098600,416011196,79816285,270536255,391156346,407785566,37961904,405952717,814976074,260320243,296195710,869189078,264508629,41969596,991936881,169886046,462835691,345497260,506298855,197451653,788828443,277356393,951220871,598832795,386230271,456888103,114359022,331393694,184427729,243894779,902402153,738539244,930558608,108261818,373104897,474036421,790699783,956813136,228211462,365032991,479068164,132160003,517672501,406242403,430891623,152546124,685113138,543483444,241795133,859238693,7429153,20038074,554544723,126253992,529961827,704807892,486993585,164043914,301255848,514336913,722421116,438964570,569564623,618059123,101884739,772584763,971142384,902733902,127014577,447540511,947376689,308412653,247406452,246155091,971107389,918249019,371608507,505988278,8614712,358112117,25451103,186269796,387380176,873456673,722471522,793527033,642693495,791571938,988575875,463688824,82764557,466534863,114547784,244282826,109306274,483471534,918325397,640853174,128892386,396871376,363063701,842473825,410879798,634660889,250184044,742631796,368168457,668048433,989786452,};

#define MD 1000000007
#define D 81920

int inverse(int a){
	int b=MD;
	int u=1;
	int v=0;
	int s,t;
	while(b){
		t=a/b;
		s=b; b=a-t*b; a=s;
		s=v; v=u-t*v; u=s;
	}
	if(u<0){
		u+=MD;
	}
	return u;
}

int faclo(int n){
	long z;
	if(n%D<=D/2){
		z=tbl[n/D];
		for(int i=n/D*D;i<n;){
			z=z*++i%MD;
		}
	}else{
		z=1;
		for(int i=(n/D+1)*D;i>n;){
			z=z*i--%MD;
		}
		z=(long)inverse(z)*tbl[n/D+1]%MD;
		
	}
	return z;
}


int fac(int n){
	return
		n>=MD?0:
		n<MD/2?faclo(n):
		n&1?inverse(faclo(MD-1-n)):
		MD-inverse(faclo(MD-1-n));
}

main(){
	long z=0;
	long n;
	scanf("%ld",&n);
	printf("%d",n>=MD?0:fac(n));
}