#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 14;
char cn[cm], * ci = cn, ct;
inline int getint() {
	int A = 0;
	while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

const int mod = 1e9 + 7;
int A[1001], B[1001];
int fac[2500] = { 1,390998217,848793393,109119920,19055157,100292593,838031598,82350513,406550952,493805103,593395757,95830437,764072301,981977466,454991628,969117405,380720579,784044468,926581590,234400402,532467852,242416192,856456398,484820571,747441725,531950728,776372982,425234994,830834436,433393698,577889084,705155009,342781022,516225514,493498994,927344283,854869794,643851306,772036106,473281893,317614965,76366192,264056892,14755475,412197753,810673643,827016778,285454093,224496577,988628897,368774859,516927020,425401251,372729338,636443576,766392363,343383160,330910979,849664749,109741460,965651681,571604742,763368909,375079861,685687553,77721395,415201993,165312868,687272398,579283662,806918317,792006720,320822040,451541316,164658610,548996970,414973328,856256948,540085415,63875222,200360748,163813057,279161231,19981188,455285322,981996609,360664468,996704108,834011569,581004588,67347184,957769185,482209772,942501868,442596118,139475086,658072182,859866616,737050414,713522909,422550956,372816409,154582382,626613065,619362396,320014428,690587073,434274056,722446075,362569914,246899301,284046782,313235165,715520777,342675806,78896243,138938342,4904868,158370004,65348113,473058849,727422266,665131,321460624,345366515,737935835,695118839,317001033,110949981,17300606,445302346,270947557,231821182,16217817,926110356,703924556,354410308,397207557,607917045,967621908,307636910,81781900,697481470,997427770,562494885,387514542,212623047,20108421,73700185,841644761,309944332,557761881,189099472,253818913,701754988,364031813,788127248,865141725,726882647,386941508,616292959,346845309,101653426,953923388,749373796,727093888,223530088,793982951,258598151,245917194,972353660,399728595,334038704,303642327,74464463,296716438,274952061,343362475,495959165,197810318,604632373,590107402,382285276,271463541,554131598,687268896,809996715,129158745,269610437,851059476,388289544,568876602,666808812,937092326,842684285,135821388,167897791,234934482,517708259,47582098,65533322,154738290,717265250,472703372,355862327,645452094,857639774,820059873,775373984,8278520,808037302,957942297,669701582,748856536,161917011,314136411,866978149,484001044,324217435,751439779,19122513,813367160,99527175,802260377,811802215,851076783,552700981,766255808,394225159,982506554,591254491,619489363,784373520,86224435,401192710,894437844,37693984,449868160,168356987,676617343,318526308,491981417,187019771,486874504,367421824,300098050,31995309,224418847,671417846,127550549,457992974,15839498,530581311,59466245,664980914,133097627,783112758,877308397,344558162,601681586,356519615,888534544,754297579,516985593,828524406,139468211,942938062,75266003,25647683,79719269,268147727,897351995,583865802,263295338,131824084,559938709,735217324,376580544,294519817,934868205,259920986,693276974,633022951,77026581,753807865,848001963,698272928,212188347,488255637,602924257,126142258,829409492,69063083,341281076,544292770,426153882,504184872,313026009,623910550,526552415,118586228,277781927,412570835,653979014,641754696,170487827,349659653,846068884,170135174,841147847,584611895,475063670,837398790,810946626,872619945,849250992,175240077,27403736,682438185,474310496,411557429,443227197,115957705,815233294,754748691,177829816,495693949,47205438,531118527,357792113,350302884,296595730,3274189,204477956,433365363,430900437,547541020,5115349,336219981,649982328,902349808,205459599,239920785,718392117,35831479,981466142,106878802,187551272,467431845,1019817,830760447,861034044,139925365,648860855,864481378,289509856,602596414,191723709,622540065,541421526,175583016,213660817,835578492,435786777,829030184,973411258,908592101,853467653,659816341,88908366,82067555,732861256,607728934,551094266,852919824,240586351,847820063,366465454,760045418,77894517,962394741,579172254,58041033,640598259,740355273,870741191,91191794,314602668,926287373,381771477,996128105,676436428,16038420,445167189,21240951,770455357,11152992,718101467,140828336,193686441,611862881,525156436,295066216,585109252,349961266,725655669,665131400,451188034,400304903,266485419,610766863,344041962,445291878,404926961,807715039,59996720,803394057,844184041,803094044,574135690,763184678,625872226,958346799,440618058,616313658,267145356,64190024,195184459,36642064,166316690,101278761,586337165,77325413,379482747,689354918,328110256,63361341,221665715,26314956,920512580,135914446,522197666,710705969,15076428,145622217,699703979,467646369,634072288,800750169,770269500,334356152,832409515,342024694,951553609,588962133,201761485,840414737,838779094,950000780,212809520,105501058,596352947,503723361,184825262,450428122,981027538,361798085,908636534,367924415,799246183,258397918,151632629,294157205,191094180,892336948,706226766,260808786,328279132,735863058,484961716,475800730,95142235,233475558,489746958,771503873,312608844,372404311,343210044,660918937,395211897,8289646,699243937,685070977,90174632,742634562,358757469,494454809,767794056,311455590,781179867,107146451,721101721,563841292,623123039,375868954,147390880,696968562,178435551,562882088,41802402,757515880,451712709,619011641,948484028,611189232,44598880,484753440,902600274,555326921,400485990,60971813,242960551,378931839,250875254,130615185,469491375,649980226,738179817,23212978,227268571,581534598,167459392,217010142,623526481,868182029,553154844,274428135,113960229,488698644,244880531,265358995,27007150,523055772,543836597,474933481,914563847,180820304,103793289,572347906,314385364,469619345,631158058,377372966,821127151,236770764,884720651,228443630,260438987,866276491,958784814,752000194,136223067,557700589,45818297,520734852,631467899,969505217,295855795,889986153,115285528,66680976,825894025,421309670,621910915,981200569,630906046,882467241,789937735,769511386,91520412,666124073,91042008,254564838,304424279,950993007,790014252,232951930,468969632,277200838,930429558,75003243,69500799,402785820,512965505,880530937,687694799,176570314,304826278,479913223,219360210,658967159,364595909,717264695,72154836,387648711,412185586,569052040,39916768,585414925,23438872,247050552,247126818,663721356,193868440,49986275,161463264,522580419,126017153,236719774,109441182,409855571,3055887,67228684,398305412,777800290,50180518,800047846,670890199,581943809,274684255,245357084,290299242,579889759,390477570,86512102,734897297,243642112,423491033,235149611,715153625,571220378,907205355,273594103,202250544,464411454,512704957,355945607,900201978,509654534,198178428,287209856,94359680,397885013,475180466,175589823,737403289,395852258,341870338,197427287,992837468,233151863,832372093,707349992,220489524,281513216,234240119,314710530,438392433,526152085,421671082,229679385,557757619,529706969,281335747,657448446,372045574,692918815,302917566,51639751,939157644,373583894,389984709,148310661,978996936,171506311,267330203,926240206,382337844,54020634,498714709,933690870,75318117,873342914,560848216,236242168,77938347,18078741,77721371,656220324,740172789,702584502,845067851,414579750,105117076,29804250,572702990,462311640,46512529,938683804,758468631,781966098,210571668,214905477,697084400,291086761,206775296,986586487,216676169,386251860,498824845,229585834,654025026,487484138,2696780,912378548,210306242,941833733,509246959,652195871,249520221,690126643,982461944,764886490,126481252,817857386,342229409,525882488,545548901,207496413,586369638,368788183,364419766,363417919,705144824,838676721,607847441,796014845,375930404,958338391,696205534,373281933,756518546,853610384,818228182,237557408,719843924,88973905,316456771,435017843,702752732,19434639,67995595,346658793,118943600,161886693,395942940,258892135,321424314,690643111,505950458,684953395,529856775,169060021,30498292,445230158,330131954,594770157,160244401,421898288,647230289,618257200,955631095,509296670,933668087,761727629,777843045,192426132,519186361,664427304,282570703,309626261,984594092,565068825,253608891,66509695,636217986,842505665,274551924,994816177,391329717,179035946,58215732,891291718,895520591,634297519,621703982,684145600,535555245,859583277,31638851,857767425,678511140,502138156,53984090,891359664,213633073,656697065,85984191,805387480,270320004,487537111,85495157,887402749,434201884,196789010,642845435,459630359,847070754,955732921,836484398,896653343,772931361,716580779,805176113,92709603,205250346,49088956,895766147,886626868,433743234,780942965,233469072,316991943,677686652,411086001,215648079,720917589,967540846,976172039,564006684,293008185,66423960,81406801,455586172,950064027,202569677,605330319,441088968,528936092,993008170,927957860,245809025,160033980,77998081,589588442,794249305,820449545,249865038,223815246,935337485,116954611,243770013,498464483,745912406,501941641,889591949,612929411,585900206,926222736,755381941,907890404,115946837,123201113,922031925,345373733,467772374,219939951,175155468,617504528,200193223,943477841,314854180,343043980,716510093,453851404,708568481,768061747,89284843,11191543,827464903,832275593,339264927,581911034,921021417,724780630,412586966,30689486,670927901,810493130,316423211,990832219,678158315,332067649,667853849,250697844,460267027,874747659,678769337,669679560,627794163,171979335,949841850,772674656,803879624,181385243,783222990,364738010,630771759,219053160,808139670,288986879,181682828,980144145,292811119,534858152,805877048,999870557,586408319,110054635,283258478,855554180,977124786,448722447,243189942,761022298,65150285,696923331,381693990,851943937,231329702,698245208,914575555,13188899,478733153,188071880,203416423,688535139,728752389,277775900,956301911,96765717,930076279,496110969,474530318,123145002,477301732,601870745,440614490,376467079,737998293,79323369,36290916,303696070,174369185,686028400,968856847,103871672,810726031,907026494,523838521,976492434,582081176,101830818,97022641,892829306,808037739,603627045,643588156,565982017,865819616,614351373,754349762,54556096,177753777,115918921,182548361,919832562,218447080,254652799,392207470,559805077,429303236,761309611,600706205,440970837,978840326,47676844,174063397,366709705,849708078,959000834,852693282,46582084,683256978,516012751,274125098,46807199,164059717,461779868,990422821,995577108,761179574,362645955,694092932,453338976,612250579,230816690,593540200,22254825,693116425,547647475,250206711,939015170,347275552,759741240,109124789,75327366,887539869,154160119,701408414,456925520,249003067,155106502,904817753,160283240,967029794,825736828,258427060,705303743,616065239,425371772,35453237,323262367,123997463,329195803,620903151,421654565,673309181,697252159,797735032,338506329,627009235,205482440,554042237,150130345,33156533,661547351,128115230,174118771,725126987,621098959,762688929,767931144,502898414,140206255,408721018,455682907,542035318,622178318,445410513,511662841,595663933,255462887,597591632,901139201,788458324,169034365,107073180,41058006,890736286,287745397,234880840,677214847,257623240,867494201,427103363,821553881,931612113,355629653,129077925,227278675,446361395,79525781,871697226,836840727,613534600,270306414,388404539,785471485,686337593,181975257,69391465,14537313,955619333,830633573,849029423,749338566,805113498,726336321,814654886,668500633,487616021,570999336,215722210,72310043,231684727,79000193,632415887,590513783,415882287,23645260,783562440,899492995,265091163,684728123,515317957,807629243,589112108,689561161,484928106,146879070,646266295,888738601,616579772,557309459,146221861,24045233,46400796,80345731,993459215,711739673,730972293,120517837,633552264,445191191,329569053,338910863,708870287,978524736,221913829,665423642,76331782,386192908,713354548,914506135,32793033,439003608,299489823,47776857,274877726,381619272,156400406,857640210,236098686,996616768,93615261,498875595,319268272,789462827,862163592,629353676,170614582,111988192,217427509,299100051,232170568,490173008,267685335,524604026,12626545,580983135,439175258,636559642,453498448,453116720,294111525,338031327,789769290,967590562,79937574,795156156,591982007,139164808,587146330,112548438,546421276,864757633,589120629,532361418,688592490,414060514,220929521,175860315,799790778,88920549,149514118,896851833,979117700,940452766,870738298,386531804,420664447,752023733,448667089,86675963,111810641,390013885,774577342,188064092,288714920,419209336,546406552,267801022,421973055,15403328,124927837,73427319,77826191,365049939,304196168,683580606,910340534,479792388,609468425,295982682,778924854,692251029,43268122,550809798,238597952,154425679,584990029,295523500,33654838,1279495,293094634,524335441,892801777,726078705,924670227,112582078,736354406,865792136,724329768,738537564,6016511,988721995,606681280,406143534,696845446,607689609,181632470,338578698,9947524,900706685,950741508,777958968,854139954,63517233,240851303,804138346,10152810,795103750,583038318,535156156,504444082,229911589,329276992,27578941,322059407,940358287,29217954,242741494,195051709,355243297,964032960,305167272,656325947,375079910,59399779,384634755,861636290,474793317,162209530,190515710,44821033,407184899,393537578,671747665,711449950,622395046,625720545,72090046,880504584,922473655,593532124,500798972,316853946,5995000,102632144,244072502,133179641,913009156,818697691,964628387,797824545,465423828,700264943,321575082,190567247,709819079,660116030,391863372,854801260,497111056,321792583,120546138,318944572,457275062,865465330,226144630,376658624,892021903,52955796,640242474,934717533,74960359,663068007,735685101,344314765,581839401,119470968,480713341,748882037,115019254,726388121,422048730,443381780,269476532,399739415,935299955,330125170,119701424,327086469,397675186,924880898,681579869,697493884,497902519,997697972,229919917,568821716,58483458,964838853,505857071,899281002,189778137,703419020,704731344,28711538,31241308,128197784,754678722,284203209,301406742,805616393,537321469,288902036,640028773,464499476,95654799,528508337,760540378,3547499,11742391,610035146,847443867,325661038,123493238,77062914,343434222,669326428,489749518,833836851,823261728,134707066,355006115,65211452,403295891,695108036,171237061,772426986,617637145,75478030,721547453,262405894,561974155,967897209,100907940,411462167,553872179,517850114,398722094,787384867,419174600,924042332,850921651,540970454,695496980,833559013,879176764,778596281,664820333,706617828,608171948,469386997,562881667,900045698,950870784,301442901,943765912,576534609,88911187,757587626,430534748,797540981,207997833,621686221,669962383,9032507,973241307,517655534,663136865,456077523,99011629,627333027,57446778,527583422,329300135,322092040,828208151,360652038,274827000,897244354,901225166,222104605,587776951,325342308,328752881,550109381,739140505,748277975,137447785,421969752,405577969,253333132,929580206,522461776,420670988,810991148,145298115,158592736,104143378,8945449,202379581,793332112,147797727,421471389,238016889,660497568,276302316,980091567,158352400,358063076,328047294,866898497,118681106,868977315,587400837,280361807,679209364,784685141,271540932,103549414,822808209,998767109,273642320,898211572,720336883,759795052,931423638,432125874,477858794,434954901,491705952,449656911,255327352,405532057,926353547,829356793,887485139,701809745,929644984,85499124,493968875,663967499,384048817,862626061,655029939,490440420,247778530,263756,235494202,23957434,229327077,833476199,486456303,299133969,352836970,248567120,227641050,152805138,560832220,87816610,652731597,158177667,746129267,196082135,213908504,671493391,840761205,138555135,876698721,807533158,670359716,323916364,457185428,787453815,108650303,284483679,833673413,196149299,360207241,739772261,210937282,815002850,40514408,461280530,402045365,60929370,758133380,721088538,631571061,50385816,340501563,567656070,956262666,29877233,696177570,535589875,913030124,46844570,356989580,208962365,85105977,501255706,475764038,774652714,26668102,320200977,988378213,50453440,490960572,929427791,119069894,329175197,890540426,569750056,878473356,419169430,152546903,862444918,133687344,593225625,98726614,665282791,83454702,416685431,348231923,892213110,48393618,459064867,258278332,416286356,837338106,914607739,484659919,280797778,735255225,257507544,118339569,609314978,952990355,592594641,503510012,44613330,728661937,37643053,100550349,542332506,314934847,177905883,323135671,924403010,837421939,701953715,381488958,872549901,17839368,497246476,175666781,108417945,298014653,611369983,35724995,719749095,341758172,39541813,702153942,978808764,82447511,649497487,796368669,955168395,752811066,14669256,996232535,509979408,763737908,286300580,597698852,388612185,268047887,196227180,924228857,242967280,17276084,820265201,224815800,777102772,544735003,905963065,162333100,96537126,926263315,402958911,185279496,279651363,677606646,608200163,985591894,678680410,199168939,595168855,804656333,904417343,677022448,569612430,134463178,783825361,920050913,770120002,208112226,29867472,837045295,774264645,738618350,196144973,462519354,403666717,571952764,759642921,798637126,85098584,160225309,196156559,40659769,30871301,228241085,147337397,297444905,443688374,515320537,264914724,814397040,622705850,790161240,351688895,823129583,912822786,451361308,621552262,815697957,415960645,429509958,757842436,391921301,758521755,177651146,897430507,500713207,615778119,309325055,539439912,25708551,211374774,977687707,232050691,575214801,754757556,408668259,784524151,827056920,907268594,918424353,835797831,542941410,654401292,426511195,808423510,526226141,568138535,280281560,283261595,864948948,445257455,803257864,594178259,616951878,91756729,322571901,882698033,588260787,174389981,252106239,345435435,443535098,115254343,481401553,665407916,104050332,550486856,752435955,947708446,88537209,184978106,137556017,776387033,561525293,486028426,531377426,502503294,694478853,435431256,290290235,229118010,367241764,426310455,385287830,781392553,513537151,851494857,717147098,856747496,689421986,567520164,176277644,269113817,825972896,348944291,402043945,613347150,550968022,741333709,936626789,908318314,551392840,885874014,192245148,870399650,211604803,17843182,830989461,812633775,541789622,165819171,913975922,280256222,930290860,744691092,71245470,973540448,876361281,680060695,469831257,99111089,498853346,153334381,905187008,352503571,260818411,714830330,140638766,229105912,680889579,906202444,327166868,179265102,239704102,687371172,933757306,799298320,157520349,677060168,500812706,478754513,43415467,750365855,423002570,937509850,19484938,228614,147555435,538945197,486866463,810734940,230083017,638029879,965482276,867828592,259534248,493736617,590449059,644500576,631159052,671365457,861846748,549990890,329459491,581764936,78710457,35811951,386652394,490232136,840221522,419049924,793773703,354127646,17843157,752243797,472930903,376085687,364518764,574485027,492278720,826859777,347182370,296339002,119098876,799367222,994626083,902862144,100998589,65580757,320207961,177821398,466970064,667820991,801128370,874111930,253026585,631251572,56270709,505446724,537208091,578481619,426817689,526794507,478460721,964765062,145274938,916071960,843778447,26817692,636703850,815295234,705962875,536057040,587206557,56265430,581365761,756052852,657858432,844173012,350798610,713158286,911072090,121628330,794244269,497905512,271157897,531330245,359768851,242419422,573047474,756436321,563230487,55001696,804449986,290701418,37638418,667590050,752937621,63572118,280438557,901727617,871278706,851014244,125668263,562836804,874682245,464407883,887019552,377407921,900896878,856814318,822072002,48153550,410502885,964274307,327934694,158324964,219824799,843657866,766189282,483793256,376663425,783013072,198809107,194472733,958450843,29374886,88745840,584458548,699438496,220437571,421308441,989139652,734789276,978396140,266112694,15446230,483878621,977946154,457653265,18992782,995273794,26123260,391775265,618096421,72824104,95938783,399574056,99685146,374014437,504602731,683338756,103725846,329129512,790929684,644158465,709054109,181904331,988661514,442413455,776531520,874776442,549131327,275832951,218230327,220635341,965661216,661379944,579899924,362346957,980895408,774467245,974620716,135040929,469230418,725574561,833123402,656464521,333634442,306869116,63869907,145043583,239106215,831873898,548156856,216733111,724773523,869943197,978543953,584015002,941754362,738451825,638628334,889736594,177292920,201596668,625695144,881460696,739897295,983522462,514584320,78910394,760606426,571624523,212584988,114643102,699640707,781899373,131921597,703402723,424492167,246868253,874938468,955980946,760745217,77740167,258013846,681912561,525049759,548392730,496129791,667447659,271375380,325096079,346902494,478398710,327664409,322751692,834811585,123483506,972816308,106213122,419925040,973023600,875830048,19652299,845828565,972491331,439829157,674585929,646533728,691954361,586270892,176117248,430436164,331478750,669077633,34315460,752356751,147978996,795749974,686547072,878678974,737958185,970805767,728256514,225676445,798725783,218994834,148277249,526699434,861712751,740119375,504200947,381672030,113248522,913230020,585737458,243347527,582161032,533966369,695329192,577772893,220349713,802679692,547099968,393498175,310478375,934197576,693848334,963945752,988910728,686203400,612358978,471094880,27177875,544074133,962731047,314411142,393873172,907294033,450866501,118895792,789250012,223580984,966880832,135734490,906102826,154052717,575576200,820722508,113915110,293996657,354047782,215162201,933338751,271582665,66821022,28629493,606764926,642756565,261580416,848980005,853740091,973932371,362810925,277717121,746742261,757603192,133983695,834663866,785716182,272255709,487823244,147559301,170001461,547569177,171842154,239243283,430841927,18380550,831454428,340483698,974663952,90181574,841160160,619834562,21065762,792502156,368406048,482593224,665923580,340312077,752735533,440785244,7734487,598610737,773251998,834880080,717762182,619397280,273251493,129135378,160231388,758900029,857887831,58125299,256086704,111712470,244650631,821860586,982846496,480878519,164471363,429368661,990386420,963078997,894035123,700161974,804850289,504043541,86396854,747387762,311961491,602116266,388167107,398095552,240449473,117254129,850298410,720850066,994540918,154570586,58291527,574387669,157608575,405036210,884115109,334621988,175801715,831034782,504486463,759877364,445096787,646919091,858971448,710865548,302723091,821892074,988803000,190418212,464986511,55988477,508878556,137009714,730342129,193766278,938512339,243024168,26075202,927382894,40980798,984161744,256587082,537609897,175944650,808328306,238710164,9008510,192384967,848482164,456837173,130782834,476238398,926677424,310035443,292826062,172685955,332528949,775643541,178869710,827644650,465322717,938597091,966914608,393354318,424664052,131887481,872470741,955143866,225513279,987853210,729545154,809364313,677193710,707027751,804041765,596734794,329535587,98065300,18730041,628930220,823100251,42585235,743919223,711198175,866531536,155189947,525120935,377877915,348820947,207510894,733307124,243670553,677841532,337723734,726575638,823753385,37030266,708361782,913407519,936392232,569953070,989475192,160013667,238781658,158992538,902328444,454943900,171582884,194146825,38283857,842822924,799455462,415067285,663884683,21764785,101095322,245576615,182580263,152750269,645879497,253198320,339661992,942177009,667044581,488941276,295074327,980669860,454107938,808756301,668410998,417021955,634315948,760176354,768522507,826347493,919107431,295615711,817430757,85643805,403357445,446186565,229599978,232982279,264614140,733899665,952279144,603874163,669923246,878596254,268277902,56246114,162461926,506908901,278730911,748470991,331152493,252521925,967155639,643362481,861590363,534483282,617141643,680343499,788945099,983346923,982114052,650239508,524064078,75183433,737145308,909937023,710692973,890834055,501543259,503936515,161391410,501886055,71976397,831233334,233469767,81338646,841358493,96749994,281968565,27290725,404874001,40175015,944399986,392406273,700286634,851466858,242867736,714085035,201989123,369252563,719760140,917831995,420200097,729225857,565533554,28129751,484661320,428089657,226721862,943078027,869872561,853996053,510819704,947088120,117821455,171573785,386115435,89507797,545679397,787558119,995894412,706850721,164309044,116923462,392003561,181776892,430520210,920886419,709230826,912527320,589004191,639295138,239902041,330781825,918937009,961612026,721509816,647285830,949574384,879459567,322327807,146465924,651693321,348901683,192686082,700115586,588809139,926882457,262509325,142083228,476444932,167453085,189052536,321225275,256282826,10552542,506761641,430780397,181074508,652840185,762186257,148052123,135634832,121835953,350848772,931126722,123455257,347710523,381308939,198207616,975715880,359753886,587657161,910844113,158824520,574627453,89759712,819148358,381450047,481277898,798276227,506620970,456295034,107674516,994502884,463079088,291258299,408587826 };
int ifac[2500] = { 1,622119051,199218939,929600184,456284567,337096023,567003993,642881367,592221510,642895641,655050076,407246857,34551843,913843010,94585374,851565784,616848512,918083807,202355454,681016452,624583629,626219333,528170199,254370875,570411807,556156297,409818284,599835466,811067448,713595672,868598564,139763013,523399648,984476181,782892647,506994043,800134110,318180034,31886676,10669280,831912970,166033591,35608694,38833518,748289407,9890218,366303825,13538762,57980831,74416922,903472374,527470394,739662649,827196085,894358731,801195154,537732189,844545194,190710440,561126282,75865328,345670415,319054360,917344305,567978863,919438753,379398037,138251483,377706184,999153149,866804585,694721960,623328305,384246491,488197596,837333711,622125369,709407678,362151954,231711619,686286168,713190749,796025228,397459303,4043985,420756629,345689473,604435395,204621886,847361213,63896139,68556066,333465084,562069465,894244996,603574244,247750731,706145937,294097837,761569068,419011586,330242540,556542864,736535481,840557173,877288967,578831505,357756435,605965518,975296261,384825191,720073014,915277022,119755538,225365591,16940097,111147311,539532770,469003016,817087379,54227966,539597054,760955366,706841590,847214311,603445007,964092479,106103043,963525174,832187098,53669264,895862496,165535569,552555690,445507196,979506886,266520334,611836123,213100659,590974570,467053508,895920216,921796921,126582427,250821095,762477190,531639262,427191228,716847690,267016991,99314948,167761636,167942982,608283517,236484900,355484420,333722692,572293673,220201687,944326561,569548862,617603626,264507083,497579980,903116257,448961721,964897909,180321649,763267141,320526728,809203189,558191036,708809823,221546410,590725556,655894738,783302059,447446341,767493559,412774836,609982396,639001318,731418217,454358049,411374593,685418751,967751255,786768505,127374647,765597249,346821273,670354443,198678775,203592612,298052151,386517191,498939522,23608263,366961079,32518890,387684378,79345436,83455329,866517034,292121188,83048006,138050344,495513578,431136399,966281057,205318571,127956397,896598720,12704758,774563859,234019343,400835037,848888929,800890223,878159335,375485118,634245106,356111356,932862898,78127118,11634767,592375582,207599823,356878192,326845880,971367519,122118590,156861055,465855616,304516819,612122200,51218598,124703863,53255426,56111824,266541995,429713831,183456637,597571129,708317236,13277184,930871779,828574056,332649458,510537861,716327852,605421022,398096765,80048724,33055964,55764368,697925308,582436839,734501703,432702474,358432629,598090724,919306685,387182885,417916118,712903772,581080670,847152086,300824252,977956315,526924239,222456945,372150576,51465754,980793782,561301332,605981869,845180348,476055657,65022,197015232,147105468,959398512,642808946,558263212,320786650,475951769,55164255,79406625,29441846,856147872,861266519,109114924,600012016,787782961,652684804,760258661,975799037,952879401,613706974,369790810,556335485,661076222,126514478,271052842,85284418,665023850,138458336,185675804,494174354,104103642,598783041,647921668,24537747,730495057,736418933,823181041,998318229,781313154,528430648,667747431,690629479,150754123,164456902,647507686,804483057,72440909,933396769,507099288,849970307,114672882,877498165,541134923,312718626,814124500,895817522,417581314,180166594,882644289,846514173,493750774,64889215,187243395,252801310,40530200,309233829,338937849,910037540,353632278,168631236,895202895,445788329,747799391,166976058,604829876,978528161,479614585,251602833,213240216,135302536,247242235,227002363,382684641,398882856,54145813,976059580,835766958,498711428,320058923,750430724,433817204,908452442,346490043,40784560,728103097,476104930,308528168,946519132,966560888,451616296,808575778,926400785,835808924,809162300,429883295,259405310,970034997,418915271,390629742,719937862,936847840,340727390,651780978,236292587,921143556,39271850,352606460,833764959,531829287,167520597,876860044,113059434,385111611,212830902,594089034,888945551,831336877,460167094,378546163,27095978,164676499,79011255,748644994,470271458,580000241,739661390,955982229,538488935,62423854,656238893,127297529,547472815,895339232,483856616,870912922,129437134,308566595,171563271,981888609,4180741,606745381,776530011,726190850,502759432,37445688,634285307,704630846,979200295,803750124,807855643,436132046,59500387,700243302,705456828,345019602,955051237,746058829,447359584,149024067,978588484,4227543,108437483,599442017,920702656,557713542,261083216,457355892,538603789,191439841,695613890,780742991,683527151,515924005,778144927,268552064,767631145,569885074,172366391,465602869,145329950,923686671,133402654,92525839,17160214,348963875,52103541,474107348,537433827,533955876,268055324,486469091,717046877,312295643,523178312,116998930,751492567,731032818,141741590,239157773,920582296,774739361,118788935,622471083,494055682,485214454,243004955,975650906,847435096,350255514,730443935,750007460,174526764,464304581,136278021,950188819,72003214,180619435,167214381,205104899,648527881,446649144,708367586,748571396,545248052,621027400,360019290,577689101,952917239,528637163,876762604,609668918,733913656,206061889,497076989,401063187,479562023,324619350,582929468,862111580,750800788,696360229,576192858,163695885,235848907,197788781,998753573,516774776,972542963,408415601,439904460,907372402,36647962,493088295,638763256,230877380,724544074,566405207,99575928,392704539,556922218,448759598,241228130,453500260,236532922,419170053,735047406,701908073,942514558,805621352,456254909,748940324,656607002,10429227,578425169,410338593,741668145,831060,532573219,620987312,458946637,620072407,514830683,19515021,125114097,793960708,565483637,974328774,404334766,91012537,612779643,388128729,294430338,585804588,759367214,651420067,911740248,369293131,950424722,185792019,456817811,514360176,974339827,831315212,399397126,571591739,816416820,334743888,391083343,300893891,382244882,136553671,333617783,283394582,899993584,258997672,486804525,252073849,690673383,997799443,316614940,987157781,632445371,531247139,752963288,908118925,613871956,128544159,654613738,476292588,656943686,696656013,542744549,88323803,440097164,486391757,625225017,487566997,298610729,361470120,168965463,681243335,133936186,500672596,522429671,516527541,854505654,902982989,533220007,456654435,578265418,168947470,745428384,799333144,461406688,774405998,269962816,36413606,959173990,68624829,267711970,225012701,939022871,657345397,848366157,336989977,11809169,630556976,408182391,270672176,851476696,831386084,873135521,585100514,692471766,637578572,213395466,925329124,148082354,33479668,196386760,454008172,514137728,282673000,350748825,621606166,857010048,15890804,797947910,254867594,116626454,801315565,417129114,879098711,475465615,701251051,611260188,872463572,42748761,275422223,807611413,742231336,211704378,457410375,528511741,363601885,936348323,979852199,507955531,321691680,810788539,208542468,241187112,754202561,332640505,646387919,73938600,451450754,109235020,843370591,643611189,97842323,217118275,628002817,515650701,477242395,755498578,449112764,937879031,185264603,726996406,494889331,171958973,884245846,271500458,591663754,426123841,669144860,522129152,411589378,427069034,247997900,992158377,95498755,902406072,550355766,838682803,485578175,165286757,5211160,183835473,603143926,42274362,432182278,501387856,905715335,82257815,105716744,286972654,248030491,727298454,238296587,396208464,947333029,92750310,536136149,505871825,573672723,991585439,601225736,420500386,343934253,572888836,937992954,793021715,282660486,976643553,367470598,221738731,734144089,15665022,212396988,635010960,208940192,666308695,555524841,821670649,818066698,633317664,908506203,582682872,218456102,286957478,15707028,215755297,584809608,135878412,612899218,712019965,284527239,709945289,466425792,543110426,570933212,847391693,408576557,55796925,609457511,912927038,987635211,554020380,492134946,696938025,265790295,250192432,403995939,933585333,661583821,494920,111740767,223991290,108618088,805184541,292633245,457017932,236865224,414466175,828466419,35414301,55812312,329297456,63250205,127682859,214806307,124417280,23996701,355552441,389415966,24158779,805880090,41886344,586729180,704796831,857663280,566609924,431715971,887993720,369116775,750409354,514586576,750441030,777200690,376091175,650878210,866730716,691766417,96213749,716999766,793653791,685937765,859109486,697867974,55994509,954519384,647498746,822429905,390842878,889280054,548620211,197666507,59235220,807399985,872674258,568787439,453456185,60463338,242494664,567711754,552392776,193964862,741564663,173171985,561725617,478517874,573971266,740988990,721498041,245950017,443643771,125309705,465713664,973800643,232046116,723572340,802850549,42490154,450956953,125148251,113894915,29291434,912101966,622434732,974365845,304087067,678384919,603307110,805985378,573109516,343211750,814932406,651345478,603649399,578077534,513413896,407234837,561462604,529350451,410241380,704159266,596056885,534801403,736073636,332045569,709256377,436001298,792371419,934232306,856476972,613696458,943343084,14365371,981597982,920180726,376232093,773118774,652216635,900770880,483749742,356438362,934863384,970629189,578832488,820779155,324640101,182176437,491666708,92802496,668543844,196047788,283628965,486859560,447840182,492618807,281791452,997145847,60053409,25584800,256175185,391910960,215846829,886186247,44623569,555071320,721318062,824511750,272924253,434416938,273921191,297543050,215132261,263780259,111916559,980033437,290195422,881707988,233403782,786900475,385982390,233142214,23332630,403090591,629664574,340443903,714947179,591231230,548135995,775782007,590470378,972865072,219909687,496447486,922692834,60954868,36631946,118980116,543791940,180943201,69371208,148916845,674161767,430613348,267470865,753275289,827240595,12492466,538178262,259169965,441809119,351927879,128360204,745545818,632470676,474269573,705025200,870459796,527667805,489404735,229404385,189926675,291463769,682631798,656040774,220534692,175766225,480870580,659697505,294442589,299297467,413863645,378953251,922546671,985547269,403287652,881156345,209691353,34487732,83214398,626961066,618971149,716905530,138193966,50096793,170597108,394441444,389890118,179877583,162034248,370885784,654456244,860085175,936370412,119336336,110640642,922810341,626528128,288738469,303664616,12987563,553612915,126684386,980375233,730485217,578910556,287075896,265700188,97147995,895630180,362520451,786679779,341331152,374712273,214053438,410527540,80090820,871982712,23719935,656358195,266093984,413405630,417007403,44588236,996659396,864539010,195257790,588153235,716196276,519683102,834082277,572158302,217848096,742712973,445318906,776779455,542861672,968609676,969527516,882870783,971466797,92679017,471955826,671841036,193911562,260088892,320193728,997813469,150959356,818459342,591217294,94283369,770678951,474351307,973198799,71756793,661625434,80848404,116581681,769427283,541444074,924546483,289968163,586122532,602578524,551806440,856720089,378751461,250193892,957872747,133109353,632392809,871132594,460182087,93980700,630939042,765356736,106881193,789102800,530846381,344531224,786859631,501835550,156746321,993552922,668892374,941309007,104673324,371580803,926906920,267857809,871115989,490199239,350971272,364278909,804035124,51694197,434846479,366483488,971466893,144840103,245487105,640231394,240532188,455239679,68060048,868301285,150887507,106951652,864289776,627573860,929963677,543302391,233952659,781189669,935018306,370924797,547602340,974375796,436105166,47814006,215964552,606256209,7189273,653504739,943178805,814033500,72819978,546997127,910456027,639238324,654204319,506516729,167036506,409754465,179387851,507492731,202892617,112263656,52769932,587609106,34889405,950505234,755620169,6856218,682586338,375752839,266274944,81498068,396129097,16719557,491724336,172210849,542701700,759740316,851499555,154145358,797889157,956388393,398261371,62612736,483212293,905690439,467179564,627090220,83291210,697536581,571510646,450623548,580021678,954392384,547445073,576594258,748819588,989155810,734266935,54729200,206867488,569712682,889547451,130202050,223177285,854196101,781151797,132243623,697183550,192880210,255745874,768819380,881947518,579148427,392212465,376819578,517483738,713006405,225912360,960816586,615368113,92367746,209170568,866280891,116426154,973300135,215669820,329292354,555751102,393134075,864202086,508702265,16120169,757061369,601935997,460014358,188069089,636603008,865290825,268831172,264977510,827142893,646488476,971082765,426102844,998700331,797919645,908444638,322885646,130367544,865988065,599387675,776819697,295199562,202214435,801300544,436486722,556217129,273253121,816860833,340956092,307956682,541493364,627683431,723389731,406070526,72512759,931741462,654606655,356981298,926194465,885464995,251318688,349993081,419232176,916262429,795527696,390503617,692393192,448090969,240071143,993848530,902887162,337616376,771453315,826299271,189897628,927975823,155548309,124471568,286835825,935253493,263621273,957978325,973710623,534254716,324080078,611936850,485504248,421739227,496009194,848921910,922631839,310001451,327387041,328666609,932899415,69237435,775271933,615943719,255815157,328098038,426078770,885545315,771089187,474228552,971672537,890691848,139285406,812882060,89966149,495874454,606367266,285036337,457436943,951035114,494517141,446787927,617945688,730229017,380262367,112536907,789190739,81324323,954877397,479903155,550700382,74927591,978021092,631018003,396957891,727063144,392102244,878331957,633703151,473443788,756117093,723003963,327186092,979123967,671645850,111679523,656935436,567925186,280355681,338522367,593074224,847334727,964776816,952053099,510231058,397405735,392812151,576837106,532435438,722671870,544170101,617276551,911071676,331802713,940612252,13196631,623811638,38021564,75869841,946516309,524316032,51957586,197095851,194026616,691366742,516357408,957722514,635960816,329013394,315820909,290625848,296220433,282212611,905594920,232621693,573656775,363327074,986000977,291695729,753588048,64654370,713174963,49654791,455156584,606344797,192258924,90755056,888036892,884642085,543117498,534578300,112592145,104466856,759652940,835740523,191903744,724965160,528618096,429782655,790235707,614491775,913260956,206209518,688542910,342306054,24557500,970773703,231501125,660513156,246222593,828195323,14535198,863180866,644449242,988941672,338566657,998405884,174547458,656716847,65369506,625165336,920188953,762354103,904266534,757777828,792475713,762003238,640654027,487341911,351629797,411738195,820882440,846652090,253882136,90760973,663015209,810477259,638836246,659979955,353464713,796471699,80711729,318142045,106369942,136128439,920842915,810137318,710577056,742104630,282290386,879785291,647098862,559719550,386012826,512612449,640652919,98164875,639199988,412345240,879700547,544381254,170811888,969193453,629088458,726632770,303518402,538783423,791635075,359208669,605488710,382216402,812870238,963906984,327492929,729013623,239726449,816750695,485650914,132999674,307480674,873986129,432211993,188532211,362296551,155539852,249084232,462917463,40940944,58573458,188038585,368418407,963795405,802199766,503780793,138279209,430182977,123922167,733642225,372044212,654074511,184973046,958310720,159351508,384902491,316519360,80793422,200621433,811818268,858416975,239382766,117460037,933395568,752720877,67320377,963068987,335568378,767073709,744961975,864551195,284446986,679385735,698109190,659254015,329535521,437341673,945538041,168068011,451661965,705192910,353218518,42863680,221903431,171988289,31128898,323422471,155028799,169443476,256463009,127658844,151604048,686617460,815857732,570048080,493226436,144015872,179705899,976914921,306292318,47401617,470576762,641968180,387972376,485931924,710724623,126832110,228206344,113045854,332124917,450941377,892082394,460967152,288656285,27856774,813514926,541838081,33197300,927499759,191443798,604574108,72488372,171764970,32016226,866990165,75702646,450515948,930407066,819093170,608298218,397450395,761412455,60488671,903298488,908491107,693111177,131243773,36086665,353965667,266683011,782850456,866627013,505012659,777458230,991033159,630696137,558900247,933389958,805496123,427954961,326179731,89970957,501984458,992275530,841978813,495397765,611470432,539187539,316866079,758730986,862947489,178035098,731009885,17588730,80413411,854977647,253303742,328776337,561070654,977315034,694012358,883030551,138599081,478231126,948847151,978516174,483557057,926365028,78016666,911723346,502171347,357649496,252485516,658867733,201061782,785488960,466261315,636257446,998195828,122633630,489529114,489359668,573769112,889432578,619584732,771204430,873192786,918686695,244537055,474092917,245618548,40644146,972652290,475111266,628328088,978922336,421287516,184795977,143216778,856935468,546017408,358003337,451576240,413940188,822891697,710860891,795190687,981272566,24240301,929933696,115873705,649315210,130003465,818018546,129372922,568920662,304820345,713382825,36452375,358866627,292927696,528921306,187526018,470018530,260082442,217103897,488631006,162875999,677108502,805037617,104711008,583732771,565856745,100180384,676218573,528187195,619111215,286022462,881026164,913121603,140769696,636590557,733785609,205588941,825165564,247606632,440620648,980320324,596316919,744652908,194567241,650624385,621941129,514850675,985772609,497542464,678006026,193796749,902391224,394292953,782012760,556037107,663392866,161168258,909931488,964388007,1537531,747280968,579387718,593644228,942579255,836259134,214307733,533671237,590293279,819688815,783199765,139562216,944435101,475125319,727745270,556120841,679332063,932106906,654964740,650564826,707120435,836846247,402298002,152926739,775125558,192731438,464937466,363421063,675701440,553800467,813537152,80784220,880018523,263187437,481334728,521126732,237670295,373390894,959382319,685379406,338820551,715844875,34829789,242088994,823004893,872854727,587491804,630912040,476101127,795426517,587743643,944986463,759096057,137027881,409351746,185004589,220572922,176387314,607398185,38910584,73949947,913767355,749390974,760000703,77247451,920005585,365702851,378545952,230537935,528076729,849276881,12714442,990424417,349179703,273205475,82748451,909651808,303844240,659706004,413864138,214146123,531143934,616260029,104038315,684418950,427219457,257735168,290255737,930306112,263818932,164051696,570325500,659582256,841410978,146704281,124421215,88351578,301586192,541889124,403091144,339893981,246828443,124041411,852126701,75039638,271247240,181361363,56492113,485130484,805047019,80863147,353309730,760777294,327078002,500113985,433396963,145184709,905812355,453988530,429510976,487035226,669890056,342807812,179308147,80903003,976881745,427290154,176201786,152888592,134566168,877871361,412702406,773560851,418092776,513239115,552346923,286389443,744254851,570895452,412398592,885684245,438707569,306531377,278402566,324281193,325111946,911424673,904275326,925753980,120686947,762758896,517490446,370488187,611826061,32067888,431441546,29494434,320877332,948025,737072204,159496743,843955964,818126083,540125283,654780737,593004069,182482241,867358717,619434904,46039239,938974430,391627732,591769760,832809271,908844290,219969285,884685794,584655475,215150088,780068927,881408126,134265383,798871418,332115213,444837682,547072195,396339374,895830168,142524791,527039508,288905144,942999546,423102112,907654386,395347947,522139993,392295829,248335864,494104755,242167952,704844913,583200980,908252603,432291065,304423621,626569581,507029588,473713963,573275182,679663829,414862569,666994063,974584979,71810660,968141748,332898259,777836677,431123672,543498126,962820379,228147981,443471606,981846005,66128844,591896919,700688822,788926452,736808480,563576613,598766329,652166226,750095160,651736828,183715659,632227569,286130700,733962845,984388797,605243454,38548923,317741434,21594149,434318364,437099985,19192868,749861754,708463325,875159657,923751428,44434358,342038966,526963833,56695930,576354188,170724471,902690227,169353615,28236416,361288261,345001878,610303784,770684824,813610788,842742942,338437805,516585176,78059338,377473715,639057091,459452707,841403043,57183427,368891239,438420420,226653301,104357418,552486234,849955031,701963837,808187266,93692953,726142340,464283674,222943116,523501346,131099938,747091051,113949892,754823788,307633858,182795393,143406503,468378302,862496319,401954076,42928767,182086734,344781819,601225471,501083454,689505098,289397232,559118011,514663274,662702336,452704079,39983959,543592266,195681312,952336334,66150139,968893901,694960687,323504277,13826032,457973743,741307635,94015108,797505026,47233644,739082810,324352752,456278196,284686191,289528920,663729891,489803711,239677076,538376599,884869887,129887580,110776864,707153100,148566876,205024624,440568986,546437349,655554480,661229545,13602333,355371705,815729437,592162822,958606337,505114948,984827939,132238030,819926936,606100072,985137261,147286881,846571985,768104279,4497290,869493681,333868901,747990591,531787878,26587816,880301193,820705566,970996716,93083688,614546721,547249197,119011678,198680609,763161474,746043804,713263348,833412802,746114130,824746219,570567317,20313259,194509866,424820358,159779585,557194767,379095292,765138591,807418827,193795409,284184137,948269364,792372604,627807107,137457342,122059161,720601839,254076768,828546287,764037720,376583336,18602973,307944764,535299599,196735345,115910784,62414814,344099008,950511164,993333600,863888790,272901181,595041074,359020604,447126684,694689098,839499754,451196424,133678755,103879210,512670152,219471164,760336135,166708258,576771373,850078287,240908116,423379501,878482981,642219434,659564060,543385621,212384248,920847840,985361932,546712832,538429124,406931136,645344026,132138484,141871310,429418245,543090606,165482509,279316751,243167439,334151677,961492909,221149891,563468822,136189904,560489149,497573651,479593259,568354563,312525120,962787443,384394310,484769615,178626266,29359391,908458474,586538190,437272367,355524269,453087791,549742132,894329510,433745289,565942710,770503289,112223131,323351559,750633778,411239569,572242266,783792325,579389273,932348431,837342678,128707504,72777756,687644389,510593850,427113507,395837446,842341253,498541795,637570741,190380725,472943555,691309647,766760916,686563667,837686465,649317297,900569971,172604172,356348728,959342538,731387105,485367938,646117797,893284841,517465053,284252741,91297349,346210086,118044983,598024423,568096239,588507843,896901291,805093806,344920254,704899827,673333583,180306736,796579744,377741807,773089588,533879464,823630320,48771605,383471545,485122349,554558537,791706648,179160732,990166923,294744205,876337496,822860477,212141808,270647742,35104168,504530646,912390470,531888011,709612867,29847472,451042112,792877443,695333611,206018608,236583097,441344609,799780997,109109386,76565950,777057209,89006834,7467554,989469376,109678052,44433922,662852567,931005066,260343165,538642559,454910476,600548988,606521164,841207451,937127468,37455148,552496169,43533625,555757028,727611734,226408067,776352796,46298956,192245873,182567146,452291032,697507759,413785379,417013418,237143368,939190010,593888214,870062103,279277652,19204766,728958468,667962311,6851681,822039199,943956557,672204179,748801497,288828258,875168224,344059978,734200565,68719570,878767796,383226603,257116579,734196710,316894443,456809790,300275960,301136506,757865138,860390649,516102596,384535226,908980036,104823502,476851133,99883422,253729269,26217853,875058234,932019709,940403526,350645416,958576455,393063213,276950133,279058863,344697602,557118017,262944391,216555841,848224948,493977904,435667406,233123131,334981919,179110140,414734947,911865216,812159960,589576779,647064520,123693161,538661615,200111119,339378322,60629887,842038270,331625877,88904088,538294704,862583679,867254067,320429997,47450172,819758072,447346311,401833017,691008639,141453814,432171861,278597554,654998059,529882354,392585538,420894628,864313785,859366064,522342269,849481050,46036768,613572860,898347516,466998298,772197794,476875547,808863570,853938507,651259746,170438060,869400909,770826372,619905583,587208934,462332112,403915001,275948620,111040079,480889737,859721967,833917028,130401038,297594098,743835030,192355347,382419672,239589758,660088944,837600049,816001200,221507307,705632866,276736019,953032979,502382324,686422785,352587772,343555592,567682912,417156833,734491917,357308242,413190932,127421425,702649136,130319975,461046902,476332298,239213094,646548818,240806696,373095767,164395007,426912238,845977751,319460632,755289616,375370155,152034087,182557391,356977340,443781347,704698757,178659586,60745136,887568293,432296321,565944581,253903410,820394432,161204114,791539126,110897138,918341325,34266834,598769623,54717473,501353152 };

ll kotae = 1;
void keisan(int A, int B) {
	if (B <= 0) kotae = 0;
	int a = A / 400;
	int b = B / 400 + 1;
	if (a < b) {
		for (int i = B; i <= A; i++) kotae = kotae * i % mod;
	}
	else {
		if (a > b) {
			kotae = kotae * fac[a] % mod;
			kotae = kotae * ifac[b] % mod;
		}
		for (int i = a * 400 + 1; i <= A; i++) kotae = kotae * i % mod;
		for (int i = B; i <= b * 400; i++) kotae = kotae * i % mod;
	}
}

int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);




	fread(cn, 1, cm, stdin);

	int N = getint(), M = getint();
	rep(i, N) A[i] = getint();
	rep(i, M) B[i] = getint();
	sort(A, A + N, greater<int>());
	sort(B, B + M, greater<int>());

	int Aima = 0;
	int Bima = 0;
	int nokori = 0;
	int mae = -1;

	for (int i = N * M; i >= 1; i--) {
		if (A[Aima] != i && B[Bima] != i) {
			if (mae < nokori) mae = nokori;
			nokori--;
		}
		else {
			if (mae > nokori) keisan(mae, nokori + 1);
			mae = -1;
			if (A[Aima] == i && B[Bima] == i) {
				nokori += Aima++ + Bima++;
			}
			else if (A[Aima] == i) {
				kotae = kotae * Bima % mod;
				nokori += Bima - 1;
				Aima++;
			}
			else {
				kotae = kotae * Aima % mod;
				nokori += Aima - 1;
				Bima++;
			}
		}
	}
	if (mae > nokori) keisan(mae, nokori + 1);

	printf("%lld", kotae);

	Would you please return 0;
}

Measured memory_bytes: 128