結果
| 問題 |
No.148 試験監督（3）
|
| コンテスト | |
| ユーザー |
 koyumeishi
|
| 提出日時 | 2015-02-11 16:22:54 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 102 ms / 1,000 ms |
| コード長 | 27,604 bytes |
| コンパイル時間 | 940 ms |
| コンパイル使用メモリ | 111,820 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-06-23 18:32:40 |
| 合計ジャッジ時間 | 2,275 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 12 |
ソースコード
#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define MOD 1000000007
vector<pair<int, int>> built_in =
{
{ 0, 1},
{ 1, 1},
{ 1000001, 5614648},
{ 2000001, 208001982},
{ 3000001, 692709757},
{ 4000001, 819826874},
{ 5000001, 179975082},
{ 6000001, 564939602},
{ 7000001, 224304330},
{ 8000001, 829291584},
{ 9000001, 301494702},
{ 10000001, 924724006},
{ 11000001, 372257555},
{ 12000001, 299877928},
{ 13000001, 730186003},
{ 14000001, 324933863},
{ 15000001, 965940468},
{ 16000001, 154421937},
{ 17000001, 759144014},
{ 18000001, 979558839},
{ 19000001, 166427196},
{ 20000001, 582347126},
{ 21000001, 159276683},
{ 22000001, 88639941},
{ 23000001, 544148531},
{ 24000001, 976806214},
{ 25000001, 233739301},
{ 26000001, 358364726},
{ 27000001, 657096124},
{ 28000001, 739619018},
{ 29000001, 721848529},
{ 30000001, 500419162},
{ 31000001, 766941211},
{ 32000001, 589599772},
{ 33000001, 769560345},
{ 34000001, 373835714},
{ 35000001, 35204778},
{ 36000001, 258968740},
{ 37000001, 964557256},
{ 38000001, 346442158},
{ 39000001, 616287645},
{ 40000001, 881147799},
{ 41000001, 9606444},
{ 42000001, 817729301},
{ 43000001, 95060835},
{ 44000001, 691934419},
{ 45000001, 253386772},
{ 46000001, 26318521},
{ 47000001, 149891086},
{ 48000001, 3606179},
{ 49000001, 228670281},
{ 50000001, 693776109},
{ 51000001, 176878679},
{ 52000001, 576940423},
{ 53000001, 359172522},
{ 54000001, 966026401},
{ 55000001, 955747701},
{ 56000001, 55587507},
{ 57000001, 421668610},
{ 58000001, 304130410},
{ 59000001, 19140052},
{ 60000001, 435873621},
{ 61000001, 121186966},
{ 62000001, 25659746},
{ 63000001, 150339841},
{ 64000001, 270940457},
{ 65000001, 350445658},
{ 66000001, 56595903},
{ 67000001, 449457638},
{ 68000001, 654653353},
{ 69000001, 135943165},
{ 70000001, 279027658},
{ 71000001, 6806089},
{ 72000001, 768972550},
{ 73000001, 501509977},
{ 74000001, 64084446},
{ 75000001, 300793083},
{ 76000001, 557316278},
{ 77000001, 558625006},
{ 78000001, 726195312},
{ 79000001, 786241736},
{ 80000001, 727951124},
{ 81000001, 836107508},
{ 82000001, 826948451},
{ 83000001, 475924281},
{ 84000001, 577185544},
{ 85000001, 86469187},
{ 86000001, 147012461},
{ 87000001, 391595794},
{ 88000001, 385330367},
{ 89000001, 131919894},
{ 90000001, 398578768},
{ 91000001, 304170372},
{ 92000001, 922211842},
{ 93000001, 881875046},
{ 94000001, 715408882},
{ 95000001, 756254931},
{ 96000001, 682468105},
{ 97000001, 2486683},
{ 98000001, 121032015},
{ 99000001, 370075313},
{ 100000001, 678364145},
{ 101000001, 75755289},
{ 102000001, 205356809},
{ 103000001, 929717097},
{ 104000001, 402299519},
{ 105000001, 214746065},
{ 106000001, 321591977},
{ 107000001, 206893887},
{ 108000001, 567565935},
{ 109000001, 909790222},
{ 110000001, 204828554},
{ 111000001, 781417489},
{ 112000001, 565609426},
{ 113000001, 356449994},
{ 114000001, 630875596},
{ 115000001, 230249800},
{ 116000001, 351255605},
{ 117000001, 535168999},
{ 118000001, 181399344},
{ 119000001, 958758149},
{ 120000001, 345795998},
{ 121000001, 417055393},
{ 122000001, 780557789},
{ 123000001, 738507785},
{ 124000001, 911816508},
{ 125000001, 491885103},
{ 126000001, 216908213},
{ 127000001, 691506262},
{ 128000001, 574128088},
{ 129000001, 568325161},
{ 130000001, 116118093},
{ 131000001, 703818301},
{ 132000001, 846488984},
{ 133000001, 188277720},
{ 134000001, 971723141},
{ 135000001, 478881653},
{ 136000001, 747002821},
{ 137000001, 737069565},
{ 138000001, 625424874},
{ 139000001, 873960350},
{ 140000001, 359401113},
{ 141000001, 72255055},
{ 142000001, 860928000},
{ 143000001, 758143746},
{ 144000001, 119343162},
{ 145000001, 196516201},
{ 146000001, 718705964},
{ 147000001, 647920833},
{ 148000001, 259943851},
{ 149000001, 414100127},
{ 150000001, 236930793},
{ 151000001, 732606485},
{ 152000001, 155314298},
{ 153000001, 825915852},
{ 154000001, 879360913},
{ 155000001, 213965925},
{ 156000001, 344572857},
{ 157000001, 591566652},
{ 158000001, 375511144},
{ 159000001, 508509581},
{ 160000001, 856493327},
{ 161000001, 807746594},
{ 162000001, 834643710},
{ 163000001, 833851217},
{ 164000001, 540485110},
{ 165000001, 116090093},
{ 166000001, 397937762},
{ 167000001, 621363890},
{ 168000001, 984722836},
{ 169000001, 861975384},
{ 170000001, 207383191},
{ 171000001, 391473474},
{ 172000001, 8160762},
{ 173000001, 744504245},
{ 174000001, 867797811},
{ 175000001, 548349502},
{ 176000001, 340630442},
{ 177000001, 287166912},
{ 178000001, 985166878},
{ 179000001, 411230108},
{ 180000001, 617606889},
{ 181000001, 274801334},
{ 182000001, 132095411},
{ 183000001, 702209449},
{ 184000001, 298674444},
{ 185000001, 211143815},
{ 186000001, 913049410},
{ 187000001, 83938986},
{ 188000001, 307453041},
{ 189000001, 614486415},
{ 190000001, 933753281},
{ 191000001, 26543999},
{ 192000001, 915682368},
{ 193000001, 115235049},
{ 194000001, 291809269},
{ 195000001, 107393333},
{ 196000001, 258863167},
{ 197000001, 292057463},
{ 198000001, 314580174},
{ 199000001, 906446509},
{ 200000001, 26701748},
{ 201000001, 199138044},
{ 202000001, 263065768},
{ 203000001, 854712526},
{ 204000001, 893474909},
{ 205000001, 458541645},
{ 206000001, 790763153},
{ 207000001, 177412352},
{ 208000001, 690130678},
{ 209000001, 238606822},
{ 210000001, 329394893},
{ 211000001, 709238020},
{ 212000001, 156765891},
{ 213000001, 691397537},
{ 214000001, 134674617},
{ 215000001, 486932244},
{ 216000001, 715974523},
{ 217000001, 159248979},
{ 218000001, 594863167},
{ 219000001, 269311835},
{ 220000001, 360779992},
{ 221000001, 941730537},
{ 222000001, 49710412},
{ 223000001, 4720998},
{ 224000001, 710165010},
{ 225000001, 82937316},
{ 226000001, 965828879},
{ 227000001, 309643766},
{ 228000001, 334707855},
{ 229000001, 818800869},
{ 230000001, 416008308},
{ 231000001, 637774725},
{ 232000001, 367978403},
{ 233000001, 433149091},
{ 234000001, 426700127},
{ 235000001, 844816460},
{ 236000001, 217940862},
{ 237000001, 252986092},
{ 238000001, 939120076},
{ 239000001, 561849995},
{ 240000001, 187501984},
{ 241000001, 948036669},
{ 242000001, 130753612},
{ 243000001, 752387419},
{ 244000001, 599659},
{ 245000001, 771197527},
{ 246000001, 640886967},
{ 247000001, 621980698},
{ 248000001, 253212669},
{ 249000001, 562814284},
{ 250000001, 165706817},
{ 251000001, 322131396},
{ 252000001, 201264538},
{ 253000001, 147301796},
{ 254000001, 611896552},
{ 255000001, 443716239},
{ 256000001, 458216762},
{ 257000001, 250575124},
{ 258000001, 649656447},
{ 259000001, 455035577},
{ 260000001, 328891607},
{ 261000001, 845327573},
{ 262000001, 929065410},
{ 263000001, 860412822},
{ 264000001, 892368025},
{ 265000001, 139554063},
{ 266000001, 72049990},
{ 267000001, 363852031},
{ 268000001, 591031407},
{ 269000001, 462584264},
{ 270000001, 16385287},
{ 271000001, 60044725},
{ 272000001, 160515639},
{ 273000001, 324276557},
{ 274000001, 368372171},
{ 275000001, 553609389},
{ 276000001, 30546939},
{ 277000001, 73102931},
{ 278000001, 48856450},
{ 279000001, 924477109},
{ 280000001, 117411011},
{ 281000001, 759429344},
{ 282000001, 203771396},
{ 283000001, 617555672},
{ 284000001, 684972093},
{ 285000001, 770307789},
{ 286000001, 342380290},
{ 287000001, 180898760},
{ 288000001, 612624778},
{ 289000001, 528730541},
{ 290000001, 404196042},
{ 291000001, 710012554},
{ 292000001, 511229292},
{ 293000001, 977984170},
{ 294000001, 420925074},
{ 295000001, 596598678},
{ 296000001, 425362301},
{ 297000001, 795961803},
{ 298000001, 191008264},
{ 299000001, 968913323},
{ 300000001, 765064133},
{ 301000001, 54831613},
{ 302000001, 279760259},
{ 303000001, 453492735},
{ 304000001, 166551016},
{ 305000001, 390504408},
{ 306000001, 434664677},
{ 307000001, 156255424},
{ 308000001, 704263144},
{ 309000001, 67426771},
{ 310000001, 239669664},
{ 311000001, 687922230},
{ 312000001, 309780005},
{ 313000001, 757891666},
{ 314000001, 181811730},
{ 315000001, 15662891},
{ 316000001, 458873573},
{ 317000001, 93971059},
{ 318000001, 471459820},
{ 319000001, 106760939},
{ 320000001, 761588352},
{ 321000001, 538353577},
{ 322000001, 980581522},
{ 323000001, 326183677},
{ 324000001, 572317727},
{ 325000001, 255226407},
{ 326000001, 649183166},
{ 327000001, 601395295},
{ 328000001, 371921701},
{ 329000001, 803871263},
{ 330000001, 566114869},
{ 331000001, 627146251},
{ 332000001, 743908749},
{ 333000001, 776738749},
{ 334000001, 236447546},
{ 335000001, 621870992},
{ 336000001, 142947438},
{ 337000001, 325346539},
{ 338000001, 333357587},
{ 339000001, 474795016},
{ 340000001, 673499119},
{ 341000001, 528555548},
{ 342000001, 957194280},
{ 343000001, 136141870},
{ 344000001, 151585137},
{ 345000001, 636222967},
{ 346000001, 742442742},
{ 347000001, 356637091},
{ 348000001, 62336156},
{ 349000001, 602728751},
{ 350000001, 840260100},
{ 351000001, 894300632},
{ 352000001, 555763111},
{ 353000001, 164669381},
{ 354000001, 58864862},
{ 355000001, 605274385},
{ 356000001, 952792810},
{ 357000001, 416300551},
{ 358000001, 58975386},
{ 359000001, 324811362},
{ 360000001, 352356536},
{ 361000001, 785671564},
{ 362000001, 962435847},
{ 363000001, 68731029},
{ 364000001, 232485180},
{ 365000001, 510849444},
{ 366000001, 149142275},
{ 367000001, 105566139},
{ 368000001, 647506607},
{ 369000001, 588080572},
{ 370000001, 53839501},
{ 371000001, 90387244},
{ 372000001, 749033441},
{ 373000001, 110423383},
{ 374000001, 911060663},
{ 375000001, 514194465},
{ 376000001, 882846940},
{ 377000001, 516160743},
{ 378000001, 707137280},
{ 379000001, 200533857},
{ 380000001, 178657924},
{ 381000001, 555607668},
{ 382000001, 667390782},
{ 383000001, 245219574},
{ 384000001, 357352119},
{ 385000001, 492046360},
{ 386000001, 638743964},
{ 387000001, 24691537},
{ 388000001, 787115903},
{ 389000001, 280349069},
{ 390000001, 373444237},
{ 391000001, 956635248},
{ 392000001, 792789102},
{ 393000001, 955051508},
{ 394000001, 430785301},
{ 395000001, 273934501},
{ 396000001, 169887271},
{ 397000001, 563294886},
{ 398000001, 123626749},
{ 399000001, 954434908},
{ 400000001, 227300165},
{ 401000001, 112673002},
{ 402000001, 373893180},
{ 403000001, 54199837},
{ 404000001, 637061350},
{ 405000001, 519854486},
{ 406000001, 939553315},
{ 407000001, 681980692},
{ 408000001, 996930210},
{ 409000001, 120263839},
{ 410000001, 207172723},
{ 411000001, 254810458},
{ 412000001, 857699043},
{ 413000001, 233988454},
{ 414000001, 923583317},
{ 415000001, 622686362},
{ 416000001, 766734984},
{ 417000001, 746515458},
{ 418000001, 364670975},
{ 419000001, 570530467},
{ 420000001, 444208499},
{ 421000001, 568785064},
{ 422000001, 801102476},
{ 423000001, 278320916},
{ 424000001, 581011688},
{ 425000001, 693771264},
{ 426000001, 325547387},
{ 427000001, 404385343},
{ 428000001, 293665913},
{ 429000001, 985884408},
{ 430000001, 367531373},
{ 431000001, 580093282},
{ 432000001, 240489335},
{ 433000001, 321244888},
{ 434000001, 317141733},
{ 435000001, 566644864},
{ 436000001, 909655906},
{ 437000001, 85983999},
{ 438000001, 62531810},
{ 439000001, 532523519},
{ 440000001, 297449176},
{ 441000001, 466004208},
{ 442000001, 197210129},
{ 443000001, 643125656},
{ 444000001, 364058565},
{ 445000001, 817899263},
{ 446000001, 266083791},
{ 447000001, 32629606},
{ 448000001, 19866621},
{ 449000001, 536936916},
{ 450000001, 605324209},
{ 451000001, 943369557},
{ 452000001, 835419862},
{ 453000001, 138992247},
{ 454000001, 188925146},
{ 455000001, 337342765},
{ 456000001, 951832734},
{ 457000001, 775561781},
{ 458000001, 156974539},
{ 459000001, 914914415},
{ 460000001, 729265513},
{ 461000001, 413266882},
{ 462000001, 535912440},
{ 463000001, 880939054},
{ 464000001, 728264037},
{ 465000001, 430770292},
{ 466000001, 318776764},
{ 467000001, 996874160},
{ 468000001, 63067924},
{ 469000001, 542580831},
{ 470000001, 567907756},
{ 471000001, 672814847},
{ 472000001, 206118827},
{ 473000001, 478501971},
{ 474000001, 964873947},
{ 475000001, 52080967},
{ 476000001, 642022936},
{ 477000001, 677788962},
{ 478000001, 325689189},
{ 479000001, 18182882},
{ 480000001, 125889461},
{ 481000001, 974419170},
{ 482000001, 101655515},
{ 483000001, 983889580},
{ 484000001, 868693736},
{ 485000001, 23017262},
{ 486000001, 503751120},
{ 487000001, 855274043},
{ 488000001, 348310253},
{ 489000001, 17438490},
{ 490000001, 250743107},
{ 491000001, 279449758},
{ 492000001, 772869729},
{ 493000001, 192916655},
{ 494000001, 618015062},
{ 495000001, 202087450},
{ 496000001, 624401755},
{ 497000001, 460432797},
{ 498000001, 654575673},
{ 499000001, 768139555},
{ 500000001, 666666670},
{ 501000001, 704713357},
{ 502000001, 593865149},
{ 503000001, 618164631},
{ 504000001, 413947383},
{ 505000001, 71422798},
{ 506000001, 907318605},
{ 507000001, 251720271},
{ 508000001, 286849371},
{ 509000001, 866456044},
{ 510000001, 598576559},
{ 511000001, 850516770},
{ 512000001, 639555085},
{ 513000001, 58836133},
{ 514000001, 596479895},
{ 515000001, 622016210},
{ 516000001, 829624985},
{ 517000001, 449416866},
{ 518000001, 723221920},
{ 519000001, 624469308},
{ 520000001, 632705086},
{ 521000001, 978964765},
{ 522000001, 825180038},
{ 523000001, 228817097},
{ 524000001, 129072399},
{ 525000001, 974758851},
{ 526000001, 638178235},
{ 527000001, 862942583},
{ 528000001, 166224366},
{ 529000001, 72745362},
{ 530000001, 295855233},
{ 531000001, 83938876},
{ 532000001, 249960011},
{ 533000001, 494533351},
{ 534000001, 313793901},
{ 535000001, 556064787},
{ 536000001, 590158882},
{ 537000001, 857899074},
{ 538000001, 564385190},
{ 539000001, 990902216},
{ 540000001, 185718228},
{ 541000001, 165740098},
{ 542000001, 654903680},
{ 543000001, 318377788},
{ 544000001, 836093366},
{ 545000001, 611000459},
{ 546000001, 992281555},
{ 547000001, 999241420},
{ 548000001, 526988704},
{ 549000001, 791231979},
{ 550000001, 414607857},
{ 551000001, 396753419},
{ 552000001, 890222274},
{ 553000001, 257449185},
{ 554000001, 567867315},
{ 555000001, 550200119},
{ 556000001, 522556971},
{ 557000001, 63043320},
{ 558000001, 771417960},
{ 559000001, 443024264},
{ 560000001, 737215408},
{ 561000001, 509280433},
{ 562000001, 744354777},
{ 563000001, 33669713},
{ 564000001, 264464882},
{ 565000001, 25711034},
{ 566000001, 519671487},
{ 567000001, 963619707},
{ 568000001, 341490693},
{ 569000001, 405525225},
{ 570000001, 863388390},
{ 571000001, 273457993},
{ 572000001, 564959746},
{ 573000001, 552854555},
{ 574000001, 739440838},
{ 575000001, 454638929},
{ 576000001, 627626319},
{ 577000001, 929500199},
{ 578000001, 159732309},
{ 579000001, 93580577},
{ 580000001, 182290465},
{ 581000001, 524681987},
{ 582000001, 185549208},
{ 583000001, 302560062},
{ 584000001, 261927573},
{ 585000001, 499494263},
{ 586000001, 720212525},
{ 587000001, 889901798},
{ 588000001, 905073640},
{ 589000001, 136877326},
{ 590000001, 707552496},
{ 591000001, 135625686},
{ 592000001, 928450895},
{ 593000001, 890334328},
{ 594000001, 808165766},
{ 595000001, 156656954},
{ 596000001, 352513039},
{ 597000001, 395064410},
{ 598000001, 268078344},
{ 599000001, 411038724},
{ 600000001, 881713600},
{ 601000001, 629600032},
{ 602000001, 989530010},
{ 603000001, 326518123},
{ 604000001, 832187361},
{ 605000001, 298044708},
{ 606000001, 466688548},
{ 607000001, 68184456},
{ 608000001, 53183314},
{ 609000001, 786473813},
{ 610000001, 417895708},
{ 611000001, 333445452},
{ 612000001, 447659742},
{ 613000001, 406339029},
{ 614000001, 876243850},
{ 615000001, 575355848},
{ 616000001, 567277975},
{ 617000001, 465859745},
{ 618000001, 286691172},
{ 619000001, 625772136},
{ 620000001, 490627919},
{ 621000001, 731202351},
{ 622000001, 668109597},
{ 623000001, 345834453},
{ 624000001, 435669988},
{ 625000001, 351042205},
{ 626000001, 38612732},
{ 627000001, 256118157},
{ 628000001, 322654922},
{ 629000001, 830742029},
{ 630000001, 364521407},
{ 631000001, 13198172},
{ 632000001, 540670943},
{ 633000001, 636971551},
{ 634000001, 754176309},
{ 635000001, 580677631},
{ 636000001, 481492358},
{ 637000001, 226803100},
{ 638000001, 280874835},
{ 639000001, 826457237},
{ 640000001, 775935292},
{ 641000001, 664156867},
{ 642000001, 15807139},
{ 643000001, 567819107},
{ 644000001, 732340142},
{ 645000001, 973353162},
{ 646000001, 116481947},
{ 647000001, 572520253},
{ 648000001, 410195470},
{ 649000001, 918011189},
{ 650000001, 972492338},
{ 651000001, 902572989},
{ 652000001, 620505449},
{ 653000001, 652142174},
{ 654000001, 733402435},
{ 655000001, 486102832},
{ 656000001, 279100282},
{ 657000001, 961111697},
{ 658000001, 401351052},
{ 659000001, 70894458},
{ 660000001, 473340273},
{ 661000001, 854576141},
{ 662000001, 760477195},
{ 663000001, 833985502},
{ 664000001, 50576048},
{ 665000001, 390521460},
{ 666000001, 59086324},
{ 667000001, 150288656},
{ 668000001, 36859587},
{ 669000001, 563099282},
{ 670000001, 920880265},
{ 671000001, 726301005},
{ 672000001, 8613050},
{ 673000001, 154753996},
{ 674000001, 62903086},
{ 675000001, 827235910},
{ 676000001, 481847874},
{ 677000001, 446790032},
{ 678000001, 870408510},
{ 679000001, 172094735},
{ 680000001, 530581},
{ 681000001, 986409076},
{ 682000001, 627008546},
{ 683000001, 147652776},
{ 684000001, 431867430},
{ 685000001, 525656798},
{ 686000001, 522011212},
{ 687000001, 546992739},
{ 688000001, 906952196},
{ 689000001, 363487610},
{ 690000001, 696910290},
{ 691000001, 437988110},
{ 692000001, 339410446},
{ 693000001, 595943759},
{ 694000001, 309412918},
{ 695000001, 86690147},
{ 696000001, 274525867},
{ 697000001, 126597931},
{ 698000001, 668857109},
{ 699000001, 772901915},
{ 700000001, 64037482},
{ 701000001, 272770432},
{ 702000001, 742762852},
{ 703000001, 104708874},
{ 704000001, 143859375},
{ 705000001, 783875464},
{ 706000001, 883917971},
{ 707000001, 295407332},
{ 708000001, 733324972},
{ 709000001, 400020535},
{ 710000001, 649527920},
{ 711000001, 71118283},
{ 712000001, 747589160},
{ 713000001, 338841814},
{ 714000001, 854763771},
{ 715000001, 643636394},
{ 716000001, 994924954},
{ 717000001, 517496044},
{ 718000001, 278402466},
{ 719000001, 710292551},
{ 720000001, 756691728},
{ 721000001, 398764308},
{ 722000001, 66025260},
{ 723000001, 701722682},
{ 724000001, 81307995},
{ 725000001, 885042572},
{ 726000001, 913175062},
{ 727000001, 773143805},
{ 728000001, 8604016},
{ 729000001, 1487574},
{ 730000001, 283805222},
{ 731000001, 323529765},
{ 732000001, 89289760},
{ 733000001, 460164594},
{ 734000001, 366904568},
{ 735000001, 32989098},
{ 736000001, 434531120},
{ 737000001, 228254934},
{ 738000001, 736193086},
{ 739000001, 420602554},
{ 740000001, 711255329},
{ 741000001, 840120298},
{ 742000001, 155549330},
{ 743000001, 744414246},
{ 744000001, 794525609},
{ 745000001, 278580339},
{ 746000001, 508165835},
{ 747000001, 583549204},
{ 748000001, 156320509},
{ 749000001, 603435404},
{ 750000001, 825205499},
{ 751000001, 237612150},
{ 752000001, 615806680},
{ 753000001, 611203860},
{ 754000001, 857720528},
{ 755000001, 81085271},
{ 756000001, 353678644},
{ 757000001, 421675529},
{ 758000001, 640716607},
{ 759000001, 273672383},
{ 760000001, 263679166},
{ 761000001, 501209621},
{ 762000001, 626038603},
{ 763000001, 263027603},
{ 764000001, 825386080},
{ 765000001, 1361141},
{ 766000001, 793481077},
{ 767000001, 75144100},
{ 768000001, 539488803},
{ 769000001, 169394126},
{ 770000001, 341083474},
{ 771000001, 727934511},
{ 772000001, 399104463},
{ 773000001, 486973046},
{ 774000001, 92338118},
{ 775000001, 75699},
{ 776000001, 997911339},
{ 777000001, 229587871},
{ 778000001, 667281084},
{ 779000001, 506014403},
{ 780000001, 914727729},
{ 781000001, 398031746},
{ 782000001, 641912335},
{ 783000001, 41154371},
{ 784000001, 262319788},
{ 785000001, 564884265},
{ 786000001, 769011417},
{ 787000001, 183425300},
{ 788000001, 578554498},
{ 789000001, 725813957},
{ 790000001, 919247968},
{ 791000001, 691627931},
{ 792000001, 797672078},
{ 793000001, 288009486},
{ 794000001, 169585796},
{ 795000001, 537604886},
{ 796000001, 169752841},
{ 797000001, 350315181},
{ 798000001, 225413886},
{ 799000001, 443178461},
{ 800000001, 465317279},
{ 801000001, 779067985},
{ 802000001, 938491295},
{ 803000001, 337054180},
{ 804000001, 518020692},
{ 805000001, 178960077},
{ 806000001, 187313969},
{ 807000001, 711649036},
{ 808000001, 693293608},
{ 809000001, 984450571},
{ 810000001, 960145703},
{ 811000001, 13529682},
{ 812000001, 545016096},
{ 813000001, 207934224},
{ 814000001, 365110946},
{ 815000001, 528363060},
{ 816000001, 650238695},
{ 817000001, 647757742},
{ 818000001, 810330630},
{ 819000001, 68017571},
{ 820000001, 274813468},
{ 821000001, 331192404},
{ 822000001, 576457392},
{ 823000001, 227651951},
{ 824000001, 761959351},
{ 825000001, 746342372},
{ 826000001, 180265132},
{ 827000001, 463226941},
{ 828000001, 6007936},
{ 829000001, 933080800},
{ 830000001, 393588827},
{ 831000001, 746850283},
{ 832000001, 642443769},
{ 833000001, 264794472},
{ 834000001, 957092529},
{ 835000001, 702392034},
{ 836000001, 592393306},
{ 837000001, 613613203},
{ 838000001, 789140198},
{ 839000001, 967215128},
{ 840000001, 65909169},
{ 841000001, 134531186},
{ 842000001, 116918500},
{ 843000001, 513979384},
{ 844000001, 470599364},
{ 845000001, 912028045},
{ 846000001, 516045672},
{ 847000001, 895709241},
{ 848000001, 495964200},
{ 849000001, 880228617},
{ 850000001, 521964827},
{ 851000001, 232196248},
{ 852000001, 381965993},
{ 853000001, 975810006},
{ 854000001, 281510854},
{ 855000001, 209440455},
{ 856000001, 871914241},
{ 857000001, 746488999},
{ 858000001, 723876953},
{ 859000001, 36371194},
{ 860000001, 794328994},
{ 861000001, 743674331},
{ 862000001, 682651567},
{ 863000001, 609694565},
{ 864000001, 73448426},
{ 865000001, 326342214},
{ 866000001, 448061396},
{ 867000001, 352489674},
{ 868000001, 323999002},
{ 869000001, 343361035},
{ 870000001, 484551338},
{ 871000001, 695035563},
{ 872000001, 254133608},
{ 873000001, 874022494},
{ 874000001, 19516020},
{ 875000001, 108021830},
{ 876000001, 28562682},
{ 877000001, 656471213},
{ 878000001, 753628442},
{ 879000001, 960581850},
{ 880000001, 521297378},
{ 881000001, 915896263},
{ 882000001, 818477212},
{ 883000001, 329503005},
{ 884000001, 506954384},
{ 885000001, 319655682},
{ 886000001, 229436987},
{ 887000001, 768233498},
{ 888000001, 518434282},
{ 889000001, 950903931},
{ 890000001, 54488990},
{ 891000001, 707526991},
{ 892000001, 629066079},
{ 893000001, 738011434},
{ 894000001, 193052120},
{ 895000001, 148921085},
{ 896000001, 704986521},
{ 897000001, 243923822},
{ 898000001, 712775258},
{ 899000001, 563093861},
{ 900000001, 591837535},
{ 901000001, 77676252},
{ 902000001, 547232982},
{ 903000001, 858340939},
{ 904000001, 549433589},
{ 905000001, 612360836},
{ 906000001, 642431679},
{ 907000001, 803969799},
{ 908000001, 909242071},
{ 909000001, 991929142},
{ 910000001, 255746228},
{ 911000001, 817523991},
{ 912000001, 558174948},
{ 913000001, 898395355},
{ 914000001, 975239204},
{ 915000001, 927176157},
{ 916000001, 32177284},
{ 917000001, 79990965},
{ 918000001, 353384287},
{ 919000001, 46650635},
{ 920000001, 25827429},
{ 921000001, 773286506},
{ 922000001, 617648953},
{ 923000001, 906423641},
{ 924000001, 910196803},
{ 925000001, 560053576},
{ 926000001, 941752538},
{ 927000001, 925886944},
{ 928000001, 186162693},
{ 929000001, 802005099},
{ 930000001, 177799409},
{ 931000001, 435683742},
{ 932000001, 107173979},
{ 933000001, 997656163},
{ 934000001, 555328260},
{ 935000001, 233122981},
{ 936000001, 799990729},
{ 937000001, 941171892},
{ 938000001, 940724891},
{ 939000001, 565507403},
{ 940000001, 92011129},
{ 941000001, 499787378},
{ 942000001, 346434378},
{ 943000001, 410754885},
{ 944000001, 495571727},
{ 945000001, 779638169},
{ 946000001, 83671673},
{ 947000001, 849578933},
{ 948000001, 565212365},
{ 949000001, 319154757},
{ 950000001, 469664591},
{ 951000001, 62802869},
{ 952000001, 740566050},
{ 953000001, 808881279},
{ 954000001, 785762461},
{ 955000001, 642498007},
{ 956000001, 926672572},
{ 957000001, 989045133},
{ 958000001, 828241173},
{ 959000001, 742592273},
{ 960000001, 35708489},
{ 961000001, 678055221},
{ 962000001, 635982602},
{ 963000001, 555408249},
{ 964000001, 751108186},
{ 965000001, 612460332},
{ 966000001, 284200074},
{ 967000001, 959038326},
{ 968000001, 485102056},
{ 969000001, 683192433},
{ 970000001, 197025781},
{ 971000001, 650504017},
{ 972000001, 120056772},
{ 973000001, 515774387},
{ 974000001, 786653742},
{ 975000001, 522010089},
{ 976000001, 282832488},
{ 977000001, 736270779},
{ 978000001, 943625970},
{ 979000001, 545007315},
{ 980000001, 288851931},
{ 981000001, 6878070},
{ 982000001, 494842864},
{ 983000001, 987438832},
{ 984000001, 881116147},
{ 985000001, 113132018},
{ 986000001, 539727236},
{ 987000001, 239239534},
{ 988000001, 599267301},
{ 989000001, 311778406},
{ 990000001, 254032854},
{ 991000001, 428463830},
{ 992000001, 420285135},
{ 993000001, 492305827},
{ 994000001, 982941187},
{ 995000001, 45560143},
{ 996000001, 544567071},
{ 997000001, 809636715},
{ 998000001, 834903713},
{ 999000001, 81818608},
{ 1000000001, 808333339}
};
// X = a*Y + b
pair<string, long long> divide(string X, long long Y){
string a = "";
long long b = 0;
for(int i=0; i<X.size(); i++){
b *= 10;
b += X[i] - '0';
if(a.size() == 0){
if(b/Y > 0) a.push_back(b/Y + '0');
}else{
a.push_back(b/Y + '0');
}
b %= Y;
}
return {a,b};
}
long long extgcd(long long a, long long b, long long &x, long long &y){
long long d=a;
if(b!=0){
d = extgcd(b, a%b, y, x);
y -= (a/b) * x;
}else{
x = 1;
y = 0;
}
return d;
}
long long mod_inverse(long long a, long long m){
if(a==0) return 1;
long long x,y;
extgcd(a,m,x,y);
return (m+x%m)%m;
}
int main(){
int T;
cin >> T;
while(T--){
string c,p;
cin >> c >> p;
auto x = divide(p, MOD);
if(x.first.size() > 0){
cout << 0 << endl;
continue;
}
long long P = x.second;
auto y = divide(c, MOD);
int C = y.second+1;
C -= P;
if(y.first.size()>0 && C<0) C += MOD;
if( /*y.first.size()>0 &&*/ C-P+1 <= 0){
cout << 0 << endl;
continue;
}
auto itr_begin = upper_bound(built_in.begin(), built_in.end(), pair<int,int>{C-P+1-1, 1});
itr_begin--;
long long inv = itr_begin->second;
for(int i=itr_begin->first+1; i<=C-P; i++){
inv *= i;
inv %= MOD;
}
inv = mod_inverse(inv, MOD);
auto itr_end = upper_bound(built_in.begin(), built_in.end(), pair<int,int>{C, 0});
itr_end--;
long long tmp_val = itr_end->second;
for(int i= itr_end->first+1; i<=C; i++){
tmp_val *= i;
tmp_val %= MOD;
}
long long ret = inv * tmp_val;
ret %= MOD;
cout << ret << endl;
}
return 0;
}