840
8739030 120926307 803295434 56216289 413716471 873354656 451870557 139064866 255901070 685179806 709845263 999433969 775321202 766982406 144659535 800440547 761254991 666201675 549422134 260210471 742336200 66061212 234578447 543558521 601757679 652131053 667679063 440240809 594666914 629222305 384573904 79886815 937774818 177870625 623214359 30001108 55849856 602438579 687770618 23138999 980674573 224320457 631685397 79450442 447358760 670162920 110135509 439770249 181941492 28280691 879362162 872656291 484225885 551236798 950831382 532610351 169180112 762086615 955712632 614619045 452696254 981662384 952867160 156010639 389957863 745090052 17547210 446696080 401783657 135146967 685307973 462286829 550465806 903326250 45474550 992986372 58672164 517454732 70571365 411189265 824804881 330948063 292754509 202333551 269246464 360859262 48367184 279612113 671458926 353497051 105760086 221904205 17804662 783159260 977753328 763232412 361223527 330567198 802611845 284624845 126031708 24396795 265099138 161888801 612581815 597001613 429876456 52253810 435620850 600319552 298629406 726727600 283292020 705648067 935292951 899156260 620384926 951775843 571559088 916665254 290316909 347944813 577524843 296389909 485281880 543045103 530564538 342713531 873584198 234892110 319016848 801990467 675474295 927995284 286952115 381606062 816690757 818291172 890707954 701850395 946641496 201549657 177112229 52632346 207838408 437498681 235686586 899116397 291109308 402447126 233593311 673665792 44199458 792975018 268408266 78058035 390506165 634769273 633673152 315704953 705030313 681521436 246800143 266139605 51777442 605102657 541329885 462191279 581150822 103234392 605368550 964731284 795170543 521472450 48366574 176783033 494856618 594147821 70657635 109298255 902179145 857328289 414425427 661213103 874877789 66314032 756754574 379582620 386366260 539563803 549542385 503816269 162069854 65282531 611943637 637623246 80769454 511037183 435750011 285712625 874867908 797749637 124604661 775430210 482159757 948694551 178626155 153125159 941627192 297193613 103744658 478695024 42325497 357613704 213421533 174364504 304141197 889358003 778471954 255656551 272462878 126062885 272945095 112015219 444116290 732689826 711696378 383425145 394337036 352291921 246078486 310779627 265449592 248475915 396291297 876862920 119144933 303716076 816933120 240819332 374968907 719320462 48797384 680751147 519294300 103320252 823030958 850353204 707050189 706071659 372984709 399762600 35346043 342125310 123975319 221996145 220770486 635271182 398449589 76456953 336563697 313208534 194916645 147442322 846407109 969004219 970418438 425354843 146161360 240886538 577457758 868703110 601570745 245527017 460569262 97133223 64994186 788471997 8354859 852759954 935122089 111220129 9047187 413150114 570298415 804178049 562414640 49480250 813706216 459205831 792366603 445399597 462115558 438457615 753762125 854647630 441566253 198958376 591062037 718725812 430431081 5794521 9622383 658422944 986805161 177650885 481470919 821030373 205739818 229376629 568442207 267255912 304920224 784573524 819496887 967673363 539516856 426904662 788408021 133756919 456244524 516283755 811137765 331551649 526591501 72764425 178321898 100008989 613004746 696700508 619292887 702044327 757834563 784585037 90184856 387835253 227963969 45326114 614518971 369307034 957525156 862996962 742572952 420682876 966233430 792630672 144604520 132383948 518879489 918891269 839949336 905497046 958447291 739765087 563236475 932244258 459646554 498285270 218096412 985698808 137238797 733767945 166231712 793280328 823118479 675894069 240574257 999771133 281827220 920431925 183711919 717016237 937998855 234848361 7000508 740897883 107191232 600289028 263025370 27487736 576979344 535195311 663043206 384235142 220546464 594480123 465488725 261480854 172891424 644231519 873101204 701824676 852921121 713999774 68845922 215766934 672147081 601399418 225908314 907342379 812245420 410889565 873372660 477819074 164902285 665064688 45147916 839666609 162027270 268722634 633154109 565752888 260247490 246830381 156483837 367434663 864494183 207328296 60693843 963649447 148491693 909533208 453105425 673821769 615258039 294094491 575503827 634242613 713655314 898051543 679012181 250115157 703337937 234816158 541465195 988265111 123989881 406123380 978581412 601134148 670128900 663930633 631115181 141149390 970562411 167620739 675331170 126861992 987916680 303656071 119636718 750593760 63950374 34945078 953486399 620856893 134310331 872869537 10648775 987453008 787351211 969249993 439430954 528259670 335624239 898821710 671147339 828926162 81230797 174504006 517157830 135275919 351025646 985884393 700737957 833016830 881765339 509811321 158322570 778971449 792697048 298466068 106490250 293277069 187634013 386972610 25403124 916929680 555302604 54751099 844626394 35487301 694705792 988401363 498046665 254579038 86424757 667235048 907910786 531223932 411069143 747916177 399090209 122520297 203802720 21106697 910219692 552760086 297492274 272719000 637771846 720563747 929718554 323734393 235698859 121492516 428618558 544201708 172703033 290559726 945757200 245307727 95628742 299365527 728702732 125903248 83863906 574690173 189629960 100354613 500565261 162756889 410991450 464487408 541317295 97041095 828006262 156330136 49357900 357534079 10485261 133166383 262180450 439173893 386230301 840495235 84655979 930348398 909745459 188023744 709226717 542178227 281201866 252300493 351980594 484752251 355867707 924885360 415110022 275321200 880581828 878518560 767980234 789980703 206263071 442725089 90552867 191339015 426609783 821726186 410252382 312412866 247264872 705251792 698782977 257665511 342379960 674685648 579424333 646872508 394281606 384761338 799340497 545742934 195737627 401852732 399409246 553107355 27814671 704743504 405430172 260627496 612632702 69720511 735460832 944911273 163182386 395517714 843805473 104566348 197526525 700832178 897540029 80490627 879060344 848056038 858056413 231549071 491466612 51201390 173873488 27561346 829837905 594341108 770826816 511832999 475049996 493614016 1065853 52782696 793000272 63249187 516397672 351432042 723647878 132000851 439891625 936295627 852829180 416949034 619469157 217677250 719990306 884788257 855396818 44160852 705338809 980363769 421388002 846748322 490430834 43029051 917649302 445125612 188917709 218820682 35982384 813442321 788023030 616214298 528795936 867431108 857815995 859443494 719861249 449109228 922554710 588167370 832648897 290448453 74283432 254304440 501279918 238693793 943210756 246602832 457337758 842512441 65212082 678977844 735353928 172677766 85227504 69281127 634351261 224498600 524914 491472804 641343171 247521533 168096568 154337807 100356933 755877314 493353686 895790037 847616865 973413786 639404010 547333891 231895063 524439369 289789473 299798810 756988281 472514494 957739543 651288343 686679957 16247703 878483409 342457523 836837843 731950077 529039413 581453921 942607406 844857011 230507247 860960708 962291719 586167880 869756162 281702871 282137628 283848822 729061239 789261166 230068554 386896292 301017057 24754091 297602200 422292118 551422697 441417599 531155607 616802424 647509119 781989720 658395084 11679075 729822096 165805621 449994888 209861544 720569367 560483726 921224853 101413047 33191562 699396 351119728 887117946 403051091 212570608 488918858 716700266 969425143 713818206 83479850 239963044 929393806 829891873 501068051 662426329 267916975 306345481 971735764 622034449 390907600 24356436 815986955 165919496 939264104 323431247 583829395 651046474 14253378 387659837 95863359 795721362 526600571 393047992 652168179 11148764 137396680 193672496 107849496 298729068 550274875 151457052 745929486 609217008 93471475 989815353 45055291 522578755 572111857 778073566 504106287 872082390 137518314 791544602 530992049 905305582 531043304 614603317 907942752 621491236 722785184 12954026 699477483 388357952 181564131 525200940 92559878 712832482 227999218 16652922 865869867 458212795 487202373 765495600 746212317 354115595 662678762 216564098 235224546 236598603 620714104 974118836 822494295 316773925 231893429 854193384 433801779 270100391 387949057 587990655 217840348 364483302 213937489 784237459 342828795 267266216 763203643 692783818 727119715 322025114 
972919134 531885332 395476438 911600942 180971535 530378141 901417919 518413402 393026059 978481384 309810704 776674085 463167273 953570151 719991670 309331628 933166087 112510284 816290316 124712284 342450204 832781810 281744906 178065432 458855921 376433067 62918700 289886185 403273806 69251514 728635701 49315125 766692060 42088233 695686998 117445720 250426620 175534532 449898895 640657780 636767046 71816930 351123663 547419483 769550930 283310800 911990871 501535230 111721915 478662695 158061960 822801269 976927381 40456799 33043060 304754764 797052441 124024403 578673400 362608514 827086497 218334788 487466077 277385984 494473906 265388967 721186971 358302506 680755809 5233360 767630170 604403066 379411345 767250135 47563565 586290515 309100627 463348157 195313642 316140437 862433326 933609011 45593012 832861352 566174928 460276659 846103292 695768391 24602131 277394737 281129571 571837997 372665444 978815392 394690735 394358552 451898585 45399030 81480843 453383929 624152612 914880258 430981938 625705120 726727279 216439721 183526333 23606771 664062692 655078462 353176057 87787177 80266465 698635215 192313869 64708729 282296743 572545487 874463952 672815125 860480158 77523465 6715287 548621878 647993725 11317116 122670589 410691011 352141434 727086590 388614996 830511589 617832587 383719027 140130645 659765206 753482856 611797229 54779219 788287718 877543302 212607307 325402068 971810318 604806363 848422417 444776081 230933359 561562163 139463927 871938776 641721960 865615470 138991337 926016108 124262152 531764705 521994099 549934773 921244719 40342978 735982373 222379700 371827331 472807633 412645144 441250160 577029614 442377786 320057522 783043945 535469496 92833145 189371190 966162528 416512103 368751386 690299021 183367467 173999563 100027404 510935676 113809990 102311499 895087696 440937006 931608477 556502264 956150819 937807930 250049049 38634964 5052924 431013472 171148086 167772545 283132431 39161527 853958094 953304932 187104938 676359153 2679361 415832334 208221711 926001913 302909136 818367067 199572139 808835351 184762166 985300804 170739048 713837514 871508380 777890289 285812748 916240102 790944836 413924253 435609320 339296253 722437502 793009226 237210864 17192786 548031178 71838049 867443732 158314199 381012883 539807922 48182662 484929715 920148412 689416008 135670918 111157390 256054188 785377903 660637823 369197687 378807715 902446548 496070931 927538571 645672181 276335175 476345013 861417383 151057038 683201344 495233413 432535934 819001335 944706635 155811861 457658270 227868652 703336150 876968079 480024327 813176801 288241722 950020645 535188255 266908069 727400147 838971536 395311066 15290217 68858537 12601683 331187357 727665648 869305414 670695231 397098683 315927389 833711746 756384261 485890094 180681037 722619817 95957712 732211049 75580067 455360114 797558729 82703731 257832205 51207575 282844990 294274255 192520656 974865438 84435717 486685071 992145258 525735120 60388377 328590689 553179978 44057625 337001682 630167773 753257843 372165958 276323856 252463490 528467126 559549359 467089378 223134642 435624644 520671781 525876987 290141511 459021102 929477802 176824139 191065057 753970990 601912792 861005590 40946197 292648360 920959311 252644620 68436644 605995299 754358621 941943119 783533495 256374442 103124949 327175996 520438361 503722077 392896077 191230443 946027354 264042123 782360114 1282484 196706649 595150976 582949995 145126261 381285278 531374924 274982054 709783733 83280686 882471933 159535501 64513528 708899838 764102655 80498975 230028861 570208727 660207628 765829676 226868710 204626669 570682119 422983733 512602978 689581967 737542992 323182860 790639663 91482782 104227024 745246864 827517420 206378864 108012585 83957080 368335400 835922157 417932279 280838814 648049834 890387385 780029556 808337455 887735428 229510933 857328136 970985181 616577137 10422711 364960685 709938068 983633178 80718765 228654485 841840337 216243152 218207665 199856104 379065195 123302022 360420940 267852909 582444001 737266833 60187908 894841319 74511457 83355978 148067663 537843890 452165478 247675060 876109223 104479800 6223493 684987158 425737797 530633540 382375445 168692333 858498214 10375343 46624841 582710844 789219285 240797272 466512357 845616471 572471645 560206013 66106545 776110609 301647962 576688696 852006083 238774294 365646131 807885589 690335614 851545959 536569235 42142639 534250151 817511261 796407760 925442302 456718150 832009300 696503739 52969464 124674338 311042666 458393478 492470135 310101225 913411937 766097878 272402556 619782665 879504225 220515305 656266132 324299634 682884899 696392475 315293421 159527373 140613457 110727261 286401863 467838510 507812266 691557411 376197694 287413682 73334361 488053538 133703530 980068064 630381985 648555619 465322092 994236910 63214850 269487367 63490545 402624018 855899172 999006205 944060841 588890983 95718274 452552947 363997684 109864809 964240454 32642508 261357786 679423235 549720642 161561819 612053538 584912771 298740394 648527114 144372846 310221742 682920397 902772931 818608589 130249214 89664157 674379661 460210536 969912293 749414972 504054363 498029529 220188550 982834825 984255839 239658239 852591267 243543677 988929970 309729569 276222351 773581139 758829039 483512864 125972102 488007955 663290138 882326216 561578782 658976988 166608329 172733964 405382281 586830117 106420451 156365225 451951340 846420869 346583829 898597078 966824137 190007141 15256230 188654008 679535393 341569242 538032890 414990217 934548142 367665525 333377914 568034232 880678293 901550192 619612945 465654297 130673620 375303956 828439600 469522254 31664566 470022307 874756744 884983539 216977603 471263154 189841490 184033408 184099299 329828210 141920986 855575787 526238311 238217693 515979294 213365714 851035431 166474177 135821052 351756039 974770751 332812237 144969577 892854779 210204117 424573767 282082551 936468201 185924814 248780458 186486028 570263790 475363448 450227676 128699117 747419660 801581004 42773240 155661978 271328703 979383444 898917809 245120557 492607183 120108014 739212373 282867386 161302444 631138728 264087747 85703582 549432213 598168494 954793021 910035195 436814376 342913577 291735619 933111350 846938740 593614837 895667430 838001290 171734736 905124512 693079347 825573390 591922629 950060781 955316193 862592314 260233320 257492084 507439817 503355024 975646182 180453915 345387002 963641545 415182364 813265074 421650733 636794432 834246833 400729981 787213633 143850620 987414194 332062154 279201834 789124428 839122140 206718569 594485486 485320057 816845291 685688454 62377576 791571079 614622426 218653462 650533153 100857306 714965643 272717680 913036777 511286773 237064868 969965791 982429675 6472480 163282270 233432280 942184643 738159559 425706773 918353140 478100319 34229932 831290895 467889879 160856860 433049297 822438126 722248636 88989840 133296468 135236918 202634345 896614066 829042328 896380087 161222391 711019694 655121687 242175454 792918009 718838427 410841596 764142750 312963678 82665444 620211914 837048636 957776222 76871545 995588176 70709708 908030271 674185398 31949105 994924187 518528280 80148345 565900293 563165662 648930338 339152511 128022113 578047487 972666093 29666569 672778875 231193957 754213673 967512852 60781648 224413142 879045918 445008436 578273860 17645249 600500837 764822833 248759542 297100468 974963056 891586752 627233574 919058690 152126898 196301876 302927101 977914939 955430320 46319695 811328889 884655381 169667918 30676856 280533461 331916696 539267753 105503914 32698780 590692353 914288760 99897534 812489757 584503383 942544212 595496775 354240767 319889436 259379470 506602962 77489177 914551532 296491556 303017544 547427245 577490732 947174968 692514954 620960251 692128172 728911333 665877915 587140666 52427964 764502736 883121513 747042402 33570290 491376375 818315327 310822111 583099289 53518850 920574200 795686669 228947593 762031946 152965401 44655798 137482214 949752309 206324517 626757844 655361471 98959789 76380803 4272903 943545807 301387119 28097028 329144038 569153533 35023793 518791020 490577381 584361895 860923494 926212997 23333686 601813537 766698217 247299709 658900265 470484905 659440861 671617107 301226245 160206546 997809968 575627029 923042824 374410047 330443044