995 808 294
326023328 426475772 299106585 602916010 626483869 199900024 936049674 410557868 128927902 841710158 823344262 70778326 502651060 539856934 967113205 189158330 159371074 258299933 82280789 87177118 387828095 739172419 391786424 192741374 776227831 551167006 293007556 263150088 669835018 333784358 464287025 869603870 913546092 177909063 388020559 300245592 616318115 554334562 315145085 289143039 999175565 578163659 565913779 166693651 189293783 391893196 184455417 882151622 201796486 921879329 976588782 148405247 369894770 273511035 403079490 33803481 530307526 41713661 946008891 335320609 69070210 304345282 430555956 427747291 220309497 665569877 101492762 25567677 991058259 351636279 228621038 616722866 318496012 889045852 463306565 939070040 239453299 749268654 957285323 461963651 587263788 108361097 279640251 885478072 629884335 973158717 845465193 589931954 924157895 795233424 643613624 57347809 828388115 558845497 90828964 995537382 682418568 687983974 679941818 141199385 568167405 810710071 136780699 736683267 64918621 264835648 5155709 18477284 580562633 581381387 995966377 74700590 40754548 955572884 965821694 480127751 23146357 559905739 9782893 701777356 217102648 255507733 839786363 519213961 682887421 894996172 944089794 2002817 610909016 49683386 273806960 309847724 526060975 275264418 631003334 616233012 901880511 220262840 729246874 235281911 707426072 388267811 699359701 935316232 665128860 723023234 667113462 319588910 678481412 613926244 310265998 665355364 759388507 731954382 208316866 207355223 649181825 921456058 473732812 487209963 172102825 581121170 366459002 742699703 710032859 534308537 270210478 922633348 900452211 676153602 321796572 973864657 580891296 775463991 563835279 9525330 655886566 154232211 917772004 954993517 834502812 561784648 592078860 792903867 11637615 765037819 618828239 99309965 202604253 880211523 318093316 905433701 328799931 416783149 554724378 279074680 645958576 686775995 789739923 288953651 615276471 316556128 956077187 817286323 494270113 487134085 691699221 923787851 710417041 109928456 58855686 163700738 778158718 622265528 315336744 495003666 209967796 888807130 147430113 295581035 913297235 305037735 933889961 585778221 315052239 255843019 751256720 764675634 536191086 304747240 794094005 167636354 985156813 488218129 898276816 916568284 388101212 406060111 365011113 677967412 975969245 761054752 44221854 311732015 873632489 770279155 974728225 902306728 621666411 250603437 187406904 689155631 77784354 828815655 562785020 177115781 976876579 505594029 369101082 906183202 592332118 907589760 439143765 644010671 350250484 539636821 665636098 359973004 359845135 482216405 253018762 814131531 516141066 792317723 624956907 272383027 610824989 227436857 473948472 152514238 278094290 423305907 509579028 321982235 545473931 121897473 29506875 312677549 368152057 856653330 180277498 174051465 126644134 123674308 400262578 638164476 701851245 47136109 416287577 223216387 79569404 696608085 397547256 110515410 367922265 614775353 594058542 27273806 17206874 595281610 838782635 440864914 342445099 821069100 733348534 171094894 489429452 18491768 582768040 14322147 555625361 470695482 549165935 782744232 814912672 960545011 636489740 708801192 124710774 134334616 668707349 253297538 715734115 440581137 568670516 414684680 112737801 704066747 82951333 145388224 963610593 646855911 982022588 133269094 396432566 706501208 551866461 948294248 414248743 426409161 968772994 503857001 900258857 827410533 361886137 168402366 7510403 187174989 875677091 21015540 847370321 132389142 626164342 53391176 879053186 605303112 576700028 826511405 624347738 83866080 839307666 895111882 749926640 684103374 837159850 952364409 853238961 604895096 9033545 716946762 856038107 468510517 52484106 930893950 476271363 550992851 90357529 598797580 327896976 683083282 200289720 593354527 734190141 439689255 935954877 777221525 378954907 814342714 146994706 768445570 89738892 538470120 264747316 166475691 285253322 699719105 318234549 998765324 749783902 252660683 422787771 146920274 999808041 390946301 460594814 839495266 153035102 686746565 429724365 730833872 88237062 41129859 482844554 707290985 55776891 236327692 234391337 858700202 392501485 104591399 101788469 756919366 635901408 85708051 322375884 960120483 900776620 240132864 562601246 203466333 803834364 791903889 613284337 181091266 975407183 565405792 43395616 941218389 200010874 298884474 333795863 851106124 52706341 251382751 175681113 28642322 649894473 605623555 605044219 430914757 491716024 588490320 830959910 358139577 271773589 186516386 43295640 227581171 597703640 146749897 751578916 714855086 562111947 567609611 392016941 475287514 989537423 817965983 67011631 857147288 362619800 795954226 612688439 883249855 983270701 84260966 457458021 6499930 313458409 357665615 359952241 656245288 455776317 529954292 322610468 479517467 490917611 960539092 931575002 36664281 955658636 473161054 778345223 33553726 841242124 113731703 348299951 964760280 521652777 980605176 890401771 880393066 832054775 894400814 717600363 797824874 682896478 759338585 871674351 230869378 623290266 209581357 172152013 95644946 633979323 906563667 904700527 50075820 11000611 926891241 793459153 392150167 236898570 573184254 652495879 626615630 492022269 43766807 348933813 54348798 150463067 675306413 583612053 302034699 161752279 343514029 358035957 70400651 987546361 728008950 4354870 740602569 241633693 16133086 161512270 533174980 904665458 329719982 815854151 112427693 583453051 85079073 473458110 289085037 503198098 222044649 139319141 407042076 265499360 717776170 40264065 695052939 640759911 620311805 858184556 311312315 576472952 19152111 793049108 431596388 402336829 823150463 762214010 806166383 408802864 473644195 687994421 825259644 930616482 843059268 35867116 227798109 572662581 709990589 399134175 415372441 490487906 693871968 919095903 372079850 845979125 938027249 452400722 188233151 399637899 919807529 76781488 174837435 860153627 839102516 467162120 104626996 479498602 270480691 419736316 248118965 127575189 541008571 422423744 505569148 593435275 212890197 216869023 613191933 464639889 797691900 764913014 14651997 176475324 854260898 370092087 878767863 12690042 225532075 396723304 968722139 528056586 919442543 647886497 686050634 343794431 786009276 851760914 835247419 725400513 904499539 938010618 884240858 820645899 479254375 795074609 239272195 605669486 669367841 660561823 911291851 482363853 281027358 774372290 142674168 8995807 556836591 669112877 156592516 423014321 406615959 948976899 402999582 932386337 306487569 630501248 701157544 837612644 162890184 846917744 469455034 746807424 249752349 996747446 598233118 135700435 176149989 719641031 732543058 494455690 929077992 586525740 107974153 463842603 516086115 902999556 767287722 534504716 720752007 174973823 337775055 404756697 447758072 52872548 1951176 369945106 360356174 794096524 957981718 86234762 181897879 826756452 814108912 14186217 205584339 857858671 537070273 888179499 341536119 303650498 326900391 66912543 806049771 161291143 261536502 262325482 680684044 250441082 223378355 51557249 857414570 152128367 470989594 527873842 683928075 672952010 220549657 36887068 947322471 67540485 601356498 139535538 149040745 282015534 208607005 77872699 718844596 472790118 924514051 325237589 347438428 522726499 819842372 600767598 877614185 136926959 515729874 420394058 282537560 608327526 32951892 173910144 893686425 980294972 900844708 667609597 297588242 763064437 79172945 238937983 227184026 275462699 606975518 246515226 487997567 299579660 985984129 270506423 432489217 680851418 813136933 668986768 317958356 113884137 502389608 314888374 362651554 143447459 264039902 338471563 932546951 682361607 695710412 879003976 662459795 229404198 971571118 241474168 416868940 699135398 863250097 72674683 556095017 25867583 603258169 308098052 220424728 425582144 845138013 753872540 69343225 810967050 134057318 540742429 728645408 422130324 990264404 392977719 131238103 298780902 291992665 334878446 137393369 815468446 62918747 585684250 61494745 531463022 382402422 906615781 690086905 117482395 271249272 482224977 719898963 487168640 413310820 666455472 278712948 290779657 370673136 911306282 664613083 291577913 532428806 343979834 237571967 377225124 122234694 600835377 687447366 520758261 977587331 375656626 318081423 289717354 949617730 973993780 498805417 97199699 659560254 948049284 813568089 123412886 882621159 805867072 656473688 820547374 297401821 740686428 236959955 156980135 235801722 259854753 695351530 656432548 672359750 584025897 244035377 385471066 105842560 644803557 310045233 297369106 548081052 61703447 792949480 29890218 942656959 241256664 472107333 653318165 337791045 894068371 416196269 618552022 666144316 416638856 618267769 792181385 500947942 616689482 359505014 817802843 142797115 426590785 703453539 208715661 833787493 180219433 879919990 692439029 780624450 698031249 339915480 958080124 559438565 995844957 605798948 309443489 97261076 388288325 628239084 432473076 818315724 516116052 752042036 225017500 343314617 500639849 776534773 635250642 935674559 688868281 275549339 346682724 199738740 986346827 248264584 937967411 126400675 711175035 848303503 743568821 488454346 645327991 660911225 189793907 919908252 674453701 88295043 609844876 771288705 679449531 323027678 847189297 618150161 929577478 641263662 247871015 651431325 461419044 66307852 737480776 297954726 820356329 272949892 91021314 956481635 694451198 501844120 144429014 815647040 241562717 434400955 407696090 667882586 573276887 271703638 887557944 688539907 108819086 574504262 871280813 670992964 824302459 661128284 289423626 969238870 956401385 260645852 268174519 447283240 132443128 437808126 568539435 354967005 757538843 393449329 554871157
262263115 606759834 634852819 24843446 588489084 608042001 289944122 262337700 573229616 175375599 191761838 915782665 912866394 752916472 987396012 987116866 815441567 533180868 964892325 798459073 68394458 507922493 620208252 401915276 89232795 883504421 335655692 216330171 123905699 641597070 41019040 594663165 415264105 164155744 217771129 127475988 993890968 265623510 934025036 517113428 814697871 923081217 188969921 589555240 899245279 969009220 298195701 859672974 447597265 521989590 200171769 636295574 975298526 1709891 440222544 877999078 362539316 382453483 824635765 790731577 331982648 459181442 57507155 535987163 300120062 87522446 31914955 98202159 497072595 353063661 381707057 39328041 7556532 59379532 614810575 629902549 159613396 470037168 213808737 619298510 278642202 125014257 549741208 196284615 637382816 409639226 870954903 890122502 415226421 725707915 400028281 654379748 230761180 706711607 910372041 764321614 94278219 546596454 699344136 719437639 331568237 610022548 449936170 292456036 126359009 690883088 237423385 750546254 671284344 31365246 220082993 985658948 393033146 733887062 384734914 577013654 494369122 94463330 170231954 167234603 638216158 915561796 337545048 290699772 856706768 222495214 343201858 971975318 908964751 445424168 560155504 692377500 663440807 982685197 482555510 595819843 125507925 966407566 181342430 127785173 5078539 562889453 304496804 591364911 344589042 660174660 591922360 91419458 566415203 377910012 963409792 259575445 142310253 676145238 134264147 445816257 685233747 495189478 975019775 213109492 855899403 426408210 77333059 715709039 12805823 975085719 149747798 123945736 651704656 223296773 710846558 258116777 254002126 734307134 980726778 93480655 495712513 3991291 399801 107020043 564236260 533020999 440965537 248336772 862495268 531212545 522929577 521129332 196767397 261823839 834199102 677349287 403839485 474832486 93361346 796914431 352655607 539151731 153467912 471753458 635894546 406739381 915399898 187379210 655795456 719116976 774227059 926800484 317447463 967322299 860115205 673138738 13402147 435715459 98440757 298048057 429926210 512535174 513364378 75582548 149345030 631254425 797481281 38266863 918624679 373644131 330591788 567205004 156469135 863207391 987102414 912728130 541424092 441152222 376397713 908599352 308604129 99793539 987981136 656097583 750407845 562350021 2212317 996259830 196640098 413411056 983741052 99889651 757093383 430228516 801772646 682531233 936189111 56100820 650560840 567149324 951937352 113046345 77503425 432536663 621791173 520833821 270619623 744457782 848419565 343985600 303342531 46389364 967371441 529827831 963910096 334398063 144477881 234807640 447716736 854244759 61492448 421131982 7432119 315005938 168622004 40918299 861860686 11400859 728147191 846683985 60685713 867446334 135060513 629703512 819230401 382962590 726260955 172893804 815740563 761938448 303450501 42435996 81591984 923676157 924315569 900730444 171324211 888368484 938808997 407498932 658877230 519410773 630543325 515328606 294593317 352568695 31628168 556682412 634043281 351930499 120207110 103180111 318174046 362452166 302831984 992163025 524301421 538651043 558757904 789313805 250031123 88492303 555157732 371534257 677276056 422954515 195805472 779013827 407225 404287310 111620521 798140697 56854567 828959089 958784410 424987871 125718534 892924352 682548419 544476181 417113711 318904472 459831333 260303631 203573230 425642979 782404727 364231411 414366212 50235301 723737252 683733566 643387814 753626739 201453131 537145152 695145404 201253367 396812862 837417627 894969763 277210990 746604803 448263112 27803564 262934569 126244694 434899345 653446042 825944591 341918885 313950872 607158056 771398170 333184914 668141519 993398913 827688662 566909045 936099070 791161542 288992997 227046360 36280641 746165388 808375677 636649209 73385351 644289627 407671016 844322379 947215636 935319344 490920195 481221621 145606143 646657275 68880831 57663569 581964213 487620898 399372196 240655982 58506612 869129469 139076681 368925327 386614481 148931160 936699101 285144746 467106867 701683700 27100321 782350570 408194389 270987269 674468716 643404334 650298312 165310645 857671206 96146055 299410798 387104416 144012621 83647422 14334720 262599510 76465011 785987019 544486538 472895965 920950205 810220895 411548650 5923629 809364582 693685339 383359316 871217841 116415290 809409623 872195536 459643084 723327515 439639836 669527995 471029586 744165760 814723882 306657602 135753739 655102193 189013555 871843562 93771059 413174668 966459806 675606539 563005437 120112771 102715653 12326224 349109515 793175964 24033463 482986296 119408888 699891119 746406967 826240152 139065038 70173484 975413435 139473687 590540944 898225298 752455598 993746865 641483698 373587705 566514990 767742261 868661147 628321417 222575758 845973191 519825450 135626497 318257365 548845150 263468078 909985329 430917438 266159943 312865773 55143040 252886454 306416288 665396126 771302247 513284962 591261150 589752815 573846515 965048086 982057288 209406079 79663943 592291806 689914489 888253541 13739800 972665721 497651938 836557479 250194479 257338585 628656709 648872132 911592683 136482468 877627707 37058859 833934780 460512694 558178223 753227713 761083305 710913437 698765153 599605856 948012747 352644891 57027685 482597714 176533712 546327208 920443809 443720666 347344761 214899438 348540242 649000107 488265500 420255051 522663815 735323247 930501922 264430162 928773797 247415873 411361930 300295242 699839457 770187827 214445668 741382573 556666313 938939849 524602455 530655147 849684156 251262588 467099421 570043045 490648429 599250489 812378881 556191410 133802852 897635295 899906151 454007837 342646653 702579141 879210565 908037092 28293222 863504945 780169890 777388091 584073509 406174177 509390110 533487367 649390481 785325190 809597802 183973988 835774164 358231365 809856459 309949728 919363055 645918516 424251803 762282813 952156726 846013923 165622728 825898611 43412944 350280144 238190420 49457835 574095928 983546609 930419155 76452485 852419263 496218927 914221040 62466003 38207751 100352741 329531368 291461660 30924169 517471077 564426253 206191386 220062224 306891123 41620804 351805244 753567292 928312264 992504199 578408997 57339393 951057808 283927141 457733931 8183845 548085996 307221373 774645721 964113093 888070001 708239622 67427437 113090512 719716008 350685258 455871578 96781706 71114380 409886247 773853895 187367691 747421199 308941709 385251087 540618942 97022357 646688770 340563776 871935203 303746934 436997665 318021276 850525709 731099265 527336982 221336602 692960164 340274292 745748516 314808037 940796515 953753733 8820511 47916252 465429211 949003228 178870514 813977361 829515759 54735894 853474075 487925322 628867414 562659780 303395114 435248003 238422557 91334378 704167238 247023722 712078626 418772352 305092263 822429666 352283034 522270196 936345117 495659649 620325771 140059559 961947272 164888337 893489747 728371563 925425501 20879634 355522847 553919499 742696744 24402743 62961013 934943427 302667780 955673061 619991467 866010564 570534437 456476087 605839213 256572594 181807182 105526268 819456571 715641125 276322907 288988471 523203048 114172715 972365241 633664414 416896796 639529924 568857577 792245149 675355091 707001701 245185281 312675920 876919772 725951606 819510826 842189324 670132059 581585876 964224035 305842390 464433480 620952912 216698300 265201898 84473326 990827565 489896028 22744374 99007340 452633510 406738556 770880988 976403511 538978662 469706282 956113588 376557462 896935438 864124295 840030151 803448357 404729266 960060233 949873109 544546387 89246812 638614330 856137424 129499876 282874504 149551799 448342111 137404271 225592742 369070385 652641884 157471456 100587164 694374576 465757014 886911480 285697089 643220555 626577168 665929160 135646179 135304881 548608 366596666 821991362 245853859 339604177 736234120 103368083 830523767