999 1 20
770032430 298850322 436841858 858983233 582787681 514782301 15205664 168906688 232646110 943875647 47570132 695437720 998227481 59356243 133439096 188375210 6281528 617238013 167805870 47968827 307112997 493471091 582465460 425219 232013822 401832192 77276372 480727034 248111408 610117280 833798982 320007336 623739760 240747324 783422440 830802862 764238019 995337098 359743445 996468362 622969818 805405407 949567681 734565057 959397554 790046791 427214811 762539344 469125385 567655302 627656035 972256425 444296227 206474995 827191949 615212933 890429926 763870031 985614117 609321534 460724170 184566077 600806578 793544302 650973055 354657484 446839706 124633227 63309509 825137818 758088409 627970118 904081529 972265982 705597250 161544408 207233589 399636274 449284945 78509338 213039951 260074081 877033084 221241019 677874776 675271977 873577111 207322591 224998808 137277733 398309416 723412901 50815952 772269612 280815343 894916637 410729467 254994078 662538699 432489084 287370585 768186826 967097349 449756280 941392171 754621422 536639627 392791635 562706756 960053293 762148289 875930761 664667123 837758227 97864403 296528101 672716432 769250518 710597254 211811498 623610515 957415623 28643024 543888621 89621015 260684712 244417326 876890728 310579791 709508455 386553638 653182403 972069740 924773248 426520865 355257808 103794781 541455479 906227713 205236214 833582793 76264627 963725899 647669350 71770526 818004328 950276288 864763242 674283561 205138446 958166499 134144457 148711029 333943508 963858787 241512213 438749462 945790060 219737198 268309136 91585738 53518397 543765684 684207969 207192477 588698260 739048975 217292047 931864173 129843463 606557874 423453033 408344315 734500865 823509405 46127801 864745359 596323171 15622173 586598165 73951550 615987922 809878083 791285633 142622496 919618161 229711741 933070560 348319887 153951292 213962281 430586303 263531489 144844052 562746663 708330627 807710369 535513300 77471780 271756113 328682138 488292100 839545930 4295156 159598392 239365758 405005151 101065821 240278680 638213295 327424352 224488483 870079127 139729444 242643454 647780056 965306270 735321905 82275290 1894922 608998011 515414803 41707746 71384477 961807495 910284564 543666431 917814247 689447914 285462605 646199406 22507390 661574566 14723876 818596579 723312776 766392517 507393704 267002034 72259956 324281564 975054401 298219053 879184830 293838027 561664240 207529826 794496949 988662969 884985205 367699139 786019064 762881958 425675583 908352737 206093892 234095816 731827544 507267502 511800788 291327177 356747297 632113954 678708198 140913223 701449758 962317261 120383189 773386864 8027746 82254997 370270682 281303816 566620932 884037398 59877304 694948176 956252622 192121028 789642908 343217435 945667374 857855268 149796308 790254895 441925398 47732062 974045676 824493789 789975375 147669240 602747614 738977937 792872772 424239390 949614519 33985728 680151943 548173920 269223029 496507098 468608961 427598539 243789319 526598889 320582431 548513138 573825291 571259869 288544197 463874075 166134379 261481621 942634124 377232504 724294751 379105737 734391554 162047327 5987317 823890480 215895134 774457874 941452082 930750533 628745200 105677064 416760071 468280330 837525787 582753045 53385126 283577460 336836657 955027489 24955061 78972950 234071737 588128917 421254188 230217824 294405100 256199380 752123703 402186432 287304374 437128212 308789612 752799279 564089960 716128846 615058016 701222228 482151608 720346653 276262084 918761857 576670013 590383523 442532751 701420800 975279217 148802870 936432495 289015409 990144943 56814938 61961640 265327700 646326873 324262881 25936146 179663750 598996014 58039088 432983915 73126774 661834685 313692867 481364911 230689678 243271499 899008787 643690613 347368798 459088064 819886750 816723732 469112536 882608641 870181866 76553587 560949892 389562491 51569447 101731565 587012177 568683992 367646457 247515196 220135170 174018943 179674299 519259994 839908524 278223687 562564256 771332685 399171582 112763867 823011115 117293299 920664767 535831930 306133657 590844818 557085015 874771152 169502036 503143739 207707499 704005782 994132394 88152102 949734393 500623903 307435313 154259307 721429983 786271961 216518975 74637255 371107628 345953420 814073131 265310081 86332409 685733579 78573505 582070962 484088432 78927622 739960335 867496564 248265599 73239312 170243602 852407020 63000727 385719512 403680970 952184107 349093105 813559140 794298716 998692098 15382661 905739724 526663757 744307748 886445013 261666765 223053391 478382137 440052687 939714529 412137964 273748349 175947180 594373302 811495390 389840375 628262478 569415446 954120287 664104046 42028792 266923165 349226754 897986609 730051038 913185883 206907405 118395965 262953651 791158408 197530465 132767258 646175495 259576012 716790921 254080093 545020906 690337515 616809162 166873437 210344843 968930732 872897647 28749290 877476377 750827162 477841237 427652199 651431130 504500391 929662872 138064064 550815961 939927098 322375544 386151293 611995586 432489685 670166468 973936818 274268931 912094125 109188599 257779331 739411922 962340767 455168701 154674215 533147294 615027366 241111642 57340296 277931507 408749644 631101775 129171948 996678656 383672508 329987318 806251959 430536083 491727475 525036156 618185045 197310411 831806618 183199856 913496987 422153773 549963905 402977790 377984727 275294087 912394431 326356295 306739565 168298048 162055296 659101745 474609405 422428858 255506433 741260131 264924519 922445564 249329629 364599193 492578460 219118271 167315844 315603998 831977661 427811670 744386242 824568772 780485746 244952216 667430907 964835137 224522786 980375737 694384437 326830839 249647582 262440939 459861871 662470434 713271257 426654020 617501046 257128330 262049547 843299963 919633245 476037482 89557195 631234562 34874943 26645159 140463204 364888567 611351184 169177219 292835391 825402732 963622500 46360271 46221856 784203183 470114041 608186209 45649496 865181543 536643925 928860460 956184482 228613650 934333195 883258719 379697577 510099784 41865741 198444229 638950578 483530436 592395317 286588857 697277643 932807880 53862856 516287332 146198647 167204568 135579928 100029486 325413922 754818356 654943060 416149149 317675361 253407041 285531763 391943149 238382576 948667159 374565382 835632933 744947457 170382448 490050286 445291938 845196783 705512808 741031628 176335809 441858746 931379387 262829820 203529914 894705747 609003998 740682670 789890414 831145080 602612374 777817514 501148445 461891652 796249787 189247540 951916718 23602960 532101069 815729578 252839620 646170899 319345374 866885298 584524325 640761326 812826699 511521831 472994242 260895010 726143541 119844510 3650975 245184171 608392268 445855737 679161321 600276845 125397346 673540749 873736694 231067406 880815517 314262642 378741140 682011163 186174366 877053184 499551734 761087945 865584024 440716675 913095824 186741854 559454332 46320056 817396215 752839888 517494342 29294047 11399345 168618081 852342840 159828867 525426074 118976057 766358796 878895029 171887736 88868593 550274812 845098457 206440560 372823167 602135754 704412075 761727403 988882440 645841317 543875245 94082326 241914528 655171802 335350526 890729644 332659278 840041497 805991071 716375125 242737213 597926673 782982035 246555857 191328805 999516110 232920912 382715545 174524535 445967374 196933345 500901904 893458888 102844732 687757274 608479936 210333259 148747145 966520672 866910817 307662707 960403959 230514599 467918473 990069645 975469721 760650849 229693471 981319599 901094656 613056247 468685215 857503466 456705521 440906385 689260667 451266980 863276293 434875742 592873639 126849974 329916530 897511409 545263850 616669426 907186439 934185991 28686396 197648552 349562604 59397664 29411604 891513029 479350528 927457014 928868383 568202491 946140334 262359139 401678712 293838215 284769498 870902090 4936304 587217104 40465894 51737035 451510865 505930847 279099823 527182822 297626914 219458127 248786106 257276832 89729435 262809732 850552002 749215878 803786846 159457346 708855456 692923068 35865931 809206843 544324188 787212370 485419436 487888264 727618901 297918368 543009982 996761819 39813153 541563848 362006832 745240820 717599746 462764725 484485015 889546006 992635059 58859848 107516567 706861093 246260479 186341881 697332472 581988944 92306863 76113380 56127902 638032471 26391169 967509343 766109570 691792813 265040153 152215597 564324440 391591514 8937963 59692615 573095523 22392202 6575586 682744434 264912466 447649405 82833888 153017282 976954168 723226020 523133263 271544689 312168372 985223305 666882195 342670925 395601286 335171676 778744133 577047225 840099088 254747134 822091428 492879370 104819691 776648167 764489587 922442571 305616713 656419783 259495764 209891679 917878692 747063229 283279022 914353071 415817208 140904404 630376280 532637225 369935091 894782917 851072842 176003504 747070296 681354992 965916953 309246879 937025923 373480571 558730982 240262307 123593912 259853535 342852481 506351252 518946557 363225068 880209818 466074390 722094513 689210571 812641646 30860297 416442321 159695457 592261918 701891631 929835448 695193807 763884346 909940418 868669431 483693856 301384770 489045918 470411380 855157256 426636337 668857256 526831553 790072484 465287339 957798196 810163002 325672406 895007518 440636840 954595581 482514810 496923949 11562983 306847784 532028878 399735479 454365188 187543182 532845950 104326566 766962158 948870347 109741298 472991795 662148138 466084493 783597814 705353692 153596973 546327211 185707527 938641756 494439331 439491417 793833679 314650030 198769166 213759545 491290389 209256584 525332827 596070324 53855771 952060613 25955992 202199048 597177217 714510588 787579654 206170229 494172525 462797286 280531406 911941390 948696027 559647162 240747782 397237165