N=1000;
M=1000;
Q=130;
u=1;
v=2;
t=1;
A=[719730,265368,766225,978873,180882,759547,799075,652390,846784,103245,459582,527132,263286,875985,799682,891145,100193,88894,987389,957935,788555,838621,490241,492976,211689,983306,786624,536496,66529,302515,193420,648550,811429,619495,698831,327320,858313,113793,193509,179067,150461,885560,243848,852471,581570,325461,430354,777241,882948,316071,85705,694323,518730,916987,405523,13089,855503,652044,750860,686618,921096,740351,172480,355559,922176,210079,287800,549983,509057,54375,504900,433337,995935,923834,83592,933400,64830,368237,970893,20804,148548,680392,523481,841760,731829,971566,145442,984096,823015,72613,194861,301258,866656,242280,969531,738522,6094,963329,608191,331092,536418,230862,414192,888327,331090,430053,952223,637394,175666,453929,811110,350871,904179,259425,851918,334142,241765,613806,867094,219967,571026,28558,210630,406379,229383,701298,833729,546761,28019,853153,519282,562193,132151,179583,299612,899696,796862,535732,546066,952296,650863,54216,355760,861840,948372,988964,373678,893824,942925,272149,359312,947063,702350,901056,970643,108416,28498,448428,131708,255414,460576,772993,96132,668268,601255,323624,842105,454842,341135,387319,60782,974955,401752,585947,896355,212977,66061,173056,639966,228218,324434,882829,264924,946588,56984,539186,632434,400563,812424,187183,79860,548270,268594,631224,522809,701807,168253,425798,646376,785475,188878,375577,711198,562140,781922,743050,643932,115488,730994,2513,212692,318928,474395,582267,179052,893634,464223,777092,854213,130004,151647,22104,110352,933235,632684,419589,96617,153327,105377,941958,458910,262190,287978,453242,178702,37184,637167,752891,182021,130335,826408,267118,318275,515815,13004,339467,419736,926960,446405,879815,209481,257166,821076,331920,958077,353345,809694,46465,779376,42552,669919,602146,365912,343180,954583,912774,257927,836662,61826,50150,656127,742240,694979,124910,908946,866018,736347,517332,874115,331334,924001,6284,454748,180502,99175,253937,277450,991722,753750,631773,543605,892769,134107,635738,858848,205325,753381,772443,272710,704101,934465,537408,649777,63432,351014,204728,853572,44181,684817,500830,378729,88802,937850,713562,583713,666723,793623,166885,289096,922474,174666,696460,124640,48483,981718,32024,764671,339586,292537,551190,309699,849593,608669,200610,81992,92903,363673,566309,104382,739894,975050,269668,977433,31170,214710,576539,899922,464712,923636,434555,96165,522436,508069,813411,754252,91393,517748,954845,23580,116558,552707,267287,692731,82201,930235,7873,861089,71062,130460,389757,855031,693335,198709,949565,345819,523679,762651,509831,429840,118928,621674,501208,503316,573700,270057,277093,167775,950044,674704,524560,787318,994434,109287,245962,767704,546484,734251,101860,67033,29666,610855,541095,732962,79821,633378,520226,499206,467900,600449,990028,864444,23595,775886,632333,613700,420331,641239,433908,954536,790164,82371,514689,547348,150092,559736,472718,891224,277984,417781,936418,830392,340197,169594,550857,964595,55502,92968,268315,627456,710576,152138,931743,842769,624869,843516,851997,454225,942726,845697,998520,200295,437765,899737,78362,65089,300978,187431,207245,598671,260314,783146,205474,815166,644089,992641,901870,436625,700283,731117,979827,745887,602012,247012,585083,796542,769937,194211,684936,132274,484950,578306,123616,527149,609846,205317,832382,379045,656738,297814,727066,958864,977753,33693,391415,345636,637610,893463,124666,116223,557739,36951,714941,11592,91483,823375,123914,270728,744008,544468,575415,123487,88345,614416,523859,506590,391666,742136,827345,542652,285244,466282,65389,605487,352602,906210,641134,632840,188677,674825,636538,857317,740543,612840,745385,954159,945262,418499,831111,984838,69483,523183,887223,633552,162513,842617,351938,566998,981724,231156,231319,47375,12949,998275,693451,88860,708198,830526,955514,968291,183040,792644,741534,178341,565790,531945,131338,767680,918910,489190,847769,322891,772324,69103,480589,331822,522314,552527,322515,312635,691761,448171,62134,752938,940491,436420,516281,495632,481112,608962,444448,15989,72653,823203,148966,447495,80617,655886,885278,689722,329962,539955,650477,975863,283751,654411,270572,164734,511814,373485,522743,814329,720278,730944,228609,665074,828786,794142,647562,923157,155623,412099,660089,680022,2513,806453,903634,599177,894137,506557,840902,136631,251645,801113,733655,451718,498656,54012,858149,834413,719391,340092,24838,1125,444549,719966,299841,30934,486455,230872,478057,943815,493092,976724,938813,558852,132558,993891,649311,38584,86254,172057,430883,962780,359048,875477,994088,313255,296989,60643,384860,995275,7609,855207,623936,845548,997541,271501,698917,662540,739951,274302,479000,395712,718545,830968,347038,236011,56519,458237,982066,732887,974064,947804,587224,745455,309431,88776,185443,780653,379929,325265,549988,159960,158562,467694,359483,407715,723760,610076,896629,131825,689912,179273,424353,526443,268557,452369,674105,469575,583902,385451,59939,83046,637470,279446,224096,47012,901830,817342,817079,157457,178695,217524,845501,431621,388138,325396,800134,919401,854475,7917,867332,378990,97255,506245,332385,82933,919426,237989,759951,230498,403849,140272,705483,768448,393567,331329,759236,543046,567023,517976,705306,502903,912965,161898,554717,322898,380124,393144,471067,531901,474944,397535,920874,37275,803370,381882,14056,761511,848472,22918,232970,503340,132153,422929,817489,190054,548743,257087,814795,730373,108278,435935,457783,248714,878653,112071,202371,969709,95389,917082,747224,61025,10150,441479,349268,824628,569171,819607,195619,951549,930298,204217,61278,677915,264242,565392,477756,833535,551164,611384,841278,58106,762660,28023,956360,227644,620223,233269,6247,884695,830296,347773,861765,982859,771834,265971,79167,568004,528067,394815,235070,674159,503172,324959,840501,27903,317606,819157,585077,326335,57645,515088,493607,282312,555687,90766,743160,130666,984860,154392,231832,656739,447406,120844,901844,755652,24029,208775,727373,499618,440972,380180,246091,643500,149677,814974,702593,300675,371707,516193,735520,602858,2085,457325,415997,370604,436636,595233,375243,823301,932990,299915,837656,827017,567869,270894,614889,661778,753693,527186,797443,511962,441295,383867,652211,523131,273620,443815,404127,284180,359999,583212,605627,841816,172370,332483,102426,235763,204544,45932,719522,770041,344564,656290,998028,762162,470213,168013,927110,418739,484110,719914,518753,738947,965167,678548,146917,27211,165563,414830,817809,660251,719499,158469,207430,944842,210381,921707,839557,684457,549439,899667,365824,30119,472029,290441,281157,970583,261317,620320,746881,469853,267771,752234,880595,332315,952278,839619,573936,884836,780582,724056,440959,800872,544606,395159,476721,637687,97719,860133,866346,633697,15339,499997,407542,808780,356282,962338,277317,559661,318013,549171,409,853176,627962,929145,273287,524281,616510];