This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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] = {0, };
int C[5010][5010];
void init(void)
{
C[0][0] = 1;
for(ll i = 1 ; i <= 4000 ; ++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] * C[X][k << 1] % ss * fac[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 |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
