87 22 947781131 975002951 967852878 986769540 967062215 963482661 965222949 977649706 986014225 949774962 959283841 975549678 974250438 978169499 971365583 989937081 974406914 995552139 947980535 967190023 994070481 987698156 947944346 23 90909090 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 22 90909090 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 27 752386915 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 765341689 25 83333333 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 19 603306641 548635696 548635696 548635696 548635696 548635696 548635696 548635696 548635696 548635696 548635696 548635696 548635696 548635696 548635696 548635696 548635696 548635696 548635696 548635696 23 90909090 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 21 100000000 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 29 100433995 539890764 257441399 61915346 23546566 693548007 9172492 230025154 271844557 52762119 825987816 625618062 76034708 62127350 766463064 881582810 56477871 457279204 583131808 55806015 489308768 59582411 39822163 31529156 89526961 509593811 822930194 510936643 386836180 626117035 22 941744907 943764312 969965960 947042797 961401834 956197616 956461918 955784647 958984379 971210350 988024327 987281816 985793691 994712011 962152375 986446656 946929795 998297938 966614743 969979220 952239700 943152479 945137140 16 196326287 191529499 633838817 657706256 150713170 711313333 344093065 194428382 186789785 421053218 2303064 714674975 50642280 9095643 337772855 456576146 159555884 26 224785462 110113294 133638350 50870624 25982007 55391871 72165955 54381392 27805493 201148852 34046617 63561353 38541003 167789446 79657284 217587204 206272494 69104531 218387007 198784908 56707808 161948228 179021988 123277508 143123092 200592363 189764002 16 615529949 543672289 520572878 476303791 401174454 388683283 327842835 314855504 302285383 266637071 241301741 215292034 115663545 84349540 70232193 30769181 4790638 25 674624788 69915578 93890266 436736400 492603810 596097804 630024257 674624788 674624788 674624788 674624788 674624788 674624788 693954517 697024579 716421565 718592602 753151772 762992602 827643055 857994869 858195910 900273950 900426670 902508286 909422480 21 554484667 376098895 428128298 554484667 138437187 554484667 255277491 336091891 947417357 808239411 658291093 554484667 735886396 728975434 788380848 567613328 452104482 450678241 654008811 472568838 888927522 293598483 13 857646570 718057118 737722264 844214109 857646570 857646570 857646570 857646570 857646570 857646570 860035793 895673599 956819770 991003337 21 100000000 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 27 327900415 887194867 784347543 404607610 490637417 442080019 350086950 517687429 537236902 773939209 844665557 646359480 332296591 363360615 558436080 348464612 384035877 342458836 654433705 901012331 913111566 598707049 763317259 521689715 995444635 409163689 841641649 481574195 21 38441246 2434140 2505756 3544772 9981159 10578426 15415157 16087472 17482124 27006675 30928399 32217133 37795770 38008617 62833888 144653040 202077388 251664416 551131699 630253742 806716087 884275587 23 959423421 993641665 992524101 998050681 984437105 976230280 975192996 996022582 963699354 985118881 987944944 968346392 993732883 985461056 980673363 973404146 973246003 976208589 972608452 988098281 980878131 981682512 975780368 997215446 27 891829687 966877086 663909441 941916491 327368572 410270587 972314857 938168484 985053509 907552807 982550450 45423795 981239567 931277440 919398099 912758496 661253683 931578493 916376402 726749843 951173627 957378928 928874779 956078462 262513831 35097231 158217260 729696731 19 606065115 527863430 522066913 519471966 512387068 507484368 505814250 450704460 434186303 413305752 278744432 232325550 198667226 159591591 102396193 97420198 84997430 78480906 54741979 14286554 25 495552819 849587670 875140421 987129797 958686986 624816652 528328418 893644731 734158943 880143317 697756832 576636244 744674538 925075066 720999071 756775962 887571324 820698856 799006197 779647518 660813550 859348064 687857446 531910261 883269972 744217244 23 521006686 754519214 521873246 301571842 521006686 521006686 625101199 521006686 445699129 335886961 791436411 596158363 781260553 794442513 623631019 284825271 552571866 526890085 476610489 97971216 380386746 521006686 740189444 268101467 24 691955277 557054914 486889681 875420256 866937663 693870792 845299253 614939760 473614381 609757993 385968122 555431852 754845389 643222810 749468985 332773350 121765327 137963927 310276060 825348150 896902733 924654233 791839695 96206566 282411715 20 828738511 220013816 921176235 837233347 791416570 977082005 991482006 400589415 842202257 481893691 765372321 323185489 600689703 391180140 861965155 121289258 246604950 590096252 713294349 737387986 307208369 25 46858838 400882092 668147165 618981696 671806172 503593731 673915371 744239947 652203857 182229347 626522730 98117908 550879532 280576998 210129499 315444128 319859251 422216819 389970154 340393907 188945140 127829296 220633389 569068565 611936194 58881260 27 76923076 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1000000000 15 470636581 436792279 407045096 371327398 330576778 327502304 304617435 290370204 290230033 282231836 266864103 245028866 230653989 128971779 111972168 28298414 26 81591027 19386976 149265490 122009283 26973262 81591027 98554318 81591027 49167103 49664908 147750528 119582828 96028455 47116870 78890784 81591027 55701129 119010783 119753038 81591027 89104314 48368130 27371655 81591027 124479633 76612418 48619662 30 274987955 15616523 27675564 47149214 57406110 57422720 72635372 79722589 88834996 95765945 100419197 113629699 128453747 141281311 146743145 157977964 169901767 170953394 178312065 179697596 183860963 196303802 197786781 205784589 213276293 219493087 219982810 225925699 252186127 257846984 258969559 21 903538318 972528343 98611180 250109970 921777329 39133393 991915620 544494187 947474156 958840513 948495870 911186565 599119300 536242536 937150426 936846707 592360022 384964162 355688232 242082323 981515269 972934907 14 928553244 942600423 954012052 945426291 948411857 954524815 932104655 935161574 995849884 956103366 951117987 946346059 991638445 931918532 968421615 22 571340195 926159315 845911210 764736782 747694595 939140034 577051238 931473428 602643720 878906473 604963042 832036393 723139005 621378858 684981272 869847169 661305843 646201024 658615448 739742777 689301183 600411819 761691814 19 662080585 422213041 422213041 422213041 422213041 422213041 422213041 422213041 422213041 422213041 422213041 422213041 422213041 422213041 422213041 422213041 422213041 422213041 422213041 422213041 19 169598037 59352312 171105147 90338278 213156071 134695495 320862524 284366521 169598037 89534815 169598037 50741907 113111185 138141237 125270161 230810876 231520957 55444490 331864916 242849737 24 301829553 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 637056737 26 526012751 89202212 189984116 206805578 218077819 314604178 345044241 364965648 447404865 452750301 476193211 496459926 526012751 526012751 526012751 526012751 526012751 526012751 648565974 697535605 716455901 728043414 742268785 789034196 804436135 805468029 986954886 29 273601104 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 800643488 16 839215291 62955558 215782215 107973391 304070017 613721664 544304561 506410610 411257895 197708598 548779045 772287094 355213031 170028103 541688471 276709967 703723012 13 241128569 324525383 258228619 295966825 368465409 130073804 72631511 253896184 269601556 269309311 228360954 249609269 351219622 62782950 23 90909090 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 25 466095635 984714609 972976594 951368271 895556012 865391697 860243474 842452473 838049152 787001428 777113345 773036331 769366966 730656545 704855831 676936213 653468013 651124909 628131334 614211701 595265400 550979966 550487556 536063824 525368411 514349979 18 111111111 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1000000000 18 999301071 999749542 999640819 999821229 999353935 999426271 999766020 999367100 999491044 999460110 999435026 999497062 999368135 999727172 999760155 999346601 999810609 999703843 999568957 24 256882507 808280726 895649542 605395709 258828481 556480099 322861885 916995330 718353155 863518698 764298511 416735053 405875311 294325778 865311105 294910781 576000035 587778498 268335978 693994087 791542582 439842545 694759382 908063285 566778781 23 629898772 726158526 920337038 985937801 820764063 873239863 916525121 846824013 769270971 998803525 872241447 797211388 849401582 632765486 692009863 726993439 639542364 814964374 773115066 630020426 873251211 862278773 643758046 903887655 16 516966552 658482378 415430299 908354374 381268226 690820134 494368833 453934943 516966552 516966552 276034034 540961085 505639546 131442991 643308104 590376392 547110389 20 342258928 503847893 711100811 131818354 796701942 544830846 865734501 696440928 323686249 320048899 339111387 714656727 481204210 580703778 18532949 511976800 838171390 15167660 241350036 208447452 790077153 20 706992101 135533428 379825277 456205609 555835328 614538402 620993724 685781721 706992101 706992101 706992101 706992101 713918820 784353004 787950681 792108234 921041564 922606708 957778593 990463795 992938728 31 66666666 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 26 664741432 588201868 576559253 566098814 565216567 516132771 513308837 479619254 466242902 433897188 420208110 395873967 328961842 322092968 273806603 238556325 229792165 180241921 170899315 162414553 124365177 99646736 70619752 55786800 37106603 30077604 18315467 23 213019173 194969230 144290099 150973700 308586040 209264491 390065724 277515706 213019173 213019173 92241980 213019173 318327094 262167814 325558661 124390380 198280699 208037009 213019173 17234941 213019173 285502929 69200659 257737958 21 100000000 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 25 130037422 931731104 920601981 853373358 735493843 520667193 517725229 487985047 464554153 446958746 399452565 319317095 285353203 264661872 174994566 159866739 120386947 115679118 88759652 81498902 44475468 39355157 38547104 31490821 30671375 3338114 17 125000000 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 23 535973371 904727514 826749037 826582087 765654298 750330888 692146170 631740036 623314852 575417082 568296119 535973371 535973371 535973371 535973371 499487681 462358699 448554247 392546755 337483218 287356625 281894503 277662402 31191836 17 125000000 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 24 206808722 863303155 360162684 624703800 359099999 319713482 880468201 255450741 237988772 254976851 601641600 642579129 579886647 805376481 942281021 458905939 781325241 633280607 825888382 915241893 302665999 614476517 905358840 844392836 992970267 26 514401830 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 62658471 20 271497833 466162804 580309091 543123037 932601430 482084538 412767052 919870470 956361632 334052248 768283974 748086691 415899630 501907971 522596216 570936737 555318813 793541393 529883790 689942806 882329934 13 166666666 1 1 1 1 1 1 1 1 1 1 1 1 1000000000 26 100064450 999264559 994372037 973949404 967402519 911331005 857199528 855670464 673401847 671013720 573312583 567722887 559596003 522541223 487719815 460109149 457348601 452997958 384007228 357141495 355559114 324480577 287991599 265764480 207363357 205492570 183403774 18 795782921 795782921 795204524 795782921 758536034 806553392 813274469 795782921 795782921 862917031 795782921 565155111 795782921 795782921 924524128 795782921 850421184 796230887 785012450 19 678698965 988651912 971838499 971622424 968212879 956497878 939410072 896418138 890667491 885352693 873787862 868108454 825689792 820126193 818591856 733071394 718563597 713708985 711752001 681643329 25 216998600 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 975079536 23 576207899 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 689546873 19 334749113 590850180 590850180 590850180 590850180 590850180 590850180 590850180 590850180 590850180 590850180 590850180 590850180 590850180 590850180 590850180 590850180 590850180 590850180 590850180 20 576352732 130536999 110552673 921036142 564431674 679715078 296185757 607672974 210702943 977230877 708619935 866802270 502045359 980179216 867826259 898506953 962383027 389489025 71376410 168871378 634207525 19 831780864 966016405 886523848 831780864 929956983 635934346 834266468 736919525 964176060 664243489 511894848 633758413 926642203 831780864 993238173 831780864 831780864 831780864 999318239 962043096 9 513324859 879617019 671715505 671283129 535416652 785582054 914052352 523527258 844728315 826545368 21 254497336 527283105 398346199 363431320 776179134 551944259 551551839 259664067 872986362 859678506 997335754 364618575 521677397 589651916 898625676 491245471 635077010 828338737 556292320 843336785 551535807 505068101 23 961107703 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 75657366 33 67714267 33255744 16748837 563361956 7544239 767199977 13897711 50090670 287599177 232136327 499241593 33307322 242862210 11587057 55899740 18461688 51379903 668685751 431602053 936864451 522881508 230361484 702912931 15133276 64652758 727561748 518615794 11832292 604240475 570491901 51324897 762591363 867961527 496698139 17 125000000 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 22 313837009 59128325 89244233 92447162 249581386 264910292 276975705 307457811 415791723 420037029 527920257 556975256 644403558 676112546 704088663 705769483 750075775 778260124 857330305 858507548 884889967 892648393 912895791 25 112910695 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 289954178 35 377900361 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 344369296 16 195811637 354064 8146733 17795640 38766604 46018995 85991636 99675693 124584867 129835956 131076435 143650555 148300100 156702227 181846265 182320337 188603538 21 424431525 56146320 323900477 116905856 379137829 269594216 406351958 5154482 38710136 204868432 23356948 380771017 379697154 231191808 416436550 45622621 83904809 352733130 216604950 22153628 315468166 91392952 21 918536746 933529678 934907324 955589843 976780518 922082715 962044289 973114308 977226605 967892039 935423921 937813215 939775172 967132426 981390101 956763716 929527098 961612407 971931667 948738443 992780923 976210868 13 166666666 1 1 1 1 1 1 1 1 1 1 1 1 1000000000 19 91343755 83089110 101283290 57576107 127604246 25930454 143859618 61821375 65200370 129905382 91343755 114341147 117256232 98535151 30366902 75514868 91343755 147931136 81284692 91343755 24 83333333 1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 25 427561236 54439537 99148536 192749380 302091587 365034313 372103513 392969920 415668065 426076175 427561236 427561236 427561236 427561236 427561236 427561236 461536214 477641767 497733908 499498378 516511068 569427002 580104331 584277842 640662094 675989854 32 891636535 837320944 891636535 891636535 967580676 865134689 945952126 891636535 891636535 891636535 891636535 815692394 891636535 792461726 891636535 990811344 900674021 891636535 891636535 882599049 891636535 891636535 891636535 891636535 891636535 918138381 891636535 891636535 891636535 891636535 891636535 891636535 891636535 24 426571471 447915911 909082538 883104772 540113529 671780101 797187991 953615181 544472691 700340387 587106673 807599954 821150289 763602637 916315251 784889557 494793181 794177351 496740986 938249150 475714173 904605839 836750942 446802256 871891152