結果
| 問題 | No.148 試験監督（3） |
| ユーザー |
 kmjp
|
| 提出日時 | 2015-02-09 01:38:27 |
| 言語 | PyPy2 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 189 ms / 1,000 ms |
| コード長 | 23,521 bytes |
| コンパイル時間 | 178 ms |
| コンパイル使用メモリ | 77,060 KB |
| 実行使用メモリ | 77,596 KB |
| 最終ジャッジ日時 | 2024-06-23 11:27:13 |
| 合計ジャッジ時間 | 2,480 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 104 ms
76,948 KB |
| testcase_01 | AC | 115 ms
76,704 KB |
| testcase_02 | AC | 171 ms
76,984 KB |
| testcase_03 | AC | 187 ms
76,420 KB |
| testcase_04 | AC | 189 ms
76,304 KB |
| testcase_05 | AC | 161 ms
76,840 KB |
| testcase_06 | AC | 151 ms
77,448 KB |
| testcase_07 | AC | 189 ms
77,596 KB |
| testcase_08 | AC | 172 ms
77,576 KB |
| testcase_09 | AC | 88 ms
76,448 KB |
| testcase_10 | AC | 88 ms
76,692 KB |
| testcase_11 | AC | 73 ms
75,684 KB |
ソースコード
import sys
import math
T=input()
mo=1000000007
facts=[
[0,1],
[1000000,641102369],
[2000000,578095319],
[3000000,5832229],
[4000000,259081142],
[5000000,974067448],
[6000000,316220877],
[7000000,690120224],
[8000000,251368199],
[9000000,980250487],
[10000000,682498929],
[11000000,134623568],
[12000000,95936601],
[13000000,933097914],
[14000000,167332441],
[15000000,598816162],
[16000000,336060741],
[17000000,248744620],
[18000000,626497524],
[19000000,288843364],
[20000000,491101308],
[21000000,245341950],
[22000000,565768255],
[23000000,246899319],
[24000000,968999],
[25000000,586350670],
[26000000,638587686],
[27000000,881746146],
[28000000,19426633],
[29000000,850500036],
[30000000,76479948],
[31000000,268124147],
[32000000,842267748],
[33000000,886294336],
[34000000,485348706],
[35000000,463847391],
[36000000,544075857],
[37000000,898187927],
[38000000,798967520],
[39000000,82926604],
[40000000,723816384],
[41000000,156530778],
[42000000,721996174],
[43000000,299085602],
[44000000,323604647],
[45000000,172827403],
[46000000,398699886],
[47000000,530389102],
[48000000,294587621],
[49000000,813805606],
[50000000,67347853],
[51000000,497478507],
[52000000,196447201],
[53000000,722054885],
[54000000,228338256],
[55000000,407719831],
[56000000,762479457],
[57000000,746536789],
[58000000,811667359],
[59000000,778773518],
[60000000,27368307],
[61000000,438371670],
[62000000,59469516],
[63000000,5974669],
[64000000,766196482],
[65000000,606322308],
[66000000,86609485],
[67000000,889750731],
[68000000,340941507],
[69000000,371263376],
[70000000,625544428],
[71000000,788878910],
[72000000,808412394],
[73000000,996952918],
[74000000,585237443],
[75000000,1669644],
[76000000,361786913],
[77000000,480748381],
[78000000,595143852],
[79000000,837229828],
[80000000,199888908],
[81000000,526807168],
[82000000,579691190],
[83000000,145404005],
[84000000,459188207],
[85000000,534491822],
[86000000,439729802],
[87000000,840398449],
[88000000,899297830],
[89000000,235861787],
[90000000,888050723],
[91000000,656116726],
[92000000,736550105],
[93000000,440902696],
[94000000,85990869],
[95000000,884343068],
[96000000,56305184],
[97000000,973478770],
[98000000,168891766],
[99000000,804805577],
[100000000,927880474],
[101000000,876297919],
[102000000,934814019],
[103000000,676405347],
[104000000,567277637],
[105000000,112249297],
[106000000,44930135],
[107000000,39417871],
[108000000,47401357],
[109000000,108819476],
[110000000,281863274],
[111000000,60168088],
[112000000,692636218],
[113000000,432775082],
[114000000,14235602],
[115000000,770511792],
[116000000,400295761],
[117000000,697066277],
[118000000,421835306],
[119000000,220108638],
[120000000,661224977],
[121000000,261799937],
[122000000,168203998],
[123000000,802214249],
[124000000,544064410],
[125000000,935080803],
[126000000,583967898],
[127000000,211768084],
[128000000,751231582],
[129000000,972424306],
[130000000,623534362],
[131000000,335160196],
[132000000,243276029],
[133000000,554749550],
[134000000,60050552],
[135000000,797848181],
[136000000,395891998],
[137000000,172428290],
[138000000,159554990],
[139000000,887420150],
[140000000,970055531],
[141000000,250388809],
[142000000,487998999],
[143000000,856259313],
[144000000,82104855],
[145000000,232253360],
[146000000,513365505],
[147000000,244109365],
[148000000,1559745],
[149000000,695345956],
[150000000,261384175],
[151000000,849009131],
[152000000,323214113],
[153000000,747664143],
[154000000,444090941],
[155000000,659224434],
[156000000,80729842],
[157000000,570033864],
[158000000,664989237],
[159000000,827348878],
[160000000,195888993],
[161000000,576798521],
[162000000,457882808],
[163000000,731551699],
[164000000,212938473],
[165000000,509096183],
[166000000,827544702],
[167000000,678320208],
[168000000,677711203],
[169000000,289752035],
[170000000,66404266],
[171000000,555972231],
[172000000,195290384],
[173000000,97136305],
[174000000,349551356],
[175000000,785113347],
[176000000,83489485],
[177000000,66247239],
[178000000,52167191],
[179000000,307390891],
[180000000,547665832],
[181000000,143066173],
[182000000,350016754],
[183000000,917404120],
[184000000,296269301],
[185000000,996122673],
[186000000,23015220],
[187000000,602139210],
[188000000,748566338],
[189000000,187348575],
[190000000,109838563],
[191000000,574053420],
[192000000,105574531],
[193000000,304173654],
[194000000,542432219],
[195000000,34538816],
[196000000,325636655],
[197000000,437843114],
[198000000,630621321],
[199000000,26853683],
[200000000,933245637],
[201000000,616368450],
[202000000,238971581],
[203000000,511371690],
[204000000,557301633],
[205000000,911398531],
[206000000,848952161],
[207000000,958992544],
[208000000,925152039],
[209000000,914456118],
[210000000,724691727],
[211000000,636817583],
[212000000,238087006],
[213000000,946237212],
[214000000,910291942],
[215000000,114985663],
[216000000,492237273],
[217000000,450387329],
[218000000,834860913],
[219000000,763017204],
[220000000,368925948],
[221000000,475812562],
[222000000,740594930],
[223000000,45060610],
[224000000,806047532],
[225000000,464456846],
[226000000,172115341],
[227000000,75307702],
[228000000,116261993],
[229000000,562519302],
[230000000,268838846],
[231000000,173784895],
[232000000,243624360],
[233000000,61570384],
[234000000,481661251],
[235000000,938269070],
[236000000,95182730],
[237000000,91068149],
[238000000,115435332],
[239000000,495022305],
[240000000,136026497],
[241000000,506496856],
[242000000,710729672],
[243000000,113570024],
[244000000,366384665],
[245000000,564758715],
[246000000,270239666],
[247000000,277118392],
[248000000,79874094],
[249000000,702807165],
[250000000,112390913],
[251000000,730341625],
[252000000,103056890],
[253000000,677948390],
[254000000,339464594],
[255000000,167240465],
[256000000,108312174],
[257000000,839079953],
[258000000,479334442],
[259000000,271788964],
[260000000,135498044],
[261000000,277717575],
[262000000,591048681],
[263000000,811637561],
[264000000,353339603],
[265000000,889410460],
[266000000,839849206],
[267000000,192345193],
[268000000,736265527],
[269000000,316439118],
[270000000,217544623],
[271000000,788132977],
[272000000,618898635],
[273000000,183011467],
[274000000,380858207],
[275000000,996097969],
[276000000,898554793],
[277000000,335353644],
[278000000,54062950],
[279000000,611251733],
[280000000,419363534],
[281000000,965429853],
[282000000,160398980],
[283000000,151319402],
[284000000,990918946],
[285000000,607730875],
[286000000,450718279],
[287000000,173539388],
[288000000,648991369],
[289000000,970937898],
[290000000,500780548],
[291000000,780122909],
[292000000,39052406],
[293000000,276894233],
[294000000,460373282],
[295000000,651081062],
[296000000,461415770],
[297000000,358700839],
[298000000,643638805],
[299000000,560006119],
[300000000,668123525],
[301000000,686692315],
[302000000,673464765],
[303000000,957633609],
[304000000,199866123],
[305000000,563432246],
[306000000,841799766],
[307000000,385330357],
[308000000,504962686],
[309000000,954061253],
[310000000,128487469],
[311000000,685707545],
[312000000,299172297],
[313000000,717975101],
[314000000,577786541],
[315000000,318951960],
[316000000,773206631],
[317000000,306832604],
[318000000,204355779],
[319000000,573592106],
[320000000,30977140],
[321000000,450398100],
[322000000,363172638],
[323000000,258379324],
[324000000,472935553],
[325000000,93940075],
[326000000,587220627],
[327000000,776264326],
[328000000,793270300],
[329000000,291733496],
[330000000,522049725],
[331000000,579995261],
[332000000,335416359],
[333000000,142946099],
[334000000,472012302],
[335000000,559947225],
[336000000,332139472],
[337000000,499377092],
[338000000,464599136],
[339000000,164752359],
[340000000,309058615],
[341000000,86117128],
[342000000,580204973],
[343000000,563781682],
[344000000,954840109],
[345000000,624577416],
[346000000,895609896],
[347000000,888287558],
[348000000,836813268],
[349000000,926036911],
[350000000,386027524],
[351000000,184419613],
[352000000,724205533],
[353000000,403351886],
[354000000,715247054],
[355000000,716986954],
[356000000,830567832],
[357000000,383388563],
[358000000,68409439],
[359000000,6734065],
[360000000,189239124],
[361000000,68322490],
[362000000,943653305],
[363000000,405755338],
[364000000,811056092],
[365000000,179518046],
[366000000,825132993],
[367000000,343807435],
[368000000,985084650],
[369000000,868553027],
[370000000,148528617],
[371000000,160684257],
[372000000,882148737],
[373000000,591915968],
[374000000,701445829],
[375000000,529726489],
[376000000,302177126],
[377000000,974886682],
[378000000,241107368],
[379000000,798830099],
[380000000,940567523],
[381000000,11633075],
[382000000,325334066],
[383000000,346091869],
[384000000,115312728],
[385000000,473718967],
[386000000,218129285],
[387000000,878471898],
[388000000,180002392],
[389000000,699739374],
[390000000,917084264],
[391000000,856859395],
[392000000,435327356],
[393000000,808651347],
[394000000,421623838],
[395000000,105419548],
[396000000,59883031],
[397000000,322487421],
[398000000,79716267],
[399000000,715317963],
[400000000,429277690],
[401000000,398078032],
[402000000,316486674],
[403000000,384843585],
[404000000,940338439],
[405000000,937409008],
[406000000,940524812],
[407000000,947549662],
[408000000,833550543],
[409000000,593524514],
[410000000,996164327],
[411000000,987314628],
[412000000,697611981],
[413000000,636177449],
[414000000,274192146],
[415000000,418537348],
[416000000,925347821],
[417000000,952831975],
[418000000,893732627],
[419000000,1277567],
[420000000,358655417],
[421000000,141866945],
[422000000,581830879],
[423000000,987597705],
[424000000,347046911],
[425000000,775305697],
[426000000,125354499],
[427000000,951540811],
[428000000,247662371],
[429000000,343043237],
[430000000,568392357],
[431000000,997474832],
[432000000,209244402],
[433000000,380480118],
[434000000,149586983],
[435000000,392838702],
[436000000,309134554],
[437000000,990779998],
[438000000,263053337],
[439000000,325362513],
[440000000,780072518],
[441000000,551028176],
[442000000,990826116],
[443000000,989944961],
[444000000,155569943],
[445000000,596737944],
[446000000,711553356],
[447000000,268844715],
[448000000,451373308],
[449000000,379404150],
[450000000,462639908],
[451000000,961812918],
[452000000,654611901],
[453000000,382776490],
[454000000,41815820],
[455000000,843321396],
[456000000,675258797],
[457000000,845583555],
[458000000,934281721],
[459000000,741114145],
[460000000,275105629],
[461000000,666247477],
[462000000,325912072],
[463000000,526131620],
[464000000,252551589],
[465000000,432030917],
[466000000,554917439],
[467000000,818036959],
[468000000,754363835],
[469000000,795190182],
[470000000,909210595],
[471000000,278704903],
[472000000,719566487],
[473000000,628514947],
[474000000,424989675],
[475000000,321685608],
[476000000,50590510],
[477000000,832069712],
[478000000,198768464],
[479000000,702004730],
[480000000,99199382],
[481000000,707469729],
[482000000,747407118],
[483000000,302020341],
[484000000,497196934],
[485000000,5003231],
[486000000,726997875],
[487000000,382617671],
[488000000,296229203],
[489000000,183888367],
[490000000,703397904],
[491000000,552133875],
[492000000,732868367],
[493000000,350095207],
[494000000,26031303],
[495000000,863250534],
[496000000,216665960],
[497000000,561745549],
[498000000,352946234],
[499000000,784139777],
[500000000,733333339],
[501000000,503105966],
[502000000,459878625],
[503000000,803187381],
[504000000,16634739],
[505000000,180898306],
[506000000,68718097],
[507000000,985594252],
[508000000,404206040],
[509000000,749724532],
[510000000,97830135],
[511000000,611751357],
[512000000,31131935],
[513000000,662741752],
[514000000,864326453],
[515000000,864869025],
[516000000,167831173],
[517000000,559214642],
[518000000,718498895],
[519000000,91352335],
[520000000,608823837],
[521000000,473379392],
[522000000,385388084],
[523000000,152267158],
[524000000,681756977],
[525000000,46819124],
[526000000,313132653],
[527000000,56547945],
[528000000,442795120],
[529000000,796616594],
[530000000,256141983],
[531000000,152028387],
[532000000,636578562],
[533000000,385377759],
[534000000,553033642],
[535000000,491415383],
[536000000,919273670],
[537000000,996049638],
[538000000,326686486],
[539000000,160150665],
[540000000,141827977],
[541000000,540818053],
[542000000,693305776],
[543000000,593938674],
[544000000,186576440],
[545000000,688809790],
[546000000,565456578],
[547000000,749296077],
[548000000,519397500],
[549000000,551096742],
[550000000,696628828],
[551000000,775025061],
[552000000,370732451],
[553000000,164246193],
[554000000,915265013],
[555000000,457469634],
[556000000,923043932],
[557000000,912368644],
[558000000,777901604],
[559000000,464118005],
[560000000,637939935],
[561000000,956856710],
[562000000,490676632],
[563000000,453019482],
[564000000,462528877],
[565000000,502297454],
[566000000,798895521],
[567000000,100498586],
[568000000,699767918],
[569000000,849974789],
[570000000,811575797],
[571000000,438952959],
[572000000,606870929],
[573000000,907720182],
[574000000,179111720],
[575000000,48053248],
[576000000,508038818],
[577000000,811944661],
[578000000,752550134],
[579000000,401382061],
[580000000,848924691],
[581000000,764368449],
[582000000,34629406],
[583000000,529840945],
[584000000,435904287],
[585000000,26011548],
[586000000,208184231],
[587000000,446477394],
[588000000,206330671],
[589000000,366033520],
[590000000,131772368],
[591000000,185646898],
[592000000,648711554],
[593000000,472759660],
[594000000,523696723],
[595000000,271198437],
[596000000,25058942],
[597000000,859369491],
[598000000,817928963],
[599000000,330711333],
[600000000,724464507],
[601000000,437605233],
[602000000,701453022],
[603000000,626663115],
[604000000,281230685],
[605000000,510650790],
[606000000,596949867],
[607000000,295726547],
[608000000,303076380],
[609000000,465070856],
[610000000,272814771],
[611000000,538771609],
[612000000,48824684],
[613000000,951279549],
[614000000,939889684],
[615000000,564188856],
[616000000,48527183],
[617000000,201307702],
[618000000,484458461],
[619000000,861754542],
[620000000,326159309],
[621000000,181594759],
[622000000,668422905],
[623000000,286273596],
[624000000,965656187],
[625000000,44135644],
[626000000,359960756],
[627000000,936229527],
[628000000,407934361],
[629000000,267193060],
[630000000,456152084],
[631000000,459116722],
[632000000,124804049],
[633000000,262322489],
[634000000,920251227],
[635000000,816929577],
[636000000,483924582],
[637000000,151834896],
[638000000,167087470],
[639000000,490222511],
[640000000,903466878],
[641000000,361583925],
[642000000,368114731],
[643000000,339383292],
[644000000,388728584],
[645000000,218107212],
[646000000,249153339],
[647000000,909458706],
[648000000,322908524],
[649000000,202649964],
[650000000,92255682],
[651000000,573074791],
[652000000,15570863],
[653000000,94331513],
[654000000,744158074],
[655000000,196345098],
[656000000,334326205],
[657000000,9416035],
[658000000,98349682],
[659000000,882121662],
[660000000,769795511],
[661000000,231988936],
[662000000,888146074],
[663000000,137603545],
[664000000,582627184],
[665000000,407518072],
[666000000,919419361],
[667000000,909433461],
[668000000,986708498],
[669000000,310317874],
[670000000,373745190],
[671000000,263645931],
[672000000,256853930],
[673000000,876379959],
[674000000,702823274],
[675000000,147050765],
[676000000,308186532],
[677000000,175504139],
[678000000,180350107],
[679000000,797736554],
[680000000,606241871],
[681000000,384547635],
[682000000,273712630],
[683000000,586444655],
[684000000,682189174],
[685000000,666493603],
[686000000,946867127],
[687000000,819114541],
[688000000,502371023],
[689000000,261970285],
[690000000,825871994],
[691000000,126925175],
[692000000,701506133],
[693000000,314738056],
[694000000,341779962],
[695000000,561011609],
[696000000,815463367],
[697000000,46765164],
[698000000,49187570],
[699000000,188054995],
[700000000,957939114],
[701000000,64814326],
[702000000,933376898],
[703000000,329837066],
[704000000,338121343],
[705000000,765215899],
[706000000,869630152],
[707000000,978119194],
[708000000,632627667],
[709000000,975266085],
[710000000,435887178],
[711000000,282092463],
[712000000,129621197],
[713000000,758245605],
[714000000,827722926],
[715000000,201339230],
[716000000,918513230],
[717000000,322096036],
[718000000,547838438],
[719000000,985546115],
[720000000,852304035],
[721000000,593090119],
[722000000,689189630],
[723000000,555842733],
[724000000,567033437],
[725000000,469928208],
[726000000,212842957],
[727000000,117842065],
[728000000,404149413],
[729000000,155133422],
[730000000,663307737],
[731000000,208761293],
[732000000,206282795],
[733000000,717946122],
[734000000,488906585],
[735000000,414236650],
[736000000,280700600],
[737000000,962670136],
[738000000,534279149],
[739000000,214569244],
[740000000,375297772],
[741000000,811053196],
[742000000,922377372],
[743000000,289594327],
[744000000,219932130],
[745000000,211487466],
[746000000,701050258],
[747000000,398782410],
[748000000,863002719],
[749000000,27236531],
[750000000,217598709],
[751000000,375472836],
[752000000,810551911],
[753000000,178598958],
[754000000,247844667],
[755000000,676526196],
[756000000,812283640],
[757000000,863066876],
[758000000,857241854],
[759000000,113917835],
[760000000,624148346],
[761000000,726089763],
[762000000,564827277],
[763000000,826300950],
[764000000,478982047],
[765000000,439411911],
[766000000,454039189],
[767000000,633292726],
[768000000,48562889],
[769000000,802100365],
[770000000,671734977],
[771000000,945204804],
[772000000,508831870],
[773000000,398781902],
[774000000,897162044],
[775000000,644050694],
[776000000,892168027],
[777000000,828883117],
[778000000,277714559],
[779000000,713448377],
[780000000,624500515],
[781000000,590098114],
[782000000,808691930],
[783000000,514359662],
[784000000,895205045],
[785000000,715264908],
[786000000,628829100],
[787000000,484492064],
[788000000,919717789],
[789000000,513196123],
[790000000,748510389],
[791000000,403652653],
[792000000,574455974],
[793000000,77123823],
[794000000,172096141],
[795000000,819801784],
[796000000,581418893],
[797000000,15655126],
[798000000,15391652],
[799000000,875641535],
[800000000,203191898],
[801000000,264582598],
[802000000,880691101],
[803000000,907800444],
[804000000,986598821],
[805000000,340030191],
[806000000,264688936],
[807000000,369832433],
[808000000,785804644],
[809000000,842065079],
[810000000,423951674],
[811000000,663560047],
[812000000,696623384],
[813000000,496709826],
[814000000,161960209],
[815000000,331910086],
[816000000,541120825],
[817000000,951524114],
[818000000,841656666],
[819000000,162683802],
[820000000,629786193],
[821000000,190395535],
[822000000,269571439],
[823000000,832671304],
[824000000,76770272],
[825000000,341080135],
[826000000,421943723],
[827000000,494210290],
[828000000,751040886],
[829000000,317076664],
[830000000,672850561],
[831000000,72482816],
[832000000,493689107],
[833000000,135625240],
[834000000,100228913],
[835000000,684748812],
[836000000,639655136],
[837000000,906233141],
[838000000,929893103],
[839000000,277813439],
[840000000,814362881],
[841000000,562608724],
[842000000,406024012],
[843000000,885537778],
[844000000,10065330],
[845000000,60625018],
[846000000,983737173],
[847000000,60517502],
[848000000,551060742],
[849000000,804930491],
[850000000,823845496],
[851000000,727416538],
[852000000,946421040],
[853000000,678171399],
[854000000,842203531],
[855000000,175638827],
[856000000,894247956],
[857000000,538609927],
[858000000,885362182],
[859000000,946464959],
[860000000,116667533],
[861000000,749816133],
[862000000,241427979],
[863000000,871117927],
[864000000,281804989],
[865000000,163928347],
[866000000,563796647],
[867000000,640266394],
[868000000,774625892],
[869000000,59342705],
[870000000,256473217],
[871000000,674115061],
[872000000,918860977],
[873000000,322633051],
[874000000,753513874],
[875000000,393556719],
[876000000,304644842],
[877000000,767372800],
[878000000,161362528],
[879000000,754787150],
[880000000,627655552],
[881000000,677395736],
[882000000,799289297],
[883000000,846650652],
[884000000,816701166],
[885000000,687265514],
[886000000,787113234],
[887000000,358757251],
[888000000,701220427],
[889000000,607715125],
[890000000,245795606],
[891000000,600624983],
[892000000,10475577],
[893000000,728620948],
[894000000,759404319],
[895000000,36292292],
[896000000,491466901],
[897000000,22556579],
[898000000,114495791],
[899000000,647630109],
[900000000,586445753],
[901000000,482254337],
[902000000,718623833],
[903000000,763514207],
[904000000,66547751],
[905000000,953634340],
[906000000,351472920],
[907000000,308474522],
[908000000,494166907],
[909000000,634359666],
[910000000,172114298],
[911000000,865440961],
[912000000,364380585],
[913000000,921648059],
[914000000,965683742],
[915000000,260466949],
[916000000,117483873],
[917000000,962540888],
[918000000,237120480],
[919000000,620531822],
[920000000,193781724],
[921000000,213092254],
[922000000,107141741],
[923000000,602742426],
[924000000,793307102],
[925000000,756154604],
[926000000,236455213],
[927000000,362928234],
[928000000,14162538],
[929000000,753042874],
[930000000,778983779],
[931000000,25977209],
[932000000,49389215],
[933000000,698308420],
[934000000,859637374],
[935000000,49031023],
[936000000,713258160],
[937000000,737331920],
[938000000,923333660],
[939000000,804861409],
[940000000,83868974],
[941000000,682873215],
[942000000,217298111],
[943000000,883278906],
[944000000,176966527],
[945000000,954913],
[946000000,105359006],
[947000000,390019735],
[948000000,10430738],
[949000000,706334445],
[950000000,315103615],
[951000000,567473423],
[952000000,708233401],
[953000000,48160594],
[954000000,946149627],
[955000000,346966053],
[956000000,281329488],
[957000000,462880311],
[958000000,31503476],
[959000000,185438078],
[960000000,965785236],
[961000000,992656683],
[962000000,916291845],
[963000000,881482632],
[964000000,899946391],
[965000000,321900901],
[966000000,512634493],
[967000000,303338827],
[968000000,121000338],
[969000000,967284733],
[970000000,492741665],
[971000000,152233223],
[972000000,165393390],
[973000000,680128316],
[974000000,917041303],
[975000000,532702135],
[976000000,741626808],
[977000000,496442755],
[978000000,536841269],
[979000000,131384366],
[980000000,377329025],
[981000000,301196854],
[982000000,859917803],
[983000000,676511002],
[984000000,373451745],
[985000000,847645126],
[986000000,823495900],
[987000000,576368335],
[988000000,73146164],
[989000000,954958912],
[990000000,847549272],
[991000000,241289571],
[992000000,646654592],
[993000000,216046746],
[994000000,205951465],
[995000000,3258987],
[996000000,780882948],
[997000000,822439091],
[998000000,598245292],
[999000000,869544707],
[1000000000,698611116],
[1001000000,0]
]
def fact(x):
ret = facts[x/1000000][1]
cur = facts[x/1000000][0]
for i in range(1,len(facts)):
if x < facts[i][0]:
cur = facts[i-1][0]
ret = facts[i-1][1]
break
for i in range(cur+1,x+1):
ret = ret*i%mo
return ret
def mult(L,R):
if L/mo != R/mo:
return 0
L%=mo
R%=mo
if L==0:
if R==0:
return 1
return 0
elif L==1:
return fact(R)
else:
return fact(R)*pow(fact(L-1),mo-2,mo)%mo
for i in range(T):
C,P=map(int,raw_input().strip().split(" "))
if P*2-1>C:
print 0
else:
# P! * H(P+1,C-(2*P-1))
# = P! * C(C-P+1,P) = (C-P+1)*(C-P+2)*...*(C-2*P+2)
if P >= mo:
print 0
else:
print mult(C-2*P+2,C-P+1) % mo