oj.uz

Submission #476471

# Submission time Handle Problem Language Result Execution time Memory
476471 2021-09-27T09:35:13 Z tmbao Calvinball championship (CEOI15_teams) C++14
10 / 100
 21 ms 8972 KB 
#include<bits/stdc++.h>
using namespace std;
const int mod=1000007;
const int p1=517246;
const int p2=241382;
vector<int> factorial;
/*
int eval(int N,vector<int> g){
    int total=0;
    int K=N;
    for(int i=0;i<N;i++){
        if(g[i]!=i+1){
            return 0;
        }
    }
    for(int i=N;i<g.size();i++){
        total*=N;
        total+=(min(K,g[i]-1));
        if(g[i]>N){
            K=0;
        }
        total=total%mod;
    }
    return total;
}
*/

vector<int> inverse={0};
vector<int> calc={1,1,2,5,15,52,203,877,4140,21147,115975,678570,213569,644248,897992,948871,68787,289756,31655,376150,168800,91307,657986,206795,572061,963085,4999,385141,770693,994876,63020,227947,500096,456556,176372,417897,668247,479021,826626,836392,477381,777458,310987,101121,814571,725335,801448,717728,675537,309204,315192,677296,404901,830968,519367,407946,615013,279029,458582,420481,737671,802836,946621,785669,828421,154453,275741,708831,60683,112355,608611,71590,193969,693860,696252,588334,895074,169899,584318,286599,80653,590271,78772,885292,366834,369055,523881,867086,128536,739440,628404,400204,170905,305202,354765,503810,862604,855408,331322,646648,301983,857350,697969,729787,486214,364391,205015,246431,288604,764739,602633,278069,984746,711674,88592,521257,595364,764823,657199,620114,121580,253996,629662,776215,475882,316964,552500,11980,978878,34452,762981,594325,99211,115745,836931,722248,688358,380137,598350,269788,459428,156984,655121,128826,131114,392457,356794,732432,601711,267319,58347,18604,929385,312809,750448,633645,637058,215424,416083,531241,867681,472940,832123,707623,874251,240226,628312,851637,414537,773505,96675,960731,348854,743275,494573,824746,514458,664957,890267,293755,556895,763984,2031,339136,182826,302091,449300,815055,125445,669416,280957,187737,948514,393769,321192,591882,321847,137343,753629,593928,207353,659594,343024,340134,736468,761322,538339,464503,184723,594806,337801,509309,355821,130479,215413,600081,258855,571010,792932,676479,815975,777972,492531,666545,998206,465135,474909,702017,691661,752339,907034,564026,698471,59448,839489,899457,57452,996449,223064,469791,953319,334717,959155,620904,660112,869508,67091,435967,593251,792793,788987,279158,304825,135112,160611,494759,360060,15518,395611,839382,189323,108058,681408,705444,903462,556319,381674,876338,811384,353656,397221,395670,370793,955014,578594,28502,870820,237760,506083,81333,675710,837208,368252,162080,671046,927970,389640,100629,703644,734440,85636,877322,828284,672982,669250,559837,626612,115994,298100,720913,951860,613712,757220,378866,33469,669752,491195,181909,397907,878978,553018,137121,383046,424168,990374,347908,786699,158343,312344,228069,377957,719571,370123,738146,124672,41270,833202,445944,151694,413083,140984,287140,327829,374013,426696,364051,310841,556641,979567,524984,731780,270279,799974,976855,329538,379832,383890,24242,244628,460050,813730,840657,48585,968604,682057,223488,632032,256652,619375,60694,167441,332585,651533,289772,630783,808670,370176,60699,887942,467096,434544,332803,434450,389384,907852,398156,684904,622492,409232,335873,770922,123322,934506,427596,479187,368685,878666,549569,384764,415723,344697,446101,753254,711582,337730,284976,183505,270757,69688,692730,662708,106751,589926,391000,216540,987265,812716,834077,320779,597545,252063,854312,177259,421630,782945,592919,243002,489201,154088,780387,221156,840698,133057,576567,924448,889929,619367,500606,818474,816352,525751,420298,131650,616265,634181,398430,838118,867980,445754,755185,359902,544456,824588,191765,817042,579721,419235,260979,422355,764923,365741,113413,524469,935706,226278,142934,55985,63055,99366,294535,189999,850256,968769,185289,267165,808925,671094,295559,612633,166888,236014,345583,95162,614604,927413,181820,516990,279549,21878,202291,840505,298232,589292,116129,121083,643534,135045,998232,495,949079,859299,197406,792682,379568,638613,644753,732916,144740,844137,721696,441267,141192,897666,636591,308963,731927,299977,322566,623079,85892,365814,103903,912535,713635,207685,570764,794480,865068,146446,656012,258621,20631,245360,87348,706000,406290,886101,416389,294007,606152,713246,537846,585403,281699,542326,988465,884339,163858,540678,772680,519958,541077,262585,199812,47223,483888,89981,337530,793848,713730,569128,700921,216886,822638,731995,512356,306455,443409,164212,509040,423450,635740,379832,509556,849684,460077,296825,964894,581297,998250,378493,377137,246919,917362,464394,620477,767022,420774,195474,991446,912007,385864,369809,238573,872519,903738,314489,245125,590319,803903,374353,383077,871199,836307,766791,137447,877161,460495,66088,735765,162463,769765,886436,368513,211201,834431,708004,25151,415086,443792,229236,254959,819961,50409,717832,853906,969366,314204,136518,89357,794510,373593,169048,770548,338763,911675,202189,641048,93565,942349,775442,858403,245518,153911,973890,208603,516971,396270,167587,382927,721903,370178,728946,921210,643146,965411,287684,665660,418040,747835,285382,540121,911792,167491,341014,555,397691,201903,663032,235871,335015,135790,77566,306519,329608,734688,270986,858465,892811,414786,970451,489924,226876,142404,418823,133340,517939,460885,104144,619777,986956,818341,313335,291805,303474,952582,555157,678619,374179,489510,91933,280990,31158,663864,469116,855923,570222,677253,190408,349095,390144,807615,974332,876702,299886,819991,567088,652204,916504,5847,932562,55126,173880,583836,984260,515127,852611,907972,59066,688211,190928,545353,872038,786712,667563,60157,92839,978157,302180,477689,492433,269113,919445,209596,350938,652574,43105,503214,317055,963212,970275,6703,801626,856776,260257,435196,662625,346613,967734,463449,621921,919424,620061,680943,736911,28910,49171,539140,642190,261586,761156,818161,308872,683497,238291,836261,14881,547263,808664,433576,114359,985515,364715,214256,726157,605268,828539,89846,296454,395816,614182,39272,951360,98995,55055,223201,248690,339958,228867,309987,342438,505111,474115,522885,403440,223714,336606,302089,424598,438703,958933,809550,939688,451014,799635,85824,859667,333511,977344,501059,699820,260801,390748,582379,498136,353864,755991,850082,818537,327521,725592,434951,436399,570662,718921,381204,561242,904713,235548,124183,464973,880418,890788,920607,737938,830098,482151,53546,832753,268130,149095,720769,337158,612663,20760,47410,750537,178473,570321,30877,602926,481697,744035,781850,273213,285017,719384,241208,389259,734129,61743,922313,305666,90457,277558,48468,397272,924882,460696,436401,239286,933581,68416,185011,47746,936115,923635,358033,518209,543947,229176,8083,876481,943756,263248,421627,302245,162415,666445,597805,334924,10336,184329,388231,261880,231754,868479,211421,248372,990747,239268,940582,550626,635194,28748,239466,947727,56581,673334,190975,737215,942465,417102,236912,51594,491659,560378,251860,960163,536486,852008,841274,295673,140559,302791,223762,530147,638123,326462,153018,938265,727040,314927,616794,665947,551183,338734,831452,39137,999688,991383,698268,182743,174025,51044,21147,458197,252056,960193,323989,83696,423443,901724,783928,781778,799854,439975,211578,511370,377792,548880,126797,529669,89697,324591,58645,627018,497714,876804,810168,534519,506611,479805,889237,317756,395052,47000,563097,68153,479270,122073,556914,526317,149235,89254,463575,864526,881245,37097,198917,27224,876219,407560,857792,529411,443638,624143,728986,202058,567328,358914,989200,842463,586252,207848,709625,794085,499631,36104,854872,961141,315053,278190,679356,559891,724420,873247,239755,872725,234819,975567,533247,871235,995524,14240,537591,76298,882370,29417,963748,905171,253606,388216,536152,101241,869272,90498,463226,479345,324298,644167,563929,965603,564734,711079,732145,122913,281798,435912,760643,455544,986667,236218,928251,145568,392356,816638,65194,117464,619957,19076,839398,990207,623818,110766,157729,380783,589855,428253,288767,173724,62212,605768,296912,16813,526366,827185,786350,850120,778894,688299,992876,400091,587050,890603,103356,848730,759751,551453,791629,108107,945720,424458,251095,744383,887901,427755,449901,224401,860596,855059,43265,260858,914553,972984,723641,396343,80994,238260,320031,79673,509946,988568,372112,811059,743005,338921,516843,374169,36739,861315,517097,857351,755788,7524,786944,262589,961051,646483,634279,343302,644305,761670,479640,628173,652178,211809,656456,846652,81336,174258,393762,500482,654165,412983,316451,546521,780861,570267,381479,11970,271367,306765,921430,471534,99397,946305,660307,337058,975746,704146,657714,545416,192503,275809,411660,903127,755409,59728,351535,120234,260287,242330,403126,692829,860772,799896,560101,206457,238445,543303,507690,260427,59255,603568,921313,955953,801824,361987,407238,762243,382176,985411,811850,995468,417771,586298,488026,202591,540485,500616,789412,499860,943557,383218,622266,690491,984563,632253,748987,386216,521464,893228,506691,950281,299512,320172,129572,514284,648026,447533,982912,172704,294535,348031,401901,735248,891730,288087,304637,79363,73109,266796,826409,993612,700944,857016,914572,283154,168470,798558,763688,498783,504348,647843,882540,972571,466658,37175,186983,876926,597623,920618,728095,74357,667078,889498,245768,98669,498036,65304,446273,378924,182322,720266,637224,174403,960545,190582,818744,394153,630278,469328,92882,799221,61236,642395,353034,428287,185992,768446,219216,256904,27542,467974,137376,651373,18851,92670,957046,401971,503768,427539,657343,501849,172496,673642,565394,991105,249464,891299,575289,625593,714935,383848,516262,684316,603520,475155,764478,655572,486170,187275,295688,245811,843151,721826,493699,510158,401052,696987,712522,809278,277973,263296,608257,202228,151445,147281,78648,759995,511302,936615,376138,991865,195174,585240,469364,412242,913657,833322,627934,443073,259214,46276,501661,59646,664913,547677,924745,664096,454877,91885,478864,528605,91658,842476,169959,512277,44220,844514,473580,293901,569716,401181,403757,932356,344220,908502,551352,646882,448421,967908,915628,928911,39550,961247,934936,50652,901966,427688,129311,286790,574414,255215,864622,906609,628649,943689,516041,645710,273525,135929,475759,166079,268797,134569,162249,790233,113914,7016,491333,450712,183547,744408,861086,348893,278687,808756,729868,458499,369393,70670,379264,55765,894851,438380,683023,795423,126955,324629,4979,572267,395726,206514,522815,929688,17733,768297,105515,2735,959175,883701,900852,143852,92559,230029,980751,974608,852484,958409,353074,603345,927300,781593,847005,113358,443269,715368,479219,154571,563617,165007,838224,899908,721453,324495,701001,208532,384897,528596,500549,10796,564430,53816,558193,149993,541812,34962,709907,642407,801324,315588,307909,200418,967470,861677,335607,505117,241718,591425,628435,520480,666014,85091,848190,662250,452895,325692,905489,285928,624555,432965,607166,223045,17758,663339,69836,518506,940175,672864,594294,975923,153845,393357,251420,470684,686544,166056,824184,956210,708081,489206,786889,500341,232298,590638,153599,76744,314359,55802,918853,205783,291466,443500,752199,307506,309179,367605,535604,104615,370171,47793,490613,72069,58766,845437,984527,454311,838574,295532,549935,949757,584913,614426,567134,267231,709030,694787,694602,432522,37077,504445,871334,271804,649977,63289,948565,822484,633938,563689,956963,200008,401463,522244,709288,618399,594217,831607,149032,461347,373655,223170,866272,668978,502314,978213,893170,303205,286261,711694,771651,229493,744185,535670,29218,793430,621599,422022,812704,865028,909683,599777,700310,803831,772280,531638,127285,339113,780888,834161,387323,243561,877029,103433,972528,994680,670637,950714,468258,416794,260133,29984,429226,378803,728657,907234,293966,652785,741644,972757,940574,141373,445517,492295,291986,863292,806395,71727,424332,261453,70500,803794,773056,564449,849489,994052,198710,403130,411142,485606,483541,373406,128536,941689,697499,95485,207575,562347,221819,410713,740213,550053,64907,622403,479962,877571,996918,538871,707793,378278,354587,463271,161399,771121,25976,371174,902751,890774,27749,330568,852784,208432,724267,950889,269478,203262,718278,803168,148831,135341,595414,357928,290336,726986,373942,608717,777038,860596,64879,988552,230154,579561,964137,311629,752940,653535,513045,527503,999898,250666,942211,539197,298602,89041,731503,796939,893970,675034,407637,631181,795410,99298,268512,86849,977638,583339,489373,836540,449800,581253,333818,678598,216261,818123,362555,454545,681181,440681,168307,75749,466976,256505,529326,335672,647373,665683,887095,594335,105293,248124,178005,478495,579781,37056,938442,658507,70225,185819,340088,236579,257526,271046,826762,87460,939860,464722,664639,740188,824634,416806,295876,260754,891115,834498,28799,748861,308186,324127,292410,293565,838195,800726,818492,466471,441168,194013,169555,481054,116264,194782,400300,590756,346748,85430,517229,896109,351462,727647,611849,858636,606495,239363,25661,894994,335411,567556,810953,887575,771696,243615,487899,251722,809938,925268,952964,743989,116701,579180,356151,727417,767477,368958,538395,986139,223697,935965,123990,563684,669023,803286,562738,184751,324619,575586,378270,498015,857943,681695,332126,750931,734192,492237,483506,614093,431548,266710,657801,321042,153325,309471,822905,359691,162994,320025,278782,702145,261091,271477,541409,983549,130137,463523,912734,89225,894133,789321,686788,261516,583310,669252,37999,919887,523757,483832,722758,980612,780752,275166,162239,901760,58047,249018,444904,833085,83086,489474,378872,451291,259114,299832,151210,362828,104629,483956,582358,486682,803878,795029,339531,215602,833310,740731,79563,684223,454653,921764,573009,432698,190350,352392,626816,236309,822617,409986,287998,887148,910708,719490,647024,928013,204514,401535,804966,874160,373725,972217,926543,433710,931375,539582,799791,775415,757642,308434,916107,326962,971396,363870,188291,365224,474750,700395,320781,777701,855646,289963,335680,969401,913606,378573,502961,805530,654661,386419,75414,671793,434649,649648,656452,585059,117886,50032,811871,722664,297278,912678,997978,242548,233961,737564,81605,185243,90750,337466,624193,851753,603991,385262,408979,480106,778053,292213,682407,597741,617531,137389,480151,58572,322784,740030,192380,630547,404620,222187,899484,181939,489240,518516,79321,817674,507848,861911,665250,653709,826415,739476,29656,952450,257166,435079,628447,793905,261143,507550,3552,688160,461918,723311,117539,289762,119347,135866,414274,322638,89526,895787,790948,737988,502763,448458,934923,551503,933590,383010,64374,98099,171706,267946,262140,183385,581884,511405,587314,496745,728186,840332,667807,152362,142280,813956,874186,72145,407843,93824,822303,464317,992279,304898,787518,404610,14706,847670,920896,621456,960527,390178,495605,41468,7586,803347,197660,876970,861039,22644,825015,287526,986292,418866,108744,844280,215914,485920,236222,669529,846581,96693,113231,188177,901209,448604,382192,408423,207470,712183,310481,189508,510502,880011,291290,635918,130916,567148,756077,637869,216855,540117,851975,700608,98670,436310,745748,483250,466049,102303,667254,979979,797820,223656,652388,745955,50451,788602,751369,648034,91967,278160,777887,735373,393894,680519,932247,510983,382140,155048,457045,354245,354012,630941,279114,958080,351609,834195,459373,24219,615305,614258,658486,450565,386868,927387,676931,893324,453510,429374,942773,591379,9142,94416,889390,997848,121462,304724,152211,239729,961804,562510,944043,356377,156707,592870,969812,871119,927465,421188,468400,615065,617149,839960,688411,775278,317856,128449,427675,121272,483303,209611,218960,869338,567295,735558,994363,180298,403917,515955,51188,365286,310171,209742,184950,185785,373669,218871,416018,431,886070,657260,628356,801735,548427,826611,51118,399191,811113,697409,922209,464479,457390,685414,515198,244689,513049,148472,141684,75608,98444,15429,610945,429750,800357,262607,681463,564465,266394,118096,410019,989842,893122,883981,910905,6174,98560,423313,8349,722153,254144,694812,445191,565935,704030,963672,791479,14959,409445,392418,939806,293974,462506,163790,711867,466988,418537,870095,202068,114059,120170,889384,92064,606402,340098,823734,709801,985963,209305,211283,4131,920298,282805,513676,464535,735330,625896,763496,506333,960107,759728,931666,576058,439297,549241,531790,999518,502365,692661,297111,491058,633796,277006,97357,220009,433539,112118,524553,250446,481570,958923,432067,778430,386212,621262,346929,674024,189309,482144,515763,724202,24918,811493,161934,171672,956654,56109,976635,533810,909094,692548,527715,350194,116787,155781,909967,921739,475888,638034,723207,437386,84276,690939,59360,321328,897147,104068,459870,567078,867324,663484,953910,265398,782791,953458,732942,552633,389566,330746,890852,246260,944930,587914,181393,30400,872060,1076,226587,522245,714831,956900,293056,921915,621191,570652,262454,917531,669875,504440,457394,900482,242250,406657,161522,981829,800273,415406,790194,510886,986885,408137,923732,659553,987633,505300,533555,147604,928342,363222,358003,819005,839595,843263,523763,282348,333997,67588,323544,609386,101342,534908,595439,168980,781283,388454,462156,128030,793680,406586,892142,90800,730728,274,420053,533375,171755,683434,815736,274499,92629,371159,622480,920922,359666,989502,269187,17168,507670,850415,292798,889728,774088,476637,372458,864033,589573,335660,164277,789773,236569,631880,977591,869821,975468,744989,703236,292097,610728,432265,645929,796391,677765,953492,988931,310135,827366,738761,897003,758633,768557,969889,513826,733863,631804,556962,35299,116414,174670,166069,565906,821044,971403,403132,376211,245712,645885,995491,866726,878096,681731,149444,454636,880567,471545,803166,706111,459531,105175,398327,192519,598727,390716,492186,570917,832169,339775,944896,641611,736683,96382,400454,957867,710692,111207,777553,753025,571308,398145,914956,955966,58710,265598,815264,298933,348654,883300,581309,30189,70451,624420,915527,510595,15494,446132,285476,139465,926068,53342,162031,305070,748853,26023,510542,490058,344510,448526,745513,206264,659861,691303,14706,105026,880167,79523,706636,785237,380838,255666,509229,478315,660997,735154,220251,33122,488143,556619,710113,467391,29904,862079,698907,748880,589315,587948,622652,141140,798903,112516,921218,578135,358996,571496,138792,327639,660750,826686,796998,13318,757643,520670,305805,17226,93109,301782,398878,151107,821515,932438,762964,913346,911924,982615,341528,149601,957182,468154,436769,797292,655860,260621,909054,329638,708800,714035,392692,430184,72003,261631,176266,991771,909952,793641,809381,291711,960906,554281,191317,833686,901214,508687,731499,919314,244758,103284,967534,890846,764605,910884,588689,148292,120965,107743,263378,62728,859931,878979,564685,974259,858796,619370,318003,714522,61036,892412,360449,817740,870903,521660,443063,738154,594367,905828,460861,227594,480545,781042,980618,57743,578107,448441,812008,34047,939856,863226,545940,126296,65969,433499,933980,1459,727940,162328,177715,739999,897639,906552,833701,118396,911383,268797,124996,248148,482751,312968,330568,107084,144706,424653,461354,618666,130380,152431,805937,543331,393438,96426,427937,10542,239705,69336,785019,137817,933170,808766,677722,265638,874948,161874,339331,352931,727477,833651,335005,771674,118158,249025,512980,556599,482507,39182,656304,430026,712396,315951,519752,557698,689365,572883,286796,275614,250838,14928,858493,597100,950520,740239,172983,570578,898114,501729,231057,859628,637648,953447,159646,112811,114267,647462,772104,435077,249831,5430,651263,862589,257786,678217,2642,171403,353699,491212,193023,425977,169337,829575,2535,332660,749927,428575,15297,426150,205471,939320,319798,812321,71899,325366,46184,330163,673047,763892,770228,469736,85742,750577,82821,163083,748025,645014,988271,127943,309751,141237,920241,574329,820514,238844,985273,751051,777259,646368,108282,620298,498114,812603,114117,203188,693490,557079,595448,89186,389105,921637,776558,454037,879527,273378,844224,836016,820552,652944,550730,608330,538792,778609,525304,281249,304452,881530,25706,953910,105065,455043,369282,671598,965321,533776,458963,916141,344340,431288,717589,498693,76443,749776,295046,621914,989916,366943,511270,819441,204477,308607,211222,481782,619892,630400,964250,57184,271393,588702,939861,148550,209278,754493,737423,757810,540353,311280,562700,612734,2618,827379,629455,303784,939987,555589,792083,966819,806302,706833,601319,261919,954992,567284,431605,397383,37330,448556,55102,540891,557841,719852,47600,268881,263153,454275,220610,433324,398026,281897,894495,420548,99460,813148,467812,773366,301342,936470,120051,990780,685428,512989,315127,863875,702586,22785,727074,579840,122186,131381,156538,245895,916371,699187,233737,591236,213012,956525,195554,184739,180737,806961,513388,161769,383029,435933,99318,983521,964229,688626,989704,105306,46426,851231,600393,223793,910130,283060,222205,327816,177977,310123,33257,546515,933791,444015,962651,281113,338825,313970,268490,938738,420707,892796,810722,230732,405240,325815,741427,634171,695830,842238,149089,457684,613721,657647,312212,456409,256944,112579,392303,720915,925391,843771,818836,521693,927164,309725,985966,786264,723156,251262,952302,506230,150222,238722,838084,230823,526962,547283,413937,495761,908483,987487,392295,87585,384203,505388,148936,309338,478592,487826,214028,489466,914155,346879,414033,6884,730364,883938,466471,657668,703635,424498,415519,848014,640306,195516,581378,327871,137756,83441,684536,304633,196694,861635,245772,319857,826790,134205,678335,223138,936895,139604,807457,176331,161569,405350,600962,371212,448528,579511,617384,841438,513253,795628,536339,86664,985307,503715,380537,585286,306447,84103,556436,334412,984972,337611,991963,856349,529254,870628,651261,69418,667166,658095,322782,894657,879828,24465,558518,474475,175203,507872,694924,849174,248487,427622,897534,457221,709033,233863,171174,606793,376681,618260,684788,196356,719183,191510,904044,336139,321275,75187,412129,397261,622953,895245,961665,911889,830725,50846,803640,735810,537584,554193,944154,229352,350281,856998,328738,551042,666475,614374,349064,727995,17061,148022,94474,726709,143070,289626,453676,119683,323779,958324,127785,684438,320773,217703,207409,733743,193492,589932,497905,475157,788955,679479,450064,621390,354216,665382,44515,572285,264265,341519,632430,547365,756911,493770,885112,98687,564972,272236,881369,210966,247325,677908,926464,674352,58047,828954,613745,651133,691681,20435,512220,432758,57930,535646,504345,107096,977084,37616,464216,4628,758061,409478,353848,630202,951020,844342,413525,780672,613209,692305,716421,864013,824793,511915,631627,266205,270597,619606,549243,514183,837905,354413,267605,943346,702018,15650,183673,48692,272676,667550,32642,832902,703102,493929,533157,469777,157176,526429,766231,146587,553978,797946,899768,945827,248745,23219,537461,406315,739434,857832,915063,914107,449143,406382,845037,523728,64370,82754,364604,771265,563866,165588,581704,1000005,410642,760194,977546,4915,426080,687273,898793,525515,797736,437989,288805,668856,771446,679561,948599,248003,451867,782242,122391,539800,298388,152663,117947,398167,846655,926161,520309,795113,149321,502009,95151,83722,183451,388237,495289,562225,732492,434223,374067,772989,904962,409124,586132,85293,42701,731713,238097,732574,503412,721795,232330,528091,639041,517058,816329,914845,600987,304635,335986,470294,254181,235346,274584,308792,831848,777245,208193,551947,598310,218002,96198,973141,117177,749445,868832,712194,398466,425822,488820,937292,594817,747547,628165,115700,978404,293606,508990,59675,323086,573830,371397,644769,599906,896563,268239,53149,332660,929499,410538,658409,139495,802793,999475,348178,56423,157230,507656,398584,987663,871027,658513,441975,542785,385712,130956,160055,913026,962166,134938,835844,670069,374981,510533,268086,706723,179473,976377,270925,547721,432671,419983,267432,125041,810183,249548,13098,897800,696486,14319,622452,428337,87468,252101,760376,817069,762549,617444,447071,673584,279653,615495,217324,143321,597414,729405,48500,912983,960759,800831,93524,771213,329327,179755,397757,583633,946919,747171,43054,885692,849682,337162,987450,431887,509344,987565,270582,77699,151242,92515,412551,178583,989033,625686,522792,201074,294373,860125,886090,302920,700920,702106,400902,355947,49725,383145,547843,819590,23475,166334,72073,176426,40114,881007,888658,68402,581407,920153,434074,142504,142379,558249,704720,132121,587667,207822,408474,143096,750583,534099,533013,234443,28121,596256,756727,733609,240735,384892,862487,547141,133339,5823,572226,545869,571219,848625,789568,377145,148612,379105,515987,836464,498924,654288,683344,960963,419848,733856,777721,9106,478585,976495,500209,144852,396113,21644,431493,79659,427281,899571,425915,948242,860293,649372,461228,491216,868798,571507,235748,36431,963202,602908,589693,641487,154662,140444,484658,919502,898215,100171,901576,474541,569588,419990,828774,318824,141917,750767,233549,240112,238069,447859,913835,64232,148481,938692,648944,403549,79434,67767,660277,60827,544400,677616,76538,930764,173272,993137,399185,36114,399314,708771,704782,310310,505401,510261,959521,116874,29957,587908,197402,744762,429691,348021,454548,747094,596402,675929,648439,128112,716674,616032,988590,884487,833205,913616,218431,884567,43841,521966,120472,26830,404955,304640,111915,479430,906747,10170,249448,351753,22196,962471,469069,745153,335978,551246,697127,339231,619340,94406,738740,141690,578717,173513,371290,761117,408728,979115,908774,935812,930498,841603,274252,474388,854607,894848,833963,383962,115675,323380,632068,241098,300770,165820,625946,973167,327937,844188,454464,895365,243299,14006,86545,433188,85999,552411,969227,116882,894839,410145,285411,566259,938829,165243,675386,96118,777631,373776,854209,372626,572782,586766,895557,653713,793546,895117,222085,703709,93852,233032,253207,168862,9164,968865,705752,123280,641536,695114,972912,486763,846643,641000,237255,705268,13464,492962,207765,204556,69898,61115,431102,924697,498930,997535,310045,994176,439730,543659,857207,50115,697068,528790,52125,551154,587974,774282,879661,559022,345550,195026,941678,844909,60577,777083,800429,718938,8843,275085,823136,849836,897770,640820,522782,416038,712966,1942,384010,504367,660560,431548,443165,166336,918293,207418,310779,512539,446604,463436,960877,491128,201801,174778,212308,306703,36218,209775,577526,356372,768566,126986,609499,262482,90920,316506,134348,375048,496709,354348,313621,171572,942964,248200,203721,621652,156162,490845,94170,947724,3686,756624,136729,301859,624221,5322,468533,527231,584813,634552,320016,423670,518325,23901,743435,225225,140812,551748,583144,300927,783008,485942,732438,823865,613877,33193,638694,692908,760474,538924,144428,925730,313136,799338,911233,412429,925284,65281,320541,352128,337055,103514,687354,27755,769659,751430,963038,527748,742257,669433,217097,262178,366250,61386,216210,643664,427971,112022,184262,490854,728408,497819,708940,939905,931713,273,46493,603997,798571,580784,938739,270278,304385,246742,631318,193761,758880,520462,182961,113991,760001,791586,721731,278424,433461,963654,487626,696634,110215,592316,283312,155345,754248,177029,137710,727833,431387,218340,767060,382807,893953,738815,150044,23693,583326,308509,189166,10954,387981,460549,819376,259611,157463,726026,839902,778028,61346,392144,635624,483984,129058,567095,568808,483555,495932,479323,362103,146728,474533,766335,269796,113098,469240,893778,147152,375164,342211,330909,576907,588046,508424,27351,915951,143077,855701,796792,267591,588821,391917,151156,77084,630674,688791,849192,513407,285386,425250,413846,165087,793998,443428,434728,418561,148332,4787,574172,637101,175531,556548,79489,460887,492803,836291,63293,699070,444873,110274,528109,179984,186019,228311,398834,817747,148323,46391,449713,390433,76093,868430,22076,71826,934787,435724,302966,270890,253019,67892,961678,656956,315864,894268,353253,248918,287573,480095,477549,642698,355186,447883,680302,402812,562158,70884,776911,853921,908979,539045,675877,49648,45321,424676,52869,14533,754720,210421,778401,224720,155687,325893,853295,597154,788936,291633,100926,806293,574571,604274,648177,331202,599628,795703,168586,780552,491192,83719,865820,326804,317022,424380,196622,587198,945718,884463,949469,814331,693288,181662,823300,71905,855883,563238,969514,301960,36424,329464,878148,179066,570650,660674,815055,653976,332202,725682,960675,225213,318881,160271,194354,294793,117803,681346,838681,239937,501058,588807,148389,243952,34182,537695,908498,876349,319476,176112,177300,842208,653291,893358,959326,718453,678836,418956,64445,618416,391931,402795,765729,719407,741311,875013,149255,895396,959220,353410,979114,424270,124173,818841,274564,443742,93332,584444,563169,928738,557059,831973,176774,839273,736176,21370,170056,118405,147017,34317,297219,605595,73039,766479,55233,339661,106148,892304,608481,958553,317197,681260,379686,222986,415013,962005,281586,989337,393773,583702,135151,581424,480061,372310,308557,84185,511284,499290,979251,998166,347599,902129,452919,474731,816400,411927,456756,439572,394556,744678,446175,860250,767513,486747,770949,3188,263913,333646,537284,718808,57650,565938,248767,482961,792031,228241,185257,401006,568101,100226,335060,368153,910883,353774,117438,218569,10006,401880,824989,167943,303710,111254,150041,422831,807748,172622,427085,850585,114591,19373,999203,687822,382952,833889,740560,502714,473497,909433,115155,790097,330707,125392,912476,56650,865502,729929,883335,696465,485051,454317,872093,764649,813646,716992,994861,458971,142069,74543,197963,21816,537870,878469,106382,327831,693635,462963,782467,141334,868968,202146,542635,737561,193817,877884,544585,408229,513124,782014,114935,328900,402693,484260,707844,112843,74893,963420,759010,338621,571489,820505,858469,476002,454226,28179,347416,287570,935801,111417,216778,843021,452037,679157,126604,51755,570308,49385,717613,896815,650219,285667,799589,873786,777074,804225,46723,638561,662508,480872,475039,869485,501579,191216,852471,651081,523340,736367,805738,548790,498312,100447,120839,600860,943122,11940,581514,796135,425256,405882,710837,691783,314511,671076,48663,674641,840723,381811,472191,447322,255521,540980,995257,609134,47684,176905,831199,385667,735758,443203,719883,330866,545338,40808,648351,557268,533395,620482,783799,486249,239969,739203,842844,307995,16905,621103,191294,707697,425255,842698,569667,807239,900331,334615,198627,166776,850333,363655,528131,171991,616045,185917,657926,442252,152513,429283,375129,776381,535746,735485,123202,138362,686907,374137,662554,771333,60764,675976,270403,268439,221755,345342,7617,410643,437950,585326,828740,426391,126807,110660,210628,111510,889260,784680,750472,836802,209895,34468,87171,150523,184572,812079,808258,73033,507413,771975,217406,782877,577745,314623,591049,554734,392046,119781,226342,725272,578428,376174,397413,831001,659092,729294,300651,167724,293190,293315,415496,677827,567153,95853,467616,651930,910263,257892,848818,245964,966628,881522,691478,925528,855981,73637,204893,761113,832160,318487,381072,142422,487853,969974,802295,430878,307765,205764,312323,607341,458790,549210,683297,43414,35981,340002,849857,127400,822223,802236,543616,589594,198051,528461,952751,496815,196720,230535,806395,107083,445400,552563,806337,749018,126337,879828,509474,313274,810641,470195,853448,897840,675461,330221,995733,375797,589153,407532,767070,23148,296733,851734,222728,92047,375550,45209,677359,262863,627796,736818,623228,352145,888376,997059,359019,196580,646720,417361,269986,861626,538465,804567,921636,35152,538534,316084,683632,114199,413696,926936,244018,769640,832417,889080,150949,129382,525230,654984,935196,364691,882371,587685,471723,191040,214812,529611,176570,853125,263784,946457,980033,972651,650014,59960,945631,610607,286876,102216,36590,202470,694096,377695,522669,577233,724270,636725,737725,842180,602334,335634,955385,859441,629587,410285,22680,428177,774651,594107,767737,975790,723346,489458,887329,553070,59093,211148,966292,358047,47504,305669,655865,127271,617654,636343,431544,979489,730302,71622,1766,445214,656380,53553,181564,858394,919498,152904,374336,668526,451730,93520,630298,783984,885894,587124,3027,942235,537211,130888,280063,726557,959641,119517,135247,790404,100436,730961,568447,419372,472091,607070,140026,359647,312029,849914,137857,20148,139911,770783,394349,443072,181743,46305,526612,762707,274206,966625,768927,685300,767652,14539,79778,124555,648748,499144,597811,53468,724916,911019,28360,996472,332753,522319,36107,877669,639487,884913,446251,149628,357783,961893,996839,260718,15156,792665,473762,482756,393379,682953,229428,645945,909226,327076,893665,881394,992897,411555,563800,179250,219714,939781,629563,246689,234022,823267,3428,567401,308384,86828,34582,216689,369341,371545,406838,757462,502876,623729,980705,152026,150237,158024,197592,85432,377195,921341,319984,902956,225341,975113,890947,325484,756211,42927,112222,86616,583465,18473,444876,376783,354465,33924,937390,567248,149928,933291,811226,250116,446567,771971,705066,130107,905515,640323,717469,534625,982572,457213,113039,164804,739640,737774,245745,536224,616634,116101,860620,515680,193762,626682,461755,966543,784224,999467,661744,96338,342158,44734,41972,288929,272690,352923,651961,330793,598303,137569,989592,544933,175935,560753,160731,258577,781397,479623,772474,345959,267743,716276,572759,312407,406675,382643,814411,670415,961337,727526,659137,223688,335622,222252,794344,378336,565117,942207,949623,927903,336937,638842,881738,270190,561445,529234,751702,718465,326979,842441,411350,765367,771572,770062,427713,937451,627946,992138,769804,806265,509227,664913,996760,499909,420496,276216,92409,685307,909213,313564,98449,196465,347886,455695,641631,424949,880289,149432,767374,769238,367572,886640,4860,169407,702183,136357,103954,727848,415361,94644,817918,191292,534386,866971,369988,699996,464970,659220,613186,384176,748366,794098,117242,219606,193349,861057,341301,787687,398180,273345,948195,585690,43002,53626,429884,662,543692,84372,271227,493967,281282,227785,648665,245456,111831,774189,264105,266446,447301,17847,664724,144433,863238,636893,70285,252492,48081,567792,438076,651125,207003,480240,592927,783737,522285,594192,379321,679412,317890,478327,411290,423973,573279,542631,98694,25168,710992,736791,357017,277036,373354,52103,633460,467226,351091,302151,745564,178253,941764,860750,539132,951988,373875,548512,416162,157181,563868,196787,844087,677329,636666,838844,710229,330342,923297,87422,80780,976572,288383,828441,177744,790821,521299,944808,696322,989647,382750,59034,605572,524840,27359,549563,488494,332817,532288,95511,391999,201481,763024,434700,37158,332159,215004,418713,993368,569572,853706,921828,641800,141456,846583,125872,659045,175156,808318,143867,700740,583211,983284,743498,985509,71458,648997,476274,723106,945888,53847,285210,720504,100980,408920,583750,232274,251705,319132,916844,198134,152883,866007,580346,838857,590572,280514,591686,943352,917971,950013,37358,719604,330314,529664,137183,975732,870566,192404,784236,356520,920780,970826,745474,244927,809533,62786,170110,491449,834157,789123,427757,544128,854301,984766,93028,402124,553394,339307,183897,273068,236004,856788,463296,133701,883469,967705,938824,982503,918570,739987,674997,24643,64603,133515,911728,62825,820484,261962,377910,203878,740999,529456,678725,442981,973179,462631,508066,454239,523920,447484,587341,466874,950499,107346,704856,309507,530649,427884,611162,310663,65553,322557,95638,770886,289534,385170,98906,655941,193951,214536,524129,655386,467947,533504,788925,33319,287669,61355,606524,463804,654180,301119,968222,18938,884178,126117,923974,488391,864373,953204,523639,230206,503069,610498,146748,351167,127734,264676,526182,733872,565576,224280,467132,97998,224940,718136,802236,302379,80045,452236,212059,233363,221326,583502,943632,870848,143058,605174,742969,348918,113690,727200,207435,962408,853001,590335,440422,512927,155427,978936,388420,490774,606036,108746,783975,396087,460231,755320,841398,300799,319433,815790,609110,228470,687917,231249,49233,609182,501932,528850,868486,383160,136454,316106,427499,736951,560329,853643,379297,228956,490072,622185,483502,621174,457191,948229,23149,770678,641663,256755,537326,19838,682299,414943,596640,429634,811515,372221,512198,934357,823505,713937,241412,545155,627148,415879,475460,988124,226956,694773,369087,619883,494537,196323,553401,796495,957273,837518,593256,399404,649299,309573,764967,877997,152170,132109,324690,419926,40569,451102,549581,108431,443388,898665,938464,113025,143849,160885,878579,430807,288471,282163,965252,506402,350545,548690,771546,401147,942418,548899,180354,269379,120669,700980,844181,524593,474763,704154,694124,422358,600742,75333,764709,769986,400511,563675,108883,396524,151893,315927,624118,705329,991246,130822,827874,174832,365482,114368,979871,174755,219644,34009,640390,978695,606725,787939,811521,25531,671939,119623,675757,912645,880178,915031,755614,484788,995191,557459,769815,964627,453490,811362,138170,159821,520101,140869,469376,861,924896,769099,159417,233291,820893,694923,277988,18788,994720,474505,758289,501946,936627,301303,583957,120480,369685,273837,430188,91041,310897,349177,317042,538807,978593,815018,413190,473659,433366,205744,230573,751757,57860,801633,736474,206760,805897,597920,432104,874651,246180,25179,633163,347824,742755,974528,370119,989637,1361,773638,744577,415513,407135,427885,32364,423110,628596,936418,160237,971368,955371,351442,622432,909565,906691,872073,379119,516418,838922,317788,513313,993979,630436,942954,199872,19550,224789,737850,725732,802752,812440,729518,229090,689678,507579,16936,572219,670099,5199,925260,916802,100209,959625,83975,739661,949245,621785,339722,367246,49404,988648,831193,923992,486280,667072,851279,917135,465257,820331,730393,162210,460829,622767,438037,949103,186602,636380,246088,106615,41567,996353,667789,830799,898888,921662,443538,517598,435558,897692,727353,456101,973155,89980,911265,59995,814369,290221,610051,410507,892826,695518,603387,499363,794259,580020,899781,967532,758110,654772,377528,434810,283718,144872,720733,256146,139851,466034,794456,318094,98359,676159,322819,467124,622644,801192,324941,894756,460651,956666,492038,978775,189621,96510,667627,974490,247077,925189,985378,165145,215900,54635,174651,533469,320452,979434,914752,955370,183670,307792,467814,842288,308189,598467,284640,936947,742463,278342,817432,772783,711530,951014,392850,393232,356671,440335,986308,172498,906293,23890,667099,37466,926624,205165,963315,609289,257237,108198,8875,289563,338593,170694,638434,552731,152125,158983,860178,108518,6067,619443,447880,155506,686451,929826,849746,177533,744218,76452,961501,56618,527988,292761,415002,150995,926179,781150,940731,54113,702106,933789,984230,999707,830774,123739,222183,362915,967359,235808,195641,373561,423951,71650,479908,760856,460970,744748,968759,405552,422641,284626,655302,56612,153988,740643,150632,783637,252634,830420,721218,71329,754320,278581,180129,422814,468365,362979,99225,890232,154234,985962,96722,168518,630777,904988,123756,885052,471957,519057,259443,561984,874439,330610,809205,542305,896433,530314,799320,923946,342364,234879,512331,805798,808181,206249,606276,980003,283593,324513,760726,882447,368007,102266,660792,544779,373474,189483,174401,273994,661137,816826,151611,598409,432351,878995,127091,535571,339296,234521,349968,701125,992074,372138,666249,26746,263734,592127,194504,353050,671469,989750,158292,46934,682193,440258,994344,273438,807850,514003,140458,11042,920328,756692,975085,817087,867211,512134,850071,862506,719930,832671,910555,489821,180454,878829,839382,407339,806555,103484,975260,8867,860323,265472,425402,447140,762839,307723,67472,621793,415315,41739,37945,436915,82686,396593,704050,458907,465588,303049,350617,444014,882033,505296,997793,983662,317330,704110,710009,462678,330399,423734,409980,769099,339921,313372,641937,145109,273886,763410,849083,264233,615707,308295,997490,993655,540709,23424,129897,487927,879679,489489,899773,58523,355563,900742,686886,968556,337313,306257,548441,494766,168492,260140,987644,690447,731934,38652,130100,250479,202355,829839,60554,747219,764124,852364,30535,378168,837805,739752,611656,269575,941103,648233,858626,737476,500800,479372,468708,686942,52025,943759,504978,87006,46911,490736,125136,883352,20966,202591,620084,477985,847533,852164,676245,510232,33875,22026,829205,391653,598343,553108,950784,438915,558574,568430,363788,715111,718319,227313,967250,98288,533595,443078,534005,717183,996016,140182,489146,409319,134314,502055,226367,438741,367758,340565,750862,725886,215116,54903,283978,77768,475112,272200,203332,968931,877906,595515,390828,747524,594734,769961,919837,480455,795784,370366,702698,987234,639391,571844,953578,697675,145821,892299,373619,697895,523634,779375,506907,492014,621175,207506,420055,801469,248270,861869,17047,19561,660120,871521,607315,681295,978351,15227,632119,46937,964381,627697,914305,491166,653952,909447,819405,957979,59006,775934,461203,800155,899604,300620,773576,987175,199082,77565,902406,708509,203588,402178,746006,795349,351050,63722,35910,372091,525887,169135,312721,114971,664907,173748,798039,202075,689749,804867,46600,398405,666634,548681,172441,177612,494085,189415,186299,772786,823473,906699,26087,490975,994642,659648,446878,137576,899863,22251,860277,275645,624786,698585,361917,426813,620268,724347,879887,32045,538573,290563,224990,399730,267843,702350,383573,847203,57838,419749,303196,669631,38140,670146,663493,338041,160131,727176,762990,829189,906521,5205,456722,83885,117718,892186,472335,10003,401664,146911,755325,431145,143311,93784,650488,759787,967333,359760,264716,563869,291273,68488,645643,886462,392119,451495,392168,137858,769749,245016,342940,295905,800801,650449,571864,492749,372662,962927,285087,706694,673549,37604,186428,283074,367774,418581,141452,633618,237587,463494,461541,108988,127107,341624,267230,35344,899806,525245,973627,482274,214294,462002,63125,469446,755066,807760,742428,143328,908935,102646,653551,555371,768704,484407,401200,672816,157312,699138,59385,529697,12215,350324,217818,774578,717940,981699,224380,15007,66659,657939,44800,565892,195650,746331,215289,19671,981909,683127,51439,316534,407211,307131,640615,471338,866494,88211,418005,73636,328849,982385,381991,486404,967734,447187,922024,2138,221069,880705,419641,270319,329732,148077,756735,190126,502635,998674,717108,255627,617837,864533,733407,482856,97444,907783,756457,195203,968188,8554,787479,939039,652172,401023,830536,903485,488818,696296,135329,898992,565338,480129,639752,92840,861599,762534,682367,631782,412219,806902,81356,667322,88692,984057,839596,782677,883686,926311,699956,555527,587260,745186,549131,346197,127439,13601,92183,120995,573015,771214,699961,407502,172454,803839,859942,920097,24999,708750,33889,203188,226503,161743,267455,716458,976946,833190,549758,201855,350159,207420,947622,902607,348269,818335,82178,599255,38436,921322,417605,975513,50010,806846,195917,843020,194605,51002,11172,670801,904566,138324,645103,818671,79612,890401,931998,846269,863474,446567,569822,857646,444299,745872,275447,596289,251904,66848,982546,548957,446016,618940,266917,338558,428190,994793,301888,862295,945081,795491,186665,491375,82571,291790,348909,206989,394332,760143,990231,509009,989615,457747,470754,763972,27957,70802,568342,836112,410797,137681,735608,459315,38384,627020,635887,25266,432863,692483,930681,855462,538218,34249,898828,346779,951235,876336,224742,762002,531532,119626,799248,286165,374358,238249,899738,344939,801614,115073,478251,28224,871277,891778,637377,53922,912646,315347,263992,783178,434824,562723,438424,146188,743766,869759,815573,474024,211602,498183,754966,577681,466803,223630,79893,559262,146517,328161,486749,972708,521573,969876,912441,218048,960797,64049,359548,474362,362531,165305,363205,144827,546565,513497,824177,664357,796261,969973,127543,397861,914361,633274,69580,699446,697804,497878,406909,596214,957607,977453,29159,63173,590464,543707,688976,462217,417437,904488,849685,372370,391532,723749,223639,8577,857824,347003,436171,771237,40079,772639,28227,81668,796776,372720,643091,747401,964396,910722,246319,415943,272374,747253,254803,89300,697824,45287,669747,396077,846001,188557,518739,903798,603806,23541,975850,317572,767178,817503,733818,969455,365289,915746,514749,709050,829733,225975,425922,272212,153789,230537,176948,439194,121922,540285,816186,828923,609675,783418,652689,107938,701114,611745,851665,848881,871484,856955,749616,432377,908067,915867,928824,263841,911890,948263,488859,67674,487568,322730,338668,119198,467272,803379,693937,523244,892644,347759,228866,936454,221135,409190,47195,550580,701044,966058,281503,666866,768361,833729,692173,20224,964292,100201,868809,833280,500606,584330,738045,972181,360908,966006,83537,685466,55440,765412,693408,808620,904680,796698,631284,231157,681368,339598,234997,472653,701353,527031,434284,682034,5331,837336,748117,941245,549813,878108,908864,984878,775709,151776,388343,469491,470655,769000,876674,760846,109397,946131,935997,329015,449511,664991,640048,967345,891459,398143,661223,748221,255004,902987,195628,667808,617839,698977,605309,51807,924227,822389,842966,413438,866428,394972,984416,249551,428573,443048,791235,465366,190435,461596,491676,147011,812455,80447,895284,138577,54925,250407,625277,514537,989267,499654,71119,918174,89156,694670,966832,233806,39391,154702,604595,637350,259103,399559,218616,23144,987880,242928,105196,594781,121018,620041,170923,606024,74138,355589,410408,52082,867225,346002,985560,912617,839913,130,825200,849506,889969,39378,946637,313365,164029,141244,384928,132923,431169,285089,826566,974607,233645,605919,832202,825232,478583,525746,113323,845145,93358,587987,779953,969916,751189,481545,961369,692389,852017,957883,252518,224499,887338,743260,116605,744979,256170,593762,248499,538745,458921,71354,877377,219759,673355,634956,2403,356921,907676,92239,770888,344355,317650,661347,607685,763052,134629,134947,287998,442130,858261,890634,168476,337757,13351,877859,92930,901272,34837,680089,2055,466212,16850,516698,444944,638217,854160,389465,921388,489481,951193,660954,458047,616070,186224,439632,797886,627439,205525,55295,835491,103017,565998,110269,601764,716382,275576,988396,525138,547060,426454,447650,360559,323825,174617,365418,919179,670267,158062,598394,536391,464653,371934,740000,934207,774043,854279,578022,937157,936014,535934,565487,749849,241260,247644,457859,376067,959678,527610,478138,819345,26606,214271,969409,251878,879439,480010,458452,575636,156622,176547,353613,864121,291890,796747,244055,270296,841670,314181,283157,108965,437180,188696,310233,243428,954685,406777,94046,426903,254931,996501,702947,722110,100541,227724,131044,50118,922875,672469,270581,427165,719300,527139,522804,96142,841976,437608,656962,556146,654257,585363,896809,610907,920003,287679,726704,535391,177350,873910,687841,160715,297896,855630,150432,968715,106937,21775,613001,812557,422538,982887,497319,825368,286227,136781,287471,278873,95063,570706,322462,867338,877540,535462,803205,704135,867978,974932,795281,256869,599725,575469,341991,371817,46993,237201,791231,170322,208843,689618,755409,250760,792682,314925,410709,555324,942974,846961,473683,383455,769405,492368,821829,627480,388159,952291,555490,106170,665426,303976,295642,130096,998346,703563,29208,678310,53988,829470,761352,262406,283903,866414,409650,862271,500930,361685,954838,757784,566886,154089,186445,15868,855066,68858,282734,455818,365973,186431,555306,277258,324765,157282,399068,176441,29454,258943,50516,923505,987225,58467,488453,544253,987187,556375,403458,532554,647491,200570,603187,233401,759980,308834,261692,258515,815266,678728,704414,724017,383827,242797,860763,183545,116053,94996,330542,910714,503099,534074,734695,522016,161944,753341,845863,681218,913506,335689,319080,579155,231812,661567,431616,578816,74963,990235,760019,617649,962090,706896,18061,5296,667579,33105,56658,860051,272547,267600,194551,549053,869415,223113,232405,358787,308835,470835,905532,341754,594743,226814,711108,90784,955582,680832,98849,616012,863120,261065,797138,882308,971459,357063,383156,928541,632725,906504,151532,361355,216737,94754,650804,531684,878481,747538,838591,269783,833721,782726,529051,853802,274212,182383,69529,66740,347639,259115,205777,122494,252619,379265,632194,836097,800248,92303,680485,324155,495761,157385,405823,121726,620437,862275,24421,200471,648523,363328,185910,939878,154774,474836,146990,427255,396312,396707,940695,559024,263463,869220,567150,587909,662293,397057,568222,920830,694404,404674,173419,827786,124666,88914,484785,471479,678010,477033,129173,932126,365186,979814,342614,985291,99002,826,721935,941179,164187,342288,591455,608583,238044,564784,781680,793313,701763,231021,325967,35882,733038,767973,922772,853807,319074,495931,650402,954579,954677,946395,440654,919556,920443,614607,690774,713016,2989,671224,519652,301618,401477,732967,358695,319786,162439,806344,563484,103,91132,702873,476689,65231,854519,306461,444736,862320,840954,379558,752935,192612,194452,237503,133636,174103,95579,923120,894786,863494,8719,560273,458505,263259,148522,361494,755318,58900,956276,670552,146727,503292,765934,110310,508351,645015,780175,101779,955564,178526,422212,544127,90361,500357,657847,65382,802152,91157,713728,16919,49772,516299,538105,351966,90502,968063,837319,383946,232900,357061,422107,778804,874557,878098,240453,986470,250679,515491,855851,29494,716616,287436,708646,141460,104196,879302,251072,353618,714580,629059,319341,391706,298541,88979,217661,65557,853080,771762,489400,205457,261216,534568,534578,707417,716425,428117,737721,99532,313923,558844,800477,812870,794626,723339,489329,112792,654310,202837,304107,344226,155951,547977,105293,196015,885693,719114,733275,836145,192188,890411,123688,237406,324104,223676,89068,430412,41153,352130,12793,172743,487980,710402,134419,878085,378299,11826,845345,684699,688242,315415,871901,380333,683480,953583,438694,417975,440909,964772,653455,312084,112880,144071,746816,200538,22007,480573,21795,668183,724204,52679,811065,668999,928365,952174,846499,243053,858858,17280,275933,619106,917566,14571,972531,852087,455088,700430,788276,704597,768382,27474,460614,373299,937424,291460,400549,658020,633399,920723,169281,951394,465320,333360,766737,993098,768324,690045,251598,148463,305564,737924,603954,818811,983303,504845,841484,869895,383130,615128,733921,107724,64651,889294,17063,455137,898324,980908,339339,764178,191174,789980,509512,459446,241706,897161,773501,688640,861767,741018,144526,938175,131801,842840,320628,818643,352575,845399,519243,968375,449354,875848,535128,455467,168231,578089,763621,346385,649634,514921,784510,39508,244750,3459,450690,469355,882421,281777,236118,131124,372700,484947,60627,155127,312354,631546,373741,873137,30543,345669,632152,839476,538873,45622,809299,315522,221980,878006,533860,284241,957406,991972,695139,509637,81315,132030,876074,736992,144398,945604,839953,859496,29987,838340,861360,921469,452556,665487,549694,338627,754356,302644,440888,176840,889475,852471,242934,632095,303555,505323,758212,126411,290860,637180,145035,713631,195975,709087,677554,586255,370093,872213,533291,453962,945608,688379,265083,139280,823892,422277,356121,328134,591875,352846,575174,6537,307133,813083,594418,853912,405062,298682,811853,655318,713073,804490,307029,241472,844872,977391,147542,935053,82680,959186,446397,467351,685700,362626,887206,911644,11961,973634,666411,262595,192160,519307,333138,97394,61796,699162,232125,432422,515269,736912,376688,995362,892363,330126,433776,870547,333246,962957,246917,1234,651554,214866,10140,863716,927636,136069,807397,207863,693512,35361,671108,591772,212579,65451,230299,565744,450457,800593,393095,250359,108053,909028,263072,771999,866871,726991,588259,65799,518692,135707,382099,749185,744336,584944,374834,674133,736597,777071,879686,468657,521572,415403,329506,507551,6421,232396,215895,326716,299513,297417,155244,881951,665456,994519,773704,625319,354753,583465,866531,393176,315367,925455,809761,739856,610910,909975,531151,292627,888149,631750,25564,743619,593896,627127,369759,141135,587021,400,611842,159945,282601,239439,420709,418069,79999,463894,282949,346439,603476,484560,209700,971212,46578,126072,410466,270632,983605,769031,495378,889330,842949,523747,990651,786046,366990,444132,524227,752560,953091,681656,411125,590509,935736,193921,812789,885806,449520,34437,625037,149440,431526,96728,86081,926902,297382,854883,92113,801228,605803,842869,919985,238189,633704,534230,290687,112640,114798,291090,703079,796169,541376,85599,503415,360883,830668,562025,48154,678487,78570,309971,783428,115578,727862,506754,790164,599658,82746,263848,336576,712589,962170,39254,872709,530579,226945,172554,270097,444286,889640,279004,498650,528246,827688,892965,18086,807754,824511,282082,764974,108756,758644,459736,817838,948355,972143,405406,94548,360067,725966,902679,165358,149647,264205,414115,67623,370008,42759,56465,257539,772711,155334,620364,232828,803539,392921,452121,832775,117845,285892,828997,602947,53453,553960,891741,229355,27880,336557,654361,118229,271012,706636,824625,351528,819097,278729,877265,221059,635415,920099,893264,68423,908245,420971,425064,736245,851556,749736,263942,758680,911194,20221,279959,871638,115686,716236,621893,514925,285015,834156,944475,128934,377330,359921,517994,760619,67268,40960,260152,406453,307754,489289,212124,22421,35953,767948,377099,892557,343443,657916,188559,579514,768751,953664,242103,253594,680953,356384,801128,944852,996103,31768,472814,791964,214885,941572,698731,698969,911668,380371,927555,670357,514225,909142,770425,739072,565288,169871,247915,286644,245192,610932,621799,841870,739203,651724,9460,406151,69324,519646,624787,90945,106747,944699,424739,417877,102811,455708,267290,943991,856795,544609,132272,899076,314793,845214,913251,969965,711027,400476,853440,361901,572801,379900,103195,116244,656203,835615,141642,789015,21488,918104,388716,792562,196439,280931,520085,165425,128356,38375,863467,602235,761759,140222,201223,344563,738579,465006,234073,676608,518610,601511,486778,127103,911821,689359,151192,416545,730347,828696,285904,516511,881730,828705,916320,734810,125204,762623,205204,265450,675563,118024,411857,345889,761677,193283,80770,881768,302076,896096,851533,909275,486590,73982,63902,74215,608826,280433,646598,650194,627305,896753,724196,956812,362461,277435,729824,512124,89979,252679,266561,191260,432330,3992,641,658676,978843,769175,862491,866216,615040,875831,467353,368783,820182,972489,865174,108198,919581,151575,354229,607341,434773,636416,935919,554793,201410,630744,511352,621816,439498,415384,516425,560050,553528,418571,858787,739575,303972,284471,604496,107453,545977,29935,294573,103430,47463,843419,561020,977056,503961,324497,870013,131801,793700,744052,305272,514395,498076,539449,634646,471419,420855,41895,284572,696375,758593,395245,600736,241018,677094,523422,963291,542191,947610,285797,364934,530500,92178,612756,725232,765406,207606,239654,987525,899591,900444,851403,104807,379296,788599,156365,988769,546237,917627,821962,840251,973037,703889,765777,103848,196654,950372,25528,865679,825776,963370,899089,175610,961852,892218,717337,920881,465130,924728,857864,855957,60094,5691,136415,844665,328925,465597,792478,88847,650214,483431,721060,159009,796721,22754,350689,648042,208337,19044,477680,658230,215552,741978,196675,176270,990828,194855,761299,860496,992698,330584,448201,692559,150151,913219,994030,150583,907290,848633,189462,700356,509507,3241,26052,15167,226238,289847,257764,100987,893241,50178,142342,929281,950613,857345,218510,407855,126128,128250,84989,37919,631155,957955,18711,140720,85561,361168,373734,586710,946891,906713,933803,8797,370977,528787,415458,109438,100303,745436,277374,402448,952300,691632,574735,565900,123952,174251,134591,379442,282185,802282,792023,982683,36679,176971,9293,60806,982601,11060,558832,714689,528631,345661,550744,44018,563889,589814,350445,528065,414713,115081,200269,870906,691128,452483,915522,695138,882085,487821,709283,806512,604836,66011,333468,427988,878803,285191,830167,146175,292526,500946,593703,818294,411142,986518,87485,301729,932106,357331,138740,365982,458555,160163,598577,568690,783609,926583,457546,75452,349136,530661,540651,428768,326011,602989,168653,430736,432698,86568,196751,749521,209970,623534,764022,989891,209758,954893,488676,239894,261067,405423,194313,950347,615699,7254,306373,123518,847582,617376,174690,879461,356928,206146,275916,174684,160909,753441,796967,324164,81603,850295,543105,893715,852780,946774,558837,721494,475673,115316,949012,966223,791659,909937,212069,796712,646619,432123,838089,657924,898191,90954,171559,932232,913911,965448,381998,37488,780708,546401,189204,976735,912542,680647,431683,319474,250607,110662,203057,731542,810394,758835,238579,742822,392893,205059,610868,802101,903702,100962,19609,974683,724510,1348,798882,378219,738417,926764,975203,534812,551101,147336,390636,75776,956390,448066,992116,554728,828130,956372,351207,269944,952870,977649,678380,885836,530868,837189,689754,552738,810720,593821,688580,274853,72984,570518,91004,383771,405428,588208,28819,516321,842506,46821,606722,944195,979671,318610,345794,630431,228694,351179,51546,708919,955343,289489,563592,464799,40362,960058,527879,258762,722227,737201,780132,995876,697675,540221,1705,634141,940328,342967,599603,212451,418737,827147,68425,463476,596211,789195,288610,818987,511860,903763,789165,773365,929286,962488,322949,576275,605323,214835,493459,251623,896747,726307,222781,712290,820063,442150,487531,617986,837262,727335,534812,417380,978313,167783,493832,87000,214608,388849,112660,659006,975041,945388,114185,405035,531012,671562,212133,496610,63654,567164,753686,440070,532868,373392,865098,251235,155091,726816,210085,394957,450960,89046,189321,273113,587287,855293,814680,251928,88434,15970,533455,138653,552986,698380,873719,361990,730639,8884,378466,53882,194694,843707,456070,29210,423697,523148,924344,953390,454562,714789,781720,66584,880845,587167,670604,569142,407729,917970,31427,33644,404046,13965,235634,146904,35057,737957,492301,7556,842496,401300,26068,953746,487069,895486,654545,567166,859214,529988,488498,767336,570574,205961,505308,485862,161101,237329,948295,450452,65127,81350,437403,968367,138751,847080,95836,653992,487204,981839,894558,433947,232907,809254,366135,728914,209453,87160,759719,40270,723023,248155,745982,199441,381352,250791,290191,161926,808102,139459,725320,840009,564760,228206,954893,938241,125181,326733,623423,178133,656617,808276,239704,240100,120886,544157,126722,383201,180596,575357,251128,229065,887352,542185,807869,573279,814037,933438,404694,35115,751950,50189,542837,582856,111033,482422,785117,532842,196692,600200,766825,597718,610328,7004,926398,385513,664630,100814,537790,916063,91905,661501,909892,599830,910701,209170,188108,974221,375410,51590,157388,378508,70099,53997,252771,294056,491850,70326,696893,632960,611719,139035,262980,751312,305104,269892,794682,485108,48561,566356,185947,487907,970812,208256,133639,355230,359861,140596,268051,977450,979510,188940,948654,387762,292558,782895,576544,491985,909700,471252,164505,765791,922291,662344,869955,287178,875927,477225,975458,245205,823445,646976,349406,537908,653263,806030,331101,142573,695663,917542,765031,892977,777122,5933,373990,304553,337211,998877,557660,564606,587735,272124,229938,64703,545347,388235,346739,150853,890358,514813,252822,237627,715774,961247,516734,130691,760226,198788,87718,380674,317046,137515,125622,32075,215290,871653,272910,417653,683382,415057,170708,673932,77001,951272,266479,317763,293301,738287,807916,707340,486791,70334,700375,606767,672315,895475,594950,832951,248133,554495,103608,879623,888642,535102,623520,116131,995504,580354,693239,703236,445244,889479,819320,234995,996213,419949,635255,102521,308964,916783,452115,827076,269563,837048,553087,98657,792070,820695,250218,266554,3267,869960,623659,874240,255120,660821,369228,940943,1733,432098,859621,823852,261245,511014,396904,854588,945491,458117,886715,946184,395390,933394,558908,217382,418926,639496,271093,169033,442777,717729,978869,395377,18080,911243,91029,458151,606566,418635,943719,590434,988063,677806,732613,75832,99780,950019,565631,615972,738664,58468,852591,464656,568013,222004,449431,32763,177332,49487,888716,819099,696497,938226,733065,815197,806646,465211,67475,756895,487227,729749,453274,947848,186400,68439,198847,222544,438961,800815,235127,700562,461543,429547,664910,785911,164159,121839,308236,21494,679903,91546,290572,742497,82291,622837,398271,245907,279408,496529,549199,772576,402288,273138,948612,197772,30262,29490,254450,50667,320670,115021,37871,24572,949664,61161,211705,219791,766589,706924,948227,393068,892735,948090,456246,288870,738726,29100,261365,965626,353033,617745,607211,322378,176907,84344,176524,979541,712754,731346,91064,49480,392061,329760,100142,401017,821921,626365,431554,152353,857502,101927,557449,964211,472855,51062,730308,244007,259376,105244,926140,17887,132319,780612,50908,919280,685241,958089,674800,289604,261915,512122,514959,869633,240708,620220,225822,473359,621139,449522,771896,948794,146247,217503,127333,394895,330920,763428,920720,848617,904815,584100,473631,512626,561826,341926,199709,655380,894096,633909,162707,854182,404394,62877,32882,346048,446899,74888,977267,833754,877019,379120,291737,238115,216865,293977,719347,732239,368537,130816,15732,804340,615092,837226,829489,614853,845704,259023,152091,290990,215620,425917,933018,540634,219704,723801,627711,93264,570696,186851,813798,949569,487721,882042,733822,176427,525329,426302,241958,957619,44600,961899,269205,630399,318247,815307,158785,228133,63200,629792,665632,17533,855922,636134,240899,936793,671761,451626,510085,756632,326474,810643,966032,256270,105574,930026,398096,147341,727995,576458,264650,276133,737903,866290,559247,411771,457503,332812,630367,177115,668483,320572,94961,822674,252920,844755,969570,598151,113375,754230,693351,874592,528391,104497,911479,415401,69542,967415,348369,429191,741494,247312,990334,457486,674742,810296,150164,932994,330152,806181,207864,215777,747865,641969,810200,375792,381535,570442,68080,931799,295067,170889,694714,657821,277767,941953,80906,798498,363296,864628,855107,743555,219830,700965,117430,365524,773336,77137,352091,778166,634434,95506,485483,683016,492093,758721,871305,811959,383256,898810,463344,349251,175817,185957,199375,105829,423773,202861,978408,175951,125024,225984,24926,480025,773431,968880,357395,537990,188974,295259,370623,465945,352031,246573,556185,473152,536625,48667,241130,203769,700402,937772,279395,4619,807799,61279,601414,362340,290564,550818,291046,501558,366752,835974,576045,703260,623492,19624,404505,958107,117162,52940,156667,958055,794452,605824,419920,200052,398034,708927,632324,246575,2129,43129,719214,708235,600298,369175,443027,608309,121183,421292,991026,21691,81347,604111,397507,145859,981251,827126,399267,477998,536421,877377,640015,660340,101142,159096,26797,736973,636869,952436,970447,547067,777688,299602,962480,990291,636605,338054,263976,122707,19663,676526,575115,773423,544558,846824,47311,971631,834619,630247,332655,56342,575273,348601,591545,77514,219004,986859,37883,920056,358968,818001,252563,57360,111675,126032,24379,819856,521255,604868,483141,524532,21652,97083,915537,354610,208640,984858,309532,169989,616419,254467,556418,281242,373136,725333,882787,94580,905968,226175,503208,357077,648608,293213,445892,582510,550310,827597,343579,448466,210190,576007,771775,838163,176071,258654,123573,326140,883326,618267,680037,736334,955195,767434,894343,166382,578685,768918,152805,501381,697038,867987,954459,839003,643474,195287,418510,600761,407313,418535,143557,334489,176772,638769,205356,239579,623927,601288,589254,580823,804680,753014,682505,592027,135864,314275,305705,84858,578631,356682,142563,64714,156220,445666,464911,217218,89789,699321,784174,828163,29716,706675,625465,181006,392604,375370,582818,631141,366269,268064,46999,643811,205369,390225,808509,252842,707569,64588,829903,825557,300336,509521,524413,381283,630821,473967,655603,742105,982318,635732,761072,430718,755092,592785,430243,407962,889936,859721,516758,819164,340433,322733,865495,655931,166768,658100,702250,812691,277237,988932,356610,135978,558631,353601,819357,960939,499405,904041,817152,815399,788858,212382,206359,108217,248272,792570,164540,957820,607872,329115,480425,843928,55011,735635,992369,37652,430004,965410,328686,494705,432101,477261,496910,103690,1789,604815,222386,723343,542248,869957,85415,436753,785486,63977,967260,740024,497680,767917,561677,252803,52110,555224,352650,702814,817570,431280,273992,677811,75308,686555,960309,857047,389795,780575,250826,986358,174756,315048,168080,839747,883635,549139,924024,196935,48907,373470,217850,512880,862844,957654,83404,876186,33641,761911,531562,577094,252492,56670,881844,518185,371303,531761,693580,987059,266319,683002,657911,589241,216600,304761,691671,897601,472535,31689,756765,711532,982803,375022,54884,314108,573166,147576,252199,149104,660980,276508,191706,595134,224083,168900,155212,907731,653513,489700,771614,754297,355558,482037,922801,452037,458811,608363,205,570428,131757,234278,978789,507380,912214,798143,127349,954623,68931,806814,581169,414422,665981,832652,345224,837294,175682,477808,991034,205947,947252,719507,999592,700124,709820,983886,391155,359861,12449,150884,358698,529459,439249,616187,679021,404793,117826,388168,490549,520107,236242,264915,405229,232362,577918,564257,842645,814326,158818,469755,609646,12612,29341,840178,308566,771142,687424,714710,881275,329153,843080,590421,981776,54488,336497,989888,994340,232644,388368,729068,120971,238406,571349,63694,37754,747038,105696,510630,359157,274287,811729,630878,383144,711640,413783,196082,349681,189802,356492,388631,71911,679013,592883,534888,941794,164192,597058,101044,822576,467605,769793,129689,681100,223758,190519,621865,859260,393498,248090,220460,358042,593374,555863,38768,791306,795176,562911,312588,781804,209900,58333,729543,985625,624093,318942,57898,811013,431259,747791,688478,172006,820265,152146,258861,909448,145480,160333,472407,326579,385104,963927,82230,499039,347312,456999,725337,563808,502358,766192,684027,907808,580218,274904,2769,983722,163298,610128,109751,634400,707578,943614,449983,564210,605196,34373,622358,46784,779108,42030,410100,226367,103980,102917,135697,436197,726344,568548,325976,466461,6300,858022,51357,717023,950864,456456,780460,443595,964166,630508,711575,140452,23732,402030,570485,283007,400578,340434,239995,267384,392204,962202,328833,427039,219142,28694,178282,841157,911676,877604,411014,487718,271073,783994,240940,995738,131645,398772,653217,466327,307212,363557,725203,368206,606329,178383,93490,245770,499537,643529,348854,952347,141117,522002,12705,340520,765180,705144,603696,851085,684145,699353,996659,20012,59632,468734,232855,92103,896151,350783,7176,422813,872223,630287,459503,954234,874357,968428,18041,871450,483507,842455,510318,600885,389197,818462,861428,977992,394718,815446,956976,648922,330523,930219,104392,536281,657828,829537,627833,321529,784665,17130,471191,556120,613404,966927,981220,594561,945709,320561,450264,744150,267634,219107,651637,25209,113907,865760,938672,335582,690547,836994,731851,955932,863915,503366,766416,414370,385341,249490,62050,633491,961130,982235,790206,148140,568915,898057,745247,553108,806261,712361,233121,371911,529427,752365,551371,78410,606615,15307,774564,232244,475117,845716,88496,744887,214665,772523,717685,666251,285387,570331,419098,353880,123164,514960,288598,45874,884378,695254,220163,133173,774405,263428,652831,228160,36643,353150,940468,683110,906272,290608,281451,226645,872842,301106,170505,974108,108985,686010,474476,386901,788243,439416,954648,699872,617458,994093,626925,341881,251830,893790,310159,530729,245460,48405,30407,357641,476681,533215,690002,164939,260198,882092,506817,375997,697132,529906,443229,552237,943840,628606,325820,929085,87469,158506,67198,15460,127652,59019,849018,984322,926989,334146,604205,757972,699356,327178,209174,958906,771571,890396,843738,445784,878220,715014,281688,380782,413449,979599,487149,428231,192693,280630,548068,278379,140763,293478,974099,462133,450581,436346,126583,642136,414720,198700,133484,153921,222361,95155,389897,941290,692587,87264,203523,194700,503477,945172,892200,460747,363607,863953,281236,148311,524499,141689,108534,528039,314734,931152,865486,155601,320285,677104,16519,843915,84513,377662,397646,153178,82464,934798,783642,493807,783930,459633,372408,891644,379175,459118,83731,634287,232503,982288,879581,655655,413660,790818,20040,819479,219178,509174,833229,539839,181620,158835,517034,969236,218822,781405,361008,54084,810431,584422,544013,846597,967479,880546,945920,485757,804556,425701,25763,408383,891516,511900,846064,664939,212418,181412,520166,785383,288808,691297,610068,687668,377856,591008,714402,269628,303945,520706,620471,844105,291112,584350,854821,32659,156645,735604,302433,913371,284348,378150,379127,843133,356575,549183,547211,836532,569040,34966,198408,69006,269619,461335,653635,233597,377156,902980,32304,367042,136950,608140,146960,864454,772436,789241,524737,320226,889797,934170,515533,515820,981889,148452,796302,341164,828327,331667,130192,867221,240547,826857,650883,261209,107313,531965,483348,620645,448254,485250,942150,178215,44819,907147,305010,444444,401474,754476,861699,858165,23407,257528,452653,471539,997927,197194,553412,238106,607402,594327,245791,279515,45259,855560,930488,173296,255449,510713,856941,673939};
int choose(int a,int b){
    return (((factorial[a]*inverse[factorial[b]])%mod)*inverse[factorial[a-b]])%mod;
}


