#379853 (PyPy3) No.148 試験監督（3）

• 問題: No.148 試験監督（3）
• ユーザー: fumiphys
• 提出日時: 2019-09-16 19:26:27
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 22,409 bytes
• コンパイル時間: 176 ms
• コンパイル使用メモリ: 82,324 KB
• 実行使用メモリ: 73,112 KB
• 最終ジャッジ日時: 2024-07-07 02:29:29
• 合計ジャッジ時間: 2,090 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	76 ms; 62,464 KB
testcase_01	AC	80 ms; 62,464 KB
testcase_02	AC	132 ms; 62,464 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	AC	40 ms; 56,576 KB

ソースコード

MOD = int(1e9) + 7
BASE = int(1e6)
dic = {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}
dic[0] = 1

# import sys
# res = 1
# for i in range(1, MOD):
#     res = res * i % MOD
#     if i % int(1e6) == 0:
#         dic[i] = res
# print(dic)
# sys.exit()

def fac(i):
    i %= MOD
    base = (i // BASE) * BASE
    res = dic[base]
    for j in range(base + 1, i + 1):
        res = res * j % MOD
    return res

def inv(i):
    return pow(i, MOD - 2, MOD)

t = int(input())
for i_ in range(t):
    c, p = list(map(int, input().split(" ")))
    if c < 2 * p - 1 or p >= MOD:
        print(0)
        continue
    res = fac(c - p + 1) * inv(fac(c - 2 * p + 1)) % MOD
    print(res)