33 43 9 17 97050442 972327990 558069863 997918004 799499598 388541480 77252832 241570013 625444627 391692637 572100825 751434928 108512922 80130916 274197597 173403170 375458539 101232467 23274889 320186747 933655485 563606305 882133999 689177455 130788673 243825405 835639934 118342488 346254389 487563237 515922316 412751591 403212842 633679211 972068389 965638989 753863145 140995084 184870828 395424807 826716741 599154855 152881996 153199243 424440184 912134856 521363330 948988186 883365759 167582622 108727961 205519292 586200871 404426245 526366446 238358367 486406785 392172507 90392195 864912356 639946365 553317758 720564982 986892092 124678348 958963404 69695944 907481383 760347355 740546656 675643001 805245592 473245233 35341261 896466636 914406524 80555455 550964699 445604282 560588970 7711259 652815893 831151439 755677367 299225064 500867921 144884386 617914415 423959659 108468016 789225565 677641131 176764229 917460473 847208552 908345567 502496190 353745186 905655778 68432356 885187312 28630674 896503624 889513025 814124836 492894840 348745356 463255486 929923871 161387832 905776583 651271270 962851682 856781469 918893899 358967910 493452890 451137536 580030798 183293482 902470021 100094772 129755505 246613527 820523663 621711054 272344678 526949934 462401967 373578526 75388854 235241573 63263086 947972532 106109332 356099930 985190010 514673518 49133917 359600735 789156715 113644124 50096022 980844722 380254683 491498710 957894573 29569965 455447057 482940789 812365433 690972994 964614401 813571948 294414802 150442930 915560305 241524092 865234337 321401808 435727905 28132246 149829362 762784350 32692751 644968287 732448871 779032125 693030719 201829687 910004427 211829072 978391756 184930164 803452228 280693247 675299021 967941775 709251049 797986137 440278663 922403278 787370019 757457453 301394514 884690675 83442765 283878469 156578560 257653524 963178280 511913948 762160609 375916914 691410714 177228019 935491656 344343886 921639015 611991798 903553652 411464592 849254053 906979246 692065579 992110364 704899681 12728539 882599208 46474138 582276234 473217233 90438263 941241793 61220759 981014035 681634418 354365488 472445091 551890530 610412133 355829227 336676926 293036429 555783222 581552244 525720418 922383953 967177361 9293190 204991166 89471758 614504880 369398089 314050422 618579272 34402406 581637342 611432315 561889164 577362820 245818811 720210033 448159592 966315958 522769217 787823403 253967859 625625292 951306551 735057151 476832907 36472641 25061020 250729658 486983292 258546936 923140210 423600402 688478134 297752750 363048746 742670709 428500539 223171363 703352968 346652356 417948848 787463836 262171251 845767029 820875662 909497874 537044411 267851308 24442185 459922359 666168150 944124097 812274340 801701829 488260515 180393088 354213826 929203648 494877880 306910869 54516339 363276263 975977022 415923107 217617456 807662881 134726481 678009404 370430455 523298144 357773225 859626566 937497941 906224699 163282459 121736093 282677344 681388167 156011020 342603349 115658820 560425375 190664613 218947625 377158907 339389274 401779370 947706359 505618743 394828882 430544799 733331036 857190185 437210388 407559556 363835371 585164590 10729457 782691492 220090791 235090470 790010631 631481050 716488121 863958912 332256853 637484869 746999580 574549640 83749286 244689233 471445061 915787010 615782725 929916813 473299434 602370771 685268971 80200188 421077518 91095199 375572018 395251808 49142063 695695986 287806121 133844221 512616885 248187429 402200854 958741536 290044828 799353570 91729768 361277674 961766635 295757241 473856123 829377435 909465939 655158161 465445412 827498761 954754164 626592650 29064253 723156596 535801620 960407938 558164823 910536148 567719667 680186045 261917670 295163426 376226557 471432156 582054802 836801593 932224463 704525425 949332698 879866329 452805998 981802218 569616861 283525004 305981568 85961611 326985520 286866640 664056963 113909846 506054230 653751423 820270726 267120935 450417100 25162512 580286995 276208575 278971722 686783808 321261992 345256254 801013363 158419300 690695929 985331457 70040783 74152591 459523256 564522578 646248764 870922304 216422480 865289802 931848360 362400865 268992012 591623832 14773806 601222319 828656954 114438413 972775560 919713025 254776469 815508531 262588050 898526277 337036582 87489485 73992271 426066936 307325700 605963450 883019088 310465562 485018333 301215032 623440331 395319642 726423474 315226400 229200675 840372301 581406865 287228354 410551195 799659772 731834982 390221920 226213540 298006358 216324337 402104980 49704155 315278240 40273187 500509123 872282855 116744295 755213010 215726602 203538369 589639385 809254498 424696125 58424844 733981292 379993081 853355882 740238751 620667686 375383211 816205669 672410092 532364370 8645448 142972239 956486862 101456906 521022065 9624058 831878323 214143942 366622016 261561288 127637414 329064057 174931302 497252199 983983165 296617132 327031512 876322777 608578842 489070906 354842727 280613090 481023449 94464416 57476533 785787375 298627707 211448833 288980473 652141547 205948514 108418987 53619493 185134512 858125946 542992330 706112447 520020134 493819817 269671775 555927262 278207643 969393449 487076203 263608008 314517646 441219632 723821388 325430892 323326531 414415938 340270902 388369885 938962872 228566189 459147856 836802268 33982232 844128414 129003341 545050911 889003578 778151350 632169684 646619916 736227282 524272796 996335623 226981177 590902379 498865840 378366091 95026448 698405566 957557036 433840423 419320099 3266670 454781684 658978169 820346420 376776577 440831964 719480746 519963450 445921341 17925379 422285188 687994356 19552414 346500639 492491970 931752897 700092012 392382225 841932887 482946971 798190790 164026298 536312882 998904840 913356862 100900785 717246164 492444183 995076962 423807814 681878812 721016546 230968083 876156050 328770814 550844012 591837687 567822930 825788081 806668576 330993434 652954209 452989329 91626633 363377908 615769929 250411108 671360607 853631924 680367774 69815239 708182391 438306201 691651800 324825859 8835822 998169624 938692955 186627347 550466118 884124196 195199172 712860126 432235607 838223083 89224045 207720749 725710906 298928380 34832254 957925627 573999290 581429841 108645053 147826286 630139788 403798682 93769991 516770811 78017481 87819774 161115394 690304762 805797237 277249713 750505989 123593517 23961094 280443924 132294491 505744615 389008465 321421344 223396677 267135743 175785622 863937562 622102956 423946354 488427371 576655709 968192613 424282319 940216828 704044776 507339386 310422664 98482128 738118746 881675032 778295999 876348256 496559483 388169495 596894918 566442546 421870347 711328424 53775515 213023883 702743140 176276672 880713662 95755061 201941162 346629267 820365739 253781692 832296074 26855884 406656424 340092785 127415649 576393835 1448997 674074142 892523801 331884442 793245734 763103309 941767235 980874374 82698492 514372778 629467926 689219624 874842795 191131036 100957342 445974929 781807132 699370505 307718623 231710770 164921034 836121634 892364055 632082340 44840288 200296525 33981516 597279058 691312733 248700695 668138027 953561875 25596964 374539746 331253653 42485906 868716699 100398207 638430676 823568117 724474936 962799884 234908331 818015130 102933741 691165537 776973957 883923575 92233419 824312428 100041242 265812659 566999076 59557718 819634905 511293967 75523849 93232850 666853159 214528145 235045248 880234181 792728985 297181276 741931148 224483286 512982983 666902582 799186446 905587035 949425794 323051320 620137124 127420831 463272392 711555690 768863291 148600639 322530371 860655618 1011544 863173182 220749182 342827378 449364465 424907598 218837897 341569620 351908545 991600043 177656171 285101986 616250074 589274595 194676722 184448051 725396170 291563693 188677896 972421459 737091972 672086261 390611181 227526581 53275744 159759017 472964208 520932899 456368152 109963991 168222630 934023692 364536918 687118915 155763411 144605949 290213547 473172058 849921747 665545385 318251303 63621312 598850840 864382581 90655151 669973087 732852227 966539558 818964322 354378672 797983431 281523061 394711021 911086387 124123639 979904905 626796357 809252785 977640058 613864175 138230565 740201540 740129023 184954775 287126691 68809704 759993745 534375223 265786727 321422310 723344133 944841202 436093384 239446575 909459745 93226223 625331964 96700748 218698511 9763462 344494805 915238360 73297638 850601217 882512525 72332644 605591118 923814256 956154619 688132914 380767922 104283962 515794721 546388238 958213563 50710629 635377756 353850146 630230937 270071658 377223664 17185955 802323483 169580293 849121832 774967671 675898363 860948568 384674385 304420409 790228578 949219395 460106827 243383465 332886884 483774373 98853505 843648001 771144024 123522294 379187365 154166888 149456700 831942193 779126766 274797416 368902379 34847560 150152844 606866032 965898734 974113147 349756865 986123722 980197379 234169444 231196192 51772899 363272642 824938171 276886085 426183438 218731999 984324618 929491117 434720409 325443319 664713876 928042080 596770867 788465552 877108432 878368379 889706650 967108719 175804216 343015486 432858804 80636508 133113232 551184717 892116004 915107880 630900255 541388675 578219847 610404648 1504335 282503123 725334772 763785930 345928828 141833293 763258511 940871752 948215275 837938395 128276118 926665817 836165674 88919559 832204866 694287769 970174660 101666420 975620568 307642014 621619623 518811768 460765218 14858456 642482083 528616093 809457634 652656917 479371002 274028191 573901375 299477414 675490280 128145616 164041564 590647425 686574302 544594810 917287688 403965111 409039293 824604713 43850441 428300082 610943794 666406280 297749490 229831835 556618667 787843344 108217507 579163734 198765423 102381349 515290966 419931397 710132315 433535248 461395888 687258347 286253730 876910219 388593150 87656044 212140383 573791183 434283428 498416260 700823041 940873397 468341880 522797739 815186671 331367524 762868098 590181385 75272471 670581019 252650208 316025370 697564541 684438301 966557012 55211767 643868986 667577487 564552468 145821140 22853335 894095306 337993790 866598387 386840499 774113660 369532830 38718412 922940247 485363132 620776147 446456925 277159470 930044606 790359259 923349039 704011273 948504854 593224220 526511037 203730950 250225019 356457661 872875111 706902296 124698338 931966511 721732399 75767869 283963216 209709610 110305607 876179519 227077433 904540745 60744010 94656850 753014077 476361003 889465809 376368585 828220174 567637701 52674468 204896313 474633309 724068682 409934159 27325054 671509841 374690175 579094881 426525537 67836476 668137561 701098617 293373026 749886857 251444307 86969359 137004426 752962186 305634293 721596753 738952731 804594496 748893537 103313730 351967233 37406129 467890980 721978823 987340729 130945498 932871591 955941606 169345550 315783300 951172869 384124662 165104128 963878947 411714165 9604495 523477742 614726749 265958205 177021850 801533598 768697292 742443767 679604394 300023465 12255118 549027836 778482708 969794877 995134619 191240993 21692127 376358999 59957686 759429719 353900675 432766893 949317831 854785348 569105022 815180150 750781061 718569465 810056463 597330315 803510758 30793900 975514376 666096793 359795873 985474816 927716918 763536775 749181186 796158951 80721696 327107052 118665692 76896882 769437642 999761806 304161337 477280317 928734209 296040018 235755125 697205035 303800643 742059031 87757948 761445373 279690898 241824173 187689966 343670771 543747269 227040432 908385459 822528659 513343014 316005795 857332079 883076854 541549234 690295013 835022021 957114961 95837785 671694120 961395512 827805524 719285767 100053553 94004191 920476854 553481904 315095355 150614283 145236374 445685643 763792759 643229887 904395611 785471705 714786300 78325413 351474590 348134580 457930931 954354172 611113085 421173981 283137273 76130775 305992393 392842121 141516316 135341171 950407773 394500620 804812256 705188919 955938142 320186998 561445653 708570233 650353691 741582977 847738145 874097809 742704849 534392799 673525169 343789859 264794010 150299437 113977044 955315568 288393150 772565469 375444762 686677683 617070235 123078802 711510337 116104019 137299132 538864778 29386519 27779943 631043138 160187495 225801364 870909787 341289489 749381414 217899423 514352183 534415215 533873748 685080098 517911454 438616047 774938674 852284245 501135221 978343111 257373630 858173004 955218017 393562822 419475890 613267901 355437205 820485069 915988225 448339571 557052215 631800213 159429706 809502843 365168721 633770041 71263649 741117132 503018575 824026118 287737611 320047681 479533355 705647026 955187618 759693603 150148597 204856537 623003469 871623691 125069297 706195669 239339696 894710127 970492144 67540976 909416163 519196293 162082331 699764617 57895534 282524087 726273248 81647525 558574171 934271183 891206770 87656074 490072583 448206356 965737593 708751505 819473431 509731485 671849745 547090744 431070872 728599132 830553899 197011196 161958394 21604944 681428433 805421421 567927111 242101985 128831243 573082012 473393189 744929447 332038965 262036287 893764623 645900163 871999897 482629078 688052144 36640661 194235378 446047912 688200 252620866 327150127 165198119 980393542 4649381 788968363 229086188 195146819 536704455 828375112 385678652 438859482 376445153 515815249 327628908 479935837 659812723 922097807 719714648 249536385 9182669 189996938 460474965 473390338 103373897 223985022 898488027 438073191 467432407 921256416 556645959 642827550 459633214 428156444 917822565 699636725 615527013 845533000 780578363 579142703 168183242 848964837 189038383 497122694 610110206 494311507 670024805 217539243 8823482 278484978 186529048 516233524 756744260 402214571 457118705 110458800 318384675 411942474 129062409 472848817 529482387 115735716 759496319 730820425 82474305 870762036 558149214 297164556 547221602 38236699 177621195