954
620680848 2575255 666879088 792450902 269919377 731859446 656619437 611293418 663921865 25755226 407413950 756675620 374271141 164740932 745928802 103609349 639057369 33480826 222742699 557527292 396803255 275702252 426974282 989152700 381335961 316038875 350876114 894441748 778296203 764261505 714254977 634661241 38757831 593288642 585609697 332031627 260929293 820242665 273990997 445290889 29633467 417521414 421649582 373141581 37563580 203693761 657254245 304665129 267186508 125134987 865937954 787293276 531436072 684211781 934211954 770257605 411517198 938770265 285928938 552700950 940268500 931563193 322758199 965278404 622765178 10194163 383574531 298573934 291731818 301609131 595897809 462890340 234293088 34404987 944591213 51204212 289717185 520480364 265919968 773032657 620361101 907755725 505727178 923809366 54450868 396532227 936529643 415641487 774412719 605001258 303690460 889704031 371906324 166533854 396671412 456347654 600048143 399505009 21848214 319820996 66240471 910905305 78964753 173933777 870974513 839486340 10019270 780133077 531335199 767176671 38729266 358935202 236028252 521295478 477376687 809193772 175211493 53762246 974640177 57485960 611110879 525352614 683637320 443565577 167889923 72877042 791552050 897817801 592314390 860406369 594970136 307502950 897906511 95453853 328065644 997120142 838163608 127012446 955128578 547372026 634812036 298698429 247275217 393529499 4198907 356053976 620589338 542675400 998364603 956891079 4275338 534751686 441401025 952648869 799128359 231105765 48426054 207739204 215959625 337494945 664620534 144216580 281688487 283505085 700977816 673512113 972440940 154423594 521673047 970652099 647991680 603645368 528191495 421229804 230302856 685041164 356196690 697878881 313466629 922735813 400269350 157954778 631734521 473578091 56847649 10419982 187789103 184652853 329353907 519014035 206600765 275215704 300865771 174218762 40183184 619247038 789649631 668688393 202534205 221442394 63664466 987380095 712132 933818856 928650141 246606786 243939136 666875147 937564054 858914956 766487306 301725774 86868153 806498998 719501407 455680301 539091984 70114231 371372434 159139607 989714082 518604750 656763031 751397906 71943109 135217598 107269531 932517562 50036586 755691389 516600187 868767570 681345514 877008381 963632116 227825597 387579080 603597721 493695627 562230 21353124 41091147 216059163 456140701 651375224 594858862 32730695 343243049 696127255 792649528 196761561 309827033 726467892 47381687 481966679 594538788 599625313 893073108 595360069 119273537 408732599 91272980 312687819 361884786 702959013 255338899 646343839 909865715 35808845 120193484 836633359 472133122 999092860 13891764 235046723 963854495 795561365 403236208 122433090 970876169 494267291 147994656 971763843 555319079 461237713 377841859 282898003 238138634 65228985 410265022 782399345 20730688 12558465 950567434 661486952 684933736 932121772 428567039 25406436 234287127 809311678 52075360 692818761 466984600 629619626 451483876 649725043 952301639 173052541 371956215 75538579 371866064 762929123 103064555 85188591 166589386 433052310 134317984 720701541 312876670 540807861 662317799 647262282 433918048 358474459 162303846 337437999 616220748 225555209 240343156 186627989 193297850 672690360 992749954 471080743 282575607 477108117 643911835 586044260 149507992 440765186 115856217 422980540 327237698 740163450 733659840 866034806 558814436 779088676 626748414 66181753 912891611 87631261 79329776 964726236 548540453 733165945 312148294 132317438 988369719 197894358 4891869 656889467 961726609 172680226 35304625 359655577 240231270 984485255 545558790 794866739 798717284 799006006 64863565 36271913 664621082 907997713 312431914 572247155 150389474 844940939 894710112 922186811 667727494 251475749 33461626 570560940 596534756 313060605 33873987 160771266 537222343 305664580 886922474 669752813 279563507 494003729 696279908 951768476 943709478 133065341 575842587 199230446 400144851 795086626 826260835 282156734 719446279 141761192 237301495 963022542 848529599 962141583 16741429 1576179 851401031 47081464 150832875 747921799 448424786 752044629 791396477 601178198 395305643 674401353 228205928 244381962 769263617 590513957 61211524 298934450 876558713 494715872 123241554 974121977 691800642 761914866 49109380 721742134 227083229 606050364 798258029 121694812 538855815 477924720 966395371 4843826 292540596 506392127 862148597 280069452 453144038 730696811 968520216 708645979 174272087 862242335 149078725 360757358 459607078 299424571 694815480 1389460 815162327 199194051 259687866 834502524 281067076 609222232 415700258 304041289 495174403 220102440 919310873 100273769 311339636 548722732 725480666 245279853 553060344 687262356 365649949 728814226 314179220 170548702 578532948 317678492 119847012 284857757 577974980 294096711 627788418 489861331 657040349 185116839 201743399 151568904 104779619 841299022 369634670 235271642 998561288 163325387 321643627 951674495 970780853 456220404 956346450 441037531 81211952 647667425 810300528 499566401 319874173 873804243 672246102 120145486 747571862 541194581 189035024 24774666 886995806 535584921 959395695 791141261 148207730 749457940 175135874 785203360 688990726 282072783 987375685 115672556 230391543 708299334 420310967 153615637 70278452 842091622 892580034 600234163 151839126 170220546 809120904 133557348 199377383 496263231 192897855 158267244 129571832 787924342 981221548 395564548 79819733 81736924 729513170 451682997 235861599 647840851 223283367 244762820 822758916 191545382 905789408 602355916 510768142 514695842 714106801 197703269 125923147 455126863 17979507 114725332 232337578 995970624 714016500 569446803 635273187 617732516 965445516 565090904 614416622 507956240 155647566 348420577 269933 614078103 382476763 283901218 135855507 445578561 176549011 249141827 981724746 939941260 451364240 69095004 987263285 328919404 82523270 203659369 491253361 635069810 620888404 671537130 215460411 342689894 753928768 826255505 430409327 196561187 707092107 351645722 968715263 288432680 505729813 576683825 930658231 290619410 40788863 193719535 192547800 467982354 309538428 255751893 181326812 115045649 18243166 509104579 805188790 620505673 474370261 987178828 3408816 194263765 752820065 267734264 640355536 494562106 937489040 246896511 38529174 174483127 900529269 14463818 578574766 898662425 561209230 813654271 200704699 400817782 909784029 90118036 502355925 397994336 223772626 46938149 150130142 603405877 353227784 712377429 84328547 813421548 761867904 67135065 798221450 302289076 708063500 81257013 986348811 933907311 681202499 993995906 819329719 395693180 270124019 185786202 224381390 605471178 643404115 152426132 127652674 121488083 102298731 834787634 207694371 854002664 304157372 172356588 962928967 875375180 602057786 933605444 828236495 375327130 413417358 666960488 200516781 165609872 129577107 905917557 303864896 891611784 114886258 195274392 197696531 984574110 818455760 553385789 422868322 52868632 919626627 191225335 11914321 272795406 251674666 274724323 233869268 53630971 220456307 45925058 842157862 398796855 797054864 866082192 197086411 662855676 393647813 65308901 765986047 764736060 291043223 410756452 415808435 189654858 278571218 658608635 142050375 296203355 180337744 824570411 627646756 882832797 936998758 920774237 992542038 573535617 691823958 984199056 687834339 656244821 185163093 624971301 186086145 441294876 669043729 906842017 462408659 368400351 106403131 547828305 261047954 879494146 622560908 947818490 187957098 135926491 274004430 302485812 61273221 477953146 363058080 498046668 285048280 26931253 491847825 62321663 365747339 67977115 41793607 357514133 835220385 273820233 408799642 228887961 711857989 608362327 263778630 503432610 635748247 526655929 583200161 747517639 204318561 375563577 56003691 785428823 771060006 711109700 534076918 452542726 139377260 489962026 515838665 836791124 883886060 823171164 927486410 397892033 805820050 446853523 985001549 224086860 670436072 508468650 317175476 590640827 384236089 944847220 533634260 800024676 401443215 813331187 3089762 360028904 944780782 746406264 553164188 50737320 381474398 677506779 948849355 489567268 559816959 202897208 275334808 714613913 706757198 740548308 405781516 146154249 25932845 240246087 185179700 97498371 457853414 610837303 588362144 306102214 940771272 269830306 6606343 569975557 68745930 738254952 977117537 301675627 956983167 249482043 10293448 243027143 984120596 880290390 769305881 807824882 843262408 625412289 620686741 250332118 310292257 204114333 707920022 112120729 487688090 482982101 586429526 558711077 334443194 969142979 345875698 141355976 34475597 386899864 503732526 544455010 845205582 475103930 912806347 255886714 809208858 875187959 35750955 928149791 487697280 679830522 993179132 247576337 307388708 621548314 841660845 16619232 645099188 116452012 634463297 594819924 464522311 614401236 568939283 520529393 97340944 686952819 494797728 720749617 880528628 759512706 494826076 939379298 476756123 188229334 608892701 582693076 112704225 988115097 545603708 817961208 436312337 604155204 826285235 435119299 516803098 644696706 58700561 87159834 655940414 507574182 137614342 128841678 972018568 897193821 436465180 748628251 934229158 253832882 100524191 895896524 797433679 981348749 323778183 937633314 434359491 40507830 159978310 223076158 273495279 
156769177 975615333 835068424 24844718 236709816 868348327 990907659 680409037 870276744 696827419 234369643 34247665 97498095 434004981 468755256 40639036 347640727 429161793 476401260 884423077 779602392 486174608 128387343 34863367 658870027 876212628 56005230 54500868 874566256 880051422 158619199 812617702 24426067 341814794 863859394 745474903 556275055 926230884 562315348 792765535 32333245 20844087 530139162 856109443 670353132 208744804 304701718 121616799 270158479 844628319 418336630 514311693 21646629 500600999 121335266 150327651 715172783 10803672 710357234 733749426 952860745 865699430 782887529 861161949 590116474 107135597 724471908 460527167 847475653 65583584 182297769 203774656 344600789 98869145 209946408 459478972 396696538 91304564 37887950 89212466 732162777 115642188 651239038 807740533 435216260 224825780 103612024 291482627 783724648 843551049 435844873 834893204 439953539 73860569 21600568 711158968 877062332 441921285 16533594 611530654 286573136 54370102 87451879 59670663 807785211 204410867 63416765 702961288 490547915 970810987 205661082 875122439 492350601 525700492 262102096 225333262 178255520 381965570 925924666 341435938 54101270 687450811 232158071 780324599 270498903 991731343 816324529 122796702 712716547 765984762 234969733 337174584 566997790 911886307 150949898 907518003 361415369 583031387 497769071 624239734 232143572 764980493 537770223 467147735 92351626 269766819 448739178 610933651 707534647 89569545 29465083 463019266 88932348 330845423 397460742 168044606 547789984 123520676 538880310 722514242 876351639 285155291 962136324 109721083 105991783 851918138 286465711 177795175 51748500 731786770 312240391 424778231 521804888 79542092 863818046 495760002 617234637 131122112 548465411 216354576 199167573 769546395 851612190 349558445 874758642 16143689 946547243 512378991 792220000 870584443 349052344 118175893 871462665 662520253 599661468 939621408 793206308 508410109 94613435 44161627 7577774 953190064 833477310 44628057 225491568 966400014 719689964 109614902 635983133 289915984 154254963 62514472 529875306 572013717 997628096 154713364 636733333 273279543 26681871 84585109 911755050 275605719 265957396 107656992 238363879 498456119 859873573 13494272 304506847 820578999 257369636 157482757 59259728 497368563 964845160 274965200 454909984 386681022 946669134 17850587 971138168 690962915 933186663 793955091 110315632 438053075 375184192 456860990 577597120 850403704 100678290 624319121 334938642 193411708 951819746 473489228 440510036 366297916 163868207 992514798 656629009 383807960 109792751 615813246 694420926 803425563 266289050 235418837 63941875 243109036 155751783 755921342 183838068 178805122 550811489 598607795 265458584 484134095 74994259 305412266 989633711 400862794 953543259 122575211 538402073 279079136 303249384 906193197 308765946 9655134 528084358 41950 683826167 760168855 458275991 111823969 708425368 374574672 707212243 750578009 242406833 182821010 204743133 542625136 777141902 10671346 287750237 681442001 88702970 516588884 364943186 200277050 488722958 759516275 74505975 820091044 518609774 152687642 486955560 508992039 646510762 502429589 42718742 508862795 862857897 463971434 107677654 597372473 96102523 724611559 520377575 610633630 761890715 346804824 614017617 731606987 284972530 168057115 173033968 163019289 587688526 701343483 977927467 201643489 172195417 905695720 779604817 952894161 146917489 872343299 724021222 286071690 814411414 129302833 607948482 549879100 804973971 679516001 452384939 759360763 505020785 871099903 165932246 35409044 828136726 841948999 741004448 677807954 70506170 276164933 175421566 797096396 121473100 907064946 635053687 547013179 716283821 993797755 824469376 344228795 539380928 206745167 785968157 523941815 427797562 417641710 752327148 429586946 912113830 920229374 125560261 457018022 192401506 152963567 118675865 966648176 655135519 823233407 985330631 489289 83257457 100875321 888939285 226491864 504615177 292791498 709151058 628985880 72316310 796737186 934474007 93541876 364609859 55611664 520272031 25109773 224513113 353559434 507349026 760782679 18063952 312796003 703945270 120710030 178978359 250477032 248634459 590005234 524676426 575804124 599143455 10086766 540742034 623684322 797576893 822989995 209082375 567906153 998139267 78427722 28722876 254904252 738921910 827012503 784028785 993308325 224053205 853308321 459832439 49860008 961953913 709501171 517298572 327883592 259255990 783950398 793422114 444524902 580781122 669413144 402846820 603048449 678496258 759133374 384339772 487039453 993730751 234880396 32978461 14466584 320515024 723196815 61671212 167136356 498716944 278285447 738225143 475052884 189824252 985643232 714108124 529669978 930740129 688194615 823998324 79503395 752098833 62251134 57772542 264084890 70778591 558822313 501757102 402746196 319411629 338133987 799341148 333864388 260962179 775982099 166406699 282001493 259886312 84539768 442186823 751070369 676919064 590408817 973255049 510121426 594262022 953969909 975091227 941397129 222706765 91080388 871268905 866022767 552036971 444602279 35275390 113191524 932927149 856273600 77189508 277193598 107942061 405392170 414815699 707921533 102150981 296805044 313077610 905924431 521403741 912254603 470059097 680271618 305366536 28309762 90126131 551462005 420966000 259359786 790334488 180577564 233615414 143483257 268616753 929273071 838459321 289304103 652767446 107975979 588650005 449740619 575804138 638823065 452353436 332268902 225321441 43746106 846326352 603491781 411213843 103733319 764831478 598888623 518442030 269938308 99023193 612781049 699583374 144331219 854545708 16170399 219684112 612464267 574202615 371540882 536042639 315869312 75128056 720597688 825311176 37541989 547071589 477483761 910306918 756035442 97802149 503910919 54312900 832963761 276308639 824345634 124050 253181947 999310917 474915716 474900013 631817123 80286641 556178680 236216677 779047778 884169185 590325787 210491617 889807454 626563776 62638631 120161097 309858619 47106437 366005892 876256832 719037573 943686307 76548830 214026789 292810170 989561161 561204782 192441603 511982482 914636582 645585339 842261863 710702699 725081326 239764836 552865607 810313484 140351393 93211155 40960172 809556319 648376748 749738245 458872302 953123328 338266291 987250146 295397271 465754762 351092659 681685622 154288039 717373349 273730622 584232858 218203490 349059544 982217648 890017808 670092730 98436834 211583009 34441776 692957088 97057808 395630446 320751308 316994173 792764336 210893821 150930541 685339422 956902160 80885344 763514406 407786767 26799970 12795972 561948596 287133316 73348998 768552232 676433351 948797244 114819878 178586600 760953151 570474156 402053421 579381948 655499246 448971727 638494677 118552808 629370696 905853864 930997558 341902785 519962340 816603176 425163244 278925647 838317499 872145553 945105313 7532385 862478184 917349776 696971872 955961313 980318338 589364789 291574694 407668149 398304563 337739432 212001286 597687563 225477406 254066356 128634378 80739570 39635419 140284639 965192379 923383811 573889339 74057319 151985542 751822871 16682832 234627406 80245038 825170340 523468240 501249502 205064840 691281335 320104422 847965405 217597129 523470245 341922798 102274496 719766302 204283756 391234612 398141714 368452165 161373923 6404723 58564217 366083919 86804089 634699507 243651146 699544613 309190651 915520123 836077163 678375695 533858691 630415219 181001660 762272287 821308449 469751238 21451129 761975417 358133414 750168407 58796418 471162765 760774876 351257623 336368250 321239388 755554318 544562259 536791685 113667775 731460979 603962626 129640329 727923249 551713730 706758457 338991634 910234611 71428416 207400786 201504400 718071719 751216349 976379594 476782569 389014671 277717616 945323617 762001635 969502600 120681169 560159059 661734421 62632814 61733796 357385440 722217574 459625362 434876781 468964251 263151718 6713771 768813062 527568650 497340676 290973391 568455703 792309957 261643744 203025763 866884161 777008459 438698600 460753929 677214858 691788143 819982592 796345675 973018834 254696739 827628157 804906512 447154332 650052210 347349167 13464561 77297501 783237811 456384624 581247989 475164001 22027469 844306761 681580819 629073304 931232247 182600975 980735090 301333238 632424930 497570940 650221749 163017840 120651059 24923920 503876915 783831492 514554518 757543440 610965571 544258671 954419373 195724740 186744069 750727660 871790444 539318787 260200119 451717737 282999641 178453972 843212036 807529812 417298609 43617131 277370110 790677331 795505092 216465121 779556734 281239888 43294546 907664945 109763799 950696431 78664354 239653498 490702249 287688531 201747634 106112090 969160700 807338625 861266005 974430485 325703595 335141708 47012102 59251615 502476454 28928031 833479021 906964434 251243908 69816561 347010944 961748638 875160531 836517375 580674361 692829109 513900045 91689608 582575323 455661774 864450469 146002653 561408610 902480628 119619410 292798800 719111716 391933028 111756728 717820558 469658752 477004684 111196791 373122154 387461644 884654603 667549195 797612756 227131160 571960187 782972165 61277867 761033886 176345101 630298214 895005213 459050255 412031360 902279363 620426187 872716750 191079773 552517663 20086944 950838974 162268480 972229370 376516199 994911955 204037379 536666908