895 1
85250683 572632877 582935309 198388837 662775052 785987393 488515548 368545034 369689098 391917597 783690085 925023884 103664849 87840637 96685864 588028495 93540476 505872027 401649513 677274287 977271290 127769768 15561704 553015247 742414569 529329566 172189782 947161337 999380463 840106932 420599516 696647246 339640435 970461852 997564194 857480698 186966659 62111287 423990365 87936865 270818120 880807677 355767089 785602591 803391308 282532743 453622624 654438008 378160275 590780072 475191770 592870299 45594440 859493045 924970912 188365 902851406 404517623 918999883 616146420 815351006 817737648 436334548 419388934 405270080 182738981 493377294 83405716 873124715 981601987 932331891 677703277 203792420 80895417 983852159 954945794 275370028 37870526 179044654 720746553 169450106 409618414 283022033 677213853 777819478 255296878 824382335 566344271 97396373 529544380 222566121 902709577 23598884 428695761 233116046 736967798 996342363 473400660 246960018 772986332 879248200 789520328 854773509 822323698 256924319 371624405 378931036 489950468 757787206 541528093 632161445 752262138 89162581 550921120 188682037 423913360 30690506 632395709 558506720 516982137 193880328 62315442 637438295 465520044 729829164 427172676 660381625 537110803 70315048 827503316 24051154 244438979 991918839 141998640 755616600 215223942 853737686 548009567 87704720 699867669 213032235 303581729 886175266 334854265 990677172 355955129 649829258 426157889 287068507 33526624 122793333 921682712 175726814 804947848 165425913 753789572 36537135 273860594 113456514 31447253 314950621 425237789 913783035 511763059 510107514 378651904 859590138 126976866 995098925 548555820 373421244 909130652 6237384 453618574 384945151 856979070 16436132 581782277 351175297 787184258 944280260 335919174 744601513 607143924 452078147 221495719 878744416 603529091 632562381 674192394 756310708 839989327 480835801 593364863 294047929 482667949 251394334 266733882 163454089 49052770 430422488 517064418 689942411 607571221 404127996 159722764 472556606 939360499 410043125 390999081 687926262 231036551 715245890 755411521 159933013 89262100 802892001 74030600 427223196 841350079 11705236 620903817 333892863 656200412 370100017 212469128 156226187 649926777 496354297 475476820 811258105 49575785 492331052 438478352 134686125 263046714 372668676 190402850 775066027 363621598 216439212 98984326 94069956 990649735 408429631 423549529 967037016 511657579 319383078 151338 697840487 773051282 384187974 135748928 27148682 889255890 176611155 365484970 136835527 943408610 714216541 215956436 960167578 327261660 518434135 916148809 854693762 829020392 390807875 490673992 176354765 814815937 595570236 330859651 492467116 125774395 947321352 684157070 494234267 606149093 295945992 345729352 358398557 79445092 650678594 343140696 56520803 212315669 427824905 716656178 619356581 606016353 609707440 350007666 526514260 778503708 380266526 339743036 38186501 978864131 691104477 947916791 616673947 574802289 483314574 822524420 416244269 584300951 414431714 196552241 345252204 809531817 879038414 623863584 78686234 911851933 322515032 56367121 293929865 831305515 528541857 820377000 614354104 719815523 806234814 64208912 109062649 870908746 779594296 578732380 48691825 855161885 463076191 149730971 541552949 715275574 732847377 500535496 965863669 672516932 183601895 68004307 512788098 633451986 583273798 146604070 514012706 268157208 524044669 50439548 236884915 990749385 799493747 482014691 843471121 548748236 870746467 157520222 617572937 966005251 861599423 357850469 145796088 576102768 189021483 694765812 267228284 479781434 380779334 985622803 61825643 321253859 680508164 570037974 516090621 815821262 100247894 200248617 164662443 95241577 925974159 667060543 65364702 502639729 338509756 648661640 165996487 708415119 771830509 23792238 344801580 815261872 45052344 249546214 751731091 782877597 388824375 428932920 938216802 550578172 239921898 255132643 237056853 544794388 720488867 977168068 507824327 52150109 562106661 148219823 326692 853162816 789736885 911253735 381111472 266633246 982727747 557480365 960484784 714404799 330831997 201310785 164497328 29236888 335067864 494073471 449134886 700836369 969851401 111790409 839408642 565340554 996472833 731136510 409154436 782119015 867308856 432730557 260655417 356680604 106986592 843865785 668886540 194487838 694915784 273693522 748788440 309192165 818333956 288280801 161304568 716489771 462078818 941480637 838756199 212830658 9160902 475446049 367558819 834952761 691496741 236113583 816216664 459813927 151739000 478381577 226448363 365762347 329297701 148093417 407131659 722822875 746772313 444704266 815446825 874029139 133007548 936850311 76347775 563031370 777559587 937098821 58864530 394317279 480723146 548451926 626350732 540948484 905048694 380362363 975221690 912309296 118393155 798901757 394504921 132649796 433000984 300891688 230578916 211707357 303481782 727693608 113179269 417202766 192774232 876220192 716812712 986035098 422126260 57206329 342454579 227186967 505862928 2323067 672426356 651433605 219843680 907334890 190692055 887257114 813969247 606658031 422017321 277622567 349432357 277216612 229504908 658040049 393318456 61685431 948412768 866416617 88800481 41644188 816705798 672752409 778104413 131900695 701043569 240040191 793481227 89543246 606604661 969519487 768096713 708885891 790404521 929358016 472887030 118170404 959726183 743462811 152582384 622525627 977808197 471732066 366149340 70163521 711901377 474183327 127924961 25435934 636992112 690929961 49942317 703228097 194780620 455953388 524486857 574521088 175947778 624512307 37025480 467123342 316863698 12621704 955469807 37730318 190261856 835311263 775550138 392346176 555709932 477547222 982699252 382449327 814316929 514822085 680303356 634042815 849745939 303510186 734254807 424439991 567743782 484485880 622845374 430205918 546267068 914387715 898258852 787947933 243335724 407037281 75909559 38291529 950684906 590497997 717100299 319075084 161398436 137758529 389473236 938195856 99046545 756650864 3802 240309592 465631030 23884499 321522125 859979653 650843227 159660664 427249330 145713165 375130634 891605503 208134066 155642437 566284809 280580821 300436580 810551014 392863303 790305175 62546500 446550407 956491806 369608769 456050495 402703096 660416610 542093555 975078231 329261564 515159290 881332272 474178058 553403766 788931628 67204343 21670311 406239317 335599923 856779015 190083192 851021977 351916848 735546878 113415293 202679807 462748528 65026538 845293871 604199346 117664293 683684483 938807337 72813882 112419883 479406453 197342852 391727721 314439258 47589675 539936827 365213134 318970680 7756927 913301246 319184869 256745586 796284272 35522210 789641780 57879718 117921477 19848510 1260345 941075217 777554974 986447221 669828840 89566480 708798576 197899100 103731841 926966501 501047238 649200397 49520388 448653606 119539070 550431332 172898393 700086236 289021746 764481222 76678914 566161926 750335947 729739936 822429693 596841639 148700300 658508701 430888479 244351941 861220131 786710743 136795481 501921655 346299114 661799296 488042416 347620895 268599279 373730464 857267819 911255868 130049081 521475617 492113443 309567340 182355728 46220530 659588666 330561406 422965213 349883710 420993026 858037322 375207878 422164799 985811063 491610390 214052218 666654150 218425647 745943382 333591595 276633604 436474055 690866452 648342925 928867720 118395427 785090226 663166751 531074935 792715589 249960954 528233597 135446219 576356820 786701690 554038616 491069442 934113011 287058091 849877326 428657540 30317471 729501008 682976537 224041332 271466832 905202120 194246330 450343670 217234937 966396020 619069647 473765526 794897297 393475380 102077974 588936986 962068851 83233827 430334608 567978267 6438454 805978920 651823663 520426172 363885434 809273150 804163969 820935812 143236087 309960088 399413942 895741356 336065564 316881582 587266706 584509263 116232623 36081526 458913075 130184676 531528363 90163362 799947339 578655129 533293653 342805752 791353844 215831647 977040050 46317418 461104020 586016945 518417848 85798572 196891656 380436490 21404277 162684516 699961249 880822756 788035913 108557208 433721257 368858317 680813039 637906746 897473316 129224412 310835731 517789609 71748550 446155288 33935635 377815244 155060721 808246548 788342370 413489359 239691736 563041898 730614313 76611853 161081439 962460212 333075742 854064776 895649601 646455674 879403676 847979373 787770694 960865011 870278096 623874685 662202562 818134947 938331986 80319983 411221468 581713468 854959569 308884267 669043134 868992560 444093061 362467102 88686873 708925973 556435194 72563340 510192141 209274909 954701704 796795073 610530963 120659590 850686465 877082680 407704251 315391169 104779998 238720856