655 297
901280131 893070029 404265996 125985993 723608207 526989856 79984809 667989540 163285865 643753888 666960766 576773282 851807119 791141368 970023517 382677232 717808260 710930790 777028943 817799545 62638618 799753181 842577988 115140974 308382921 515461595 693624916 198843609 536279852 60988587 41349337 549988964 366740526 483107094 906955793 951417479 263140922 677182610 507092559 128232715 672719575 759006478 477760210 344907107 665222373 51269073 181504885 837750173 722621582 31939362 21571536 564354235 357225855 866147786 580315242 73213813 743065178 456819150 544551136 737519078 112103161 985615622 849583503 737044126 115846234 687377509 369161166 87891929 75185906 271374520 73479735 34538189 448861375 221784112 469436170 337603322 43962816 610309328 350458748 465356278 618805342 376593647 212870364 36125135 763256240 939056107 591489355 460960131 532885191 285406359 979560949 772314804 170579203 674879974 891499828 72071255 971839174 16834921 578567146 817788450 880653971 445387215 886107970 982184528 506800033 26693253 651060385 390508451 464575599 968326248 946904301 508543354 731765613 990770826 138649822 738601812 477780322 566434917 758554800 783453727 807831012 808912056 491519676 675486307 335074647 911890721 646943263 152854100 198992808 844424747 128782121 421600906 906592281 778262486 760312368 737651891 38940814 181195799 275603376 453303301 360068307 865398762 383911791 598649775 861803057 191481268 962011870 108827172 16798598 961112531 73935453 492634912 588893826 235540760 878276181 959267969 801136732 550438939 568218768 404775642 651312471 762338821 279152522 525576856 530411246 344243366 57113649 267375864 507036007 627388091 310429263 310519719 12721989 542816228 100001243 801081784 544271564 455423923 209185259 533850277 776330553 195997879 209922564 765946624 18294371 639990436 558992098 347933023 11468435 96729244 755741029 958412701 892878443 239171170 769820828 446340059 673415712 136551762 370756310 873579004 991717034 488407230 104484408 818194635 962077229 763563557 359082791 542101403 477729636 433436704 913465781 321618506 69284232 627349395 387876420 888913905 430301599 701938286 998011006 355033887 193206091 169355106 704019269 502811632 652372223 975351110 576317747 832396627 78472911 192039830 219075581 670540527 675056872 19133034 406490578 719480799 142224325 666425763 603312240 341439853 883525707 110480347 409846913 721255088 939217784 8075906 221638900 56339663 333096496 57842916 805339921 454099809 93471401 666263797 667326555 659113203 751671161 832154030 98938217 509103188 404737801 182125023 343578603 855710020 682276770 285576659 898041675 294040654 420627955 616597554 256474730 911212820 240758486 950155879 606314532 936332358 361233737 390186173 530111892 800163119 273538856 979576629 388135640 671696781 151003965 497417143 579671944 602066952 737587284 130244449 223450796 828949283 309636468 657626531 32324843 633883373 120192224 946064738 456523698 215157077 617642765 968544501 761685898 975488471 101633598 399607047 206584265 999353528 808107220 586415141 572094929 185739578 292097297 489802818 485149345 581659159 132159641 744672979 690718247 558236953 96763673 253471686 76958095 428883975 116237443 805500060 420497064 316727128 856710421 471951799 873730167 331749075 48550645 839383247 299353847 254538912 194942651 653822425 952108036 988833631 116943235 317967460 957984204 703192277 534058831 661222915 123843894 922735876 439121620 37108946 612253108 687318866 687703548 976116759 799683776 92984599 939755251 819342706 447431493 264989732 384823883 923849491 12126393 239282526 571133015 667768513 778689565 789313102 101388326 953260313 345253790 331787309 786217286 596535247 954786119 790504462 242627975 742711804 675278005 914829805 994563571 477852036 53790626 355501073 442837861 20538983 775090076 232624899 58608333 902144019 100685116 356269670 418641910 714488630 720198716 133339225 682068171 505816631 372810818 772962069 615980981 717696912 415108671 333669899 155787169 259448839 687371316 194766181 751850936 954791916 779749632 349311283 347489359 645612898 437687046 27486046 385985257 833182735 430547890 840035801 951461070 370023181 621791403 539035553 567527308 849310718 348115572 446856266 658810918 317925255 29538666 266777048 267810618 999562365 254936109 467039519 236452208 606393957 14341506 511802583 928629847 831244798 783762704 44354263 691408811 69840358 398624443 566263950 61243690 840214209 668624149 536929508 894305954 529191370 935586095 559750508 903559612 499298344 969021647 280606266 491914142 935784701 832163540 153620791 153071387 85910594 234852616 607051229 333948352 986020814 797484513 624125424 27825213 654936727 711987677 480226505 499277429 874087572 92316922 115653892 653834051 563668333 468347657 725079677 432214528 269888281 701306628 159406292 845845478 47049332 622079805 50502893 899295845 223856265 917801865 233221959 140388189 166085697 143943422 810760063 764025083 92344134 792918241 465882023 45125258 306304290 349928805 663307893 616493901 861460428 535776499 439261669 590946312 103619952 655400085 924594185 635585977 681108591 883286295 316418852 385821696 571622014 511928776 740438382 137177106 493122460 471824049 415474498 772603652 977087112 604867859 537233190 890570948 509904917 358373971 949766316 138829651 513156613 918044035 844260667 590002834 128330540 284537623 729762775 787343147 610103814 130526060 850239313 612701677 895188635 150419576 764094840 948569722 178538292 204693483 802887845 997486961 897551259 149077318 908148806 647683974 678122526 306647175 372081742 707326971 449687039 111707934 5293825 386705601 393131751 999579912 874500840 804042851 715442721 418209963 504969044 988164550 47734772 824281822 753606291 896461326 840015490 54399214 505613263 144275471 595558935 529521055 500690260 627291695 521148598 103046450 948631092 523649178 98414673 938833877 552582118 857345576 280692179 575649771 827284947 328092088 75859396 923157511 733536486 703662951 612146300 786816035 201940955 409562339 972009594 892128372 162865050 59101319 718481448 625889465 946456318 780494803 873821659 848061589 920700253 812072550 287577529 829635302 852739368 320703013 345116151 176106081 685334477 43762761 665842561 997053567 657090148 21247233 416783855 213577156 722749157 361791852 972272979 662600781 940990865 303672816 910853366 544674935 308713794 628823066 374983916 46526278 321055383 277852823 17402857 772783396 925805924 814510226 792150693 249118451
244256961 124290032 55795905 467965722 357540829 743058004 637826143 604590320 294880093 202594782 921697092 22340719 48950982 531643477 786850553 673350788 710441009 932070928 114753417 629841723 659173821 249792697 566405896 818436609 924613811 212489576 766776711 646186015 991971422 917913078 992596539 689176005 732307318 970246457 454073606 463816682 872923954 783005603 210735360 795000325 851509134 492316554 551858125 692090835 367923903 948208487 195108559 733984282 938057451 949380366 631668905 297184820 379273717 375305095 782179056 108127446 715382183 811033351 989934367 394606597 797621816 71934323 120709547 871238807 114133568 331931409 715871169 289033649 816884838 257825635 235308080 406425904 785831168 340839466 342214441 551049452 155890608 386415409 624641977 74889889 31925648 116145388 801260604 728568290 550892329 95281772 138435807 611844622 587809311 777888921 704024850 652040781 424514623 210561932 785152114 717878346 249598847 215030700 69530004 266598542 867885891 180860267 257520381 250799816 185000274 186730235 971113491 350439500 561642234 108051189 546880712 10446448 114066512 42803288 651186401 992040484 993203620 879157559 60411517 150073494 129131926 435992641 89452310 200944382 448047097 539120362 229765159 704563526 569234541 37522846 733896610 109154441 490083600 211685392 755420796 834262604 960928291 471319105 819898023 340148785 318903450 351395771 321571968 679686280 232655019 509953273 790922126 975512677 315694323 363018897 701774483 432252678 912463893 499853533 115598483 84630858 846425916 214322008 277636483 463928378 80778164 518562060 289661047 251777517 427716214 571476843 225949320 844901637 981956876 553610595 129231534 727760480 804491559 837258697 108353904 165261966 436360844 46360449 853570416 679428865 590910761 468201466 645154315 229334479 957834235 491874829 788297951 287031690 353294133 956749501 339294574 895567203 334319792 996127873 810037317 307623146 4606744 794532564 207254348 504790259 584842922 529132420 282142577 686454508 146034233 540573678 644926813 199341450 159888805 363678003 845426237 334580141 506633228 851488358 432434273 159078376 457567279 26923527 87632655 108641187 615959409 471328515 256318797 407790865 166219448 875509024 401026060 180396343 712110431 241493113 813952784 611573661 762410999 605927096 743526547 762530193 722530341 487619277 418993851 820392674 119171499 264252966 308879891 391695932 749163123 847294274 646423945 314563198 528050224 45391492 427349166 261234204 291969740 436138441 674106754 612273481 172999607 638156048 829599830 919042412 857131508 340351378 952724298 208702450 241451291 894214184 275396293 174729307 981499840 565368443 985531680 732368348 827635886 933375538 755011738 585782407 18739544 861092942 36905121 689846204 27630554 156382337 782796521 629925128 508178940 668136814 19006969 156028008 833373986 476453331 603770441 39764955 950328933 696266317 559779847 350679531 118818473 760642114 294648945 861331423 995627034 186437087 183136505 784433868 555904703 366865417 654753406 521104904 82361148 219934810 905854790 171881386 729073324 836647749 860675109 476305660 366307445 605132765 977830160 926668410 306204973 35805476 277861845 487654557 422947774 139277269 730974319 189650163 566453085 721297241 675513553 453843043 343976552 339281629 544018826 66392796 995972374 508185063 560626228 32994521 655956797 457562582 503844644 792681181 447272275 727868993 203259680 927421274 8554160 730614471 484075953 501985518 891408637 575716496 313451705 187924708 115678698 873179630 186307232 130393793 863905496 365122571 932719591 548193852 368470717 461594843 784610371 42499091 119729186 171751726 141213656 657931676 579090227 893730415 614822414 634431257 193213306 626326518 449227385 917562953 243451785 618196636 124456917 486880857 742871262 253557232 103555141 231428737 943523345 833530848 656715607 27246727 894102280 764051504 70618324 181632379 913202374 183812684 981770994 505790742 448629748 511999653 849127766 633217464 391337736 219834834 514044517 756945654 307369952 259237846 989463159 542518297 617235161 47791162 234601107 43212815 102309903 80864998 806088909 362414792 885600169 605776768 684901639 302215947 360714755 199984536 591360267 60496095 825753084 9804547 890879860 36132420 135130511 763434422 775850132 428881781 491743335 512086807 376145078 65568161 10320600 200869308 94399631 928492094 977451134 797186498 430427038 690876727 472060878 672189140 69525638 615097835 523296680 999171529 609137304 809375989 361485823 138847828 484862739 925696218 264284516 501908308 446945872 621861752 843365002 808126660 296297948 362853152 712726630 575538728 917437111 591981647 423707132 486402280 487042918 95777752 779967824 793388696 455162187 34922041 375913297 87736925 165582955 887374600 471824074 847432096 183727252 468213078 773021536 763519590 967543432 135477948 335880851 757549895 937795642 604504329 889823338 707703927 6130394 318939727 534836600 262482013 149781071 924992645 218781192 148352227 979021583 553588939 840349243 200449542 645826695 180787509 274692716 711950178 571769563 799832939 651796027 678096417 915734429 171723936 655025862 875440239 173029454 969931143 67413013 233716237 602195434 115179047 640463022 434598839 932227099 785789740 341821456 855718509 756909165 26233301 638532907 213422887 916672540 290866043 471326497 577113773 67726401 474312170 70229977 669243758 465795860 406227294 484827453 836409870 60534805 569048227 95983264 361617281 48665373 516152051 172932977 418141424 271695228 42209725 125561276 565579592 184394848 833004689 650088133 372259432 80836986 482116770 120841582 151399197 651560278 566960861 383619712 701614807 514212947 187307631 553291675 737329279 567890193 487287073 785359045 240978348 589700000 284790789 359262580 115244735 400113241 823808806 678723360 576954784 288005786 217033775 848382950 511823825 538384339 228583021 440550330 213522164 718193227 507722397 67629589 227603716 268150515 255042217 693300400 327497041 810785548 746345908 745784391 496521920 430905117 477478688 45503676 633112453 48301106 349659878 788204924 162558112 743836946 433753128 478472498 450159807 475320085 640344744 221779013 502580104 917280716 363933140 521281845 701514388 258496452 756674050 325863766 826095941 228005055 496254061 788777143 910976125 458061031 954922741 134045127 821828218 811938209 684851452 101226914 758226626 88557738 350850755 66157292 820912257 430851830 312027443 763402810 920152186 282635791