#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(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;
}