int calculate(int a,int b){
    int score=0;
    int k=1;
    for(int i=0;i<=a;i++){
        score=(score+(k*(choose(a,i)*calc[i])%mod))%mod;
        k=(k*b)%mod;
    }
    return score;
}


int main(){
    int N;
    scanf("%d",&N);
    factorial.push_back(1);
    for(int i=1;i<=N;i++){
        factorial.push_back((factorial.back()*i)%mod);
    }
    for(int i=1;i<mod;i++){
        inverse.push_back(0);
    }
    unsigned long long k=1;
    unsigned long long inv=1;
    for(int i=0;i<34483;i++){
        k*=2;
        inv*=((mod+1)/2);
        k=k%mod;
        inv=inv%mod;
        long long int a=k;
        long long int b=inv;
        for(int j=0;j<29;j++){
            a=(a*p1)%mod;
            b=(b*p2)%mod;
            inverse[a]=b;
        }
    }
    unsigned long long total=0;
    k=1;
    scanf("%d",&inv);
    for(int i=1;i<N;i++){
        scanf("%d",&inv);
        total=(total+calculate(N-i-1,k)*(inv-1));
        k=max(k,inv);
    }
    printf("%d",total%mod+1);

}

Compilation message

teams.cpp: In function 'int main()':
teams.cpp:73:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long unsigned int*' [-Wformat=]
   73 |     scanf("%d",&inv);
      |            ~^  ~~~~
      |             |  |
      |             |  long long unsigned int*
      |             int*
      |            %lld
teams.cpp:75:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long unsigned int*' [-Wformat=]
   75 |         scanf("%d",&inv);
      |                ~^  ~~~~
      |                 |  |
      |                 |  long long unsigned int*
      |                 int*
      |                %lld
teams.cpp:79:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long unsigned int' [-Wformat=]
   79 |     printf("%d",total%mod+1);
      |             ~^  ~~~~~~~~~~~
      |              |           |
      |              int         long long unsigned int
      |             %lld
teams.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
teams.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d",&inv);
      |     ~~~~~^~~~~~~~~~~
teams.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d",&inv);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4540 KB Output is correct
2 Correct 13 ms 4540 KB Output is correct
3 Correct 16 ms 4540 KB Output is correct
4 Correct 15 ms 4540 KB Output is correct
5 Correct 13 ms 4616 KB Output is correct
6 Correct 15 ms 4540 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4576 KB Output is correct
2 Incorrect 14 ms 4540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 4540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 4540 KB Output isn't correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 4540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 4540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 8972 KB Execution killed with signal 11

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 8780 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 8924 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -