18 100 204103525 854460277 76365386 494936246 854716026 810754478 234804481 265916366 700034528 754239928 642407871 244689996 552266547 507098666 953375300 647434643 107969712 103342256 118485789 601728033 80644105 910878333 700325047 189662262 1606403 862622474 21335391 576117420 667735464 501676893 849073568 415389617 18707341 956640204 929407020 978665797 544762805 497739156 459993349 550571512 320743706 545769709 513947676 250010858 198000797 90603198 879947066 104196379 714472830 128696303 985795480 520816220 282859505 535600492 5295489 165669678 105156167 852536258 588128695 268139013 114558039 460140355 669765550 939437669 676358691 126081119 613923285 677043117 122697499 272545419 46362666 928811941 598252700 321166126 737384018 410905384 909671460 592198917 667191682 743377446 697349230 165078793 975827272 637994594 606903991 722944506 509494309 591743455 691142498 463532051 714191934 690491875 694482915 179953847 502512217 422686426 340549673 655904392 900128172 705095789 100 237928985 754964545 481341416 472735883 631932590 859980078 471764181 556813341 23547171 680854081 8963483 706570167 460211029 608528933 794397396 610682225 317046923 621504778 813222038 820118950 628941586 769283357 356122944 965408117 417236657 854445382 775729792 943070377 17584519 995439708 459996815 428456440 29895657 127602521 55285984 241706996 883862607 236163753 94983751 976720620 471602880 580950200 618320347 191350934 398120769 905021789 3289888 755709010 158807103 37012045 690898194 902359823 132765750 185185306 176901438 313973010 139564885 777401638 475125168 119653653 843149491 281692239 918224681 431970574 119061581 514681546 804636995 401803371 842313309 304581190 199531000 53976308 274699913 627104569 528000785 880359572 491420164 811079223 56157253 674340310 346295297 993779445 870811252 190924430 133785702 184566141 854362917 376199201 161126485 488001674 824432195 726258814 222883419 31845707 369426331 675380552 989919712 572350590 278099906 477174812 100 383803594 576190991 565346943 964536535 655019428 285690134 199946558 276627314 699782764 510061855 127118470 175529542 263604820 739543582 832716875 127940499 509575512 466564342 313188160 253416098 3032081 373624902 51679802 500866282 112100615 855044028 570528145 95416138 37350499 344715241 960051545 373151606 265836991 698967472 505991976 190760412 850074391 759192814 324380596 618134711 650855982 364807297 739865666 640935539 132158779 206950441 742766393 639181123 764236473 905502045 952023031 239422737 409718066 850152745 603752278 403243874 929151409 361623084 166258601 327282570 790932671 882635800 125787164 368401414 644455345 980161029 567770659 486154693 155988307 578589751 396539713 516025194 788119719 211937097 852643385 423622101 333784128 628819087 178397161 429860178 25269290 641964202 346946274 272924168 448538524 23561689 293765741 388995570 589513281 445826191 574606876 571979093 665235816 494369258 580941827 339255573 201519077 160407156 571949155 752724215 100 562394913 591115350 966955804 818900426 126198439 465219713 555938109 700914363 949351549 481857694 395108252 958963365 219530697 888962024 956915110 424737047 460369117 877417839 805983369 211028237 317478542 938985593 825357915 422624016 734380454 368185473 932613838 373229972 621035332 45351380 930684439 618652510 311275325 338757829 802512317 182218534 356244250 417977116 478219456 136191503 551818714 131762383 133102334 545747250 245626342 764725189 70927472 967461305 255153833 2025823 952573809 940276096 263968905 141224991 867642659 727337569 650016285 993703848 450477335 491613576 777156015 999962975 610228683 66747353 998186353 680355625 702700540 774764444 506911890 3418437 642576142 134964275 698035674 875681298 162323410 213115092 43330056 75230423 750017459 460478210 421835454 935795670 94784830 755135702 141494779 970923789 944631295 151282924 459996875 675144427 102635459 995076144 752463913 886250379 792066463 254887013 686809168 677142922 744216537 449990383 100 383081289 594298026 523517199 376822248 350764733 907699423 577608015 156872272 722597709 307756861 646284166 453382277 796625861 83110692 23574893 697873222 385097142 908861488 275869457 863022110 651824307 231176786 206684845 936406474 882354405 552463823 196534922 259267066 757041990 601390977 86118835 852065891 207439420 567132854 462997928 198202565 202297503 408444056 769036001 353450497 426684137 409622057 542771347 371526505 989392627 22045572 541416297 593216480 407833830 915543531 30970629 962235045 140650247 93578225 31669544 504665381 478218074 711718099 645211322 698782307 564248637 724312550 442762050 593429624 838064664 718402319 953299802 961001479 141313851 97609745 10566352 463582612 854137748 304004107 949401678 388290943 238042481 997901754 994011030 334169887 224732998 26802278 815473018 758734458 68529743 204258384 717943234 902621691 128455072 959854040 710250163 539865354 439021382 324840428 390187731 734111937 407526155 845687793 722762838 938602773 100 976748412 882833238 827386109 913228856 647269147 530292695 555235200 724596094 337958439 570944409 541338054 316960823 692080292 754129389 247291641 675539032 471595453 196099687 63351315 672899054 349474693 93700389 888503435 727957260 482685171 972591625 298464131 809301271 540970407 77004326 475948596 252341323 281077494 211496197 647495123 821061276 431555781 239299249 996191786 638991493 913464905 603449805 354258084 776972173 94687606 655664333 689567726 305401548 473288368 84020726 154392958 661136933 235694335 871508410 178462369 876748127 252215980 634710123 42464389 987349606 849605263 191344147 438015184 224782755 274559577 483504800 730032761 405542518 996144430 306525100 305721500 526191263 600909198 669809966 774017523 628164667 575729007 90388673 512062198 922007517 762676350 922648078 855864640 606707621 89728707 443999008 593324917 59098734 298791972 344667654 209471171 156180002 187454959 997412108 55852901 897996815 608977954 611100868 419085660 505496609 100 946390134 7509908 158092157 841152067 598402042 100230966 358406217 739546322 137676444 49856165 829997734 599297154 437028131 704312379 427667852 167176540 301065580 311862315 354696144 982823212 358671374 206608064 387927591 574619856 412632229 651119324 357514010 822509286 652925873 410627529 784851644 536922040 900574509 470160974 810531924 117301358 374404873 395154475 329719689 86203971 65262587 53783108 603050032 215569032 85817104 817886868 297911626 558094320 559975442 695434268 313804083 929057828 458196720 175450487 864309337 560090646 652655566 935839688 646570284 910285876 365121580 529584190 441651013 798162230 798854436 316341750 283865099 140291238 833030010 776922300 917942940 420074837 264511594 819186602 713090150 81128707 836422516 982584626 267741603 917088418 529702907 205612609 295824971 371812805 577559784 774254023 392176557 984167785 923777790 645791196 113220489 952798313 497994747 137154068 308821068 580355986 879335983 783663819 190363110 717432832 100 391766187 313084385 556805768 944126711 524688711 183306595 214034987 93572648 253141307 95927807 902811592 948238104 857939601 805081662 489354396 831301915 260075628 730572325 758482237 340512628 915649510 305511198 887389347 780331019 16123479 760473007 573947708 763830637 122238210 436220249 641606214 988983309 606895871 87358867 936461758 560195249 735541224 619982559 866379771 104651925 738176123 329546143 311933361 169658887 802183257 320915427 559043258 671480525 94764002 351718451 502459728 296727438 394248664 167784422 466550188 107784651 955535498 719117325 367180277 550585878 215753324 997294092 557145914 200532938 458360580 366635566 327107355 927754888 496253680 52943508 89930386 456673403 754465401 152489877 369054509 313728553 626411503 629843000 622258131 293053741 639066759 262016823 592857099 787987438 414048174 597386714 782052872 787949567 145866852 127589717 446531998 429062098 103149024 266013978 150665623 810671330 565415678 23845149 262828661 479860893 100 976089132 612457930 852587666 326629834 70284637 945697174 956829432 975101380 763304775 48581949 598541913 16127854 112501072 377436395 561733799 65582647 936194653 495071354 343604455 428104460 702727635 174913147 230493260 207707850 87990258 737754778 685925674 762596365 981288292 106441064 496962972 613571507 236149954 214508289 506487436 253878142 455656513 876280650 15239124 724645312 697556316 940373828 411477868 217094558 221775525 21679589 349876928 127247270 300988437 985104130 675641535 95440454 457934145 544779176 836502251 343632030 217254442 859190634 380993341 536007958 286061556 925807755 177576521 715397423 721173050 189063514 133937839 263613807 759256327 7237530 626558396 957854021 365884942 148755480 19031648 935987952 821082128 927485935 288215815 67720803 223846376 533237423 35965654 547590116 470425763 857052870 416008232 283642629 395499197 497100797 220615200 744439371 778058800 679342528 460161823 510977300 649388719 839242581 932521007 427914010 100 156031498 628444514 434982996 612803588 192922744 188449137 402939435 721522349 823680400 991330921 654516156 531848939 82420421 437180459 381399824 144530829 404623934 722359138 612296736 778567282 123228193 474844374 93929960 40329217 606614669 353419280 7629005 19172621 624367413 996005613 957779224 28226689 420183209 102084974 929803970 607788212 404225795 436057729 854926883 362797799 948728187 749853055 110768144 570329051 981005640 958994258 216450682 454379858 726330227 697184422 714606719 950624154 567997380 227538671 789669632 917638758 117887586 253379519 881704112 207585401 794008490 300755415 870073022 965426248 459111108 603184764 743282738 11431169 922923782 287190114 623283677 997409899 925817317 635919590 683392324 887198324 229787155 673393440 625271657 297618530 94779304 511739532 123274907 736179706 138806294 370088336 582529944 900197269 112774326 100345586 374163646 736380735 610045783 749406951 497026039 4272757 758309813 715205690 723661577 985571348 100 64701485 69929106 62458670 707994939 772284347 595777366 521574158 26903485 272790773 956133917 52980656 723370702 40584851 162379650 354473779 815022460 44847738 371298713 870119393 969787045 445291059 124473330 916363023 921833177 702630304 712260501 119218561 301508903 977662304 106607344 804574262 315098595 854286234 638460821 124425839 459550692 317941351 354213674 853644681 798056279 137504677 30551603 222491683 575510027 719123571 24274863 510365128 563614897 816666809 496387134 40018228 955111541 5495633 234817307 593421060 658835662 779941367 348410176 254016484 146463959 600483476 501824970 124152754 837236162 253872505 807724695 899286584 1400162 551039685 270673413 984939097 812550557 335535217 65759736 578304261 908753959 634788656 637633241 711899891 294237121 178540479 828046077 715244605 467542496 951866298 544419341 208809522 655858589 397205083 859023145 803074830 204229760 261490874 150686663 383564343 460417161 21513867 329965552 747677453 481918630 100 671999420 58106149 51764867 598345384 209763299 675723796 24341330 520487439 553104430 440904329 484007824 473081355 633246894 244787136 920199503 932929070 82812598 781846506 458764263 917127841 144742618 956505444 663138403 200855455 657274652 359901807 549544811 30984834 900504781 245446631 882947393 547786293 120239739 435343714 736826844 136709937 292505172 747320128 897446596 910358801 586985684 427500992 658059108 973899363 685898384 139704356 548775127 457445928 735331088 426461212 313274708 746658293 801596021 345591488 848466783 74192486 599602892 359174420 437462111 850570700 128721690 664576068 258307025 703721252 178940280 701685847 383339066 52318420 697623757 433426900 946303241 15964221 161751781 463608244 858620004 442119676 432526300 52751693 867299153 179037831 152493100 946069516 314118420 165521774 998186572 654361773 344238828 215577247 65448778 514848518 543428368 196193617 582915114 178030352 233427666 124594944 281540241 6163865 476066946 172864022 100 258403087 330106287 838828116 878556601 770869981 261402960 577787278 637534785 359253391 620488329 616840524 151462872 813310620 366572439 604726741 835891457 482823851 650831359 789268564 748255957 952870528 58416375 133967570 219948860 64032926 673352430 248688540 60027355 595626236 641099216 933990783 406248440 631274221 395422472 86495923 370339873 85063817 977040519 695188389 210520389 484155637 514977714 969290117 541122252 540396536 122991375 125174726 946031554 169777525 709589778 341115518 105404314 456338837 320925095 872658394 758338270 367445488 84413166 755334689 222731756 441239503 642640717 778155121 449168113 313958817 249839372 499800692 564870176 552929224 848464090 32359007 985949709 582289220 698024468 438864654 740875980 871280575 780146519 301905354 743138074 47249348 417324744 847753313 199175769 769872670 789803036 791866943 610311943 351204280 873147526 501052631 760043373 126246151 624691224 366525515 535816492 794687649 981775840 593720868 69847993 100 526767349 254690942 733543887 575483835 451012804 187015989 613001951 624185813 126858661 638987399 62826449 852228237 440790203 942980223 471882456 604912325 218487875 142908353 602079391 990998577 66095347 22437081 372986326 250703947 360272737 821573173 259384155 126153486 575661227 239962008 672898828 482421437 250770052 596039855 825495778 507102042 164666707 902294681 668360455 248159832 86604132 43924481 994168151 29943350 37218112 873338769 698323379 326330009 894484098 858901707 367638725 848390196 713774371 37721394 695370256 810259958 400049445 190534182 738639102 122115556 117357846 153036291 847240844 248077852 245042070 745442838 682758668 127136383 385989760 888980113 684107845 318529508 402086686 814896289 557737423 756932615 566112987 292163571 330394850 784432628 898015034 62593006 102599124 887567006 175902122 430096819 18550405 136130001 210844705 892123185 2462859 216920926 964353813 894482252 692826391 577306695 352800521 573489827 910109359 336437253 100 384209854 416683691 564802580 172682611 644226139 421107331 175157188 61941550 218474305 505821161 945500184 596250490 799129037 487269483 462382406 725952272 969325327 882064323 849395021 262827881 309737240 869230954 428479930 134898985 361666766 495363637 996095289 406029771 656148579 148331852 936422506 627005074 968239093 83773030 261597950 894697192 466297688 985652958 970160099 955531389 882523016 620453836 303763930 726666126 671366419 143149852 759978545 812144737 580025270 544960262 885732922 496587858 21498646 614096818 573276850 889296550 480002481 497692847 244593049 630134437 651279897 44313449 248735127 531503326 155264331 982013 540223609 159061792 983280854 732158678 382051957 527286823 688459540 187239183 928665838 215470646 188593157 707955961 10388920 839261968 39915869 235873306 817782713 489730179 444571237 176830735 745515012 789290228 529880859 660142358 974271824 514918956 811488225 135500710 500083558 681224051 675455081 650585464 55287237 785848738 100 393707520 339950152 657150410 146177640 347298296 155386778 611481785 967877089 557401001 887482950 910705133 451112897 715322795 65102845 936161559 467684398 258330590 430618780 548591538 88211560 695188486 690585088 706745700 381437817 317648821 936405441 374458643 188182763 491138289 319043791 186942285 733666447 694357642 104646855 151814522 774289232 583128 141366041 174126386 464533445 324536476 140657513 536688612 780420831 385970162 755460259 920721167 581489456 389103095 540481706 967781836 38326737 862719146 427575339 823391750 287530501 292671084 491773614 474527921 980131399 889649513 182073048 735065953 314840562 977434016 900535827 118899230 934305301 725521286 192451897 31025709 342535467 984437562 251508153 714389849 685943059 636246219 320459100 69556205 566880881 279920828 395809499 50739688 497757928 119356161 967981082 661813241 709131166 96613382 107764745 455212372 983902339 777120408 970059963 258985137 973548226 904392971 904122084 26618991 538612488 100 165132181 351868213 417021245 472703514 652361597 606028368 820868513 332584488 8826036 974309734 614331625 554870342 250814544 459049685 887871106 282430568 768035564 200427525 471374164 73548913 168184057 444629303 473061561 83122918 157345772 23421511 505155605 93416634 54184279 940110172 790214343 15722986 183752289 752143965 16381801 318079252 320352262 937015899 131554196 962587747 986365807 166273162 777357722 248380422 420230678 143089952 13955430 26192457 251122346 485714579 282978607 146906249 272176508 439122556 369218497 832399160 543585445 686887858 976319098 72501210 787975168 498875765 253828885 669455996 277132553 162107048 609626855 34831624 139361803 168743321 157970265 912631528 259055457 874279922 60177141 312889808 497275640 14823768 669917740 17785304 369875905 857126361 949222174 414521567 178664561 687418506 193579699 661045201 152984206 786733122 483884674 623622259 526823879 620896725 239267686 620423213 973229211 306150992 42838446 699888268 100 596998866 812690804 82566519 71344772 99300752 811508419 899252767 36940649 488923840 857799492 117954912 8434255 105784313 187155013 265572282 308217862 952308133 549627807 892700965 60539990 102799270 195909087 990925255 850473101 715129614 9573024 636522300 843981231 309914621 193992839 172758883 829061559 745695422 591241502 704144195 113744149 507782854 744259672 718862576 264424371 338625392 339612880 261171806 780112882 943846638 978852632 527112350 157867105 561679898 33026697 35567313 440902116 69103789 51143049 310162615 277975168 3152050 848397245 929388130 716622282 889200920 683626787 263883316 157580039 722261903 310414803 103870245 41580301 172007498 545939338 253657228 504230485 499208322 578126231 43160526 521070860 265866071 549880575 576436142 528294831 228866744 894918078 652838871 685417417 456306149 835209206 251512193 783836599 724486573 509503476 864524519 894792635 368131736 431817600 359208305 323513 92762077 317943763 911656441 426606867