652 1
478788939 34105551 585025294 403641091 49745863 577711531 804602599 56635048 113180414 507893095 305641724 131069100 951032651 599600491 515654449 683025340 318047628 839846612 818541106 660886260 261852255 823637681 949405352 788404029 334488250 63975011 480569599 472182692 347942777 363644895 528355222 296925776 890966640 474396217 37430758 29282346 435591824 787922845 953156812 273389934 502727221 345839949 596572448 185092258 739968250 422395198 139844370 10953001 214980947 486738345 999247027 569702638 321635309 738710880 796704730 972581390 769217793 214891502 767024398 212668014 711409101 384721816 252672816 132383306 359091994 267853287 918405378 403097236 242814025 590559628 424256521 851025709 822810344 300571050 171430976 448479142 928169976 407733160 942798156 753676277 144831486 346410378 71367402 492059333 306478957 743505357 546667630 310484442 957362130 241417405 719746621 288514637 483544425 118915531 887723543 553103466 409043134 786431229 562946799 658520774 748925983 272110360 320599329 684679191 404288217 836797943 589412109 475565766 611046227 669787563 647133912 903369440 171352882 839002340 247392877 650672645 746738511 762513931 622605966 802085020 305647775 547511171 792823146 850782782 971083435 146908678 274539810 244412907 696956983 153762782 503105685 353054056 29133452 866764144 361040699 330755676 99173376 731594720 134794606 305258407 228069153 318203439 570069013 968770996 100100136 905178656 694444907 692836082 993166253 454355579 184825093 927715177 904732091 370764462 93157277 873897805 493868909 996395613 266274979 440398058 34304143 882549291 702514602 956706521 688060124 876137796 837864231 533562698 567613097 863670807 956926879 611913198 1992580 681669869 270280682 315306832 581179919 305752844 540857342 399851635 39341615 478288988 116315579 214179377 775512570 159755813 41158184 936320408 586152759 62239285 33963862 468761100 52504687 88997279 492219592 743138105 429753207 368929106 739689155 217720779 669652548 76544598 966035124 675785971 204936484 175420706 473890833 124085802 503790664 583537387 256029694 938492112 289865025 311740964 558282459 262138071 746957450 904008755 872426665 307043388 893220470 347102529 36505005 954777889 883817008 760911314 936844892 589446815 354692594 724250783 794113428 855108830 255716584 350040265 841491820 546823125 518912486 186006597 786048047 541050125 484389437 315097606 718635298 12047984 492729043 972295970 933995578 747737238 108306539 669163723 20567580 75079865 405559824 372130403 841143654 665530747 198407275 208147354 391606870 971862928 812769132 129105031 832801274 417861448 847606869 685075159 947538279 986292368 418504161 750781609 350228679 991329505 59645339 68991856 905314841 494363155 355473316 773874270 778585932 778811399 795000449 446614652 791928213 645090342 147041623 487203879 188541523 300953742 470902581 609760101 379722903 117350087 569788684 194091449 615670023 990635714 846239446 363050509 224992947 427492147 147948059 462379261 108111871 95711115 638704258 557727003 696916983 655300930 809225247 708067516 252883585 907904640 194019304 429668103 305901008 403492612 130821053 66105336 400033467 275824979 739122255 623407085 641345852 320446632 605245916 839788460 904222715 818774590 119160290 520492503 142341547 511231123 918554360 674255794 565415487 814755576 85841758 242494002 545345763 956406500 584961608 568210831 254127861 124499272 743633634 384766766 906041991 901178906 760225006 746842765 483388533 346924276 99338048 187378994 229271467 165863129 391513710 654691824 270032658 22122940 84806402 475536647 108472509 774817517 407335737 726749974 284009532 115878781 91072461 254965335 566637366 171662352 30858452 896217068 270078085 875633776 912003857 152736234 676685408 268616640 994830093 698255389 899298195 476590502 384461387 9369035 232208758 745268086 431125762 679881198 918419543 484100582 76938615 161543202 110826013 689329959 558257533 267759880 888137074 316656815 788697127 582472256 734314061 308744535 732186218 941175470 994592236 630949705 984879192 186952447 111372064 900754530 896679772 573695163 338681372 762295422 612214419 819819900 569155827 890832933 16700912 984378113 970270430 48784839 401536710 226262111 967326614 917290060 3390768 173151919 965023993 261760053 837041884 107293808 935558242 665067689 295359230 561641823 208645593 232374900 609409634 602842773 899735617 457331041 826247655 784171686 847788080 281197534 858455554 181425840 638765171 487619886 66180676 839661910 852391614 147393388 805735053 185485315 614499054 262034817 478487574 994096278 883116468 629183375 177005415 187947353 769914882 723904039 730039515 872119987 329356671 578994513 353538091 388036054 319229029 571749451 46755265 671021926 496616969 228725697 764685691 342865359 921227234 918592483 572228912 335498514 177601602 707198035 237188358 700811084 857964034 990531360 723217266 272476879 282665223 603544372 561169175 712918378 637533242 661224445 303321278 352600224 662432954 357222435 246061976 303040284 53699503 595004843 181038137 156985208 3861285 951764609 841406690 775891825 286205708 825130247 435784628 407000123 32653383 222588756 2485942 791141513 542654217 960584852 208077010 772958644 565312419 413729322 336604863 473811011 615544875 249164304 338447275 841420411 281496239 221333651 96512905 852700273 795948894 4264803 443073923 759201431 611283345 627020597 781966856 886065969 761042225 504551931 274566295 419618212 145249025 936014761 889244601 929571157 808444153 340038165 39198973 547411940 550003438 771014993 706031885 962395227 332704473 730367304 81860123 596891252 774839879 545031357 729717292 420549399 820612473 699539091 654528825 171528528 19987511 702763171 396821296 255701421 202681490 833462866 337892035 330756034 757467197 687414091 474471808 567762467 376343196 263673894 370175637 44024564 894539921 431878341 656004305 36920168 177719606 568123100 353717324 920597091 618695785 357780402 965751924 813179064 706462085 616907001 648265096 908752199 766139908 896074996 611748455 429891960 369497533 400615548 193160540 961342359 328994590 340383476 890928170 358438027 208600608 857236272 103742816 371339623 945324074 806480941 511187451 269234370 275319680 967713762 535254310 723148727 493034187 264567716 753414129 108644609 96147787 714961028 63587635 119132861 836969034 857698578 736013160 749973038 215836732 418631612 71662197 337927755 827113572 172156223 354953497 605176699 428063429 61596966
420858382 337889329 388582351 582473738 853333484 728644324 317652966 89434814 872375814 386949371 274032410 480923790 616516357 356392247 634609712 209274200 881167906 73391325 822132765 638402304 433955522 512998048 161307783 770543127 605536446 196170305 70008716 592241344 921413347 39396466 453419422 676264721 952401907 613189580 349133889 926112420 480025257 411456272 878593339 52373952 265708470 490317397 259503944 605601765 264593177 493304842 959811030 62389442 967650672 777444626 968948709 539713686 122796669 346978920 564768262 823643960 270410017 919551890 826669146 241222159 963069218 4475732 944824098 284151572 730768485 880593922 912518076 74996929 272303259 725052296 558545406 637835966 106625395 779117030 131401195 245036273 509561461 29859365 967604012 121374764 59044739 254504698 25548449 611725240 167635152 967088569 880242457 641298974 533649087 569365750 807016430 614645494 672698370 353642574 589275483 296252153 186282575 917518525 863573018 353206476 849023010 966210972 477882238 641151980 523655477 737275707 593388683 448429532 575398008 746705398 800221439 935823901 774546163 579103923 880563919 929192823 839738654 140505427 690611704 197448247 487649090 493735502 329602914 196386949 913608508 353288610 534355501 950974800 726626522 391196043 573011475 920691091 479498127 836162669 837096343 183938817 911572985 409910959 81097752 653200271 220782456 184727091 463061510 396302216 231542333 976197868 270916056 803537748 896681359 745725244 590869740 257859313 502310457 395314260 648054964 425819940 211987808 597992616 707705443 865531723 31638230 941065559 998069609 757875929 654592351 417305437 619511730 643309665 802528697 898622564 892341175 336389291 990038387 722220049 28367998 137388420 733873553 927799204 76222510 98761340 843616219 131369436 109040538 74990388 297161731 261528124 562299073 170443957 605499312 466334589 667615740 857712582 19528731 280836517 164053587 864889032 958612375 355023327 859225758 60789024 975333700 108728621 998446029 517598548 736302727 816420876 585666128 210320076 845747647 920416141 26132038 489361542 239190157 645894942 366855610 540537219 995310307 320925264 996167758 720930733 883602554 498549479 757350914 922417897 566756818 772909653 625581232 751883664 711921028 866594648 541246324 6151083 24761137 49739004 403766799 317693179 653327542 899830708 868273511 515851761 641089796 631367963 120528569 35110893 366798954 853393096 976765647 840614943 763593717 579905970 856635481 633802041 659150062 655779702 140785122 956179236 657428935 86625084 131031523 553790163 730440125 369061743 265567363 193302589 422522809 82130973 653572823 174836681 455668680 527422246 444544823 836499761 578229037 752329964 728190899 215289998 485750128 539216654 612261776 280134339 876728962 826919854 365036163 865218040 865789416 786835790 674606929 536154926 829625792 669617001 368406424 928948049 245404316 942385053 451443325 718093536 493617289 697715221 678318218 615330203 34415533 146664495 513467941 872382635 678515940 124343101 486776079 891726567 673910659 2565959 504796387 156737577 102477140 168380608 249032110 957149953 550818632 914726555 499562643 55608912 388297835 929513889 248408656 987968178 567202697 341013869 673962340 115797530 919747492 31450359 843219724 199730819 94675317 124519920 571372686 92874809 127110092 754224949 226121198 477505540 392397101 956890402 185328006 697421332 152108935 647242524 639654241 197809023 795546189 988823548 211999381 770418538 133223273 704832468 9026541 542100026 473845260 100692183 340076336 418661177 101712279 620410027 526713473 344775993 70592417 796039963 411239665 625904801 880338826 417138517 89898094 848676725 506374293 130352854 942464123 549731673 943150548 378951500 200889085 97241417 866615733 625084318 866392631 585417924 882162759 494501238 918493070 579827837 513803977 982487410 56178372 504720263 244713429 142958991 85604804 38256308 732276560 453347811 359991794 438141825 630295784 575916241 172754245 841298678 298189211 570690966 14187482 686995632 209402208 367639919 332284261 31004630 134762640 300036912 757624092 119562020 890201745 94620951 301126304 334627067 676564295 527036206 369509949 446502473 727231025 243721094 457454011 495143941 21486310 895645650 179944020 822207363 455619018 627947072 954417090 429075047 891777891 304515589 780596842 831182970 5331299 836808674 38986152 847246190 201887983 389678435 905925941 485328087 782724840 306173263 283314819 503830790 608081185 676848556 307204524 900292941 758042799 698936434 814483724 164743753 920086071 199132024 696078885 506689418 790232053 512318287 790028812 555538186 506349257 455070028 89488405 851447457 819907352 669884284 178301158 961395085 402141499 3310617 340568884 944606025 850990491 93535573 688850253 694082582 536481318 290520363 225220287 277383947 156014427 809741701 622229459 33074812 352301998 792824393 339631778 661672513 319333013 119891251 231392400 407573400 803621452 667239966 237345030 797214128 174735964 32820464 984368374 344816116 167897287 993091140 493171039 201513620 698225441 165315299 888551250 801837534 193885005 41571925 347490916 278886070 62843017 854099262 195368641 577828902 617799103 571695341 190302848 672027532 141438789 428216861 748812040 370044838 507857787 212934922 618720301 531827070 43717272 836223875 1769910 538182366 963963614 827933870 170276846 479977351 962070627 582677379 645198365 680155262 618987743 94394108 517909868 447334693 67170230 768173256 62901655 479960396 218882054 9822191 362793251 985769140 481538864 514351298 649897085 816992466 121323190 310401666 171541517 164988227 334820234 658882758 28562767 58225658 578683248 116794317 579943331 476097039 411514636 165927455 633957981 882555273 748240666 409813004 832998872 812138505 899069634 889495089 925460791 767214495 465303340 310336544 888906669 567274592 208312633 614365476 74940160 426169289 18253913 263428512 611324801 638573119 257305650 100722641 355327577 535750763 842129341 380941445 185399181 949565970 524806654 174821408 780323113 322815037 835891479 862375840 520865628 110772528 703510873 529099903 329141484 833623120 283895003 570232096 191398961 773668975 398724493 858241808 609982169 658432014 63385425 145813615 309585843 873795253 653706907 253568043 939391737 849714491 822455027 753617959 610015658 869113477 802022554 733897287 269080484 342275038 306045179 583049345 323340547 773320406 649871886 913149318 301332797 954211665