N=1000;
M=0;
Q=0;
u=1;
v=2;
t=1;
A=[751103,789683,573261,759320,204083,582213,998020,554041,172192,585984,170816,847474,615253,414729,199132,178154,149919,538838,317239,368381,986579,413192,537094,224263,126174,269494,869912,557220,415697,808534,970368,676497,775318,982926,962490,851147,497757,819335,585660,832866,793514,731538,599186,791222,497956,827259,791875,123151,775028,43573,503864,498326,202189,773178,660717,379737,585595,574249,871042,545214,411478,204424,741682,722368,955161,514796,675070,396770,701438,962935,80764,84002,966738,757878,451008,256417,685993,166968,834616,124108,945390,880638,212150,366837,551698,668540,227943,281483,180699,542385,527146,803539,97874,945292,240326,613539,388429,497527,75738,251509,231028,107855,713212,980203,75439,256726,248622,412695,658793,427052,908548,209325,395896,605640,801482,141540,354476,896752,496065,531364,479194,464026,413619,945206,528765,792495,976605,368726,545413,123821,799189,540636,458955,782736,377387,19675,492490,92656,171749,222374,427885,940428,518622,93020,266698,887432,90681,262912,258259,429829,510830,552469,939776,976142,576654,667934,385542,971064,380348,598491,652087,538678,502176,600971,158673,115187,80917,229833,50199,214945,516246,373588,538236,473806,538047,317761,98972,216087,439135,190595,257632,579515,723245,334089,389401,303315,785360,778450,105281,144052,253877,223244,277043,675552,111412,76286,410594,115348,491708,396670,602937,389863,45869,602175,709356,392872,920509,408284,967334,260459,892147,266762,649901,544308,697558,780814,93052,757733,410714,554276,661394,894044,735005,17388,613491,581137,958867,562652,247420,462098,617385,613135,760763,632222,184654,629036,486210,139552,798464,290353,639439,802639,582619,983823,845616,668718,172561,980237,910454,987069,995344,579887,750204,624844,626052,901336,905235,772923,69553,218107,457546,165573,801066,344668,345280,934773,790432,865225,880329,112300,125596,587010,996191,252227,139892,8735,434101,184010,614199,322679,267533,11488,293423,483235,345121,627016,648868,583951,962288,136658,483426,605955,398461,287851,791131,198486,448046,501811,966681,323659,469444,12291,968832,191249,578765,391317,755282,574662,793138,336392,604549,344469,24016,347596,690866,914332,656740,822867,795256,920110,477188,799512,419211,402736,501005,682355,65998,640029,182683,428624,571231,480928,940300,237978,380155,919826,688258,855993,707697,991006,479284,422667,897343,727944,412117,340344,682596,825913,592935,568497,948010,749750,292716,939251,208880,361232,188203,698946,822781,276514,640750,335470,579386,218879,97110,490537,459259,990522,125097,234631,188453,750179,935856,689038,462085,782951,550809,604639,395275,251188,207584,202174,715737,635730,554373,715810,103929,515540,956431,611245,955863,606148,903099,831907,685134,338885,984175,876404,419077,507877,284451,130548,118909,811156,719410,399542,118042,320004,380289,95110,583079,726929,824527,306483,462733,903719,586440,208653,917830,363423,356891,834649,213621,429863,386075,640726,896547,945046,562420,421539,548783,883388,646192,325836,307180,855831,240495,639438,24203,6504,986765,977935,307134,319111,271160,285228,797605,824556,859206,449537,836540,770906,918728,350759,490444,760135,586495,721912,557186,357234,102627,940361,678113,415308,346238,262865,864109,712107,796421,27420,777585,167235,635217,462758,387151,239721,163339,947474,84646,497429,664180,744408,257567,918092,999432,801456,567474,949163,179954,604547,766299,938797,215298,685312,647509,580670,864463,431709,791525,970700,89751,487803,602709,338526,379084,975008,884256,521969,554945,729794,126180,777215,179635,318736,366873,638238,95376,682610,306331,943886,696039,540631,159466,491109,846424,470811,410655,418479,855285,986951,849842,648996,352259,153550,837345,268248,191331,242831,618159,443375,29064,922752,611285,438314,21868,25503,10693,527412,564053,187366,228910,643538,69590,252960,835937,669536,314489,647605,807992,665016,86362,998469,716103,531424,319278,595652,381228,427197,482951,107616,357970,263630,153846,189404,531766,335602,562864,90182,667009,262155,128318,811598,229598,480794,278929,832588,917021,177147,532719,931807,52453,100035,146579,361597,793169,992924,288117,78143,90625,464939,934889,363049,182649,33774,837163,787549,609471,984232,965956,526698,375770,146518,886412,197183,283253,62868,550916,871239,81772,767613,111614,155664,342036,427052,548574,566410,662674,266657,928573,653516,898045,691322,827067,109767,667591,272749,516091,413006,613954,531096,570361,658828,96456,597794,918745,552205,123315,628721,896637,266253,93947,144003,29937,652096,305635,750606,428267,573776,472458,180527,537955,746752,400500,80701,230751,141455,344719,739576,164040,681129,975044,977079,733127,759749,518591,887264,966004,98348,140608,530549,444649,901374,151100,702434,606170,414294,367730,482192,331066,614520,479372,547500,526810,475877,238482,811852,491399,233966,789430,18730,542873,189435,943796,432073,891774,601967,17618,757005,108599,76464,521536,521579,530826,126902,888811,503528,45556,289444,449235,920066,553836,357494,279987,713978,710946,39391,301022,632647,257190,505771,788665,997414,268443,34776,501307,448231,370581,491429,444007,478300,379236,869183,14476,629224,797993,887888,632807,910635,666581,205204,715378,347544,123486,617558,7206,135374,274430,8286,714343,305895,198365,506240,177068,807139,102614,814673,898633,361929,347821,394356,757236,501210,858323,198856,546583,157978,775735,214078,759421,951609,740020,366314,860593,223829,727203,290044,998353,190858,514570,321810,655263,962669,736623,514789,260083,178390,726778,403722,824851,239586,699040,682229,95560,356266,60067,291399,347733,135254,333361,791271,659918,55333,226805,700431,984571,799470,552840,346528,769526,660630,327646,291705,735736,464080,476666,854309,839587,691414,643546,654465,790267,870542,18472,288502,385693,526296,583377,350664,798046,314278,547493,422734,937110,184129,430483,346757,333012,405488,287584,747880,274850,113342,10964,375720,548544,426931,391462,836981,702521,784677,246522,894465,224710,835484,181666,617424,218852,249815,876923,537030,452182,80017,612224,572013,723014,832416,669537,6469,5609,226899,860042,308958,997660,74173,40611,465401,95963,95533,599984,336964,749066,783407,519821,815312,671254,248538,334125,277662,328035,236131,892936,346368,879745,671428,473104,330162,620440,637728,889961,786004,729564,561957,698147,373829,632830,111778,681126,179442,358205,477009,75197,82407,861575,705874,404083,711804,625262,884107,92145,965484,12444,497279,18780,712574,153896,597425,356995,321673,53424,419270,928737,970571,896586,114174,314542,465336,890173,524854,602306,668638,625330,815669,870539,881930,5764,811772,920421,436478,984468,337814,407516,581574,782825,742567,239457,325234,70717,388983,534234,637602,299993,781809,472608,115337,168339,728843,71628,803596,497334,914822,393478,98722,428818,761082,250992,854003,129523,119369,717456,604685,758506,643313,765464,303701,485416,568064,164582,957298,250409,912571];