| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 897779 |
2024-01-03T16:33:54 Z |
denniskim |
NoM (RMI21_nom) |
C++17 |
|
82 ms |
60756 KB |
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())
inline int readChar();
template<class T = int> inline T readInt();
template<class T> inline void writeInt(T x, char end = 0);
inline void writeChar(int x);
inline void writeWord(const char *s);
static const int buf_size = 1 << 18;
inline int getChar(){
static char buf[buf_size];
static int len = 0, pos = 0;
if(pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
if(pos == len) return -1;
return buf[pos++];
}
inline int readChar(){
int c = getChar();
while(c <= 32) c = getChar();
return c;
}
template <class T>
inline T readInt(){
int s = 1, c = readChar();
T x = 0;
if(c == '-') s = -1, c = getChar();
while('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
return s == 1 ? x : -x;
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x){
if(write_pos == buf_size) fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt(T x, char end){
if(x < 0) writeChar('-'), x = -x;
char s[24]; int n = 0;
while(x || !n) s[n++] = '0' + x % 10, x /= 10;
while(n--) writeChar(s[n]);
if(end) writeChar(end);
}
inline void writeWord(const char *s){
while(*s) writeChar(*s++);
}
struct Flusher{
~Flusher(){ if(write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0; }
}flusher;
int n, m;
int ss = 1000000007;
int ans;
int cou[2010];
int dp[9000010];
int fac[5010] = {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,227020758,178290591,674358851,789741546,425606191,660911389,557316307,146326063,72847302,602640637,860734560,657629300,440732388,459042011,394134213,35757887,36978716,109361473,390205642,486580460,57155068,943272305,14530444,523095984,354551275,472948359,444985875,799434881,776829897,626855450,954784168,10503098,472639410,741412713,846397273,627068824,726372166,318608048,249010336,948537388,272481214,713985458,269199917,75195247,286129051,595484846,133605669,16340084,996745124,798197261,286427093,331333826,536698543,422103593,280940535,103956247,172980994,108669496,715534167,518459667,847555432,719101534,932614679,878715114,661063309,562937745,472081547,766523501,88403147,249058005,671814275,432398708,753889928,834533360,604401816,187359437,674989781,749079870,166267694,296627743,586379910,119711155,372559648,765725963,275417893,990953332,104379182,437918130,229730822,432543683,551999041,407899865,829485531,925465677,24826746,681288554,260451868,649705284,117286020,136034149,371858732,391895154,67942395,881317771,114178486,473061257,294289191,314702675,79023409,640855835,825267159,333127002,640874963,750244778,281086141,979025803,294327705,262601384,400781066,903100348,112345444,54289391,329067736,753211788,190014235,221964248,853030262,424235847,817254014,50069176,159892119,24464975,547421354,923517131,757017312,38561392,745647373,847105173,912880234,757794602,942573301,156287339,224537377,27830567,369398991,365040172,41386942,621910678,127618458,674190056,892978365,448450838,994387759,68366839,417262036,100021558,903643190,619341229,907349424,64099836,89271551,533249769,318708924,92770232,420330952,818908938,584698880,245797665,489377057,66623751,192146349,354927971,661674180,71396619,351167662,19519994,689278845,962979640,929109959,389110882,98399701,89541861,460662776,289903466,110982403,974515647,928612402,722479105,218299090,96415872,572421883,774063320,682979494,693774784,611379287,166890807,880178425,837467962,705738750,616613957,338771924,497191232,896114138,560652457,661582322,224945188,262995829,859081981,857116478,279856786,408062844,406076419,367193638,985761614,767884817,77737051,801784560,410447512,813374614,702909132,777826615,11426636,685259446,721228129,931065383,593559607,860745086,578819198,495425745,893029457,6156532,502193801,37480384,220174401,383076669,3013247,750298503,574624441,230733683,144887710,656590378,773954850,358485371,772254339,469363737,95843299,823414273,87709482,892174648,749756145,185864756,68295241,98238739,131504392,111672419,928208089,687974198,753032165,71715287,506557931,290314197,546089425,174590825,187067364,817659471,309331349,303445769,964814732,112937795,848457973,113604679,263728612,162653895,519013648,956915940,591788795,26960558,818561771,201473695,830318534,283328761,298655153,103269519,567777414,629890782,707451727,528064896,419467694,259775012,452053078,972081682,512829263,412924123,354780756,917691336,648929514,519218426,957710940,848100261,607279584,78508462,651656900,271922065,927371945,976904514,655633282,147015495,44958071,431540693,956102180,821001984,4640954,508310043,709072863,866824584,318461564,773853828,371761455,53040744,609526889,972452623,799173814,723225821,3874155,305590228,289496343,139259591,348260611,756867525,848691744,101266155,835557082,267191274,448180160,518514435,443022120,614718802,151579195,204297074,912569551,137049249,515433810,979001276,524451820,229298431,88837724,892742699,387369393,840349900,206661672,18186411,619853562,246548548,236767938,893832644,930410696,321544423,971435684,402636244,780681725,194281388,661238608,964476271,643075362,439409780,96895678,723461710,915447882,785640606,114709392,933696835,539582134,739120141,300372431,244129985,722433522,26638091,388855420,42468156,647517040,474194942,832805846,958306874,489519451,339220689,9833277,923477502,390998217,790283925,694135631,736657340,609563281,873127083,489593220,264439147,891171227,489029295,502009550,325923608,280525558,857054649,820622208,558213940,216997416,487921842,951328535,606653379,794417402,449723904,783486165,414645478,809681447,114612567,824953206,255016498,147060381,88903008,228293174,394357308,362355866,900088886,638573794,779598451,904922263,451026166,549459329,212643744,563246709,391796933,174243175,189725986,238337196,60051478,782959006,982673239,237607992,685987666,694447544,195840153,519748540,446086975,523485236,185780714,716004996,214280883,140643728,555470704,516522055,116665689,899547947,490696549,683197147,686671136,988747143,744912554,619072836,345158054,224284246,637879131,78947725,342273666,237716550,915360466,711578771,423071394,228124918,271834959,480779410,254894593,859192972,990202578,258044399,151532640,644862529,48049425,448119239,130306338,850105179,401639970,606863861,183881380,837401090,513536652,714177614,946271680,243293343,403377310,688653593,15447678,754734307,631353768,202296846,159906516,912696536,737140518,467380526,896686075,309895051,356369955,461415686,706245266,10064183,183054210,455971702,737368289,956771035,564163693,365118309,226637659,304857172,440299843,717116122,485961418,615704083,476049473,354119987,329471814,620060202,251964959,45357250,175414082,671119137,48735782,122378970,717506435,18459328,949577729,771970076,635808197,608040366,165916428,258536202,902229110,617090616,548564593,613394864,753777984,577888302,416452176,881599549,524547188,599140122,522765386,657552586,256787840,287613719,776067801,597965522,458655497,764387515,350167935,494713961,513386012,576480762,864589772,86987059,495636228,512647986,721997962,982831380,162376799,204281975,462134806,189646394,425968575,209834628,494248765,664281698,947663843,540352769,25662122,986679150,207298711,477043799,24708053,528335066,189351697,717500453,42764755,316734785,823726196,293357001,547414377,258966410,602945692,561521296,351253952,752369730,174204566,871148004,302242737,554611874,540181425,349941261,414343943,921115587,959388563,227019335,708812719,793380997,342547759,324322556,458370547,356254978,809319893,159690374,848340820,971304725,180230004,103061704,207441144,443272953,45593686,541647240,612817107,849140508,109375794,906749744,159084460,541378020,692284266,908221578,720697998,363923522,819281897,701846632,479994712,196613531,29272489,792937812,859009553,202148261,385627435,115321267,612859231,132778909,173511339,782369566,322583903,324703286,31244274,433755056,109559692,871157455,350443931,592104988,197184362,141678010,649163959,746537855,954594407,850681817,703404350,467293824,684978431,565588709,378843675,825260479,749777538,850502015,387852091,412307507,307565279,914127155,864079609,845970807,414173935,638273833,664477235,173471099,480759791,839694748,190898355,956270620,957911348,43002811,628936576,966234409,667971950,236586166,954211897,223051884,21058295,656573222,631532535,809706350,984734695,314281677,311454037,640732448,434907794,175084834,434807109,973816812,488481268,844735329,917344075,314288693,459259162,992521062,667512257,603748166,679935673,833938466,933875943,522922384,981191471,457854178,112860028,484939649,611363777,627371454,844300972,962501388,738504183,631041465,29224765,334078303,211237785,626057542,900175080,728504100,450509755,575177363,905713570,416609984,874776027,334255451,683287462,999293262,474888472,317020697,180417613,591538360,879151833,605566485,569294094,970567518,896200922,943088633,145735679,884701203,949403596,749113557,78958680,850679027,665376978,686499745,426302291,842343474,708066168,962548572,349652428,833757979,492365420,136639914,76093131,591710464,208764552,166233017,498121245,545840935,26721664,736011124,880639351,137410283,42609708,235572009,981737748,718913567,909319027,906112184,298059463,274736280,217450848,351267027,149682364,249066734,11785215,333890217,774940233,302540697,519852435,802535369,620684620,306323295,752310997,848793393,883503040,569433124,254795373,855478464,660158704,87911700,944741410,351053939,2634663,134077016,736459220,4882454,969435081,120150411,922584286,828772112,106810765,371205161,17024731,960279329,389323593,23991206,744762405,684217429,479374977,963728237,3246420,688035746,381629444,752436308,274567573,440219140,702541058,919238277,563955926,467150839,5249506,399086000,833151662,847391187,655983283,337920422,866913758,675206635,549602585,963783662,324756002,393087771,731515248,787956453,550936813,398161393,631665856,442637251,454846959,348994181,88011024,513458067,60476466,9760396,403700900,990173371,519613195,945797344,114696834,327457551,905694736,143025346,289024806,451579463,325709522,18701196,326143996,49850509,619195074,414881030,850660769,880149960,651809429,592293509,810577782,929598726,835669318,731671946,529667681,285562083,293565850,686472980,274474950,282703792,889076915,56602629,546147347,255724802,873696194,831784350,110556728,279941051,667003092,302778600,803516696,772054724,165410893,531446229,958833885,703493734,68812272,481542542,722167619,172528691,173636402,356397518,390931659,311533827,53449710,959934024,259493848,215350798,907381983,791418522,896453666,530274270,443147787,468552325,410897594,491169384,314015783,406644587,772818684,721371094,596483817,922913559,78344520,173781169,485391881,326797438,209197264,227032260,183290649,293208856,909531571,778733890,346053132,674154326,75833611,738595509,449942130,545136258,334305223,589959631,51605154,128106265,85269691,347284647,656835568,934798619,602272125,976691718,647351010,456965253,143605060,148066754,588283108,104912143,240217288,49898584,251930392,868617755,690598708,880742077,200550782,935358746,104053488,348096605,394187502,726999264,278275958,153885020,653433530,364854920,922674021,65882280,762280792,84294078,29666249,250921311,659332228,420236707,614100318,959310571,676769211,355052615,567244231,840761673,557858783,627343983,461946676,22779421,756641425,641419708,61123214,245460001,196379281,164796745,620727570,451931052,94566179,322707767,612134628,255969954,785621688,49142691,781545640,487273416,582513782,833998375,176341439,515583649,379734656,329346411,262683279,462309262,942371722,988636580,352487409,652079107,685238206,424870840,192091301,854038651,513843021,285993962,431760681,440541032,959964935,523665702,41329173,899681280,768843382,597111687,593261820,178812114,501033600,79074739,633101681,224353692,898313886,432945941,160288931,303376374,848566848,692317852,10693053,270477785,354061180,888603469,253860160,584047404,506196510,568296848,962951514,654500714,734254117,246375021,389395531,95633141,40560733,318862543,864056087,540006622,347088116,78457748,185163016,865077798,958626347,481942155,51697302,729691171,336768000,709437459,901887817,842611169,547889643,912368861,920207262,345079539,101456268,384418814,632085520,973211984,774267117,499685849,156629135,352272493,738377140,261339777,689733367,327231667,627599520,359467170,773351405,233242346,266305839,1644198,816838783,423687677,22255156,658712680,512357010,716277124,783879199,673663191,787126340,858736628,491333521,328205600,605652638,119644545,882244924,114307964,139226748,212410164,536612506,152452523,509087178,232158417,642534132,778495828,921783666,615535293,170411511,905829108,304372182,158051973,388988102,890480785,476645461,422530824,262605169,369890567,45133993,543019649,671454467,143904872,771077292,654570451,792302047,562743593,592383835,241405483,857708994,80754172,109559665,431852528,789666354,854298840,423750964,703612882,487324533,296454325,183468917,190880063,993511722,447636316,496304493,691034792,437596622,112850919,922723394,586363427,631568215,197942800,186902776,423857491,32548439,276963998,986623371,242322904,698701821,468143012,876893308,487882804,165353093,778060747,1978741,346786812,635942967,500239511,784774421,881554459,931353326,173156822,576087204,848116767,499529474,437246725,384326164,422741252,866757606,109119920,53023003,733649165,579939321,246937598,559803511,123029541,496654951,959176615,644519422,868495167,747639880,139528218,247727251,740880614,169939710,646685918,16756697,409656806,371643021,404482449,873066778,887595254,528988047,481364999,672119652,18687584,929665414,629120405,188972334,435969196,678076524,390271723,205031092,8365757,331709825,993340837,762606773,107178366,793994550,553235112,564769190,443329073,58033882,194148704,715134793,57945841,258463223,562100050,62957536,696919454,846230857,481025551,725011189,164024643,850925530,762458204,409955722,724294671,886984412,600351301,42985262,247400266,466533774,698686213,838053264,975424804,863218023,560445506,205342137,784512170,114961091,230506730,435065239,273110608,216022764,645044939,722381342,203348615,82876765,82258458,373083963,293637220,736550628,730999737,334655472,366933982,244031530,312608442,952278924,439803364,786138955,691522755,138915957,757247105,634994115,952367286,220361297,28961504,620993437,291462451,192646098,825217846,258845813,534937793,93814979,522361720,726763266,606345278,705963351,811983342,510153914,321930485,694723851,867133830,280978470,767663937,13397952,658500617,562307747,246220846,257735291,726052322,567215286,993033414,769264345,44514330,70515497,644579365,645970093,140217677,629726785,796071754,163640655,296632244,4042968,401405213,678766029,188940446,991255430,282266904,519915618,726754477,31255779,7766682,446187220,567993920,87804885,360984154,967620344,287455258,352050842,972735059,110525615,651681667,28652604,852930758,427030507,907424453,189822996,159272754,770216682,35113541,859756054,707249452,395495225,246473570,929367838,375193487,639880112,635747308,609553171,306944760,435152533,899576163,917215473,88482014,839732431,151281819,617626945,325178136,71002673,125693400,833970989,215840698,939364644,959387477,670421289,544742622,647496666,20359440,319980844,413331733,771100044,913453818,268067192,221797414,850985195,677294287,534700884,581232364,306536266,763841929,670218890,987314980,177537191,617288803,525339745,678355787,803297198,649041256,797205811,654597257,945917673,527580263,526066923,910757760,543736890,18904623,825659855,436985896,956953876,788402152,896254449,266326444,515180047,646741884,900662014,145346990,700847261,211576216,765562982,286182552,99594146,818004370,836262739,873284804,910254570,946062504,383933729,864565896,839447421,483172612,218074237,899196030,338254257,115652199,348730784,962171704,186789338,844538210,424934135,4359701,334645511,574569592,998750515,180739662,337685693,345736950,430206522,101517724,317393728,29627088,344429443,244701024,486997654,938555773,861309359,402130164,729206786,933967923,866805122,937130659,393451047,946839225,587847103,662317959,243618597,68283846,991807534,875140051,82406459,126371384,408761163,601561650,319043999,99379196,776863423,972765339,447579635,893651488,434359284,64047192,622456991,950738051,353376298,650938112,454346846,611570548,744245040,367552188,695830331,137149847,136218599,872771468,521050149,701518906,188983943,987784056,566130074,856405762,29097324,995153587,667366596,393019274,424195945,81048119,949995669,93415448,898064525,58068445,322104229,242633108,530220901,56647468,387388098,154233411,514416952,29097154,489548158,8676497,283716816,654159074,825853428,859149690,794764924,758914724,451922626,56993923,713646888,16199827,963933239,385044136,123097690,62832030,75485671,700846554,209611450,478522332,231087081,184973044,893189242,229693882,714596254,482570946,397815780,1349347,100933265,254025771,26174217,831778240,405823554,896386917,52741464,487649122,170870589,583340505,94564937,277820180,899859375,779208866,137119918,552509591,97580560,591800369,85574651,865649038,128523371,809878024,797390950,877692187,631337938,776610930,375093587,148237650,956673612,284338013,244423474,144473996,569178041,993078862,988458389,625744277,810626289,138295622,581515550,98811304,801651389,38910655,218136911,19055157,507306147,704441810,220213527,222494837,104210886,362681747,829563355,937865509,25593418,205402693,903736113,822603964,860184650,338015384,894841345,63603398,846693852,950642953,90930134,306816051,348815192,778237469,79403346,951033008,428627185,947797938,67234332,457491733,254027842,65379562,634064880,793876922,401004554,241436651,748921627,235773197,960720794,660649561,804622905,581554967,331694169,641821690,513029292,420150147,146986978,940564101,109063504,736653339,741347513,223387889,813402163,740363875,821476814,722640850,970598385,310914311,185009722,746116934,807984847,254836633,283644452,417075927,597261750,843545049,502496757,159591303,38700239,551998204,284996029,943365105,363079423,68791007,87353906,230437622,983014155,531712251,681438690,454113819,457096767,922563191,828713221,895627971,341864644,700056471,595145382,415107031,285556397,19194762,419952794,720216897,886764308,405198636,1285946,178392510,375302336,512757404,149308498,525827833,381482016,519422664,537945283,582865261,619532539,683439071,263607900,715074257,631748159,25848019,174264163,991716651,827177989,128707256,475527988,54965727,266221147,835485060,527837982,825646734,286725813,168394909,807636366,749812522,926966369,90008970,265472165,204953584,954837097,958492073,232782618,713926326,806461661,791587080,820400043,573664608,308087915,840616702,151201154,787603818,643029919,872051234,241187768,149088916,861978775,290973079,748019306,41699134,848386594,979755938,593123571,966241991,889714404,779624902,682443644,6143197,781310665,981518143,527365183,107985225,946009452,976623872,834626559,611986668,932488138,909063924,497814632,140633959,500203817,360342268,445467633,477704894,15361352,220315555,619476285,950921904,886367791,189185798,183160694,659711657,627029592,112665948,658051988,648634412,515148504,24924703,490594547,201854810,714542950,602785661,383539983,536564768,987492768,587027873,540968925,498244660,349158442,88557443,137723958,627674755,186876342,377413248,721254895,701311697,464980843,825434906,909994907,450790541,578501889,931407997,917054785,869149237,29257189,14026097,429313686,775020958,663028928,60524820,973597177,999655403,373165331,160897667,994649563,251491102,468275740,134943782,272400428,403178049,606290371,298790432,487696306,484233736,631964414,758798349,877363987,85540895,967541233,405691356,255015757,718958090,163918256,609588933,253217799,427182496,297334619,285033600,886988325,380436491,666193963,126435007,778326312,903667127,687840373,880361885,310561488,780994727,745208449,106871663,460676805,937497705,808221401,291795339,31122078,949308837,562350955,222172784,352239262,278458293,881629398,883703942,642656041,766788263,660830035,73816861,258979687,327930043,868826327,918178049,420185912,109137213,68821792,384968057,124910149,80898773,332388495,219920198,549570332,489638900,948597839,952707502,664458685,826905865,678979774,629723420,66425716,810305229,528398210,842999153,169382048,487124857,50096968,184238535,237452585,634813513,50106783,403314167,313482759,498134475,942437182,170130670,779446762,743305004,455852704,590363951,366230360,964904140,791415171,351457024,743110297,285539671,950624820,199641625,511558944,216283487,913142596,886342412,209131158,786607494,792630333,191271328,962389136,411019481,678612260,78877143,469516355,44624214,347853488,444348057,702180389,825584362,808066718,649421951,527998071,372246707,275346640,273864415,666283451,587586574,31051570,488457940,4518396,810872144,11541870,529730086,562850720,810299187,134899497,863414291,701755664,37580494,620187235,566972095,832270518,914744892,644210431,229277629,530537835,37376309,519199292,784199509,88822413,980152392,880351115,52386628,358816323,303416646,247871657,794390809,510618403,3194064,321052614,684171275,343286290,393422020,155860200,226634637,869751302,326073683,908403592,906328261,686898515,928035288,718245479,744984158,753416506,312502450,442383389,997238270,484811253,652876718,100550147,100292593,685477193,325330782,637551789,653776217,821305915,539653961,85492146,668227971,469984345,668526842,407469854,829340515,462445012,364247651,959011634,367440613,127711234,721268413,240915655,649619698,881400474,191745954,902062233,773946817,242293456,886538426,13376923,128399655,522898175,483287823,557561646,965256748,366954950,386363078,248858228,675348666,685223017,484498874,893197177,122228326,468011623,679727481,683233967,530218776,297389332,458569016,690769186,695283030,634918502,582919993,568897278,377206287,404501793,846677012,921247487,84820014,474767580,71672801,574296230,50225519,514793938,505092729,6292633,987994428,208479540,718726630,607933815,207120621,532561853,403027996,670973878,257865486,555148740,378478703,343303230,697500496,708520056,304666064,400742625,544654169,425317758,511565961,591889308,497309241,889760233,39833046,131566421,710685130,621226182,362711294,429310448,117450930,824794775,120246761,916962538,953466201,418609504,242733246,497079791,867553799,730518945,550811645,356881329,878310966,844570494,665447918,98753412,172191040,150900819,400725864,932292989,2778985,871995270,397987879,744358198,61935943,118390414,750895102,146710001,25199943,449078732,945062640,367970678,569714605,643527155,138721954,61594093,72228987,775512252,841085203,352555049,647359211,817187403,877905801,328872017,470623398,722194491,51810950,823621280,549526866,537011874,279426058,810038108,721691400,28042164,178483524,204123347,456946290,977570343,776222743,655108510,793503657,413361565,380804780,634295160,540355391,546570232,498552403,374630545,201971537,460488405,575924645,724998420,896569904,73828573,912688005,794892996,328003267,439081146,806080156,6426,13957272,329151846,576108199,35324054,865140972,411882863,80869335,214279733,129814671,125795470,485713622,312829406,219417923,428158402,954260227,967101847,18826424,211041849,181646076,986549737,517008370,799347479,768356655,542845923,89638564,935923736,160357329,625764007,680805768,453484882,573703178,868092293,275400381,257835856,785894360,468840382,199556211,819667019,464099313,123573861,345378621,322882925,862790952,81945303,590790181,781822114,81436714,708067106,908964323,809747257,258392461,406436785,915403519,772815523,287342158,910981393,666529401,694024434,674476991,758156393,205057332,893019157,4782773,689497585,716589273,10192480,810770086,314209849,830056839,157363179,808244854,893194838,329202444,59481607,595688391,511805211,538106278,201010752,274188836,199065517,295541148,854201789,370818931,196683553,718092467,734686679,922509576,949117603,5767765,40916574,553289744,94681908,359838214,33549005,22044798,975556723,562632280,612634388,680051030,395878322,435541291,985347520,680244800,556909171,525264327,26864207,196663119,195245065,158745085,97536351,577951428,463100891,722427645,747157275,1518694,473253157,803215642,560591672,754919899,521476506,224143387,960782800,35727772,995236173,62237213,958877267,499944145,371581312,637011622,763731967,110975728,577099799,637927593,423091575,649165125,623932896,37113888,695966797,683289821,82765278,353321399,232390168,750844993,206146629,435589425,260690662,280950288,523713315,14882295,541806457,74584348,259439193,936680318,781724111,290269460,457028695,962794519,348419057,816397133,21703702,613032714,205311752,197625815,456274798,857920673,960598773,879915559,122478095,598740298,651027811,707122694,788460450,151281864,755968602,502327881,963528461,364810594,940079314,186372437,161596321,74544332,402811971,219373098,623642178,300961085,365272382,312270729,646644559,81148558,591744101,699556783,52666658,503978644,909484723,840839561,267226957,793429752,635069335,114313415,37105068,13220680,372673423,726700014,912521175,150296624,255072749,562992880,360052147,924103868,291294308,863036805,616691923,193534142,578925443,316097331,524323819,85271008,712436691,723679576,317854106,307016232,689838038,472251415,42131008,945894468,309023927,39371759,452849183,838031598,113852714,474217117,543724178,112914763,560003118,367492479,554390765,972952782,843235437,197388946,904745481,246084898,802854723,91287756,459929200,188939423,666582199,795745905,909330727,580343940,12668905,684087700,544485501,832845191,649574042,866614867,274267488,921456209,217115995,591864161,821765325,533256414,412846183,867602394,611814606,380369786,961162000,312939599,259676620,610948369,324958292,548143513,114592886,65011424,952930574,868167694,406332350,701585842,183715032,101825250,573686007,678079322,328565225,299056508,183722002,221233755,571332234,334621344,833879142,342674963,323078042,418133839,863638254,4642960,444896323,114324839,39375839,179569973,358260236,902776732,761289162,906795297,504753787,760860302,129234269,984047811,486410788,325924229,966158042,71927388,451848382,487676277,900187321,65289712,244933186,903896140,989684451,334896854,558263775,76790020,283938483,574694687,713844667,328587038,824654077,336561786,394773762,144850574,981581899,954730329,780536120,901358576,100499936,651837987,854146011,489888586,150676506,896674409,756076438,751846101,885546402,492546256,768732669,593916342,699589679,167620044,899647801,313147063,817446181,964361707,155846330,44441509,125926423,838289433,680803513,709661805,315368684,252027573,377727658,650968055,600135676,543520999,738680835,817222793,659765758,165950577,16610902,158468982,352742484,965903095,359747217,477419216,77057790,35016388,116706837,135604923,385736466,856508494,240135925,346604466,187986578,741743703,671660508,420925427,464458460,155815451,420105421,629659400,298393323,886901539,354825482,62878521,157648196,209971716,577447774,730977717,419786407,11485630,506583267,918987083,715773859,970352468,716882692,256036293,293449862,926839227,464671263,922507635,147174012,708948307,795567564,155435870,490849403,354848476,283304041,624244902,921550176,971838800,90635588,746171282,329778131,784909574,270511137,705884471,770189428,411741095,291616232,618965437,691159507,14705621,249319955,730518374,539314215,374206032,806706542,277233738,748349912,696556839,316780232,796399738,399701365,19958072,150441772,254789257,273902393,528655076,490324211,668775417,522804866,748739337,445788543,857551570,357752367,742204442,286646614,734003100,226130204,270171954,282062096,823307293,121472721,716199439,753109692,690914847,560609105,765590441,861978791,900034747,191680708,37065578,890190819,884127341,748545911,155374831,966425125,160862851,803963622,895656160,593151236,850764403,376416568,256731350,108266783,340040073,806387501,765187669,103622302,428076791,256179303,436941213,700559659,889799210,535279647,984969633,944053577,846818670,465377084,626051425,931241635,415148048,860428452,64807651,230849912,292660369,866481601,704748050,610516648,963571906,409118107,436519088,307666738,162185541,143803458,968478577,364961045,285360010,762341508,173959161,776180660,925960791,760471144,188305319,106220518,158073490,8052568,709723181,123405759,948735458,636983222,854687367,510562111,538814269,414958915,48898306,269916806,394871926,918296206,746108446,207766067,46037629,808011351,326768575,523137773,795905989,884745015,967443926,545128546,659377661,847847715,145768658,636515646,595576288,754220877,497654570,108693758,299182236,869951867,228676565,58341517,272340297,761345906,997000639,802727319,656474788,458532615,545225862,283173850,329995875,858695304,825116496,644299709,669789716,233178129,840781503,945209586,545504991,502199791,45016008,749005131,764095837,27632873,45665964,718398017,468124972,684288837,900021577,359470422,419416939,171326602,861418216,375677730,621883001,262719737,157347986,67178245,815024375,172429840,285793781,362974052,438117005,22212357,572653177,967248712,147908307,445549055,844168028,254597348,271427795,297837027,986929271,650283443,88525763,367196707,275625134,615992821,155987294,736585340,599913549,158876450,265292399,431080429,576549347,302314901,667827486,577810308,557609863,634775898,102950172,157529412,82350513,663785303,926405993,715980207,608486379,804281153,812899526,808953515,541454223,944901767,173946685,964128119,128251651,771891743,103349598,929116340,391595128,123467855,932412961,472118663,374620343,803980211,832139566,129978375,58928431,472816413,179173786,524289480,690639066,817904043,668425492,312554608,154643661,105488547,954540112,121198578,719164807,270543179,801536633,562485162,457848901,748718641,858362833,325517139,770736841,746297301,962103785,109456722,732742079,582168462,180105087,479599446,817610423,642520495,753479899,185096588,635851632,628099912,109535931,163224538,822175418,243854434,911385229,295892364,435724567,350875719,609803619,306963437,371131156,775279116,51047345,556926473,492819263,869732694,611745063,767043819,18008002,809021397,363564270,701526008,394888900,674912941,99082347,654404406,302293695,117303971,539257940,837661888,167515611,952596798,4726949,665609468,942567988,849170202,498547389,294681054,396326413,157610425,755008458,769504426,562819783,740179059,999614189,879970360,433907555,501438455,180140031,667066456,829240475,260524891,127427504,941461554,536026061,443904766,538479073,666486812,475530191,121557438,704601606,732073522,654669281,288956417,330644566,474059656,150424442,991489777,99067195,969677742,216408703,861086656,983884426,765232425,661454399,45738687,197306720,95219147,563413639,745846165,296017433,995229504,974721285,655279123,831166377,122630389,23862689,275618615,972434113,763310956,240682538,772799599,758801097,222021574,407681863,884533018,910516888,577385210,750668818,727679293,475333630,512201328,115920268,239911147,616812444,615258783,627020051,114438202,423704759,132011154,809102335,224815801,702924301,388083655,384614589,459165096,556985949,33186676,763547090,79671019,260292923,412612192,584323557,868511230,900469737,101206669,698182,84073256,42740659,666347544,46447535,831681149,726618108,314745817,719477877,397270790,428736937,67117327,83510285,280322395,406534330,196447137,341406877,562030709,216176609,178352284,770257391,623443757,71920424,264713456,258070076,532853252,888277299,602928571,20843140,800380386,346466520,596550492,196271279,150444599,41796604,183946594,518709995,22883926,155223889,241813164,243002819,83522330,738568816,647790387,509278109,603381367,245529214,199042426,496631411,283059021,801063708,228336763,230407617,747927936,205053664,158080535,564823040,626852621,885659740,62569955,462941690,657436187,550611588,713496897,738526838,768313305,355563849,825295711,802492346,9115188,837783963,429989052,46533714,253562704,394743407,520073564,425094703,214876776,952683513,69579893,192790661,903371835,738026727,527955868,768591691,807883173,201323750,265231924,792464830,244405545,302640073,618217965,638447033,501506793,637898053,88091439,321630223,942710133,432609571,735298062,659207339,654626584,177624084,325543472,278234501,466367576,75799753,297034885,431857994,736766097,554288165,521858670,674431015,712838839,374707766,219358707,11986940,171500681,995108745,822414126,773429240,497773393,84147836,447324625,284924770,831103735,732597762,111621629,366507019,936342167,769487633,953960023,539410864,343651321,504811381,506686321,861310460,149926844,71603692,618328555,658392303,475932476,764909567,872199272,239303720,781334644,577418605,897639606,407226315,840035970,672711556,950713304,436900477,556786759,196837513,872948988,59803133,841639444,431114540,992989742,959727001,341397019,35014256,189862862,688285397,410699984,704940549,267654352,646511603,451069993,674747968,829824144,924980138,162275226,465160124,440821433,995718536,466270267,346573936,213351896,45394219,672702134,774941341,239209769,816542893,624409808,379077507,54766283,718648465,271563485,942495363,422756581,674891862,131430566,686335829,861585124,840675147,187623889,19210619,147399850,321119117,764380491,316227281,816337498,483925410,238121689,608182597,710653447,405786948,677715899,624566258,489180345,420371679,928248362,538240900,832627053,406550952,369588245,421552209,231715977,417985114,642280997,152861969,228331153,486333700,644832380,911925317,192172391,257715573,40130253,978632246,302648868,318752677,427354734,227524387,400996629,209136343,628156092,918914263,660648922,932109625,53519583,654173554,18043981,245970262,237970440,644515824,430612770,740462903,916548648,118306884,722767066,874209210,815192967,594808673,585278365,301889328,423305202,355455280,741464976,312365309,625420614,115298834,375311380,11353707,888193791,629800548,481567219,56585226,71738890,438346429,817616413,159022094,934956539,88382740,39347644,273318544,291765747,739860057,163349093,171435821,737951652,150078562,306658624,160376218,269852974,419218806,264704829,114194426,758353687,849953864,598885119,947636117,403533674,783374118,683714946,585007186,408563833,906490526,8376026,506869195,65293920,555819622,979084732,230576283,365389481,131384076,384991092,390665995,463112533,492673027,357612604,691134538,670555840,493144843,884825675,924707067,458006803,338452922,909993547,618658246,665488722,105699532,548349881,941393657,71589208,960276828,476555255,350993514,841503748,743401356,375477892,84681157,887395809,379273654,809248820,706063598,837192550,153631633,517912889,542430989,583025804,143810531,457633291,3581787,923768846,150235648,434939988,220029873,359561578,778292666,606022945,692530373,973838531,672993728,126042063,980487480,808647755,500778296,101831810,525570260,32507394,769739568,318316064,722174817,563445207,541430241,332724893,293833531,223822548,700820742,253572953,990824318,197212244,238710718,829296155,435061298,241012344,283494858,393200783,727424758,784293541,932040533,180452645,764504111,614331934,298603090,591009348,883507512,70817116,936947718,198526116,224162926,998195810,905422583,422886544,356508717,355963742,869367023,68618222,204061624,748592410,733882522,660084619,366673520,656550586,706470965,643025550,142650333,12576481,684576220,136250632,707143038,164883272,273354336,131381561,697304278,531832881,295448499,411235062,844141255,300953157,46445567,240045663,75613778,767367403,722825918,559189043,953001367,593642807,696528916,646231494,526768055,966431342,262303835,816805593,475108509,346197914,689253420,314440147,643055796,466085886,810234264,672803296,369682546,641441365,143866550,606129599,236769208,828685380,705575005,650125214,830219673,464996130,656683754,335414200,824839929,274175823,713176165,465518910,247114819,310545498,139778618,816892879,646627080,216783310,902414271,231627423,577858603,345742194,193529718,645171014,711008781,957338718,477263674,855036816,427362654,102135141,591855671,596174330,147864665,351060641,776173194,992444768,798431337,758288670,261666483,244356137,404501728,834491516,23506291,684360658,837630562,441443690,341143075,836749623,888667663,452113252,258332446,771903125,310468677,983331778,894554119,310191120,946618993,753643463,215667460,895097596,680783357,976249362,15246951,288093374,174428455,976302872,107422351,870803524,812312671,906641270,57705315,141717031,576473152,538383620,572958511,365484014,117912138,753689351,449603495,557859899,203951575,481877963,319150131,812702618,462384889,207643231,488881548,374155372,26900221,715677483,616077486,440967988,971178841,405390564,407118661,907507302,685739049,973086988,997043602,560934022,218951837,556834710,853851371,364575359,138460401,734434914,430707546,273994626,940969257,972115720,233856139,552294681,332335765,130278679,968192507,178798291,376332030,602365125,396178784,830852142,186787727,656789390,229475722,786186005,677414215,562345892,826669736,117569830,548591874,535649643,984015017,45481029,94386222,486879078,210779996,852240475,793993520,762853049,385365869,141508567,468597789,299888379,801059049,786080134,22539507,623815979,13557238,521354466,448975218,780244409,835453480,429797889,395623396,309864734,174928347,467976300,98952647,141047598,360873278,895932233,188558410,490362391,362420920,903198286,901013727,946353339,979289894,464303838,493805103,192163457,172767270,480469456,611907307,925826300,529614434,319250068,854237287,942347209,873400683,849844242,637380621,856167559,189536568,174688525,673701983,780055459,240630908,843249962,564841076,289521881,648245646,593959022,507480664,617394127,671088836,39191134,185433158,936925678,40187333,920205108,184928862,846550949,366127134,872122780,38405883,682195498,827204357,196634053,747947915,278339454,712284377,851967253,568648204,722689076,924352658,114120129,310227680,20796396,906844875,890615455,527618896,391813599,686880729,549046925,315543751,943489336,283966931,34993256,75316064,732108379,980865138,908975350,485659090,940552397,65063266,586994756,96749937,975516375,145071190,556334766,861246458,358218093,93264470,746924856,695751441,278030651,596727224,359441731,745560826,409381298,341928687,323345408,204474735,489393204,903337323,604686591,84131998,362938452,242878507,464563065,166823975,80935363,975228836,470523799,55948931,843196465,140505744,730743423,750646179,141489033,792396505,244237477,655608480,29401397,961576526,564156934,893896635,462596010,231185088,927855569,199848020,35693066,564046200,431618335,893721639,963308916,582524621,409050337,667242993,811159579,135931905,74478773,358948713,83946566,784902732,332461689,417167919,619159066,463300017,572351331,15152340,563684828,799133024,761823752,173517550,435079814,328333350,638387061,567591431,359528510,355675005,291534398,504778475,395375645,77155803,102791818,263731169,728145665,546224640,888610304,65837270,87272581,621266785,856761351,995611837,513645429,279508672,673090698,821006770,806440361,828616851,85188487,649462828,227530305,879122638,654954169,867291523,821727311,911940791,928698795,51830219,555414922,135900956,26105309,573646098,661296984,379988066,974891369,89349025,828661166,996507881,789287440,663652058,923021953,561089600,846300332,785635181,771679977,667092362,947126646,504216495,493152151,19247797,45389104,297037580,851683371,693420420,304157142,797131515,896867312,889496361,754637209,639922946,906792492,252200395,126897045,223943979,2610040,944252337,545631121,945818699,406674045,54796773,49687532,607620789,288535380,628073133,611278141,82482275,164770570,753114137,155325598,965082601,440922988,971340286,319248503,83260930,806098744,358167911,141257437,298494797,130548893,524452262,274410693,639410984,419928437,685329929,981579021,263414257,774154060,299877702,430000722,922763804,26801544,78737503,903171927,405550771,964906659,890611152,743522349,48068300,207158605,389258084,589903320,667186002,336391703,799181095,39824017,720704549,640244215,623141026,193766589,714094660,975841587,603548938,923726915,975682216,914467286,988372054,988194259,288144066,981959813,112288934,119616205,632407339,843236146,69751298,565283052,298226409,416685230,572051541,276118156,442910400,706891960,982137338,567806087,630050807,267571273,852244690,84065578,183227287,303823300,87921919,455872111,77732024,921695414,768698628,155929593,125408444,218336621,949489185,856263120,851197086,924597569,478079237,855565890,551474719,714661486,326390702,514026590,872006010,159493246,256560476,434256512,548489092,431758328,629117267,510552118,364288553,375406317,343564970,805367881,263542924,405969462,836096661,351564766,946391188,370951626,839879981,568182204,92410490,450454629,88498082,239950234,444114416,478443556,110710340,88026208,823257098,456200510,342397834,74650012,419645270,500578565,283003665,15457936,27930901,299127279,552743783,890671352,933158471,775410047,971304383,508807878,843951284,515207415,190934297,908876538,151065287,369597621,345764154,263332712,850863067,672037044,298897849,727758688,746453775,675012241,798578017,153283310,841303064,497049878,276201347,900346646,778239443,58243146,691233171,416768159,737261214,36872389,825851976,368397385,695171571,258691045,142498153,140132035,846551674,894603954,469751477,778131589,301281546,17204757,715798982,616913077,184638437,999827530,310436961,437398352,593395757}, inv[5010] = {1,1,500000004,166666668,41666667,808333339,301388891,900198419,487524805,831947206,283194722,571199524,380933296,490841026,320774361,821384963,738836565,514049213,639669405,402087866,120104394,862862120,130130097,179570875,799148792,791965957,761229465,917082579,282752951,699405279,123313510,649139150,957785605,604781386,958964165,170256120,671396008,261389083,243720767,211377457,230284438,469031331,654024560,317535457,393580354,297635121,202122504,366002609,861791727,854322286,57086446,138374245,98814890,662241795,956708188,762849245,960050886,16842998,379600744,752196628,279203279,250478744,971781922,888440989,92006891,262953954,367620517,856233148,659650492,328400734,261834298,102279357,626420551,159266036,785936033,757145819,470488764,58058296,590487931,361904913,517023815,623666965,775898383,33444559,512302915,711909451,833859418,262458156,412073391,746203077,108291146,902288920,444590100,843490222,455781814,720587182,986672790,267903845,992529638,545379091,875453797,751242122,732855320,463425783,917917562,427789694,494601793,929856098,360461633,462022587,631472937,708391653,979539218,150261410,966230370,704054182,781931507,664802838,73430533,244314544,735369293,204424541,157413317,90710678,403957347,35231659,341549460,435760235,26841877,287029784,832977158,494908226,18900820,428713543,234542640,890626248,477136961,324650637,415396022,556945299,311121040,775256183,97008847,909769299,860484515,247313688,97584341,197942752,622959077,816261476,218775078,61051491,388559552,270513463,930328016,535034378,939327150,802161325,87355452,76021104,300475134,921120970,141488402,117432445,836081911,411127772,279585109,331015482,251970332,113916985,971258342,929656488,889125916,178549862,909072132,142337556,23536009,73579300,595918989,327351505,474040845,682177026,267484491,181789534,164031466,579265039,169780996,589143218,907389066,354007352,970284256,753771127,915384231,880390598,520002017,689846169,600458403,815230759,706137534,732191651,538660962,47456025,599244836,111326330,657408467,412962971,375791085,784424117,527809735,930755077,237765502,688330647,526831752,551769167,745569020,26723577,264012611,623336468,599189621,669402697,589406380,862395510,571452236,262652254,206529699,414251246,621302001,764851556,933179180,287917815,979512693,56188367,340759435,756827299,7507809,544712803,794680992,674239165,82664871,130052992,267208556,113141945,12864223,559723725,842457890,921805957,885861006,35975146,40467642,554379392,778217523,182383338,405485651,139942632,890314741,678001239,811242198,707436745,425222626,905116696,126558142,441097927,852828624,326436613,232297110,604650182,671446058,10005416,522425397,518670730,38958040,830402065,800847072,376559882,110863358,113130413,279395402,246496014,986498194,953356631,314119133,22470175,961072596,215410152,155688065,70721713,297450078,812883107,541016959,1872031,644834046,476442732,755056316,91314186,326841207,285853701,396235995,476081606,270053967,311939982,581039804,985319076,135712978,964144274,904487323,678375373,515288812,705261532,807484621,122354320,419749533,972410777,211450036,949557355,18947635,222282375,48171780,378700860,623832397,478444619,510870143,876980910,810176965,748638324,113421724,440348993,863313960,855851119,438584915,828080811,720691159,71663720,48408626,843989221,837856261,23396586,696498209,699396142,558282241,447074582,748373754,670816350,949329879,230172975,253576086,513778485,518825953,716192587,608379868,932975307,856951364,238908695,952383270,413462845,749755550,255633116,371504590,575270325,736243777,7621849,202798951,842667039,502327813,12403107,546737375,494648599,151624724,395508517,384226928,242233679,35789821,275029085,239986639,890723831,812542048,364833448,745651158,442296160,329212426,335960985,66673582,971303612,458040065,136966163,279002518,756568843,351700958,866541869,396563255,517728958,965430081,680218496,838469951,144627151,576509210,798927877,640906388,538138307,199844570,847618664,622119051,373122494,767097325,617288087,395092300,433074305,67569149,815890839,568176207,776450314,850674275,408395804,136913583,801784300,794207214,262154718,34284026,400561835,433972639,573828101,184699592,812790266,404769648,582517190,392883298,497395023,656097176,460552924,608552698,486267026,331363414,476406879,202491684,432338321,344314146,993894982,649068571,532377735,925873015,756095388,83536581,782502356,467833719,201958994,113067476,982276563,417000623,683259514,595275137,339855849,540755239,602085936,629650637,694546695,783468170,990732904,300418276,153830238,781995268,886235290,762796169,704474617,834858176,120593647,291208178,185572492,867351020,704212748,633983365,436319797,679651749,574691409,884692149,583265738,954817023,25168036,437027667,13494817,926806481,260807531,473460019,215121540,398786562,665421923,247242609,357210812,375220601,951489166,260146496,562904189,803189606,115688778,402674167,664102792,62073083,931438538,989781133,54305395,845490579,408508000,817016,770460718,252530800,193344993,18240764,451521272,550299453,675641621,648967803,128976362,498292114,586102337,268722858,813389329,711699206,345071263,549118359,498160774,12544712,899831499,7499676,159323417,860458480,925163407,526574743,431479193,124394448,736478932,827152428,468482333,191449968,570982019,630772527,6811956,460686917,587776989,189529436,618602480,213045731,31935150,166725807,46518902,361709447,728106284,141044314,106680816,648547039,81624401,345039463,428679492,444415784,871949944,552304261,263204892,812749473,93356306,615275825,658196191,99745872,808765204,980015659,506203240,798053748,875307384,490913669,395559142,537801345,254916759,26857248,323421544,786532324,111710215,362083412,98363148,686582519,232498406,816375871,302974657,320593384,541140925,837139904,84057040,831759554,589762885,489023570,342716282,966455154,672855976,456926629,511811424,370359005,435482844,480465346,749545478,742002607,688642026,635383632,287496457,895129599,639223927,732732045,883082755,597812434,281256739,243843142,932634458,133552203,978803223,605228299,76527469,923076281,353392926,363322540,770576388,900277818,11219964,45472760,708339507,491437446,743928014,675393437,584018351,629556304,639854830,305512590,408488823,110876181,497784495,617034693,851537422,102938949,385266150,668331122,814641919,630622468,978945869,28268783,357972167,146329111,973624935,149958790,433931296,25598024,447940280,354732829,764891064,685394573,585294277,465409408,469130064,920721745,182673921,284022508,597678446,416816025,588422624,98457962,240636924,36839874,300511140,182273503,581213731,455560749,864940520,856724314,261438685,740632796,674273817,942626165,174802133,374887767,194299387,742848665,907493095,441999251,492506669,611675310,290416066,970929824,883609623,223358251,807963821,422005815,659475855,461490465,664907290,263359925,173600234,665950005,716496304,824226812,899890349,390028746,771125588,145203352,452007490,325362082,146808268,736600017,245688986,146065271,957412368,898799739,278661168,704941285,610928999,81601883,483849511,959722958,846205539,512459448,477514011,94771790,785546670,950680044,61469483,942823288,676349828,399270685,202224300,83614201,27855221,178708942,736070142,898806733,147446631,252269212,554679879,911476215,87670064,942585856,185967971,834953514,366759830,422843000,170643325,93981853,572719111,985870900,598086433,218375794,859943833,859649526,91331965,695015236,607644320,732718027,917982226,747216559,979635810,561306185,34036360,223449518,94586255,423202372,442944642,611697021,200279654,277309078,618283679,820550379,353246455,521460957,68835467,668938271,630939793,166620027,751195077,59571869,663276431,490471791,292464946,386389206,728831039,100424847,231097324,77617394,253639149,723976405,560621283,219949516,322944880,693507607,78791198,119998459,265121019,385833490,175839688,127126701,357575575,462477947,523972795,85257542,474256318,882209397,465260644,945308123,444097002,744917420,375150087,199218939,962795536,153320195,574288074,366385933,970641480,460261345,165378268,54660122,796112070,75056929,684432874,318576890,508386937,736496795,933419021,301388996,795962538,981413164,518902828,825023058,764707707,274652931,632168477,715573025,516018880,296024238,427201967,100757491,425935778,453525227,714143838,325377579,154052075,164453301,661274799,281891479,854578132,707463702,54478503,560779145,542878457,842687510,21165703,595996646,257510057,793448599,603061927,924060221,392136705,100461338,471328395,891398279,205030949,652464912,835850842,87425060,823905986,380913646,278673941,927068232,520240501,876473603,136589194,511732167,687296805,683241687,350269024,968145478,892943787,218267753,631708693,575265725,844874308,490669196,539989340,283721451,422216333,634877244,154305891,30857166,70409600,192823595,593649861,218997343,408157062,510618691,46798894,349151803,787794327,112121118,212247051,734542883,558493333,135971470,553224553,555304942,877988083,353984399,287379295,128097089,213238733,686489183,584370424,478522537,386164116,728903056,854166382,496535429,200766267,471649197,622910706,125683017,956326056,20739963,301662013,197927580,561829805,470110929,409651919,25445274,530972257,693634465,812235796,433779479,246955439,273484835,533196859,434841810,150091327,794785050,966482053,130865325,820075960,424860898,894572050,601383094,45465724,85336318,672082365,48587322,356055887,859189025,162098823,439790362,893587086,428005909,694221764,21829348,71677376,928496509,456286540,290395261,680262749,924193154,292067220,171853628,296940288,150623112,455840069,180683168,811842548,508120422,642272196,544234726,650304911,229451663,921643700,798472778,749018037,226545381,765423842,718894474,717080061,749196186,489999179,806854513,378512648,701818525,88561613,592947516,719258871,280773178,426531817,513644853,265496088,511425456,854621511,704306302,284837521,431600849,280960245,932742910,291976581,677356118,77062670,110519140,832608350,207247104,180387636,52180388,623428756,387847736,784035746,353370556,902839181,7855705,291964109,433821396,645623217,653114483,803811197,899015630,881440298,612309117,704051541,525299267,338766275,893260091,835027739,493955913,741913772,478221054,317183014,709294129,149960288,300341094,154138600,902873682,630615042,402553998,895637789,935945392,681448161,355591345,343338738,967512882,916072825,984504894,522602992,754348662,579975363,204971187,68269388,616923634,343174092,457307053,322308796,27025104,796975244,722663791,869384082,854438584,72986172,958323523,850197469,490388448,851930364,530105798,594457139,965655155,978289974,921177,159925609,392067602,154358750,390388707,362127827,965694883,326441251,651706959,759712150,901828096,85649421,511252936,351173261,584898864,36754781,526008125,156187219,928848328,969406897,419565074,999464056,41512421,412019830,363178658,93250395,517548947,368702986,20521746,372154468,256751059,62448995,719435516,16182133,384138855,496248079,12291665,204742760,836549772,897217581,239471161,496137330,842840710,489450538,920876544,846360328,834698887,428164745,437322674,837477344,65501329,828450591,109361267,106824540,656009704,581607891,978158869,7129722,923220658,489672814,228600423,270907037,851664514,332312593,871520710,333515105,717494256,336330821,564014456,400145020,353485,427184781,489794699,38317000,274681619,99625930,399033066,384898188,768758688,60270604,907233168,153024702,816567335,860975174,604590733,770361462,667918438,823905940,113759919,883678338,16392082,65061919,245290350,233978608,958679919,914398174,999062527,735115676,528219931,686070823,479936381,147446206,122119800,115984653,229087467,619733584,658064845,722547537,828822696,427693276,522549230,580155630,101005244,326043411,941603785,634614791,539587962,656946220,254794024,980740730,327394876,181172778,751842212,227638687,542350458,812588338,221222719,723482951,384641585,112833453,279457077,823369207,343235655,799450412,512374126,981213352,735376644,520212995,929600184,779291929,249400411,866375235,63011940,506276362,8711672,602327023,224836365,484056940,66515750,179245679,236946574,198876297,312354925,761573960,375626297,840900274,900526197,86054575,799250870,361014950,378364172,308567757,252703080,28777717,960056106,692713987,478577132,176955719,165184518,48062701,250850702,797445951,53320459,289921719,857030687,177734060,179465053,32428947,531477769,206713521,790021514,184062770,381176902,304723839,736199623,273244749,632430489,512916281,854010339,552241419,137022558,252304090,816788127,358419754,243915941,846653877,411642812,350604961,505833817,775976083,316779698,87345036,617157714,718274438,144327232,105086289,303710638,329632556,616007589,297888285,960139856,745451804,642657345,659327579,357099789,414531796,778102143,69412121,825835484,627498705,213437988,286994108,184024140,54617918,615905617,458132020,127684886,193272061,819529674,252377639,866294416,750863342,706917210,70043952,592646643,284188627,962468565,363327538,743356411,308795818,754461446,466427065,123823948,196263468,819445843,114628498,466448496,895696300,840378400,845797396,284181250,349797551,401331660,315894551,90665574,321253355,770349970,529772824,703431651,155717966,217969531,39469365,15890838,615861054,63812867,660183737,531370624,542912999,273340538,879243688,643302740,911210286,774296265,483726068,410541714,834263687,412432188,154154170,67279220,972458828,724634,900968528,488765605,372110609,965358187,645111629,158490440,159494805,100118145,135529326,957200842,970404442,764379920,701671134,438570557,296564903,34828104,306868897,6843286,867014586,687861249,853769530,826139133,411594244,795323281,198826134,57162885,737076092,368421226,841260707,924082558,813491690,290257274,49665642,181722142,785171917,439611884,937954765,888360843,970230536,429066740,806528615,855351544,757296288,364182756,595071513,130832185,56969642,132415087,250993830,383801004,627698354,726418727,548190985,15435667,71593011,495759369,883842579,288488461,799634901,777317862,972756470,848271200,242596636,270442816,393227041,620307694,397885246,37161621,918523863,603341735,812882767,117265123,234005136,593385601,738598019,215612553,943069501,660523293,879423316,75161339,454023307,654110976,619406398,4641940,966366259,778687937,607962697,160565010,721286214,987933866,175846431,901796273,381116237,237730584,689100722,167377679,32082959,182661170,719071942,316726127,427800922,79243630,294172489,162720729,95482185,299099092,332159491,542987700,111332177,144016070,521090173,775461553,867199636,684661543,83517270,448616956,740540524,910096267,459212937,549561709,122726974,228225908,17903226,506151370,50106443,451669013,774303388,970594771,844983415,858590348,223936587,477085442,352187857,854574659,783246163,809054976,978234662,523633946,404810019,556953317,831798356,493821970,17167557,619796214,549172698,318917457,740979802,962913416,406413761,443301889,489915142,806218155,237997472,679303479,697848571,949063991,304168824,112202780,245910863,691908068,343108391,191052600,807435921,843165634,857891954,996590121,722330416,915710159,610136146,864160149,120201032,286737255,911080361,616036337,239034963,729406484,789815283,428809092,791208953,446643373,794777841,951308916,860951684,522189356,897525998,695613569,264025910,836773879,19488422,37871729,392718771,656709730,518343137,527030175,714070942,831413576,72015214,362384428,699131987,945330183,891733856,782960973,722836873,936431337,635382313,295630094,273915838,462112207,204037469,663146936,145307887,151316158,659904388,535128477,570671249,886759102,862659890,801835044,944139555,886007778,157956500,184244219,861459587,574624180,370500720,439011802,612771841,826504956,250048700,463263393,952614923,996157958,83807085,368708002,83937038,643906175,892744722,781577692,754447556,391121651,47625472,494979565,899365924,855548156,718245467,758008976,817972321,269067909,161074211,589925302,400244777,647051601,851189380,942889223,9983024,428041294,55302090,456284567,87730347,485073493,32117950,243162170,498593874,2801117,944619049,613149643,352773868,177858867,946106685,787807764,537376202,611237536,716787149,13438606,449606335,201143145,935269397,833293382,872198213,823595689,557500679,975096990,572907756,790020244,794585144,39800114,712117746,602890874,299572590,253860034,567822331,692513972,146600927,380896458,907990780,772227106,286621251,748345506,784733915,412779987,449429571,461952211,642834018,270135381,18378953,486054845,586104343,273688550,470789639,79582803,261391159,55176174,690667785,614547509,646116207,192790180,971785896,333115536,920128312,24621016,613965501,984143015,264855343,258862460,757203882,97576262,416475483,917015860,329693010,489431638,18822135,66319488,472278403,987751963,616569922,683323348,141562433,453060457,861661553,872688271,152627861,45815100,584596927,214462989,182106974,790392249,121249493,947409030,915994926,32456262,416439729,900481966,969262828,177458293,401400980,983746415,638012804,16845890,262208612,100036551,142160915,119214884,48750273,768492825,111170764,597254788,478406823,82735911,404490205,872315713,283054477,406816254,305193481,623138229,670135787,491076916,967708603,774399836,973140274,598706822,578989387,693491298,195184634,699997215,574232776,967924910,373607825,407730412,524210131,678709133,561845768,160646971,629487409,729049249,814466931,218535368,890292436,30396720,270551637,968582413,495105329,170582057,403536153,259681294,31058776,665921663,365160621,684208668,148306231,798600637,136793270,452757582,390001574,771292717,469989356,172053465,827272350,972060957,881301574,274052954,919610927,101995245,801757510,840771103,420396591,850350909,935472223,407873151,486396318,836617611,398103002,497405924,827322488,221186557,531919636,501986460,7027536,995509573,605836899,540744020,266708215,999588969,750139831,757978807,966288747,391480030,950470370,615056133,223123986,590526301,464356125,904941119,570420584,824371064,634292921,325714292,164161043,139535646,57823174,877945524,707641683,627332400,623616255,792704112,121080634,598518301,505029588,738400574,70534733,75645991,869319171,267844169,946704053,311644663,497144552,126786109,985776140,626915266,384748446,661023467,40406486,494539700,726298383,841033028,504018084,149072221,530425959,34716080,127817978,599414752,356028052,909681592,433193290,254048582,908684845,318775130,389515378,383907348,923619728,112336385,453126610,827794543,261153278,164821861,343889998,570532412,736922954,393911853,663097742,616988718,468222879,914492036,519091374,533684859,560868978,636469794,516749046,571245568,532279018,954098975,40233011,400772660,40429369,151682975,890815048,679277743,384526101,249938251,363041124,532245218,632425122,763411118,534273823,805721900,133087759,205076193,118257093,521871417,899798981,825664086,124177199,496350416,844825656,103311149,58348337,81069041,175797285,436600954,868554528,970860765,125710968,457299745,372272984,168972719,475576689,613000835,369464458,213878667,678176690,868915977,965249043,266788473,593840838,41234964,277420681,95009131,533837096,189808293,869801057,595120193,228225365,12135959,416716523,141657995,451821421,829745481,855565272,12945607,192614757,645781802,399191777,341683574,113424252,984482574,248045919,310813304,144277250,943079943,860664470,808934097,237355891,551829040,873670202,832062852,769144075,366237951,250317814,926933160,561528563,821607384,541853636,109332230,74606341,240017785,247170016,568915389,306602832,243234157,796639285,507067954,731954469,68440100,951441664,254065156,368550879,507338385,684791908,284022855,145478850,241664364,105573951,123780843,285559178,836360921,91426722,277485483,715224731,465845295,663858881,840600340,337983074,320333327,754086250,442689318,543471268,518980525,523758963,692688772,282530385,482988162,84963686,785325088,711226869,775282597,610858224,382601038,269171747,426768431,761640773,749880347,535248313,354832123,692408442,265877962,259021473,890520037,192041282,337096023,977679715,499489354,415127057,230247071,225551247,690541157,696407848,538195426,675728325,828694398,492207211,37520978,333351975,97980811,973745903,130939359,692677714,364069714,233959422,323878200,165424978,46570438,967892528,285063190,656930900,269820797,273936766,999148891,586988249,504230047,426146842,477571926,351440028,504597565,666095630,958087480,210092337,557021639,620675346,373833667,661623637,948903838,995080234,874263744,160818712,538690531,914772205,948200579,916519382,85325132,336462862,695095747,560494449,849834716,125474373,422726401,167925488,406301230,370765569,569597463,450058032,549199838,395321961,783621770,278829843,385904567,813926423,88884878,377520005,727235522,554189881,402294496,935553453,847606348,909324154,219127807,130582152,677637436,690561639,107543540,657908483,446521573,348270056,971376336,999027046,340843256,603421587,909771760,703642787,952011319,593472989,713954820,236843745,465729155,415496771,806973048,159183107,592544896,123674391,327201752,541326611,219572469,780418252,435732141,214933841,196208422,377406841,528167654,466348115,215860830,294749344,803169868,750971690,205653252,422792274,970899247,950387772,224244755,859473458,125877111,991572792,923181709,172361368,148857045,324775935,399494253,853502354,407355972,729172084,182501960,401774992,910132171,788518586,785749077,177885598,650832348,151918968,305964417,81489465,292094156,461135965,897040686,187539451,501486729,875758275,156512470,90897305,209073976,188557039,522413286,383785411,1572391,19043926,965654159,94647636,749580083,546476397,186073438,473453488,896515494,501108988,214847878,236345285,379499238,416341573,834448917,16074965,138845054,498911412,886865864,157018364,893258302,114539006,368037969,704996804,105103400,56088702,586802616,679938877,967743098,792282327,514111957,566428823,933867419,647109326,822802892,628176869,651566813,285359329,937573230,418501862,433585086,933166256,725129069,958416922,234498370,161690715,138836075,245174552,483747810,905262954,659811659,386137003,849086275,426688931,11526151,421391723,494303170,292663788,812802116,55546270,409609201,457031006,816827933,558382319,779584113,785196029,395755276,255698855,448313381,555807439,331933309,64026961,435730231,232555386,962368630,500207623,304982142,788831312,2147458,273869185,699495466,582489702,561585720,503606977,322676034,297864408,96647840,713308021,356122015,585611839,925774142,110978946,195236623,889173831,146878529,370781880,861374909,553962376,436690653,448883473,878085656,921383977,281242852,44027159,233618808,676665321,23771774,801692689,510531726,819774677,23793004,575794875,36915104,718780100,491049774,229594642,983346389,296599097,61364141,385319846,643655515,530859509,717471799,810425268,634802476,314288453,144562902,343635177,898834934,843006948,969694576,162492202,964169224,41122175,214803642,506871365,187721536,282301322,93573058,807548488,551835758,534039182,102238030,671068518,400118064,257901664,732923374,539683746,618495519,761676883,116316976,923628455,624966857,390292830,329744275,68196682,333651734,51681963,125996400,574697536,415473488,493910714,908597202,809895728,299140717,922010857,538361527,133910463,409971516,670146481,667385942,886210676,979727292,610743973,481345981,541246822,906589889,504038900,871460967,912857776,429207918,353805921,834341825,863312358,954992863,966176726,241645073,736742906,180656729,892430872,207042030,833635107,636447801,425431324,14674097,619946606,67555344,687129658,24122183,708219538,606593635,954358950,116803042,180092062,360857427,129130615,618799466,106239424,715299259,746596913,317420238,476647240,98340376,514629323,203514215,306380870,644555064,94404625,301727599,402067370,476560740,182248868,822317718,821819929,869453634,781181938,689983681,363888184,112757937,434318675,412860758,198242914,443875105,910039367,764421648,732201271,380122365,446789506,465458911,457325582,695007248,281945262,674303240,561868189,681787095,52850141,167244726,809573680,567003993,782826746,484089440,373068704,507642711,803537487,889361410,930573069,656947917,667769597,692808208,416712076,230686864,52727181,72515629,79947212,541423823,920786694,491695945,774076771,218088463,570515530,94372633,643043493,810908852,315385944,219421018,760700220,796029948,977272971,369537975,738942637,87886079,696295889,907023957,905505971,586168110,573075986,855854426,602646931,404755186,892013425,693649478,772694909,866519112,151274651,130478854,911373312,784686024,538907593,123077106,451702605,516089605,320226700,373398628,456771245,399615952,419373066,892766228,401339070,12358268,476640539,894994580,224074299,631178606,640012653,368872676,411985764,29340351,317144328,447901681,559469005,452087167,33340917,762745899,37883938,671259247,317590337,28780303,486901488,780841498,934212357,160328048,735868039,404080465,974005673,11252617,914761266,187666706,466929560,381713629,847604066,717033554,454760145,974921723,814418812,780775013,911005523,590837076,494834272,41797934,667749624,937916773,373526937,189046937,239197226,246703592,552551541,774143766,372966979,818076885,429238584,54311003,216495947,648853026,627295771,300328816,573818172,734937979,628715740,373265366,353579243,719807134,683202465,392109037,993818664,724858999,608517954,893436920,704584203,166681655,594692490,381751461,649578272,801361323,268955174,522976721,992322820,302203439,651556603,406162033,613304279,866094933,88818756,599091521,315363103,61003678,415021991,867902291,252203965,727549889,834075878,407066647,727930701,800206713,24187948,90776287,79816495,189632455,423677077,448993627,323096056,36816197,364821234,887037768,207363369,485271774,65245529,90757495,69322989,962283790,227134301,429715063,432735998,75537194,284689531,578914868,849661983,903743087,350873885,374167008,288405336,481134165,176725179,747359419,299321998,470340035,549853247,336765788,939488908,635883977,29963676,726863417,691757376,866881948,584534448,786049518,203229131,653272995,680128236,866415440,187953256,505837034,105073315,477382904,909204376,8023486,267360195,206774296,455042845,21247143,442750385,686616678,935968861,50472827,236730584,342598141,975675436,404497969,408325508,563514632,220741518,405118516,446589831,755886663,168287958,906385493,352077043,354395770,709149642,172893214,554607717,600894612,161261260,605224477,257914698,478853537,131770518,497396429,978210464,867037207,781850455,161158915,378418905,65574289,154278101,922582878,53994176,918449400,771581149,733498715,1408336,485671726,409530976,850191992,406723239,60017592,968031628,672297985,446661266,421972432,127930092,38365113,730018167,816715478,878730481,804905756,500489282,764055661,95078328,844979436,207354917,388176408,161761384,730800963,800647034,202840303,901457922,729238787,712104984,286832877,256727653,123511085,960538028,910939104,23802957,383851009,809595782,782295242,256148122,637269948,408263574,852306196,565485450,568138640,267372224,430366239,237089496,335150888,805607694,540298377,538148948,816631445,282951031,792634233,17298571,179976830,784329513,365503817,858016065,980021415,960154939,777271449,342343265,884061297,953916788,141735611,797254969,51433869,144925133,537185638,959771115,849360686,660613064,139743251,287023761,622629140,714933129,352534802,82210530,208821324,72211213,288825848,257698072,152983797,332414256,649244308,291431951,297038509,652171249,282354809,906341617,996318877,295295780,692527445,783494551,297808995,711429859,745164281,325116468,27754588,290449931,663986360,754690883,204703956,539820223,840181363,369546677,590054227,441678167,130232493,437931996,480969566,830431048,624034169,89918277,979425140,143830657,130471038,584012453,740644053,904633945,658695760,994828242,161137286,973751768,337526570,943945821,96452105,924827805,23713967,987782716,232562109,336770596,518799131,564638711,299197647,771904992,24667111,762289237,361921970,179993524,709233527,429541440,174813724,577164517,296701420,85912300,814183677,67815000,642881367,831361263,348262444,400052897,996219712,868091350,499952994,125578894,110443583,350341919,79484108,118135712,643000764,629450058,793400663,309695704,508632708,937347764,564562583,318752951,165715871,352061582,78083651,746751009,502034972,506018423,118721168,23742031,689895246,733011633,180824387,879258510,163446067,724378207,908865348,557992549,209294075,386749842,65675388,752752973,796391820,93205348,156964535,703889194,299122326,238066477,500083653,692483350,766394838,857411868,728721904,914671603,384261809,121761046,210974690,709355863,725388435,879497867,557690521,246085238,351834298,381108648,67219116,371312339,406205070,445167963,262890849,214252841,826085868,508478946,554881007,345717481,749772191,320831806,867891736,609693184,786025629,276602722,549088469,879662767,236069329,831737621,256013790,90619499,239629204,87778035,441818360,947156854,883291958,62264899,374762032,562218877,938299529,713770589,785664750,533950147,578568357,424431680,17399735,391520320,151859146,679817950,441998562,599876683,436501338,453162310,359412653,629294608,1591917,846683262,833280653,843639058,99877624,516340504,310403688,256024154,395835402,671716095,171923139,317633412,672711523,421318973,995695188,916864767,875484570,595171110,206628563,933107840,273542730,856358334,948415146,967570261,483617865,552500385,520638211,827093920,902189071,230474019,382311260,388357373,830404209,361384023,211203735,775810812,553252657,901376323,405940728,56126889,358252,303492833,739424918,765414924,923023521,36208271,744426616,809727392,594319939,752652802,468138155,891675619,528341786,735403025,41099056,618981138,743123818,413741360,61501599,299312945,717418911,883704088,894573644,738099828,899306231,735586721,770590317,452023731,122127697,111226782,533281141,758822859,820053302,386387139,349224143,701759718,259618554,785011603,839847632,27398677,160986413,163988287,183666887,994712032,834557062,259216359,159405217,143291956,279086548,253680044,520431518,887135862,578295716,834581244,176826977,148577033,730076096,876116504,923112487,903865358,106018573,507845141,799836499,306144086,984829404,989374328,790640143,886166056,928675791,179293563,804234364,928862,24503619,286006127,867401067,638063981,160594599,592780366,864042564,808015877,669025109,29603508,992088985,170898084,953882229,879641906,366802785,275244418,805756015,704249513,611489224,882070256,668711212,292229108,505684497,80021586,16452044,342534141,278838654,891460078,511447333,646281227,439228292,577004012,671224449,752594576,562787363,877761966,659318644,423506486,779733003,64328125,439563509,573812341,332976427,209054189,106138726,163819296,389485919,726243724,134526156,673553125,272206371,346555589,681427920,787725820,309950466,686930070,193331253,21512295,260240909,459974099,130993499,843924379,710526911,943143220,631953034,587887185,222808779,740596963,8983354,202333761,911715972,707185937,408055367,582737817,591978911,94536989,342730796,815092912,488965495,585185214,515672644,631253043,945077780,441812790,775271208,630201380,995051585,189570343,643239892,581744372,101151687,663484785,517244054,270644796,427832580,505755327,843230351,291576271,461607308,937307351,399979909,474655556,216679904,798020076,538027539,455532172,346914760,161607585,33619440,105475750,693324438,117117000,919577630,131158500,430163104,903805481,546525452,305561534,887924022,954089820,102214679,669246173,582962845,194903903,389056906,433192072,66889127,466815030,374354137,494561564,31268115,536030238,496997475,238026325,614216246,276581370,652178896,236823625,413311220,808931095,270825613,470822789,398314621,988428181,588491922,306347077,287209840,287113109,797123463,927673444,252027659,530511523,960759941,449719751,283380506,383396343,395271853,121307924,223449123,552759818,593255589,7731297,341611483,715784363,563981092,7712396,550536009,864308301,998075386,363749791,839298987,81428800,65188418,337633948,893029948,470076069,254527560,396388657,111130829,108818735,592221510,642171895,546421669,353277062,446427368,629156456,506122635,649362687,792908161,911434381,628632850,381385438,901115008,683131382,470654369,11965989,252802230,769428915,414471547,944521433,124827492,922733576,997182730,925534348,450659288,873318040,193699108,132690952,908343467,164418813,254230472,212396854,972219189,899465586,328664030,88200515,39273239,766153627,949896904,856112972,87918554,357324260,199986838,826456986,638355879,409441715,631980732,5738214,588055958,864139143,554419739,347755899,263022067,541734717,650750384,80998695,660651417,13405174,65688584,729384997,953904726,269841739,291621658,842565627,45294904,233704533,782374073,621604649,305269771,960019973,489896034,51815927,90174761,349859512,891982248,34165491,565028748,659311884,631073620,947432478,111874218,560229164,870981185,372485833,444997715,850972608,916874922,818350135,841793908,980797147,881453136,435090083,419026458,71187072,362498845,28941578,920518496,153752054,375425640,111965877,602761206,104090507,760479742,689906296,377932783,434607547,737276051,171072658,185662357,891564123,867640962,564442058,109469941,853338210,895851949,732698603,675432061,420764378,854255812,462143497,689597036,720773747,605575192,152153349,316832780,191072733,462775431,124575527,932429266,418724073,592017639,642627449,423062016,394366358,79902330,440803572,18117747,952058178,144083901,246224645,953666541,655478504,643523487,70787773,15870451,24518945,984167526,89627777,531986153,414909524,945795502,34600357,106513903,962155245,786512276,318267219,132097220,584191871,915302029,31531796,63104623,157114879,145495871,476106306,450200986,761500808,783351610,858563520,263912877,360719478,90908226,326042989,381176172,980842336,767332798,484968102,840783468,901048506,774689481,450066499,326464519,543426938,266275409,151423671,756250426,669942767,836287644,161451518,625195238,672064093,27041907,603369819,166156655,959082281,581013287,606651260,433629759,759621327,226533145,558171976,9575933,259338307,427177939,100037373,695975339,883611159,760975816,628048427,447073961,531371982,388425625,833300629,873925358,998791078,106912359,120968350,100152509,335118572,911742288,20448009,150005980,773209595,485030164,113492560,98163988,187181947,196493633,781207036,976890674,171471827,227163696,33292674,347911801,19326511,42230439,651540683,158222219,177526397,76549601,912206040,965381462,224924553,993964250,311064180,463504958,57028594,344764085,818782937,951803598,497521547,182463051,694054616,54662241,941805585,643295258,650258556,767549270,296721885,21774645,863839779,613833484,261662479,865182462,176686453,537291195,212276276,890424783,160626025,221787956,590724071,177980037,712237971,809824959,848203238,757296552,47412172,573086141,445088610,271548331,870730546,644503088,194382220,169498675,124366782,362263024,292212990,929515845,51026532,166299034,861039358,13427232,55861767,59294348,196696049,107955552,569129605,713263486,810612892,433622248,779203670,340222632,348854679,212835197,876737898,245113226,49142686,63334040,321375347,786579645,890791280,971763765,337787460,477317141,548954549,917344615,549336375,219439517,6033392,482662321,393430711,195282226,989831101,695624602,917313553,471599695,202970668,263245314,801605689,639966446,364873895,497270506,538232026,921443447,254718780,380377682,772101951,884550940,307572677,765208477,201402999,407684015,948999635,226411351,932606953,648400853,982129316,222499192,210099381,364489884,900356301,452929681,389876919,923251661,107493176,324172060,905857720,397330109,485633214,900642399,409637722,706294847,901349710,219792632,733713110,896389937,380055091,346432996,2900598,665359562,182870654,884645068,180309339,412984412,417971731,218080016,206214849,989151633,389988583,307822805,949513229,847471937,310485194,203325095,933631970,960639971,825841,257947806,209160288,93703780,976064009,118099183,933477617,920360106,198140931,508402380,477192883,346906897,32901559,24745109,424291402,642895641,724699504,489929126,572714389,553155585,51471056,230186211,551214361,512625063,893741382,591383312,876098423,724218194,837454813,910303674,698177129,907549281,745896480,56590906,919054052,382574327,953433471,317491287,873121036,988099654,407996720,578711531,911380958,493635996,946126663,628635301,490947025,799969980,119130188,630742748,476377099,982254236,464663807,783800078,532504483,255915525,575736317,164628155,964909320,145160514,980286745,914969915,130494920,318018230,194112914,328272362,722905585,66189186,333442704,540321143,948437851,685981525,665760459,850646742,517313654,26917299,779029483,750349276,714646565,335620812,503229368,676623908,942644300,228174114,497200378,628473356,700252926,99863904,594636504,892377425,360787044,272132969,970430285,301786416,273525902,243009112,746873955,162342987,738300940,561546774,694317928,167849789,665356080,520787790,130528813,764534024,589478339,860127167,288345555,158442975,105590919,744346756,232010915,319424559,629445645,125845797,487740032,913151746,180640874,840761518,547055540,63828132,617497665,242075918,756064194,835244228,225501280,129371095,548109180,956528846,841980229,435371903,815828731,480854180,658370764,652865158,595983037,868241807,853308693,48832790,632227879,599471885,494928759,815315169,641409314,409823437,580383232,525343086,53716942,493854775,838150971,26723274,939798434,137223061,9130041,592783194,499757497,634820891,398780345,171313778,637161904,369630852,171435718,796737315,337902573,949690114,428938870,99794494,925952523,68174202,921189933,536187754,44060737,586227801,835750532,575754193,772554048,566393559,349074250,501155443,127888754,390368534,730923915,134748123,859149581,943729224,304943977,819009800,983519490,963694633,174030119,923510078,46048057,739292236,620730169,797254167,632847731,252150411,900145962,220639575,578658033,840881849,782899631,734895174,186258881,637780020,971415934,784538881,633215016,752934432,358301171,568850979,998569628,338862185,721331635,893610883,504049888,961731740,599516631,568769593,18809138,805575100,150198471,419944908,382100277,183564857,583359638,371086928,660731997,194457456,210273778,851732258,626893306,517188818,265388111,158969998,981460088,509414305,641252794,475586105,930843297,134848627,189739967,285054793,580121460,112423009,255576202,353406990,949479111,936867372,938705839,661089344,849012539,225077910,712483745,860862632,176740658,16703993,94201589,925362702,25988391,900942801,729373788,662351713,839870713,517361009,985592674,713132298,420117608,776964229,73612702,364645649,772456486,72776687,68430365,643800116,625393374,254952201,322872110,208675693,160726696,748101590,529802978,122680922,193621785,306251584,597340808,853460063,460070610,268058874,230520791,439429962,791704785,161885433,327961303,59620609,721221242,135167755,837274064,793212486,941516921,887787324,726752716,365413262,416396355,469258717,16568815,930888128,852024380,23844896,119903427,577802854,332968389,822815031,887874542,511509715,820433615,402311749,786677513,988162578,264273539,162638064,500681508,742195676,529481251,689905243,645791338,622353223,769900939,670866101,809111338,847499779,466134162,49123567,315143948,264366110,473416062,643159978,207658212,33692064,368925784,970037940,839055274,90335809,136698992,263139111,900601161,292446747,247213947,861527005,80269766,558455357,832755519,164000193,32791064,169551471,667386341,228226127,531886442,657842775,129444321,114832602,328379742,588229077,372648326,653765232,413225456,983910236,687322016,126628054,715076270,781272775,271867900,400776119,701035816,573914407,128900257,424817999,813632309,733050871,777486273,315627205,136958818,996506297,179137443,546896512,932396606,52097784,874667033,315519546,999324666,483651745,635776633,290003968,716584575,938622264,238366900,982480762,887015442,317993731,945374660,536112742,253959398,988529084,16793314,713788675,85871659,70913295,707004992,889511024,869559333,413881274,510236151,942348740,200285660,655050076};
int C[5010][5010];
void init(void)
{
C[0][0] = 1;
for(ll i = 1 ; i <= 2000 ; ++i)
{
C[i][0] = C[i][i] = 1;
for(ll j = 1 ; j < i ; ++j)
{
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
if(C[i][j] > ss)
C[i][j] -= ss;
}
}
}
int main(void)
{
fastio
//cin >> n >> m;
n = readInt();
m = readInt();
init();
int siz = (n << 1);
ans = fac[siz];
for(int i = siz ; i >= 1 ; --i)
{
int gap = i % m;
if(gap == 0)
gap = m;
cou[gap]++;
}
for(int i = m ; i >= 0 ; --i)
dp[i] = 1;
for(int i = 1 ; i <= n ; ++i)
{
for(int j = 1 ; j <= m ; ++j)
{
int X = cou[j];
for(int k = 1 ; (k << 1) <= X && k <= i ; ++k)
{
int num = i * (m + 1) + j;
dp[num] = (dp[i * (m + 1) + j] + (ll)dp[(i - k) * (m + 1) + j - 1] * fac[X] % ss * inv[X - (k << 1)] % ss * C[i][k]% ss);
while(abs(dp[num]) > ss)
{
if(dp[num] < 0)
dp[num] += ss;
else
dp[num] -= ss;
}
}
}
for(int j = 1 ; j <= m ; ++j)
{
int num = i * (m + 1) + j;
dp[num] = (dp[num] + dp[num - 1]);
while(abs(dp[num]) > ss)
{
if(dp[num] < 0)
dp[num] += ss;
else
dp[num] -= ss;
}
}
}
for(int i = n ; i >= 1 ; --i)
{
int num = i * (m + 1) + m;
int gap = (ll)dp[num] * C[n][i] % ss * fac[(n - i) << 1] % ss;
if(i & 1)
ans = (ans - gap);
else
ans = (ans + gap);
while(abs(ans) > ss)
{
if(ans < 0)
ans += ss;
else
ans -= ss;
}
}
ans = (ans + ss) % ss;
writeInt(ans);
Flusher();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 2 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 3 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 4 |
Correct |
5 ms |
45620 KB |
Output is correct |
| 5 |
Correct |
5 ms |
45656 KB |
Output is correct |
| 6 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 7 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 8 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 9 |
Correct |
6 ms |
45404 KB |
Output is correct |
| 10 |
Correct |
5 ms |
45404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 2 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 3 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 4 |
Correct |
5 ms |
45620 KB |
Output is correct |
| 5 |
Correct |
5 ms |
45656 KB |
Output is correct |
| 6 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 7 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 8 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 9 |
Correct |
6 ms |
45404 KB |
Output is correct |
| 10 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 11 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 12 |
Correct |
5 ms |
45632 KB |
Output is correct |
| 13 |
Correct |
5 ms |
45640 KB |
Output is correct |
| 14 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 15 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 16 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 17 |
Correct |
5 ms |
45576 KB |
Output is correct |
| 18 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 19 |
Correct |
5 ms |
45404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 2 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 3 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 4 |
Correct |
5 ms |
45620 KB |
Output is correct |
| 5 |
Correct |
5 ms |
45656 KB |
Output is correct |
| 6 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 7 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 8 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 9 |
Correct |
6 ms |
45404 KB |
Output is correct |
| 10 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 11 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 12 |
Correct |
5 ms |
45632 KB |
Output is correct |
| 13 |
Correct |
5 ms |
45640 KB |
Output is correct |
| 14 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 15 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 16 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 17 |
Correct |
5 ms |
45576 KB |
Output is correct |
| 18 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 19 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 20 |
Correct |
6 ms |
45404 KB |
Output is correct |
| 21 |
Correct |
6 ms |
45588 KB |
Output is correct |
| 22 |
Correct |
7 ms |
45400 KB |
Output is correct |
| 23 |
Correct |
6 ms |
45404 KB |
Output is correct |
| 24 |
Correct |
7 ms |
45404 KB |
Output is correct |
| 25 |
Correct |
6 ms |
45624 KB |
Output is correct |
| 26 |
Correct |
7 ms |
45404 KB |
Output is correct |
| 27 |
Correct |
7 ms |
45404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 2 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 3 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 4 |
Correct |
5 ms |
45620 KB |
Output is correct |
| 5 |
Correct |
5 ms |
45656 KB |
Output is correct |
| 6 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 7 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 8 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 9 |
Correct |
6 ms |
45404 KB |
Output is correct |
| 10 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 11 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 12 |
Correct |
5 ms |
45632 KB |
Output is correct |
| 13 |
Correct |
5 ms |
45640 KB |
Output is correct |
| 14 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 15 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 16 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 17 |
Correct |
5 ms |
45576 KB |
Output is correct |
| 18 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 19 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 20 |
Correct |
6 ms |
45404 KB |
Output is correct |
| 21 |
Correct |
6 ms |
45588 KB |
Output is correct |
| 22 |
Correct |
7 ms |
45400 KB |
Output is correct |
| 23 |
Correct |
6 ms |
45404 KB |
Output is correct |
| 24 |
Correct |
7 ms |
45404 KB |
Output is correct |
| 25 |
Correct |
6 ms |
45624 KB |
Output is correct |
| 26 |
Correct |
7 ms |
45404 KB |
Output is correct |
| 27 |
Correct |
7 ms |
45404 KB |
Output is correct |
| 28 |
Correct |
13 ms |
45404 KB |
Output is correct |
| 29 |
Correct |
13 ms |
45916 KB |
Output is correct |
| 30 |
Correct |
12 ms |
46692 KB |
Output is correct |
| 31 |
Correct |
14 ms |
45404 KB |
Output is correct |
| 32 |
Correct |
14 ms |
46172 KB |
Output is correct |
| 33 |
Correct |
14 ms |
47016 KB |
Output is correct |
| 34 |
Correct |
21 ms |
48236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 2 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 3 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 4 |
Correct |
5 ms |
45620 KB |
Output is correct |
| 5 |
Correct |
5 ms |
45656 KB |
Output is correct |
| 6 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 7 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 8 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 9 |
Correct |
6 ms |
45404 KB |
Output is correct |
| 10 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 11 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 12 |
Correct |
5 ms |
45632 KB |
Output is correct |
| 13 |
Correct |
5 ms |
45640 KB |
Output is correct |
| 14 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 15 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 16 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 17 |
Correct |
5 ms |
45576 KB |
Output is correct |
| 18 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 19 |
Correct |
5 ms |
45404 KB |
Output is correct |
| 20 |
Correct |
6 ms |
45404 KB |
Output is correct |
| 21 |
Correct |
6 ms |
45588 KB |
Output is correct |
| 22 |
Correct |
7 ms |
45400 KB |
Output is correct |
| 23 |
Correct |
6 ms |
45404 KB |
Output is correct |
| 24 |
Correct |
7 ms |
45404 KB |
Output is correct |
| 25 |
Correct |
6 ms |
45624 KB |
Output is correct |
| 26 |
Correct |
7 ms |
45404 KB |
Output is correct |
| 27 |
Correct |
7 ms |
45404 KB |
Output is correct |
| 28 |
Correct |
13 ms |
45404 KB |
Output is correct |
| 29 |
Correct |
13 ms |
45916 KB |
Output is correct |
| 30 |
Correct |
12 ms |
46692 KB |
Output is correct |
| 31 |
Correct |
14 ms |
45404 KB |
Output is correct |
| 32 |
Correct |
14 ms |
46172 KB |
Output is correct |
| 33 |
Correct |
14 ms |
47016 KB |
Output is correct |
| 34 |
Correct |
21 ms |
48236 KB |
Output is correct |
| 35 |
Correct |
59 ms |
45404 KB |
Output is correct |
| 36 |
Correct |
65 ms |
56916 KB |
Output is correct |
| 37 |
Correct |
58 ms |
45620 KB |
Output is correct |
| 38 |
Correct |
59 ms |
50512 KB |
Output is correct |
| 39 |
Correct |
51 ms |
54352 KB |
Output is correct |
| 40 |
Correct |
82 ms |
60756 KB |
Output is correct |
