4000 999999937
900745846 560920827 990081099 767880789 495377884 901476906 46603858 680129653 362322599 77625447 16635391 212117916 20576687 562169441 305584746 459185625 127701777 60875934 221055634 420590438 896802540 385999461 235069247 384365177 567655099 626948454 658639612 384095528 928808585 155231323 249620081 938473211 998410780 276159337 88638217 955593187 179571638 134584871 162458504 669325334 686150621 132623680 429946690 726430363 189219861 857319238 944910593 418925905 857911008 722496381 335938911 618126034 236217364 220195178 828061950 745889914 765866381 147513027 265214092 640133805 782597367 565154848 264671859 192308309 383187189 476120868 85398532 538855181 11191855 714173340 722671468 214415264 21042071 83662139 831930759 711077105 481437613 963926069 65692301 262951417 183975190 492077184 629052774 31616148 645308975 628047977 982657242 758859209 627307644 669919354 472506569 662588833 971474040 891466290 867942030 267674650 567066877 942776295 52548146 469658797 32006282 673587231 821333312 87784190 30147560 592343739 778966220 882820089 846410544 802069290 494768283 244921873 810781736 947359689 658517494 7222205 577857411 338854337 195515205 172513939 917706880 651754291 371006114 582794597 789334364 540167679 243114884 104807030 947014801 83549254 665292373 109533543 191729731 15864634 273498863 262499456 66520004 890753022 3607746 642385867 83751232 971467351 398714023 951375608 959671337 200699138 319977954 484440482 746334228 208844271 422765336 467888720 251664562 30440508 457246725 621024828 622584552 41511049 615145202 872768581 963652223 91766667 60414584 779608323 968882270 966304557 93491742 330960569 147839593 426426259 566911131 719402948 292064617 653388914 793737106 380528835 56872455 707786131 491791769 445754421 931504764 449058199 837368763 818609135 978940521 366538184 753441113 858393957 429397326 560169225 55356549 951701921 101576668 817514721 134596998 560115414 325708166 939186912 523289868 962376439 360592229 334508209 207923214 595641370 838244257 392782844 677986500 451660636 846078141 46777174 568413514 137430020 903104087 419081761 280656070 66100377 917710004 804857262 346059008 42048892 297207973 239175170 118799406 716609656 662316043 906201956 354015771 542479085 224370244 34541002 4129449 803732177 462600488 527416971 113514501 98863203 801220877 596943698 782621773 710161951 556897064 517588841 744715508 404990615 366433285 665797010 819899030 484138755 171394119 766055255 641278088 391114154 203681974 841440645 219261121 109153396 745540684 750645245 698404188 613807741 55859347 617364046 595553339 660765420 613933646 555924496 169397520 262022866 973440826 214484121 701386770 894154929 223887569 394198251 231967551 104953071 527935113 583196015 90591648 171548627 853645042 742347654 990075407 860492023 883981622 140236504 425427929 287153085 489778163 371187023 18695268 960354449 809250317 772513576 678162480 166384128 319480733 771730402 110031392 584779637 298170936 293054320 512119990 348148414 429262364 651351571 6804989 84840680 849017477 633853084 591702306 718884871 336678339 136686920 933518987 18033720 748781403 57927527 689758175 361692354 851408449 339517218 667983411 696926194 417979666 529834157 350311184 947986023 170061774 994258670 906189518 914896986 383887140 106800226 182817316 937411347 799365563 375673700 442597777 483709853 533711961 464221259 891276775 635648185 42254736 474695918 206672571 335932014 158324687 306175194 604154233 444706118 887531277 419297213 724202423 224866587 427686388 359424555 17693538 269329782 796300788 171108205 293662401 515785963 586796237 339256469 411576737 170520516 869138465 484615501 647891568 694181452 220910050 497831990 233061949 530783728 172099164 785631333 159619834 793749983 40429882 328271824 478268543 309468430 222462284 787173635 989428092 353925426 442455516 923157009 535877380 78460335 531123066 849427036 64392535 811553705 251556793 542538377 924382684 960346572 867089285 641112330 710967166 708094470 358499951 575108151 592368894 305424592 899164259 947235923 187440857 569604449 663217742 601837924 470948113 203835377 600081430 324959783 831490033 945385429 49047445 882366308 839300084 60337262 665513270 923192797 240941178 93529910 801842406 104343277 222693035 141249664 503021758 829729263 424458375 284758 818583848 688508160 440805182 147999285 506845181 956913855 365814113 546700493 289130157 237826701 148664804 632731225 900695500 127065469 69311373 474377952 155757379 159700294 675830575 504296518 51392201 930024111 455121411 378743289 625385964 558182069 883886783 767301266 305757299 233604634 703288835 918941322 541476884 258970486 159696895 707717571 803620697 214030330 483334812 532373167 50671844 48714084 61953242 631169764 773821789 404990253 923486790 974748457 749233265 591182887 942369723 106817950 222320740 148899831 198806789 755453878 472299942 900135766 748627705 929893206 863176675 682640329 115990490 836198751 30116956 317754832 1804094 987941542 697197771 599831882 397315542 331061323 223231902 718504383 929302268 482917096 311143267 524943925 536729177 489129257 28693720 987712105 506290590 578005813 447094710 952606696 774486000 848742244 714752910 954792392 447765590 932478367 240497151 834863527 477190452 460384582 843446821 91662871 371917315 507097635 433723428 784538735 136800087 79282820 810554869 56333788 372191509 862075929 126113664 763184046 732755737 843619214 827226329 670048931 95663916 293902024 51219754 552309471 668377808 764409000 391079647 640097163 972743383 286585917 650057405 226518372 933845751 185538524 68293664 526461737 371022760 931314496 227465643 618189586 599437891 241947851 752618346 911323005 897572099 52766205 475649176 12441859 908714919 124372344 588459764 723999663 732031721 88700549 165946277 396015851 340074653 607902416 66484537 963207640 94100238 57380755 570570117 51376815 69796497 181211514 873253469 375038038 933449950 666252156 257820477 563973650 431043710 229201945 646054392 24616799 553658351 331040419 732006547 866298029 281266069 677247429 833302804 691625744 418368750 293172675 155428965 687906386 337023866 964144201 139513089 553655316 93702308 59944407 299431287 502557941 465390988 172972287 193665171 120515851 687023602 603476357 803157719 172948677 656383195 10308777 894343391 224764820 407964339 396606796 966875595 896190925 966047529 475701496 906571815 948604958 850388301 961778338 4728913 950810497 405049693 150262958 909405179 745796896 108169440 157519163 678386696 869153932 300431529 309642527 139611159 681847953 934857705 364532359 429472789 229074332 137612461 502530780 533949368 681515650 420334306 844270752 113059003 121626519 928870855 157225541 117458071 908413589 532093575 338854436 168874831 539825919 626650231 584497423 351752723 723854982 299314295 104038810 196157000 649197349 402980851 633628118 519881701 598862816 597583135 446062282 400478519 500572834 862240528 178810955 836635552 6866592 180605261 613508200 664421764 44911507 165986986 594741851 503215058 703987029 170201169 335555420 836479138 105639024 38564624 998315257 904472604 397393947 621271801 43353853 40549770 828466431 126909324 907586318 33048890 11805568 999976881 870874892 697840377 168419783 936830773 105662606 257655092 454063436 656006729 965336036 565234573 283224356 335293987 901907605 902530385 375449330 192714345 31320670 799503896 598162598 270870401 761446814 361626007 879956326 175216707 352865873 80819735 778621554 884280625 448059261 426009862 36598890 964221837 985781333 316037464 917144455 54628074 592257181 532582032 369654437 528220061 702405218 29057879 242765136 497880786 436393088 676182377 257302516 604098306 262397235 672914689 608154014 156350829 815424120 243985559 6695123 819136129 159223869 945256210 69070025 97861900 617919180 763344524 528587190 223678834 942150160 942952272 584905901 511195804 955627758 52122279 850108255 577277977 820274604 72265671 37605447 97465712 289638374 517175269 149075902 328007023 479816643 743256848 358154583 513074500 710664553 896465380 739267748 98775224 798409438 178397815 491498363 289597617 577290675 76466322 743547229 471682258 635063846 396705721 499803342 210374273 293824814 823318754 548173119 745701560 636864735 213348104 746578925 423046723 590360239 172517899 862364475 638874787 351777724 641548645 317088703 33853261 963209946 136779762 205961740 652324067 639384162 497362352 979834805 62647397 259111731 894789102 239968410 259202494 24874142 470192041 414480571 659410389 606518031 65963752 435416206 997899216 700338391 357861109 959963154 215195772 205151018 583129110 370701213 161714112 466895919 400909675 623652315 19000948 794782026 194747799 763148354 957798178 961761537 352811079 811653700 737143842 56167115 382818029 478827620 748137542 865399551 690808935 888737498 667092669 988593751 695439364 339892755 992845102 449787092 903136026 213326470 848608047 938894898 555196859 426496449 853334512 33843488 967284853 363871417 900291837 846591435 123180677 47613299 869307756 654271917 424471810 501482247 299931196 67571780 573600884 974374462 805105781 570718953 591417059 701061743 279403815 584014513 185017344 875705199 331358103 70824070 595713133 308015312 46175465 145992901 218469537 614092512 951093522 943831925 995194683 375450946 153654100 942245106 529025858 741294412 372258283 430118277 227352027 304783203 985894160 865557932 576501343 181206902 997817803 917451386 608344773 578544228 321049367 905528186 816418939 966187616 539354765 654855498 774685732 301521901 832698626 809929642 918312316 796077878 772125360 498769408 126060380 884443674 478084180 224384493 141130298 98024067 687472876 364943544 628613535 228941793 910427079 356014033 53761385 246492041 335808712 4566802 970910903 184405384 77160621 869402105 680441805 409752185 984172138 50308237 123202313 618563864 805728015 411884824 726082561 847862578 634755428 669706390 315676427 776349018 241908601 812622902 72346920 234384631 512175691 681517610 711935654 455510723 21516668 614124639 482833946 552301842 920235827 437762392 698320981 372504381 781046669 537265694 504328512 701486397 362147382 356787787 777369156 900734442 622888238 765786280 180686243 410751888 373658788 731491548 434219882 875776702 162039213 494450278 867465012 522808329 422243872 710298095 268225445 403768047 523421798 242220414 243834701 562307270 424201272 195601163 132882194 917889128 409587854 251969336 805631755 508529787 954551513 533538657 943022919 514034287 831203756 790524196 265117377 224186398 340203043 718006385 524244938 215132167 786289325 8634147 632402347 731728989 39143365 718796519 197270682 169811110 766839466 566642783 765487445 956952909 537364223 842754223 574289833 469727809 64236281 465028702 274365301 321163854 632251150 200655549 854683593 504986861 133008709 182052241 530733251 667983074 902378947 712011218 113474732 358503803 595859215 283415498 637112771 263023933 379625101 830287570 868551 360280071 635734477 37694325 724613044 496888189 564594034 735310741 805580555 705862190 216067282 477071943 418168946 189239085 496626896 907170454 361488556 883363028 836272422 991534533 114762724 784708967 861041354 527576803 212181220 748363510 797259679 711073415 79169341 41715219 568813533 416186780 121548295 334241918 63794050 897545859 781566414 560420447 868514937 273154124 798585448 834329107 862121231 28330199 504848592 904031981 327681472 651188249 183452280 165611249 527930951 291078213 213138357 854690641 625660965 781942946 941385390 525374104 655528846 46597395 366623962 492036473 137245988 776561814 537480137 559832416 862176169 483541713 632934569 378220387 967187942 438251570 603186674 929765843 60978314 457818731 458636985 505102137 876133674 755778279 357072422 650826023 61485796 108351950 599875326 927134652 472547684 279017541 376706981 752547604 239541154 281931332 735285774 583572700 718673373 91891185 264489640 572321107 103939232 458256944 315732363 518159191 788986880 274599485 164173999 406409241 933218832 692733241 778075940 348424011 908135017 486567974 10133085 646314075 604090008 348783065 146214125 58515260 486976101 415243579 966431677 743265428 632952584 173573091 583455962 491599856 349330243 117561677 973674950 581227207 136330300 310766996 571102405 703343119 416867627 228676358 824313918 127181441 959249263 804201464 431795727 959353678 220919607 388830256 848188787 960883662 247128898 767461137 26175163 218654711 239203274 796708396 869618926 385287686 565636065 381409760 919561571 38597508 105670902 702003553 811529558 571243739 877001728 533055223 512872145 907790937 100795936 104907489 888926371 919884355 16700151 596607325 449424482 148954950 248473824 775328291 182273854 977370419 108328403 447453880 116698203 929821844 484793923 470675709 621588575 217454111 30404281 581517564 851529131 249228723 445827915 65264162 250638070 932056143 625776647 651375695 930699666 364211917 288874018 832370281 411546393 398183927 296419511 643322141 359150030 180900555 153451262 1747532 69918735 330486223 996102004 534251064 719788524 423523791 519284299 392483804 326098196 523205654 836644989 373460278 863980027 882164136 905659873 12863593 308604270 702592083 457946697 39939189 449039191 90808890 510860258 272199259 871726766 881298427 662988279 120953697 272509987 372205799 20638330 646421106 398159767 824909640 654597100 396855784 298479348 79641196 388316424 56578404 985367390 775727564 661885737 680189298 57606036 316042131 69610415 786897290 486230727 623479399 850118217 512055435 773460579 129771980 450504128 451257380 670839618 726693427 428425967 394942916 660137240 80708335 339155772 755295313 738990294 738839036 134617133 109938340 698189409 552106276 338910645 1739326 371360666 357409497 605856114 947476318 736574884 491523063 798541076 467477509 309242602 17625389 382748565 356068834 643932476 878432569 915098454 245619451 820901778 866068192 984211605 254845111 708512501 170748866 238931561 987745952 527143298 289681047 641888468 57127408 969326997 931888499 960626705 857926469 717129518 131230794 793048560 83447236 259954732 601566215 394431126 679307385 438635475 791216634 41511472 196655373 56615534 727253511 139981495 396721971 905250110 563989085 343947283 861127150 564527915 199366628 433947440 180925660 228670836 200194628 527230091 294739374 666438197 85469622 495907594 271867154 751325783 714707645 200915985 294791842 578515699 269609090 624483155 419951709 409975915 882579328 39150335 989619390 531125692 813673738 396772591 994082602 831514321 53755681 634440125 871054708 612040487 471243877 57703916 717524519 364317761 562068286 276350783 757756860 88717060 579125331 992159918 899860304 889508122 784299320 250368178 733850532 805195837 195452267 286247740 768328842 419106217 627123564 346427796 512771000 658498515 551242701 528412362 854768506 63444068 351354764 955871197 631727153 63409542 888556233 950878899 472897440 466958168 988264585 871443776 737033640 752516080 471615042 40996405 303780939 656755766 142058481 938445831 864330889 221052973 727091457 694316778 968139400 176510646 925890366 566691839 920688496 569850380 580708644 552580159 41215881 991927530 744604272 789757973 382275799 445050809 929297634 721893467 421454918 769401193 346148959 206164671 917326708 318041947 122327000 428159876 139297892 667835844 61205968 339175796 452814251 63557792 971967421 61409452 347043058 300887754 211059398 580376632 119629362 357364988 78629287 412488444 573808633 988161187 781397084 275633438 606800808 723514492 348676225 590898966 369799323 501117543 56468086 163988957 405815194 684226209 451403548 685640933 722614648 518197001 786135659 880440143 359254304 503931938 965527384 181302384 364105054 466771266 635153693 719958295 583329642 545744750 129486298 653419572 375204140 468911790 793067402 883228257 134382639 196481216 217798302 423352573 239580505 822900199 263253690 923079206 987208688 635482386 94385002 658785555 157913748 132518936 579796835 67670172 571242384 166531114 688312990 91192447 697771385 45454491 90576567 685903662 361456656 611838676 100179496 152850799 219803913 786263219 676912560 133103286 933617992 274901534 634550158 108347236 942960788 294178866 380702140 913265240 437638274 284270810 696377681 656227723 578729105 246778571 995084018 780974509 184979144 455076233 75278876 495590916 362357863 894126006 754159890 725791893 279609801 350538077 868843324 151223807 982037510 359906877 566122965 184897730 684858856 633730470 68132364 863856823 906738354 222883218 238915379 13894161 699019860 952180450 943657954 233003283 26166345 121412164 929464659 149243189 17053430 20070880 940523463 769769960 766876124 593892097 441583944 195474671 17956826 9370246 660965570 550901609 194184184 197022132 60238525 43461779 137732174 575007088 949758286 861269541 307128245 314314915 678834747 510822982 604702643 414626131 934999501 762559408 699449809 403330232 757265860 21581807 523920741 936076839 325077720 113143762 762847251 11412233 788586593 120623248 901579789 551574084 438944175 566762116 790915618 708277047 733450980 207989925 326743510 210327536 864781864 684078605 969777107 390913368 304010883 873587259 254273914 827948636 980912943 815391978 575952218 454653634 341796160 305187727 819009798 668605907 997947272 628535609 238177074 758921082 798134535 759523196 954964172 975460160 476594597 838682958 488565773 850022771 732986212 459112023 739824399 504372996 790598275 591781229 250991736 797190778 257411210 857106207 570221824 818166021 189301057 728156629 842372367 260006713 920384218 942628281 844505941 902587024 809922735 816179603 689057950 774671390 465808145 251665299 190712292 675613175 223069007 689863827 6652879 54192767 158467358 374531428 770835385 420150722 271295159 310514044 708795546 447549272 78611201 705817926 486176842 904838015 829244379 916801648 69308393 298553615 176394421 143364179 847841221 40637867 32082730 658981738 689009240 659935910 511626744 928901347 332662749 192606691 46767960 533231185 495179253 507778335 825785808 812047288 141456033 114793500 735120719 116118550 173508360 448925225 780046272 831416753 419193339 954583059 805866914 127600678 954406285 907707041 558884086 626546494 791480418 988278198 757800219 331164967 352522676 917449593 461681313 838736052 110357438 509314909 932693524 282359054 829997504 773426420 805178015 512693022 626096526 599898058 488547551 724826083 823900064 327243186 588961299 162433482 650470011 245546439 467590342 526312499 661929273 689204922 626920942 682928161 520084099 303943364 533825671 772515813 889278300 1227848 502244873 368445248 40985923 970161325 264492029 334813791 952497176 644035517 634204877 563400800 403545843 628868857 638709698 913332939 789144167 480628458 749417720 823250617 822993146 494540093 706244003 700409631 649873991 995590519 428930967 267662777 975697417 762414786 215454709 76932491 621916160 586250679 965031859 642591460 242777557 137945440 504988082 933033616 457956722 538323720 27870200 366323890 906221094 108979865 212353034 814239857 934466221 103347483 52297273 87061412 487331706 708443161 113213305 859747307 58901451 305216009 638228471 791342511 796745371 169853919 885324431 640831029 425924239 777620997 685393741 815324189 316142286 136442830 47739435 540712325 893446920 9700329 4207715 285637065 515982835 879396543 542977270 322675899 49011573 447157434 856344951 591420972 9423009 898310145 340467940 771532508 682092113 444806701 802876719 320047516 958619621 597716339 725378834 282764621 330467699 476167637 387887687 322647609 333137385 453170352 786812824 327590253 914378202 351826666 499468591 616939136 622773333 879828041 434565615 806973564 327557747 269730315 782168061 560422546 391946490 66610225 779028694 984818757 50042843 606188978 590069648 917410911 278606298 184567528 493532580 806993010 914708151 899249595 728768053 559964340 460947621 218883332 300858599 368486286 231250957 811320754 102535796 597716979 145607646 865201233 251210292 515015627 126511473 505114721 292558066 90136041 68803855 775297877 856631344 790330584 742506676 149251306 258573811 422448981 145109521 640651053 64811262 866596741 695072027 32069328 90819720 169176872 403996602 469322081 898108517 691257673 176246344 589365353 492224938 90238176 480969928 960319742 614132853 294486653 869917160 256152294 848793991 505553476 856940326 331916558 80665880 405489254 296714289 303327425 752868249 559375022 536135706 136968478 602483592 302684004 272360635 531118413 471500392 702457829 620066750 51981084 776403765 436394625 975407117 139230579 223899713 348621483 87477302 410144432 460302176 823685734 103804143 619893142 466855858 68780573 305392758 239109871 461526811 468519174 284114848 244438164 336409903 360149800 152966546 756657051 925423639 731890400 821560663 100560347 16626552 948163049 552818196 86557814 762086805 507775623 445389510 805261528 113687729 155336436 386007753 68786425 562181971 59639911 261330671 171087940 743836984 892088922 166782826 692677651 621048629 566481877 722744960 19248851 865219906 626922441 771954310 149908456 72311286 396361038 343445242 133061221 147052220 531775694 208265770 781851095 207935839 314822414 386629417 228508692 260304291 288642978 961325371 710167527 467445075 386844758 655442368 647496017 119220690 255397330 349063624 740487450 544715232 157724234 940138566 574382237 174747887 713416838 532026964 567451129 812413801 100083631 47109554 337908191 771307426 924466010 967079710 580716651 522605913 655680375 16925093 77742154 17970090 895187549 994046623 851867220 758964239 284882139 506029167 598018267 677389079 233091594 597760441 298139299 614213958 589777771 786539043 879826147 9804596 733356954 234013399 838283979 865773540 699312293 820200806 334821407 13421287 248292228 504667416 456476127 219756621 502451987 908975429 744341577 927148650 530922922 266158158 569426203 518491139 322821481 211517870 964640190 350225190 839416828 703665295 730515897 686905936 629070933 609854361 589288324 679589482 880417508 921765952 854291080 759104864 48134555 829089225 701490651 540877858 190377191 171922845 208777537 914972788 710297830 313850780 59459210 914200689 330891759 688690863 346264059 781551612 273654210 802631637 907918715 216898759 302091687 744463893 883125419 408005938 839863097 939184056 85197745 779657025 192507905 430520402 158226605 564609226 626999923 303077044 794303842 334068590 850598208 658585987 327728626 850963688 965581106 377711257 569433988 941156915 70847960 357169642 793708011 431467079 318139559 528170654 217345947 845994387 11293585 644097864 997136905 973307800 438959000 719364659 6154599 792316674 211858451 424007937 342919385 552107265 757779769 161979175 281115014 571841993 293080329 689402876 748244964 640452739 596520642 2248127 27702313 933391889 419896325 523131022 519360912 389179684 781909431 847135207 205854918 833524137 698650029 548468429 799066306 182582617 659442085 510863036 924004759 797862056 290855658 595324343 488673255 773811135 578230140 791003431 744853224 285796342 635540872 991657933 627016020 674472633 365180096 168962565 500053453 886756862 795783313 203081022 938341249 142567014 781470848 254225084 736754035 484646749 664588043 360931363 687603915 467744875 428101626 608274181 954269164 993802936 978802303 577636001 76378435 520380950 481279588 251844656 568297077 410193728 368805647 683729013 792731235 916198554 852291422 271816135 877195431 11753274 502980477 646997443 573845899 346646755 265065881 87706864 72604805 543805419 662084156 730118632 993744962 81696965 999838217 232410290 214242005 78440691 754933068 127136057 733472583 180400011 622789976 785559840 785924381 541711107 778022656 703664839 723206951 817484146 119545538 576944839 233694269 976984773 351069191 974921206 732549885 484625592 846976605 382707322 151701586 28160313 492360523 954881818 210600001 908013760 90604673 907787976 942770102 677430220 107323094 702745773 443316061 927558596 126129383 231869230 296144616 267077531 936872549 905702410 722015657 837149566 653262640 556931838 2364721 873261107 567346285 925123047 224814122 305216965 850299055 244887563 805371488 966656176 504625762 820784240 31337550 313834468 446948241 967422637 182860881 715776474 626475857 701640288 150678632 448520637 966602282 535384632 125266313 27175919 434729709 548191559 269591070 772866721 885858246 950095972 485427679 161013636 263692505 531717059 106626043 60140042 909322951 266876815 477137266 382727922 641769344 180797070 570524765 787108941 119371222 657775731 715034189 754679181 822351734 703899467 747849535 447249866 83969608 684309377 72944007 549655220 482500246 926610747 974943305 802904432 953857846 952150262 154403097 217573764 286947776 79799817 610405170 529273138 664226631 206536567 641019814 61051877 145697364 731979123 302817999 632201693 887657143 286868871 181965149 600680963 919692607 402976438 794323124 172454658 608141490 240967760 639207139 638421099 910952929 204323530 428681469 551678265 690978868 740276547 703175403 548662908 898117303 279929307 189450191 480832668 159281980 174847665 591516432 143413517 689487260 627034688 850884498 258469102 586667161 909123379 391853102 791053167 486608321 962272797 749453339 825310944 831171312 200442313 146272764 689813739 506251422 922323796 588828386 336427654 382962463 399519036 743001218 823712685 8016570 374377560 793324129 97132150 549758299 755110209 446511256 435544979 148946804 471340060 854054897 250566844 41521242 107944159 501915760 555754740 942971142 76113049 383227650 521475093 52649123 562998667 275576049 562280284 449783348 294739842 867962164 43845467 583608798 851950918 990514618 925227739 322375196 432352801 288734962 536853791 11674020 15481173 323140827 991944233 300834078 593714794 602294607 746467973 732319771 417955174 787775324 743477632 716989749 389516836 452349279 281854915 749133306 737725041 952815841 386489572 705017037 283584103 242298424 286080225 40139384 385922049 482357399 932610219 206679899 705830065 391110672 420899850 678756380 992546879 6358942 703625992 171482209 802055582 817158744 860335604 990138255 541388626 527210575 933969755 274300986 62926865 655638124 1629046 678658536 360479298 156376753 421473714 9730177 959629242 277861155 200063841 676327102 705909929 809852243 509787366 801425332 725266302 66015657 52237750 716354465 942849705 245741142 317833478 374270104 936144881 434230247 295474190 752643793 77074103 609172613 94322274 4268993 439888743 111875915 350856330 195556583 883607379 623122092 914582534 107531444 187623322 193436826 8643348 11098959 951429710 894163580 21394397 407151870 305330639 786517826 902409638 678172913 914169446 478049007 510104494 589426119 659990813 140047064 37476577 659753136 928750775 711168864 534759773 432890439 676063554 303784609 739019847 337476213 191317580 356106380 45817252 768906377 927463371 787163570 591227245 870640205 188682248 742021435 916132345 861554330 964292533 202006065 912351876 632613702 467407224 682531779 422780842 579055291 309117522 822199866 987018735 86897669 576056172 330536137 835672738 765535542 925652858 541586349 422988702 776101079 893371531 883800630 241738176 118191880 137295477 164856169 732948313 82936818 184632963 482046695 669989725 366434725 788225151 613219701 335113350 848956518 608352397 168784079 94014098 911815416 498623065 928378712 371689431 801751463 461276001 170179068 379258490 734568876 820884304 830755887 564535307 790923515 744939984 283302229 442512217 717791310 555814039 706752866 722098642 894448301 606214158 494137263 789835456 808565132 614691312 429432862 167424919 800647229 165998033 947811857 737323711 39980083 774974690 600257149 238270330 600579523 650444263 794912525 802894047 794069119 104613598 103766537 227290056 971211646 117757873 112924027 624472495 79531307 682682197 917177339 370659237 37918896 974582422 815267600 653526540 623290317 381484284 848112999 142407975 541140791 797182382 898550122 750759594 562333287 652112652 485693613 118351653 780878277 271043781 14406359 952151114 3563265 484337817 378026539 731713206 160103031 556314656 135065935 237410404 141570388 933999941 27245820 303130949 708858638 652838565 805092247 523118322 764189900 762133038 979300986 579254667 404540741 815943600 446641663 59727587 889768658 451870541 808320246 728895241 402215310 942509843 431476103 948176081 768018083 878180205 571992910 476366130 166577442 934535451 822256154 148416720 36707530 667081340 407624017 650080835 192473742 43377906 178311812 804108598 97819990 257029472 814706916 572975497 639365716 916040180 23993791 603163213 262809813 323633827 336478217 481769779 546899062 238717328 969359051 822739449 381879195 157277155 568269812 446768855 655770282 369912074 898380130 226634401 959828132 770988268 872950695 356204883 380537398 133898674 643270848 555710455 974780689 227995949 121441013 998500171 562845577 484702320 864411734 861498617 790917898 622107395 652644404 856472694 574270343 556903923 162842500 294324224 725316934 627796560 734503025 128054494 876841593 519358094 991059929 733209832 147517078 558463219 608116029 945377553 409746687 637927842 547800298 588510847 44782136 621485374 886016593 148505600 145732940 829717016 722266858 638606528 5909649 347061607 270596260 82067940 923111209 343418639 640152288 98660337 40390269 915030765 909585528 683713784 590962054 107813429 436268776 360791303 552398421 822258244 455450649 946595900 764607621 285819566 445835252 877821614 335138440 715416739 587714961 55563672 381983466 452989029 239531731 474772922 782562654 442347350 675232812 184275424 549157506 966207513 912297771 530364564 248350565 378486830 65074996 576093115 372463908 643497959 686675996 979788200 217600491 880832580 609968436 368609708 691175442 657731798 313001342 801880379 119241430 539822582 715065377 94145860 668935290 996585074 887001684 383470637 616393588 835479509 473020564 861369645 910007088 277394060 346768956 965904639 242979401 88872608 242967926 880567198 714209047 359249467 379954039 102278516 830088583 354282884 703630626 749904573 53721960 750046219 275288377 501290096 481047727 431716562 265637962 658859542 340144596 88797628 864048717 807036925 2030919 408633652 184950319 938661563 809043183 795893259 14725347 149568495 604256561 579590879 576859089 993984438 305013436 186531500 774337314 501248185 429387192 968018942 156007809 845315434 898340923 755954153 290965701 390324179 472139243 799591428 180251827 279285255 779541178 246355053 75891268 561385539 606524199 125468687 125894204 763968015 961588615 413710398 104470409 625618501 399425384 41332289 440388926 958176422 984747870 161858631 468685705 940702318 962947050 322846801 279117702 363569262 596876582 166580116 571199992 344081405 219708864 432367500 151712659 666789191 271180130 377847753 417109221 553197744 381923501 276711438 114806924 521876659 812835579 115034556 612278110 353652319 431321248 987535091 308727981 19239544 886281286 293559560 252399862 529322920 248675159 530342760 942813952 260206779 232529498 642534742 378641174 274193667 913599605 181285353 675575399 303629565 901334495 540665039 518029272 799791561 296415184 946824154 801896677 487972973 890309099 189924492 214387551 927875232 216268027 253127609 118855190 879209030 795128518 484949231 270734294 521492087 831814603 683040766 383023112 548350021 398407895 40167194 438734046 639630261 676813218 697524228 686720924 44628939 337893997 1472810 764199801 615219826 971564272 494386930 905926433 333369907 744923461 592950416 889425306 875870733 42114326 323733442 480850474 673183231 207395180 988338005 822523601 279446633 681760600 104345736 680269257 595225999 585497853 672998360 185822008 938003517 369378247 948066365 179688047 676947497 328770756 421126791 467086223 736409288 253370247 679205475 89899577 994685244 123930340 932952722 468256683 368559315 441482517 803947366 385963753 322812323 732550626 67606196 44721987 620606361 567716848 571682006 143328485 675915162 852852708 369489371 461175845 216861488 600545822 232499898 602751066 74371476 408530676 600578861 8238722 349322927 294315634 282295294 168001799 337834465 102764903 399050029 19273227 94941810 521667077 754658009 326003046 628375245 243890606 517033402 220851524 289112795 837162215 971430581 877858519 609995424 154895106 935754716 341695342 343194813 792418053 381644976 808616789 982448272 833459222 7668002 437882335 828692039 402893182 328165026 989808826 361182590 479012603 81298234 358943573 561874468 95362281 875578848 56616573 631361211 151512711 21324948 78269485 693009130 103767933 351388821 8981851 203924098 299893754 225423437 470163471 66934745 53819799 599528405 499217039 334312790 931449004 951835472 856019773 362262986 929318801 1458068 169038045 586394177 321754689 364800812 68925129 310130889 423304099 618521756 596933122 912766968 358844851 52511769 350010218 237945317 128026632 421050109 701617491 813630611 580417856 990253818 109940698 954257168 702691810 430790388 703509758 683728720 6013193 927028448 946923187 145419217 714768919 781827838 990319546 559193482 161197895 839251604 634543297 482468032 59772950 392113995 76265192 610948159 441600639 859034037 288070758 662212368 214839049 525796146 225125605 113944032 311294526 541804712 184994508 127626976 465062941 574037107 911850100 794936449 226078748 42542009 10019403 862759635 157594322 476939579 427724179 951109149 941034086 115402910 320294938 259701598 701649042 558661484 98145767 215587272 971156024 579870618 931857296 461359854 134515715 220015612 260034212 398051684 634428949 692959372 335579899 967681721 435415502 508578373 298795369 602117960 185613347 965478877 43321134 570086236 838862869 701874686 288667791 183155515 52387186 215955854 787380577 697694782 408787162 866718999 795566045 373592801 14428184 453419009 80397293 655234882 250773062 381049148 278564839 674578538 280162841 480646936 370327123 843773974 467356653 19921261 256795237 707236515 144417809 714629870 931023185 60451558 413899392 454106592 19080576 301662573 41210366 218529632 4168503 446642130 12416894 391194028 982953042 526446566 227716678 122467789 77276657 514800886 899500927 980811101 716746550 768930482 578258350 584442461 403142858 376940002 567754789 324909768 672047319 473433184 568647822 753767620 262080405 943973434 945068181 574427630 742884824 242645111 264836278 245705920 705484117 357672541 835003471 769839731 399981632 365348470 197493882 739662546 223604296 244998310 600135481 715989344 796676017 366648299 432047831 356064282 988387021 275817152 83656313 896357853 246276351 392763512 550688074 843755747 895409972 988985228 895036123 915584748 451586149 836714702 623052587 210198858 798330607 658115530 953434112 126715919 71338346 966880412 94672529 982888697 354974087 420835385 684308145 377755385 835707179 174944068 292778989 171807538 159872291 374129582 975893002 572339051 774627888 877781568 13794493 526818950 328285898 448210979 912397503 872929339 883522585 494168962 523224545 922528260 28549287 358907813 822055285 355024900 287056114 136711948 607112399 103114588 405593878 878648351 603807850 778789954 185852741 449450217 313106128 127705436 998629514 527090374 431696187 306852753 227117377 461237546 111485838 874774859 595914488 997728405 3806444 87236077 391763594 702772530 946256095 23255892 103135150 410191754 113687462 779194267 117281983 896987700 353541977 420685963 547427760 554897569 397162484 734621938 576119268 166038312 118349106 513491741 624678274 645176684 392101933 108218301 129878560 672893912 367870181 76735986 227182918 854244082 51019467 934123973 220540323 695888315 956760930 182796894 879404852 486057653 709925234 84444460 599643433 526292991 661884127 83084685 153491634 66613781 908196244 592406311 499373225 769453276 381817543 529090304 352285014 881478146 484438227 251677809 327243581 325614376 142636906 754482574 457683994 72192635 212037136 888641043 600728641 918934599 940518240 946803708 223603196 258910815 174229973 249967722 195192197 957497058 655859203 701679867 231103994 77358943 919434450 345968092 624862497 93719179 556781792 266203747 826647922 273084070 119300160 274698999 27620213 250276501 100328860 308608452 483845696 239521815 701072504 957995450 838962663 420042252 954396449 801009922 623433120 393305645 282503640 845369799 21735982 864180963 650881412 361610066 516240081 557979265 606335712 529365719 400821185 646391457 930398558 591253939 395166109 88876567 128516401 219691739 293812416 785830810 839381964 129493369 302001268 935178109 601630272 333154487 713116980 323848214 123268287 43467254 999116144 278692875 227410471 230211148 385359569 64977770 176921954 916141361 690183571 932032175 941603828 469708200 976892651 171945642 197920318 200832447 883610272 641911410 39159328 643360439 335629320 247372674 824935763 970134050 408948790 747679633 21398011 522230220 115699702 693690695 677140464 826523725 24047988 168887210 5287636 291388139 505588744 725281806 958734837 77822020 164065281 519603711 228386318 308358092 568391823 812776076 44302664 276585065 134770183 838638398 513166864 545848140 717949619 433484617 862095823 500821583 420595845 706669076 361733000 285440603 156173652 60438736 338353098 332323013 310850407 54250913 301054381 927909370 2165635 651411173 197022609 949813567 600267338 255942132 771910448 489048422 598009934 976728781 131329749 772234211 885732649 345951987 699351820 182640091 820288211 952212452 923899276 928488041 831996702 891807 414053157 595271818 48229147 187455810 556146760 215201395 960142694 21336945 540975459 103784277 818466748 469074069 174283895 712109305 265098792 260530533 730649964 105519580 637113265 368321378 500854198 501847130 23097253 684966486 158304220 410921682 480363858 422225567 830008687 996093991 542874985 662992877 724533169 521468748 877463963 495985253 124581383 205296643 351479443 428812025 815135770 21609738 279443329 383597299 791526826 471851226 385590815 597960182 684919206 990542965 915504825 274722100 993494200 237479750 409751576 42907302 174831869 301523321 290204535 724982375 964383615 598989605 377170392 747802943 383503088 296918033 47744032 762529521 645568643 911104670 268653252 516782916 139002540 41017788 660079601 229599157 755697116 941608121 972894936 41690789 568943751 243274845 646199626 675616246 760611315 411519191 125335028 680295039 388847194 821147734 336842500 635408577 938324025 854841368 363876432 811956805 792727757 138741880 403294268 377771028 100344033 418046652 954397888 330469624 720303396 152157457 249224203 174755192 684558447 916389265 766325337 605671895 156725616 16421107 129540994 266229948 845183018 329049419 139518691 202073308 685529579 667105740 383771103 179750804 924853809 158106838 422741819 205566935 736631958 961354981 391516450 707633973 165145462 593845803 190877096 922827487 242648046 368717140 934828728 380367246 883169753 492670442 697941138 232954182 675780729 256435572 244039827 209442216 950699144 62781119 534165530 258882855 836424952 206714957 261272764 312808590 441950696 761437581 454850436 555687972 955240885 6189921 579824351 662295988 179361979 655870293 200242959 683272978 475973790 15845381 829631174 569205249 231721604 929386649 242993279 68100383 418713744 26126221 253773467 908676917 568325988 344967064 997150844 36369720 85959964 601500497 545127363 891663939 916302637 106145812 835224634 526524475 521502704 673990954 424743192 457581414 960459569 462041484 957836925 58092052 511444671 777324818 347451160 989599109 746587286 754204435 631123541 441328446 414749533 665975451 72964767 551225944 83852166 32431780 357362945 627675586 389766721 590686326 590425705 677476782 62654233 654826078