#347880 (C) No.523 LED

• 問題: No.523 LED
• ユーザー: bal4u
• 提出日時: 2019-05-21 06:39:24
• 言語: C (gcc 12.3.0)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 20,578 bytes
• コンパイル時間: 1,321 ms
• コンパイル使用メモリ: 29,472 KB
• 実行使用メモリ: 4,348 KB
• 最終ジャッジ日時: 2023-10-17 10:17:47
• 合計ジャッジ時間: 2,374 ms
• ジャッジサーバーID （参考情報）: judge15 / judge11

入力	結果	実行時間; 実行使用メモリ
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

ソースコード

// yukicoder: 523 LED 解説
// 2019.5.21 bal4u

#include <stdio.h>

#define M 1000000007
int tbl[] = {
1,498304725,895580628,487230851,103440341,173584120,176639020,843238343,218579304,568566640,10323028,
3376742,161679646,846918554,933030199,555258705,778899565,338402650,195770664,241348084,180884011,
404011487,134456019,133569790,728203727,454236308,9139060,22473748,419246611,30928923,307357340,
159623904,270979330,683831664,248007424,733795550,329764236,23831413,984516594,761952638,13878255,
365425865,898259854,864968582,636987490,522782131,843489416,539994449,58933830,687057637,604238649,
22080790,804595492,91860169,568246880,86705163,650431039,583427526,268364158,936251748,900005126,
870113429,990391024,570273559,730076976,858143738,399740501,131032684,854144791,232574389,441410382,
340411730,22955391,988305493,106071660,454214485,7018955,71191023,639906729,931691529,853605353,
602450447,541556921,976136411,871080208,583889595,726159989,832995367,467635727,110040578,364243453,
353962258,701294756,8567070,80679585,328555973,742793923,832243951,98086912,719227143,230865212,
214612668,867859395,207666778,295389292,586680299,898294570,452181270,382643536,675666695,557554330,
750009249,720452070,530978962,507645410,302594818,721610962,486261526,15744177,86674453,209121881,
672340217,774734474,91519595,839786329,295523845,533017631,560365192,888212811,654660209,62848309,
105822831,31900691,292159618,766380122,625687097,458092854,107772914,451036792,561545302,120818654,
173005062,458263126,422679040,907784725,951769736,793016750,772869813,216898477,320869528,461951733,
154928172,324042135,729569885,303247080,83014615,531809195,271273897,887049566,831924061,956676994,
905799619,237562110,351286432,725273297,667725878,57268726,721031711,69935265,433178855,34005398,
948618839,961961304,595396024,701056809,673410918,476946030,642804656,526153994,469408908,467841998,
766239346,775466750,308606414,579679872,719353775,577494706,593971019,930839,704664056,59884150,
365033236,135011472,19869018,544809268,629770583,677583304,402102926,91068505,690169813,975701239,
897025150,376847073,984903628,475751075,370800115,860670239,432814608,134097829,399572850,455938749,
445747049,703294580,959232251,541830784,192727082,25335352,496240258,109685844,2376751,847743432,
805912946,761784190,520873092,751388974,590315513,2281019,333717667,4583167,735885295,668584420,
65249846,91048414,795019506,740427505,319007027,198463346,371112257,580399371,936032141,899466530,
477645549,561201822,75882932,261302551,32597482,838819516,763049600,866357019,833212085,575724165,
226452378,526332099,599832671,520471400,624801797,896258171,241431816,759047965,238112993,145447437,
732937418,787129280,365170299,309336500,790474096,623959393,699842516,653042907,595245593,378001142,
670850774,3431983,508414737,725801065,201223078,811377514,964681987,88354373,663333525,242667019,
258971343,785163858,834910311,528480816,335904390,311313232,534495606,802803859,551558184,257733209,
229501386,547444574,898215172,766555885,2738786,27485367,618953672,842623465,164653389,544171177,
53618097,802317317,87388473,471166338,766248951,821830458,200425813,691167974,543101809,454315445,
220227442,222989467,163495075,322768428,38864774,495011156,654168064,512531682,401290661,376622923,
484330078,877831005,899648574,72441214,902639596,968222538,650034398,282106674,760884581,570663275,
133438639,417968662,871895966,414961244,259785168,843161644,114224824,160694544,113383050,392351356,
482464248,532707027,404339631,771569325,718062526,471800139,757851688,817388276,794684415,548349623,
954503915,587884582,475116065,431310906,902720171,95470242,444470289,315533955,917211794,925840018,
138770591,669007144,862279520,376706643,705906081,104970861,96369838,437289053,899113687,617718355,
666819493,960831436,72114596,215777263,838760659,498750980,426545226,185326591,220209721,757278130,
872458564,473235445,55493158,475037434,846129004,98478496,169073232,658109778,187926131,518777316,
845714297,274698362,32242554,232377150,696013455,467144096,742449412,948261976,930776921,694465021,
165056287,95003380,421788415,989093687,167524702,254694644,603789389,39878795,863721840,673335606,
522566062,961887904,195316631,263372180,643722927,923816787,655709533,259691992,817418310,548405441,
412317033,693900034,341263738,731122840,126019546,963393776,334522817,615209512,192643944,724507454,
423570362,203023273,73985701,689530504,562488170,450736850,805899871,363776983,139915998,254797077,
862627605,820162826,255781312,301329760,227580240,725719364,523113322,725823630,740577318,176203303,
226011750,484909110,963215014,344263812,542322056,575975222,396803033,969092991,445522760,273550920,
697987343,220949844,52518463,111560802,359942414,728983456,433472825,314994627,257395255,642856034,
874529052,702692042,545328299,907842086,587428158,286410835,854714302,597462715,302932749,243598545,
498209448,533427825,740298220,871566694,66204232,641941774,293217471,866659895,959632361,615550094,
720684565,628564749,120126052,413748735,742907853,372119124,167443585,655618310,191032356,137218344,
436053312,870633492,727877862,108190662,488926511,568841712,475558967,392858058,824103892,844231468,
401189300,537299791,572075947,896755997,111176767,353008956,233394450,632948206,976134956,527573545,
182007455,185379274,942477934,58348809,556383120,265931395,644818236,903141414,932551378,159480083,
337627968,367309984,382487633,848050077,194233544,66573240,917430540,257723842,8866502,43955006,
143522610,608523887,243362689,528772731,318941715,368045067,613231504,205505081,869118901,605637374,
670665037,618785515,57597981,182061578,643133717,384812417,841608138,296021973,465879607,831683565,
125180569,281655611,766366087,812187312,458886024,79538576,422228633,209082024,782870617,118040974,
674759187,314624611,608562527,247920370,960454283,277993104,892066572,944800412,82609741,233207374,
409182610,561922583,984454650,484480687,401010778,224793097,719184576,85324095,192510911,483514500,
138452969,585673614,583708037,875420912,58283619,708310119,828481830,942208389,75933840,819045129,
633148398,388199994,482944311,873927075,814306825,782717200,167447210,465113409,617585637,695887919,
727912583,447977193,748800480,672397794,611887427,884941549,235478905,909893521,348406727,591130296,
732428027,448537568,176830132,567423561,618989853,319895657,824352686,198155611,854632373,970599030,
570438838,89651223,226765126,46717105,277903942,905463154,903794623,828400818,67757203,261250366,
904100006,344655926,842480356,75725099,179913150,971442534,72585641,534483429,534359326,905012706,
80959004,356203286,706134139,166454161,15117188,738016230,796142740,558151775,329209268,993876947,
806661274,750625025,712524662,911718385,675826436,467271685,175295865,445232848,881983873,332681987,
835948535,387920805,575781359,196434590,262557652,506791641,273496145,78319632,344094429,629889511,
109587400,873628884,606062591,202039023,237462922,656566903,371323572,508796333,795675902,904348551,
862765509,956498966,469194821,469314923,889354764,612448590,102701346,895410751,794273706,671458993,
532217502,755705993,223053133,996978198,230080242,45682420,595619914,690147771,189134330,576272387,
188485839,153771699,886740778,85997964,272743170,587409845,155549088,270640689,751492022,975223812,
447464,993391535,47336772,419165226,493901812,94899480,292226374,195704903,326956360,221922036,
552567403,304154085,458785395,367840925,429702753,522987300,436701644,283526484,656798567,195721297,
540737856,760538199,850350731,612760005,756474273,722597819,582709432,305085924,705267325,843627000,
390816991,581904579,53602449,143314643,193280719,145374658,986558974,767560691,735833554,249761018,
416884442,307027073,931544081,695794333,825801091,306427854,887464144,225454689,603989079,413514724,
35328322,676227176,415829769,130746890,343271484,12926032,941341228,314392095,780497820,803998215,
574166659,622328747,647819107,727678232,623354675,738796830,799480701,234453043,117928185,333599480,
391795913,34827116,477478059,533908138,514435418,104121639,839441757,240549854,847113453,390946736,
102486904,596730800,458839729,873900214,567132109,771836332,743521276,749263064,803378962,113440172,
5002520,342955187,238892925,517157874,531590142,900032436,940732150,696444153,351427624,14630766,
193107370,729188298,538040961,812178624,807049805,726131064,124461178,565442997,461913899,344039597,
10371917,967189372,559170456,536373816,445462956,70678379,34274912,416602247,967984932,499436736,
814991582,853251111,579569994,61789303,572586075,762428340,902989867,510959051,716170950,232506753,
254645426,616355482,476743936,448186240,466846995,914484734,616115066,848108618,892053827,771239815,
236857055,837569436,531879230,570987707,815455857,485653000,911865316,576301389,154900702,515268359,
950113611,508838361,100173832,144000294,621043716,986482029,775657840,392887409,210850282,678604213,
860051370,780435156,554975511,274746575,681407531,750971290,82723314,935466689,284081447,174568470,
535637625,990174210,766058345,144785357,876786880,214443256,143906745,29645155,37045285,897054228,
128410768,948331261,469560702,977581514,675988504,20860925,492165901,742682206,965038650,482646059,
159131508,356230790,815961097,583989522,946076611,662764094,517891864,897393306,567021519,830470160,
83550660,823643109,211115037,512612808,273004547,166396191,947733362,101692155,989916693,633687553,
355531984,776188402,446475924,907386190,927639377,812867250,106371367,792991651,24231486,507851499,
178846111,440487170,100318766,47847325,393594643,985197923,578400004,173707800,595994693,843249630,
578746499,503255894,491179103,700303398,417355358,946607872,497491836,10459257,974416182,328899896,
117492953,130891739,749806640,690704033,7640463,858230622,714039699,528410419,65497746,560344802,
46274003,56843155,695014134,975274324,143991691,745982335,349127150,899914074,175758290,173263275,
274678317,128405065,200381475,270842848,326326837,498880193,959267713,186768915,826390870,69167217,
26520632,120189382,581826699,41324550,96341505,78747934,298743247,40554290,280917032,18892601,
303533454,763901971,637153845,254558094,58911242,274946015,694614851,898475244,503432653,543673524,
370721950,52681851,457786294,681455737,933382656,954394590,46156647,37717040,762706093,411157058,
392803639,780955958,159194225,495907833,51083445,912500135,970646050,343416134,514058095,599650521,
305645322,651333520,983080534,341810695,726908925,670273451,396907452,637788899,29663000,217487314,
134018083,444342299,77848842,215849848,750237305,880713510,95352422,486061100,4985294,950878535,
562033992,313027246,141145247,89544738,724240661,142418463,700272391,65310504,505842034,2414411,
171989998,976327431,1049817,393952211,794676877,901064270,149584761,942142140,566996880,882418322,
305449065,708037018,172135422,512051817,12128510,300021193,113507863,956639574,213300708,159346256,
299741882,414412843,845121327,131939510,442482837,861545102,888753516,809865657,417748218,747695640,
537968706,346908342,186708159,92306386,1013877,315395583,176723983,654052722,227464099,267078443,
643254749,776305954,344445695,875304086,600134464,979137717,752231460,306960149,519793224,190110039,
416392389,975994204,333775653,196841538,976726040,514210079,254945667,129476838,778012393,366089614,
47445447,666073289,43840110,885538777,634116077,50086010,195997704,125487956,252965188,462340458,
321266603,487348760,461009239,894650087,821953146,9628043,10973074,530234970,717399642,719356243,
605058784,741459270,862543948,272914875,355231344,815294754,468855960,345351338,970356351,688252766,
56580433,223504194,638214510,84185543,646561828,423231029,144571780,241160235,624790199,653125247,
620407803,29990693,488130170,515569907,302181388,549586199,79108010,957324104,204759459,377949712,
431907716,828132193,54433175,550062694,846796174,38516355,913845391,224441567,3648674,733307931,
839543761,948355191,828496032,389708099,46940218,902602418,161932519,471429321,947024441,821098056,
171848317,50141387,155254258,215528064,884081075,333269763,573129066,840625302,645176934,778494515,
587638925,867513407,826007800,140704146,939904678,829896637,882035233,492941597,163094339,521079861,
517780915,311331345,169196503,269812350,465446106,114795059,722278558,891993095,506685714,566380989,
205338296,333897974,320967294,794644137,788062234,43154077,285539682,180306390,23174945,203532264,
318557365,816426472,11335279,488449529,443074778,865458559,664920357,471953149,274159755,412830813,
58932541,810053106,870454978,342427264,631107104,802590443,152493882,128685988,437453516,147550637,
720945410,743380613,103641734,624282555,863827370,123856103,673021013,10879281,257704866,812282460,
353314730,906887650,287453773,274016531,124620353,165651938,578303209,453572090,989855703,673688582,
469354039,906212512,252801186,182006319,925603917,328627790,717208490,990783198,671945536,743584310,
34245211,126863163,682629651,427439939,120932033,970492483,443656193,178628493,698470198,814466512,
498510245,67001343,445082643,726568150,355656912,765393564,374684384,376365261,346478173,846309343,
345953213,983182571,309661585,350526543,506846529,402012794,437359297,183593658,150169164,298152870,
324866218,44973168,214965467,430693542,333502552,249403755,219625024,515376169,964841954,346353676,
35120045,961027110,661121273,231300814,529675288,950157193,651067479,526194390,163710652,277322237,
442542926,303416277,542237206,592494392,32316306,789911561,429355668,994817115,594543933,969274324,
768094922,795751661,853650670,566447682,134312073,19903657,228844430,136429855,46124361,675540787,
201572540,130078068,290763187,757913498,557991427,336271640,759274661,592974682,963756992,456219805,
914439771,151353168,279011818,221813710,38398307,549269073,551562508,566405153,332118073,953223763,
799491895,700707394,113435551,398766834,133353822,150602003,831333074,147032432,504487314,222205354,
405645496,723867792,61759293,584481426,471773286,777977184,519949530,646681003,526236352,194577321,
809222263,496548978,827523166,105377370,165652977,385764317,252276660,813922454,555348055,729453757,
129573367,744194981,457223102,299885815,618422709,395484082,126446890,648218151,804036996,587306174,
814786578,999272462,137124827,701349279,616547697,121611864,571547358,777891674,579026310,797047452,
26521858,114435617,802412257,169124204,215236087,688671269,970178911,579784684,219556458,147601508,
78250212,288533124,46391332,654400800,127957712,288376964,447831661,856721658,455281427,661208068,
124720505,784328296,83742308,645136939,870207228,387661543,850256427,546232102,237219249,64054870,
600134598,627224179,767939513,799543257,402672557,274944866,308858819,740265865,512448358,991650878,
645911825,956665119,227819181,264138838,640093057,939298366,349773164,466873107,51902660,210929926,
663797236,747204507,20367634,951529775,810386801,473692937,487460232,960418768,756968415,446107491,
340773498,563159079,158908121,740062166,274086954,209013538,99417853,985814949,582309740,383465160,
862445523,547122571,921000704,258154949,315644511,905760699,189086278,903688809,72306244,467635649,
757216271,692393504,226454119,303296113,600618807,281082858,955761795,977522616,928896727,73550376,
498093730,926268160,29829788,870765097,790512514,429922894,250677164,198898555,703615978,503660241,
585212953,761586,72765557,331384481,671259882,113555757,425798508,827608959,202680333,473806291,
159088126,159655782,234867834,982583389,154253434,425183211,483985637,283120609,414420320,379499494,
667976899,890748171,907572314,342273815,159288177,141475341,495595407,150316893,267112094,457803695,
579071419,580851675,54399769,291903508,277660420,835673219,854868575,941368331,39839149,153137908,
552284700,658655858,490433002,128425068,183017654,233969761,333926821,299577091,575947407,146288039,
217890425,436547374,802254992,609484588,441280021,94833141,547178759,656767153,933986248,412296490,
197492522,836497545,805912920,603375809,279485153,649127050,510910189,347312087,385087778,935143721,
29991160,642076486,417212393,68884246,471080863,395895537,287295233,651650208,149429557,665093464,
397658721,298635503,248463494,874410520,20099543,417179796,152933526,245913735,193561475,329764839,
11427806,885837398,291259321,827195170,921128170,847098127,517839802,618538497,532134263,94529002,
53425690,138849247,310570637,682585031,643704075,966299594,127215666,786540000,167907191,679025228,
485633482,806634435,738119181,349104487,800332009,29389736,551932883,996724930,553115504,682932658,
219540704,489809814,24088460,576842206,613130575,699665270,431349304,719349814,540389937,38241552,
766042037,483010622,305813127,251148939,374855030,341080926,507080284,816407982,180109787,496955257,
503893419,906099719,5964446,539086109,715276991,794068532,264344256,104530902,204823821,996644353,
27598408,795575816,860027467,29899264,457484534,867437681,518968917,834027364,383075050,976826191,
337015277,805756606,400089972,288805787,611294194,420461267,588528601,406816433,985084497,870101912,
804489059,909182872,165735289,593714442,365366010,417971458,107043907,728636918,174192020,556806865,
127009180,138842281,56625376,677887197,729410316,794195945,976229258,179638950,69504322,43880335,
687117651,798926383,406163841,452068312,125499533,791059019,103191494,662840751,65247594,318414918,
210152417,700784743,659152243,953173676,335349726,450091572,380140980,156212264,537662963,646685163,
239243603,8422870,829878984,536852008,243178390,561193704,9595701,667306635,891155205,636921201,
754320139,591109528,342815193,847267524,897455026,999506054,77075250,357175419,515055214,838231371,
510195596,549801960,637626737,572191055,102421049,435926354,534274175,517772600,850006633,197866435,
976079347,192635771,820437378,695480738,292854442,41120417,167359202,660361160,564585446,679389703,
350553695,903606576,998292565,931846039,352268502,33609374,271546767,263043927,14576039,396597056,
131409787,39120928,851367085,983967892,214379615,859688988,602966665,573348610,565916000,757045125,
804498033,380805769,879102296,35195477,701101026,377632949,333420568,829882732,708367800,846684919,
765226050,424336473,187033017,295503913,514825384,399731193,495994398,333004065,147057138,404203129,
5488485,470281533,894014898,216161532,818474929,180372248,359034750,63721621,685812381,603524919,
66213298,448698936,900536021,547035629,912487299,508884189,253391000,766872554,795215145,827762142,
200249394,539832913,237477547,418468113,38840884,736999347,596806615,125809763,970220700,390377168,
33425373,606274476,458082701,274986345,970761333,387888086,7041582,992868549,460075381,589147267,
103501237,562330336,362544845,363813038,764307588,204580805,940103841,582651835,387486521,664945089,
276691122,891751083,164262048,587281725,603060341,11393147,695373169,510833200,577606984,860228068,
938726011,115405595,169467759,840582496,284064225,477023046,234245330,534611683,167034202,576222990,
900191180,370540695,932514844,386169623,163566065,587841115,974815467,945406355,653594878,958558340,
835218871,691187773,341160117,792269492,48440019,365030977,61173650,547762041,734374326,694957317,
170046637,269294877,607477818,455912048,552685370,643046469,956784516,609832625,390886284,314407367,
247748729,573570990,904120898,151381434,854627154,946720523,645590752,744605730,137575459,394448931,
896581460,724141327,814563488,791980925,746445444,608858723,840175595,734400048,23861149,919365490,
818012381,269074959,726575910,99950451,852270575,983222539,958557011,842854317,651706625,859747016,
267027068,846312892,480173858,547168185,714178861,257440254,530387113,235029698,874402480,720658154,
550278439,954410128,59448622,510678704,638335171,688237164,181786296,425998804,209116410,375191723,
197904494,527981096,51562214,869759575,71308358,572736184,825591929,952769822,283698612,200571038,
66603251,554931343,228119733,333076163,73350823,195715562,792957209,664820669,261184050,901269902,
137486377,510102302,73168036,295954051,284854650,941335383,555381263,464428707,746341974,282442646,
892439366,922183841,384113273,733484437,435474318,52295392,260241168,890470500,479943239,260624814,
260624814 };

#if 1
int main()
{
	int i, a, N, ans;

	scanf("%d", &N);
	ans = tbl[N/5000];
	i = N - N%5000;
	while (++i <= N) ans = (long long)ans * ((long long)i*((i<<1)-1) % M) % M;
	printf("%d\n", ans);
	return 0;
}

#else
int main()
{
	int i, a, N, ans;

	scanf("%d", &N);
	ans = a = 1; for (i = 2; i <= N; i++) {
		a += (i << 2)-3;
		if (a >= M) a -= M;
		ans = (long long)ans * a % M;
		if (i % 5000 == 0) printf("%d,", ans);
		if (i % 50000 == 0) printf("\n");
	}
	printf("%d\n", ans);
	return 0;
}
#endif