790 790
947138896 953106169 808925544 382167533 436696320 376799444 964717615 898581880 687080978 361916392 368194377 205280503 338266234 478195386 193355981 244719886 17802863 739453456 31089936 980425379 199602788 757206253 10372773 370447066 29649168 271804056 361300068 78037273 889550694 862781589 684033887 297753861 222317212 775649448 626767085 761334402 391077927 631850712 891990691 973897654 357275068 108232554 914622036 71842566 244152656 89421025 573468695 239377686 457728792 757227012 16479809 238969036 102768008 890930646 224660838 417640269 103655255 251031966 132947547 532715517 177950072 585125088 456079926 20340866 842031393 453575521 136796235 706227392 794848200 498467622 139878448 189401821 776342816 859150964 899887544 995498814 540611871 998245329 705209083 107569287 272140793 707678720 260919371 677249438 558997541 787110408 400314943 145503656 956517975 164772141 615360428 511211529 960630659 755989748 472857510 451910759 718698208 288991522 177933698 592482471 560489441 426011580 842334422 920992493 856832060 621778696 162878838 57048991 140290022 506611594 132465015 225225570 78619412 892882950 455943983 671099162 38421051 747787139 228673842 77287917 205948944 314967877 794844758 389095743 855402376 677417169 278352815 673230518 470062039 436226029 736518290 500964919 305680500 716524188 543246485 249436646 363938066 845575461 394869132 632194601 660734887 769143307 989091724 820400549 789876328 614684693 440310507 448736062 453782986 222387783 548625470 293760026 764496002 151013350 362837592 394815390 479747461 503932536 711486544 60001646 8703495 197484480 208954235 954859888 943034751 376981444 81338733 697853896 62692256 685066442 582262779 949186269 14658145 235234646 818878779 268992337 23492085 27740205 905488769 385894412 717532882 365470292 51541346 23072305 397288877 827564816 158095796 903908133 893861243 537610215 610950027 840540303 952268657 874644636 729096765 34868818 90132739 4425014 295662942 199560339 570839016 589711353 268980419 236274617 967091220 59410794 460877954 799120487 692014523 581410894 542719215 563439490 299833171 478977962 723825824 788606512 16940945 499016387 19638377 997239254 715357034 227778847 815762271 243031577 213403667 769748098 988251864 264340701 659555073 753249008 24943208 425355847 948311529 861486256 293811684 869161150 135680191 543582278 753813346 639133925 560671674 430221944 338504502 504392610 260911949 864919625 109235702 671031321 93614638 762278656 491287670 50575792 856717138 728996384 869680076 790693387 704623598 184705392 530340172 723944209 416562551 778044148 813067403 308359909 812854178 507465457 643128158 76162028 433071204 137339884 389089243 17184972 394527730 876247723 131568727 289619050 365735104 677787697 46691686 46113770 687374212 624524229 706833373 292070067 935751476 195788010 759173329 564358247 896090883 274074471 489184152 641864430 126186599 528237376 499021767 371855979 77113109 124625083 860850482 233011523 771844866 847659611 205593582 456589853 106196066 221333222 318447184 294885851 231948716 367074658 227630830 142038949 415865747 387598099 62679709 97554654 717425934 225162622 175515248 939662124 847935312 487347816 408704446 541483124 701007823 305903062 69046812 844127450 211119680 867326477 785866590 567894723 622229144 124033939 42181529 38082774 165773580 915036459 32929571 748378102 772297233 234789340 785810064 187123017 44186204 501091050 692747445 695149107 114517729 823997914 105110184 144921178 30352086 126468721 127756221 503468962 611221425 265369780 66997642 953424946 422552869 890193129 109449699 309095021 44124456 120889747 590191837 137299704 633422831 964464505 113739982 25928377 604262895 435391391 117666378 704485589 632465373 119495498 140858919 460751537 39509165 441884671 944395129 408386033 650790806 198413188 485194645 903523450 916858891 708842972 479344145 75417203 181444035 642651982 965520577 832313919 655307953 287785053 541028795 130138755 126789899 671429584 957512018 355623462 788041030 270889643 209604126 627508299 650800151 692140083 393385713 474965079 962497139 233282541 827094243 105725424 31995790 152771999 172391238 969962747 235631839 85618508 997425073 290871197 400504857 426744635 750483448 365867578 368327474 779245040 881031217 949686648 558324320 485588016 697871536 965812283 793662998 43292928 752896522 479409065 11836682 226262949 994182933 261073191 796226097 500265893 297226469 612739161 381514944 439004867 28201168 931004709 479989803 402868998 312480874 123135920 844799529 396930738 303127944 137908318 800861869 44663884 301570624 119357909 545868782 708752025 878870246 232229114 681291359 54544542 586431504 488405745 333188278 171225504 929589394 899875616 305694696 692163365 193548673 10194219 169510698 64055025 891512371 162416376 415259121 109923080 411079740 652781740 132006897 855186353 609825649 524268715 865491745 91050352 494018536 14722971 1905588 348028683 486715894 383091809 68604961 606686085 549097006 30199841 674984731 828938277 743591271 767041089 256130968 816082030 502432438 526275686 308629197 477447719 306212719 39800948 658987567 508920660 836978471 255608465 322125683 103553082 361980852 753101090 327314062 367995230 444681002 716647115 839080884 426886 65427422 646650993 720602460 854209973 184748134 38041915 654773817 354057522 422461846 90918540 560082753 321481600 767863940 684201482 563901866 833708134 406091908 644089241 123755751 754190312 576483115 159997791 32900270 591556172 251030607 52721601 951491315 177409045 697576964 600864611 527458797 820340745 748728991 398739243 402479120 246575918 627272886 182731837 37750800 48461000 805089054 247078400 982614244 510403676 828534506 712287766 700491199 582263215 735070578 350949991 722177047 295388358 173612616 888971030 176845729 326073318 115699011 798831753 355604050 821300629 238979703 42978660 979783775 962360982 933123130 14926989 26881085 938309104 273108256 692487465 736496288 361706727 435262462 463935132 141469823 684758784 376012266 691235980 483494157 877638144 132036664 536051934 924413888 286876140 762091134 375877046 371673678 756629770 794906768 219682170 599814826 454129629 760260739 123920079 108570890 875980076 604850349 428563097 358839779 231352827 255945634 648043006 368656361 448287119 152001080 117091938 801648147 999072109 396439427 144264043 678106005 21743450 288328920 280260350 790464995 30760796 738421197 144032063 382415539 37783478 980123702 691039892 301671418 525421295 952791593 71775650 383982574 863075787 602896890 310349133 163484930 575232335 119771198 425165499 846811627 610079936 941578187 139930449 23377312 755319715 581318581 152204467 196841813 169235390 42802513 959276743 938107518 828920084 88876085 274039217 121782994 618961388 362557493 441090007 373918276 42217162 802911079 557410782 13533962 78304371 471019551 741052075 58528154 976956396 703407346 252007266 936091815 149257850 347881654 203053928 276655910 255608739 769537664 238176868 657347662 916991786 381829027 948737081 132405651 983461142 652310966 141698316 354774697 654655915 76128910 698115908 434004871 601427822 854539838 513977731 320034912 823478052 195720989 948988081 103968170 885984722 845774784 651917297 254110235 220214973 357283067 534745769 474228390 801784171 504919011 483046526 972236929 272054176 849296334 329539412 285972768 796228960 120162896 122841936 846618682 446908658 517242175 690368217 247159235 357512922 94016687 317276306 510935023 400703966 615659765 309727584 917483828 604326145 238179495 558113386 713513032 272378249 513571993 215838483 528642590 695887612 921350624 114965760 906639340 683882270 136608722 477385240 16389415 421879796 183770627 445524093 362313604 297695683 672301641 940999319 873412855 465128720 212680376 195524361 56396727 112023712 274953125 199135929 116721207 286473081
329165754 601778732 498029821 96615708 662787550 323832379 638981690 403020458 3370771 30874092 282768142 268213353 158364918 193041900 781087799 666540070 922637156 818689833 680961201 613368302 52092026 313138895 993219514 581387789 121603221 41576011 166222542 916287761 204091985 713001291 796175787 662860231 875778701 90839994 158692430 980972348 157974117 703947719 509176050 708858556 112003382 82648031 24349719 189027286 518612125 59541165 250187896 831946325 998152311 858156320 633052434 89302087 132013281 688465508 935796003 722357240 763332152 983379942 800824871 365701622 642933017 961747284 281365980 795249422 25332321 44422298 142242879 312022605 52260141 680239077 948396940 337926912 905723099 57114530 218146880 651855027 897017094 369980031 102005017 805396788 619528076 499728744 240543508 686491792 922843274 871540618 148472685 787557652 33133661 133141586 220089249 31822669 969224610 160776046 850412398 336486919 811379510 590441162 261057745 733891152 674264119 528302227 63922694 934514036 270533632 524705591 824052618 858534146 327067183 989593954 591301148 936147141 115448481 313937409 610679990 196578507 163134836 137763393 591175319 568499041 111978755 61194639 826294076 263808276 364068844 733101465 315626081 930894000 267407628 594230347 622480900 743284547 762473345 113405395 110548065 700260890 387602598 55885980 949378038 600607426 842413594 194077013 382936447 720903943 76884408 723796202 703289338 968850679 34022814 352598665 223567523 414404319 738616874 43134878 284332280 853299532 8371191 249122774 931769013 927562506 427035108 478902046 186208728 689392935 350571788 563693475 753100445 426841328 290286285 926120403 553786754 227363314 329125573 701181018 879189315 951209978 979970767 152122405 478166238 647400212 568929034 938962018 153058704 969561998 241469905 91779709 848933077 2068469 640848323 279337507 363734122 118199062 471298492 814757185 59617869 363890173 767014104 744369157 98923707 610929144 864752246 775387 744753711 382893716 115690545 933919856 744952681 828837278 563162088 464413617 190007140 581384482 801471927 319769036 339509085 583031150 506639866 187593773 332407507 501723407 442405712 394046593 13799808 704542930 138750613 24776885 202535779 116031939 750287589 78544631 402681529 749230897 292069791 555315635 481975294 563970727 88177759 462594454 234890223 145459698 7625986 936003470 651319691 562575649 617720740 212968135 37516812 46485631 567581348 343492782 137066737 701454490 446661790 16231152 694178807 478104127 757944431 826876795 869626138 589844603 334108979 136553595 624332440 338322074 458308169 160238685 872828141 267169834 132689229 710284238 456345815 250234616 199300636 137422268 116767570 940131089 51195603 41474899 912138652 709246657 458011087 834974208 927770929 245451926 687234989 568872304 512313295 935753053 214916426 643972497 725814642 134616611 846900163 193795215 576154712 22523957 544438389 533361879 877008638 136746783 430195965 394872087 221663263 934835887 319386424 491585595 251210939 210659058 430482243 228237680 217972749 215307828 211383675 84822563 811732882 777873155 50096253 917402113 575448840 573999661 543252262 899045112 25896043 541989052 27312275 115832628 512910329 150961152 584013345 97600803 601991727 521826180 14316397 939306352 638153673 400970007 401239636 863859978 456928196 18448067 494100723 491172126 62494046 61441240 861284775 958600983 43812884 500457442 863765774 189670564 695798178 889681581 776504835 309944753 877214214 161184839 908865444 325417579 394426748 515274749 463167822 276002111 7375489 66631003 65988766 766404315 813062611 292827183 331126130 382292011 693648495 860106374 275669477 253193820 257849745 596902573 441201749 731675868 288903863 204813105 14476640 251142487 128352669 379407070 948194273 299652538 91949121 636361410 672530678 393113138 327982303 317204010 215487484 786383149 53183989 267867811 176446097 594245463 706283071 254564857 142434960 912149917 773879483 232340538 103643160 84767532 58867365 613234611 132302212 121995634 949120379 387646705 388068722 524831771 832808697 687300800 91939008 438600468 924993821 464159791 352024713 741769355 125920803 348390025 21910572 51725036 994015369 769595739 821626692 993163492 425027851 782856820 16333744 876447584 952252071 779242463 569254795 556292493 278021786 607143914 673073460 405057753 836839008 545599266 165709638 581006576 768895414 162683988 93742752 149638592 188692122 141286540 833318493 941916532 43004232 105473816 916022748 642492539 642344510 68652421 887665337 238655873 929124409 374376864 986277072 698198900 188626485 997617013 860736 90717055 169911151 927951698 244617573 298614033 59403621 175442884 380985051 842680790 44087764 597033880 282158465 150813628 137707704 16931802 297383027 416371951 39060047 85227481 783893261 981601244 105416981 514096928 260532974 48605488 178432967 525831548 938432498 947672024 442830179 236621564 432079414 258505986 546977574 219618795 880356374 225776666 576608908 921334999 67349553 880319182 618114899 339769997 543255395 12492041 584482679 30253082 630418633 30633210 221399350 636841162 806656960 786934029 490445580 750217771 121331685 993346032 280199095 733960202 53705492 195430030 969559603 140315252 896496492 777476630 663917502 126433717 614039369 904428532 495733204 132400219 110905160 116870102 598189619 34820403 910586438 10138536 783779031 383022410 13330784 912615831 402333182 551890413 870219251 333922832 757356068 421041320 503614364 348538816 341733895 642789193 70845496 11806613 433805988 353052125 132664804 923159227 333140279 997684912 479088381 757354143 924087613 600345169 692786720 417634543 944270452 31604619 417704490 714152343 547842264 866749804 332352568 927751876 836656295 327114560 8231335 487999715 865877598 875888790 293351956 979452066 322897593 749090617 465725276 967266541 237716661 371407671 616588189 265985777 661858704 477333212 509089074 207698460 674015943 526876343 846416057 58109977 763570198 121665427 98162447 842481879 984049018 683240062 768422225 351440514 484130609 311703749 401696989 524662152 70903224 758852084 819228494 161550485 330935755 549538265 977028738 484790934 193700968 544604801 86885014 376322744 757416651 62183481 737561576 973311593 852763762 703602062 605444371 461244756 15883545 654160204 838029557 818042729 199644861 624101505 207576235 901662930 304583581 297233530 936718227 14243838 37096499 566703300 819764040 612716952 178159423 688289579 638210473 134713488 408971707 664251837 577075409 972118544 579674343 101458631 198157086 329527175 567674941 627261654 855842606 492536481 956070781 125861046 965826012 211266891 154555554 186073462 830949447 1301938 405359081 633057889 794397130 527242308 166932432 943501572 328478724 755965357 119363347 514567470 482954448 340015322 843323568 79604458 120745037 181354233 235844579 534217862 924362966 141908342 926060586 647045263 778712842 427253246 248926530 180859858 220170180 445069950 955928359 865895259 524512803 73338660 746284566 815752312 860639106 634155100 420041869 90986166 673925504 161694931 114374985 672496610 692133369 818710390 604198726 287336456 46446857 16879987 685787585 562200438 802182927 685854262 740198968 554593977 407673511 835925356 149180008 315928734 782065837 237334787 416172621 12593201 469401152 983106854 434572836 489507009 169128124 905217604 608899691 948380121 594689981 252854026 270570975 658783558 151980322 993550435 798777212 931539735 945184519 606709630 889265280 829662103 12784585 679182279 117401191 699097940 628630020 288952043 616789743 27675931 685065879 11108056 937599508 565423097 551650974 6202298 577600532 150995770 900835190 615992830 988235115 864775276 124325052 747259985 400098519 970134876 43400781 287647649 239435604 509019159 145510982 668693274