649 24
70535739 490897970 425758507 371012230 619444686 659687369 570214114 398436837 446645191 719710278 603978544 646477398 42985015 615785170 857079663 400087257 304988141 261752814 961737117 197363804 728011395 878865917 500328943 189331591 906155295 746494752 56725379 32132992 90351339 575002090 361892081 46439583 120229420 545533262 520001886 484952515 273404116 666709358 968891634 53054617 200336395 804019738 775663855 624425241 426838382 951148883 585479853 93859357 912114703 856750737 886016751 211840901 731473842 235664381 320226785 331199179 284556120 929778730 66633051 331290546 981503508 555731176 667233741 454038393 925641901 744333145 631792482 164003847 391368881 954254108 749637016 47642746 514593900 889734838 424049979 699168564 130358153 38190466 85965774 914757974 350180951 715403504 83657375 128235334 995066985 410803607 799365059 891564796 382773919 266632078 203327419 314863169 725796648 587928807 988124939 514761496 192214617 319717404 806045166 461687463 531878196 539801887 327800205 855643655 194137038 647028847 228496793 716344334 454649998 71367833 801781915 726849347 566356316 643108292 964576827 999347123 771081358 118093644 434004479 647907557 69284177 604453801 484621318 108563522 161862564 618483145 563477559 973018421 903954796 86730229 795951738 842070501 402934590 654415608 852601730 159203841 794092453 918847519 697236100 546705369 725417634 819112355 491944385 326637881 788134839 661619573 600376474 964005599 896658535 950346596 390895649 389633445 84211260 286577560 100952856 976772598 492115775 757565681 979012291 762356560 197221958 12371143 146709406 415127268 292307765 133428666 154744994 135509090 739277138 533516928 618547283 234318982 385084508 468216944 313980047 17374030 99457981 220313367 699240610 829134750 149617316 268616465 476259567 969805127 121454206 13828897 861119487 716673195 915682055 590614864 242792936 375989099 848911518 52591893 578509539 248209963 150147798 239219429 916470204 734920679 77271050 812324518 107670798 552172532 942906187 69840513 795441561 135044573 170328254 101902538 224364024 795840519 641532185 296504872 210846938 550728111 694410320 667987358 316048161 719015468 877019874 458508586 619608846 600562480 546702202 938075754 931857705 372597738 831198507 816537514 242749188 114833939 406980292 206733004 703607549 128723417 739925514 704755404 798702108 394094554 522929455 435322321 862259584 763684249 796272304 514189444 181211948 678876650 209053387 705847417 972649172 917181768 204055892 929644836 128304630 938767002 954706764 840845620 957321378 227999334 1766828 761440792 272601265 372218615 723930649 624706969 605221479 111436717 951403801 907726986 582085716 5338890 753567543 498466442 480418222 362022811 241124356 679747225 984413842 820781411 223867000 537277179 272588392 821751357 517417316 110903438 585011368 770550226 334944812 817301813 810790733 434618615 82115722 482746263 246341503 610320765 51259082 35430099 830800884 852485715 370983707 673377609 101221998 520360586 503965007 814508560 33084684 382723895 552117866 136514338 220331234 750149167 296994909 254122451 153071890 782142892 488580521 772263251 664904092 802952257 274612691 852499233 679523647 457951769 709969596 84292725 719360262 146390220 492252067 383841446 575131917 499736166 818615609 913108858 460748945 530838710 349201176 932724720 421410686 228314828 389354155 49413470 923606250 913661579 916833343 15113057 680344536 284741635 807688440 934374201 626525199 209805195 78052123 648085900 424348598 806346776 307594888 606594204 898318565 501526914 440566294 12382888 990031971 862152352 357101552 533807271 425461424 708048997 775012600 817554677 161018460 197334539 246210188 857287635 397698081 814931955 598572463 220198012 944689345 564226811 48820790 279663742 646652376 158174745 677723555 353598857 630452278 182371349 484654223 547541660 35961925 688969519 811778479 235411088 424816861 382923811 942343716 219759625 157663892 715209158 432481589 596106563 831248564 657503501 35766466 99730977 882186979 789285871 395919139 767495698 681581147 73366518 252359364 803179797 212543664 203770498 374856108 136906285 874283317 349332530 555704567 850119840 328066774 404832776 940634311 417194609 100006912 806324495 414134009 497488671 758794659 948352873 838671444 88936050 970545450 380972249 403671080 81331739 163720308 363681299 208519292 811626239 733223584 236065243 742570198 573514872 843987699 601138681 92433133 234258818 675253729 97749987 416523027 674859920 379282118 589928577 671651604 362144002 556332955 814395832 842519030 113292982 572977227 495623022 743490101 649890689 561343160 579186259 199527397 821941204 614375604 598050642 677955149 929626605 253634109 391742249 310590962 478629807 812642852 385592339 755718304 773356668 315648078 268276654 81719342 720320589 870322713 878011917 543007137 773780830 306900468 543696623 169805042 25181284 311364730 739522159 42807856 143923146 915539366 320180109 519840860 451340336 478175303 575683450 309952912 539789142 958658170 752622680 763258178 364022975 394433100 400988273 640673852 806775495 175559148 718100647 782495701 978317041 50118143 32308655 218580035 613077014 806046109 609008639 291325009 630394176 9101932 324723502 390790430 511441309 830119499 483276858 149425124 842238804 909591124 567744916 213916997 490050277 834960559 286043367 291958349 204211908 995644918 913462902 445248879 340157777 122656604 32134249 71168025 104614913 879319122 889369151 392413919 705877346 282663691 976716990 812351996 705858848 626066382 223045672 741203816 975283029 605786844 890781661 442177688 346874083 75450945 780794516 863816783 636591240 794891962 311153031 722733836 967441052 196941205 891959930 841718317 16858469 149185495 221396687 808613736 415063519 396113064 244680955 160644258 519147187 481449707 461324635 914113689 563662746 876576291 513094679 846539122 652076299 417995237 689366472 309933535 740893902 765006874 872126477 780824606 135463521 256221363 770975872 300337558 228596964 273637 39500243 609660514 646029862 848134845 279396217 447738050 778981336 852245091 930924485 158239277 852004153 963188414 830721378 324031461 229514907 129659360 133911829 733683225 159245473 684468980 843199963 417342710 188069810 613115884 113556844 316977490 359092799 693299241 129838477 42331323 498953582 810287623 455354753 102909559 373625917 317806571 651610257 580890288 528967714 438486151 595904951 180288531
58520609 407955449 651730099 212082410 965500789 510772740 42701718 457532409 881472228 576183303 14602282 958592012 166173875 516678740 658628812 790156272 362460516 602872545 274983215 571639288 407423598 41146627 742926926 490985114 79598828 638419447 353042410 457569951 550784889 63474515 855659220 715607857 846660007 281144813 787863010 868537537 707877581 367124066 862478678 646521886 484316592 130945519 22549425 278304485 800033754 275544195 49616631 725953984 367320333 424663332 188186889 491697501 815683530 204952027 985836298 23586987 383178184 945254965 775420433 151310409 159654237 703599292 161852602 180942937 154599078 678848031 631199120 884630113 445117257 866043036 668529505 172061536 169351100 407303615 326822892 941047858 521285205 708327647 322297382 165690914 699883340 105640865 311564289 738716644 299195350 81266197 335205836 282433950 31825164 613279170 405641149 690223118 336144275 419029182 925317907 437205084 637621766 319881178 417109852 672755748 610707973 411016773 72833679 985568209 743129521 646068954 158221060 579635089 870736361 190064000 190441248 464451184 441680000 611497286 492477221 858325754 439966606 979855760 239138240 150711092 802364262 565851565 93190432 109129958 612139277 715410773 306517083 833911363 104612554 242037950 217099067 669388258 533197508 346811294 160317050 678292459 160950706 178345284 708318265 129184946 204919317 695749228 152030219 163316984 852159767 809536044 287289727 961919510 905383135 416297847 765043831 918661996 490668210 520243180 655437571 475018849 318652809 466219463 52239082 733627317 609078257 168261003 821978235 906417182 342595537 895323754 629888161 956176726 204442189 142565500 255200786 733468970 319542932 608237028 704368358 265242285 783956864 517528889 843505985 514385136 259676595 978510666 959079992 324337342 434689062 382564585 465618053 502273547 582733634 695554254 941337509 616164494 128727913 257514432 402303692 330833748 98545853 736740151 642961034 447459548 79443671 984102939 871256033 673657034 576552204 238646246 294528293 805679966 578413502 589498876 456394237 124325479 527240238 198232462 923130110 515129657 392254407 241169335 77125022 158511649 687714933 281567425 309167742 745617208 897377975 561090507 590738528 146980114 573525558 731891887 673792859 87500419 545115271 365511568 674179066 125387540 793954638 580744082 525451742 400367692 174940932 248619961 451343050 559662444 933209661 220274512 203840370 416455936 467302253 194331887 376502429 718924876 829026577 6048828 76353917 366250854 641777203 262810224 538999211 994011671 193287186 284086105 14643788 715674852 820408618 114270214 434572141 286111592 729068251 656514718 426647945 338525748 326600300 189822094 371467956 336567000 184140570 229067009 323063970 167933267 802771579 204587194 159228948 492117025 431967660 519181066 891362535 152817239 166859799 190528420 657177765 756669706 724956276 374983729 996964842 100071049 212554821 467826296 309593833 720740254 266639915 929551267 610272378 137278749 900431306 362768316 927810778 530475969 831328955 415110922 839318050 153959751 528874928 831467973 404680581 966929899 948432449 58752920 128312592 942651177 644438264 131688471 591657921 254638551 414472123 522845117 912790128 513353827 554478000 301723162 693150168 384530271 685016808 882796258 386027254 894745513 601012800 47995730 555600016 683235914 992306526 958398603 418702107 828999434 525984537 292254313 682258252 393079670 365900611 411062087 235327134 534685860 818001394 640305121 511278467 654649453 891048984 569045608 362365569 920875600 35374872 196268308 737122489 406237860 217531313 256706343 756960752 910675029 568306291 697107573 909433593 817279775 390198166 277589816 559008831 90516806 962419496 165376545 77203148 195546086 167790102 594831469 126289921 824591823 978388430 709240089 329359984 574628844 882563703 689683281 801596621 412622325 48422915 311295245 808547332 773916625 114986679 98717307 730874441 704018733 999414334 31120128 390287789 425367001 90664123 629914675 77502181 743925033 603961262 20633280 317870448 685020480 186171105 455969059 298242107 647315594 562729285 430505616 47565010 52166798 607082106 348154127 545439276 976230157 867209627 7682486 827936141 165704380 424945814 439688259 171150628 27465505 897559109 806783047 7310641 209111527 337158478 61423199 473607520 620354761 131220066 441016280 509320749 833401093 457702892 411818236 445011283 214683915 193133314 234304756 752619159 554511959 867779505 222782593 349998214 241300527 269055781 877103672 684073132 401250211 781881518 158821723 511270577 854743548 323068914 450875543 429130461 36956747 928901310 830131162 297847501 918849637 986485497 372478983 775024748 552658114 461557918 26365014 405210623 651424891 628451354 108930754 16014856 810669854 79156266 63645314 652059524 244766117 72336639 330033992 975094037 246701738 373161703 701542602 262360972 278667215 348822448 975669058 846747245 48931622 363315586 886339394 993802908 249862951 843882602 303612295 447963186 46928543 261975138 255057666 8315659 258703401 94209521 732234977 982269806 977928692 636270513 309832118 487502825 997451653 604920632 669112494 955792485 341472680 752344101 349604248 975214145 813538592 940205977 377083423 919769102 713607248 293376867 812978588 543875827 587000455 365290822 737115372 164980147 937042506 333677336 288747744 752786828 71495290 265591222 695463306 399435234 398181575 959230745 478551790 430408637 321148669 849861340 486956101 185135444 685116344 209501425 237352850 949713303 971181342 921518759 380314231 852255452 144165007 784011227 610023262 920124641 152956212 102385526 845288529 679600101 193079782 772496000 315952634 777448701 918562489 842772494 760744630 807672271 983091289 157051267 687529884 521953074 110338129 646601460 914886949 140867486 290045630 630043216 263426398 788851881 307400963 523457217 455554892 200677761 102804996 471454391 473141135 593772794 202207956 439896085 521087434 32953351 598887441 944353783 446264805 958617824 241669189 841355406 567488788 909106364 562344840 154001337 91777681 536077721 217268947 356019092 377495326 995423359 716517292 189810997 323966455 285927754 733081181 363540549 88489405 686509189 85454032 748758196 862796698 456997845 695305127 868575283 451075846 444190272 580619798 319119582 458735439 101035411 556513108 111284362 292657705 99947873 788643691 673126969 133012425 343808708 280737012 526996961