N=1000;
M=1000;
Q=0;
u=1;
v=2;
t=1;
A=[132625,572871,770124,563851,578941,933006,37851,712167,787787,21841,604359,544543,291697,614202,217317,279151,895815,907188,928,230088,615013,807840,735459,4978,235862,255796,73447,976978,608845,143807,47494,86708,266274,569504,236993,720635,568066,977048,562580,835334,263018,198469,319339,920134,130806,725275,115485,435250,211565,156159,801918,444289,354245,909101,770224,401684,523563,287652,281489,808390,85089,847306,719055,19606,44203,70341,444727,799706,256062,598661,735682,121716,236113,158306,960102,617252,455887,784041,899057,721071,344767,405267,131911,112760,671609,368635,254546,81084,541152,485852,488790,862017,503918,327348,336896,23371,645572,68132,671351,924330,12014,710566,445303,194355,814454,278185,90452,755819,856266,21767,457065,851719,235619,324249,387529,155470,507744,736258,618256,817582,872159,254642,800840,409139,157286,707315,649395,737989,161937,318442,665683,588924,796853,240420,695726,719766,24949,887234,551276,116030,742490,717428,754785,622773,809381,429708,728204,189664,558978,123757,404425,239570,954105,235461,501902,159068,931890,228058,291686,855381,641385,106038,479269,335615,848586,327428,342330,481933,197232,74501,712663,493024,671117,102290,258159,198070,718462,515328,393839,200845,280220,664983,236596,413469,111268,799790,825644,675104,762129,596992,979383,982764,693974,861699,470607,239963,518467,639997,809593,764175,617461,201882,382731,379210,793446,553631,290017,307653,304088,389731,831654,254990,627047,471721,431361,95849,521921,173097,570596,823270,534701,244453,672403,391863,655574,643711,242508,650379,11738,642115,824715,831978,907286,839926,158052,988583,990821,171645,896108,699395,349741,138617,923999,757799,280848,900076,937049,932937,736825,142831,554462,750902,249541,104336,86358,818076,909764,174869,478257,609655,354866,2190,681102,870356,834367,803491,620262,941732,575484,366379,461900,617607,423127,829860,830307,873553,36255,774045,712696,973318,259034,292016,218221,291257,987062,256548,823617,857911,796645,480693,35684,239721,77879,826660,171491,210332,506084,534947,884432,679132,910283,303562,357928,971108,15710,738642,629536,748701,249874,741749,31417,958629,861564,342561,185859,299653,779966,952648,216590,279533,148527,510459,791788,908156,207242,108715,362808,588188,690100,42868,13698,368409,438530,327705,808717,69743,180930,224853,798779,255506,202066,655725,658535,874816,467664,618243,643339,966900,449415,78825,381917,128186,79031,95973,798111,897833,240217,728311,533520,750910,975294,444840,863883,1306,877731,637307,53728,563084,632501,49409,416994,91686,22954,584287,703327,138728,915885,132987,404129,790761,28113,697158,586472,723302,906198,894495,511457,798583,9556,164371,491302,434780,713361,782203,535121,453433,510256,284859,609504,954691,814182,86467,610847,355987,992902,964010,255898,897258,162243,112266,11744,546083,304453,142567,432625,752568,225147,256327,728351,703796,946983,745584,222603,678803,394881,530094,846237,683762,794359,760878,295312,733185,859884,356193,101741,33910,501281,52687,199045,665558,979755,960329,246887,212130,603157,509899,668753,407239,970725,287463,387095,9589,111731,983641,119135,733528,885817,113052,350326,341421,498142,117855,80656,920629,888582,407958,757092,352382,375491,578914,141374,590521,97956,318610,328287,465444,486135,295022,28296,87219,314962,889476,57733,678284,1062,725727,616081,415709,34299,557484,964519,838350,561358,105559,460018,615324,613990,327465,331071,654457,392332,59735,187930,413782,549109,591361,847163,675611,439057,172584,387810,140474,64525,941873,390782,912279,674210,932269,364399,359093,834472,28676,723412,921976,978593,257979,209190,419133,381564,923335,209594,199826,893472,866188,173802,763733,62752,744802,536511,194387,862887,448974,772752,357231,650696,21443,470554,965914,401953,775238,58524,413203,875215,487499,256347,452972,820671,485830,600402,240877,456287,248500,887584,714746,305282,387141,463286,382009,703916,52109,469053,585073,210524,149266,573945,505652,8318,591731,721083,976054,177989,955810,765379,795820,216205,748812,338672,438018,951105,454174,890947,324866,632348,144352,426167,816459,546341,479364,891470,707521,844584,545043,414783,363263,109416,612617,751312,630981,473264,937505,745180,229804,726061,547651,569719,805198,738344,897432,438783,705017,440721,781707,61034,386206,174728,112555,904304,651416,141323,466189,628934,963404,907340,303064,862388,734706,753215,254423,987695,52648,882072,522311,868577,896801,652438,835974,472933,367102,176522,40235,200956,519899,284103,878473,886460,669206,428884,545768,864623,91878,235289,751423,412464,4530,231401,810895,355380,408708,94150,23520,275782,264632,278598,630918,533138,939361,648095,635196,559774,331054,638122,455753,385604,516853,421005,650955,445737,341936,816513,945656,386082,868334,542398,917646,704660,864556,947334,855980,641696,689323,774607,627322,71934,845612,889703,726872,64594,45619,837803,744797,798864,882068,372302,89916,476059,669791,327511,410893,897857,487761,975089,412858,529810,787508,310243,595147,340609,204639,751907,502846,556865,26608,232548,788182,497020,775295,179436,62171,65757,757701,361267,724175,274956,91915,811231,221256,393678,98633,78679,422323,580582,756250,104057,708291,49979,61387,701716,815242,425357,992899,871097,218382,914360,951099,435142,115211,364950,920150,304893,133132,701412,924685,602508,15256,87743,696879,463317,664632,654561,518043,566558,931450,685672,942982,836662,932593,814006,15197,705161,825019,501975,857725,614247,807867,575355,653601,977069,429065,245327,778382,346926,224522,282352,88694,507519,822782,190909,443946,370408,380912,920816,821460,314936,461559,777373,405507,372348,652966,868079,667212,1969,590259,518794,832772,499350,610012,2890,956668,84746,890124,984833,891675,721881,799888,524630,164345,362015,74407,716913,328647,365698,341672,967793,242044,59148,65141,853728,712923,283055,645264,14076,503602,321236,839553,467617,546432,445427,591038,576643,18339,385620,702239,87528,531753,120286,143995,998289,726530,404007,135818,294651,871488,38070,734264,424830,673237,63735,973465,738235,547566,88783,513689,298190,316159,311583,863465,588792,999591,295258,89659,916368,109900,398128,799308,951366,758799,89561,720393,543328,266773,243996,514477,706156,35231,673682,789511,581548,56179,31261,432734,779365,186516,102220,321880,555067,656590,59659,518765,647641,820639,227112,747312,500043,232675,943430,130165,886694,811769,60987,846616,54576,717523,568726,510533,255538,183668,828649,209032,877804,57831,226269,480502,158168,538592,588349,316485,571647,543168,597285,935071,786209,10462,273253,552279,659639,365931,535730,175744,674658,330648,710157,147155,696819,862321,696681,923466,400045,950545,368933,1402,19177,911354,124840,881475,774385,172889,341358,371662,376290,235583,270357,742671,29066,970973,228754,853981,354635,959728,773939,917647,436126,40126,858675,486586,748081,82345,92352,86191,834109,218150];