999 999 145747843399383225
949397586 114247743 358340310 924838347 461003235 340991892 535220303 553078757 860586656 511311551 760980772 16152381 203525918 636418329 429011739 731500615 464692834 78835903 171136905 714887768 424217636 43423440 953044889 204108264 385363215 839206316 649569925 739968208 313612031 910684982 916597722 995822221 162032449 346470675 156092856 840030330 200769750 67279593 961215760 713431577 106735791 342643872 834711523 530044235 833627634 869565603 875186569 861991058 182752819 478102560 65946855 964836694 717238715 599204163 887288503 10838044 710295493 940809086 605060548 127828176 659076283 84208580 251578154 165940988 296372348 875948745 526679194 342187534 252836505 179518275 981307539 770807190 967334547 972594219 50234026 320171908 27379230 602127612 614908354 205573230 524107617 868852211 276674644 703076807 961161011 85923917 304861352 759469097 760784735 828726411 270411034 391096716 249907424 320586928 538068565 739766156 346247205 291757697 553160602 284954534 872930638 122623940 705072890 710006138 106309228 516287105 929855383 610280714 34545092 184849220 272758247 647217913 400193548 860095832 184774640 232638157 551351981 688396044 876470669 844054829 711719935 687498226 614201510 478162980 232405391 372393754 837988731 850052443 659933787 985563483 215865562 361315426 68800788 485685642 446170724 294844135 49933402 777622721 986783436 823381756 633210627 863312025 754426903 161346389 665987157 727721839 359687644 808241543 677559367 598896802 15137668 198794314 274257347 220414162 113737355 249023416 987013862 229882403 149879485 262120331 334691134 276481655 923076217 708011874 885467146 592888247 352298737 371290364 659266174 933721099 479827559 890225786 498207228 950902300 829819505 304890017 989414490 66330968 841426998 926472981 257125922 80083502 631968431 749578911 865178317 721600077 427962086 365577064 940120839 900629225 56816185 104949051 637865198 420562678 212270231 12388294 970718802 91765610 770652353 835177176 895641334 107623807 71420042 959281828 658752205 957820142 168611607 645302781 460027965 436895284 727647008 965495447 952900191 207681232 946494764 845412684 128796988 734750594 120287192 718858836 3794449 708039310 813350416 148111243 865649547 890599414 427604820 706058414 156017164 851827139 355663860 350608797 80164836 982008893 668862292 663101595 529043863 636965933 495146024 854166665 605213213 904181025 116892856 835647790 199775005 378797480 227449117 445803889 340347184 463045521 40370562 772396956 658517028 7792176 248540771 605854619 278876470 734739609 129136848 866960186 78412630 411419618 226039467 941564523 443250534 596883813 39483621 20150653 74632827 235512059 584138693 456464741 237413914 59141953 119977248 647709176 866692731 38106582 210295457 364851758 726246601 336818075 884466690 981094497 299597152 701547761 323898193 495309963 20456461 682516478 179686188 857046667 880378961 63687400 7041284 558990944 627937694 980555799 777462621 80426091 302857624 777077879 918964748 104741809 351407700 600711091 834929783 185202199 104887963 354669179 341393368 526354596 160877608 417513150 264848250 963069377 240136677 878897136 542065402 485694843 154284082 557621061 913248390 460629440 745184542 915143155 66538273 440635549 244631723 906721652 341922013 354024582 167320333 427713473 162886942 440530062 27950315 196467607 529891037 631336105 192707484 730656949 523567842 709026289 343200619 819311132 241603593 831990494 284693460 963112525 148856702 522936204 627046340 175510926 701899520 665720312 505662427 666936869 471495969 225964099 57680045 232044186 704748931 598151405 75577596 928503801 42332956 982478106 16569343 655049229 937063026 685404368 852597151 175740326 645516768 706021175 981107892 61185747 607258575 268815575 58027851 437383976 450873085 564462045 651736803 535710201 833074361 29625429 710837418 685409948 892975908 388229744 66849732 458242731 905501552 48563904 797449092 665899071 65709604 85619319 571491761 852276277 148987735 793117099 498522818 274766445 507935984 167993236 424730658 475791365 64927980 429065932 988144748 42469793 991248791 112759693 931359663 469573030 386434513 152583158 701180842 192743546 434656586 403550278 865420816 524991174 624868549 798088479 886163141 692680115 868645976 881401284 351179296 783260976 205891498 625682522 65384230 468823081 503355956 254712874 110429140 988841681 744706944 715764189 670371158 453292249 43302764 951740862 204170312 981640630 731893352 804810235 918304507 248707806 242179507 529844964 377055666 845271563 874188705 134810410 502379232 60184438 279675351 37570081 923204459 747280412 958891917 643450365 137505004 8673788 304606154 302089752 653806060 319575127 967924139 969692970 52041768 827974638 22573725 266401679 273267406 494803783 389228702 150294405 624309949 440180456 104419455 783306090 406497992 705462170 632108068 306622465 474909171 432151718 919842497 487518382 441807284 322378267 305955614 228125621 443229235 137225990 100627412 596352126 133476490 28807607 292529550 989474771 917766916 564204034 6764872 179803680 682061665 503882619 573489299 125945266 647841041 923834296 229829070 200389880 921254772 274397843 72133742 655511749 775612448 533621349 612993846 363946635 824732442 275672652 81398399 646000288 905903899 949642341 81033329 892899964 500822988 462021137 110349128 338058489 390859785 35601972 444319631 952500881 827266594 589906801 972580967 454705571 135132693 907233903 118642625 886523566 686581205 773947926 979571871 880978580 489053061 116164562 438312791 261726424 566905277 425805262 127103951 303482848 930053572 826407226 203178433 860185907 95535059 432473222 979088120 887720378 509668696 432373156 677311889 695557123 659288367 281229897 960115259 926859385 151525354 921033259 109710455 512125357 532032523 134430532 489248983 297773200 558328388 578299405 581621570 817915573 518567869 289094083 932178734 310875795 716517966 47358630 440431077 875392961 645984960 843024948 746322624 749113144 916337935 874669938 994629998 990649748 747835050 657058083 410586157 79832403 521318577 906509326 740275727 998627603 952624182 802506555 789065527 765869528 338568316 210694198 253169433 70204739 996867899 667417419 94721212 326266331 371703001 189423559 488303355 896523592 671242417 708586557 122310335 605585554 388771152 25990334 193344838 486415462 971695282 880525599 413348447 960294737 958281865 768484150 939162795 642021890 681715318 607275293 304000989 800032140 984599117 389127533 770704122 164767137 603844693 898544004 132994202 585788631 42163077 499842495 218886436 413025510 917809096 959253952 945373461 643804904 26003001 527803048 563289913 441799576 117862759 777302365 815488752 752060819 192123794 48960197 898980970 853042073 790151915 900726281 723187435 487053516 987187159 940882131 139430151 441646318 379508525 638882191 925419750 41795751 479173747 62135213 599921281 287068605 642702372 182917085 917323234 188248922 829050348 169808465 871365480 867214409 219928297 775789310 472950784 603649337 664903660 398015962 175989100 551642872 129056182 736944927 385558144 432707256 437252923 405421446 445043551 189987404 571557857 352358029 131200962 721160811 130317249 290515633 224482097 87942892 264017893 867014580 464735559 121660680 438627976 380982999 458271217 660768667 239230808 281823008 582725039 713630051 278247351 919402389 791809490 657337663 61766901 688157055 227154108 767790192 377040535 35840168 264432162 199909594 202356883 626679708 103579980 336712004 228532625 562342379 594990419 901635987 695026475 204339813 247124834 200539411 25963053 879881564 659169014 147507886 473225429 677549797 813670942 318538033 614236435 29729558 106041786 823013262 255755978 681585737 567114175 338142484 843859469 394358103 557580656 359776697 892812642 87277022 346678182 419036240 843098114 96305787 414350601 718018770 729209366 182106896 556253781 948858521 805519611 538156799 965872790 129098400 403633022 231905132 473080171 357543876 565952545 387905406 472580422 187163397 341580116 245963421 532763561 59816901 975927739 721726645 247528810 658738183 103573102 377995378 648339183 511890609 723354932 876012930 272564851 519506890 912389318 383923925 846081599 355069116 454809362 651608288 861409521 872983186 514187637 943652309 747391927 933631035 642652415 843127275 668204180 862377156 906440882 206110108 19380890 345387426 179563459 632824801 802313262 54933221 137200087 371575928 111907655 5205893 759068999 826974750 539786671 307821977 453615452 499535573 248745279 969720986 275729554 894766111 888885287 41762725 505988825 566273856 833425187 424549813 396409295 900095359 84668358 167613932 846185734 310958181 856537779 455285706 848996420 846490107 307017694 602853748 182242750 367675152 670585039 140904942 96460379 768743793 959612126 37705057 675245558 35732015 163186551 211915605 265246620 676226012 507820632 558900983 982761418 730981581 17986510 664023380 237455535 237289817 711897851 521552284 668078192 576743959 851264530 43040607 472621406 735070244 97615000 341950675 535882817 639049562 131944869 379421451 1165968 938769050 126862881 800885312 438517430 592062466 984073991 723550732 439213647 301654839 889957796 11369386 496949864 813513116 207184344 981972535 350656449 747122840 454901331 894584051 42182926 116676052 709950681 777548160 535624497 638230394 495187582 752035873 392890754 508384887 349939690 120274940 535650823 779794617 936339350 148084568 884765627 209060208 742330381 601278431 701410506 92837200 78780971 931510493 584105171 998463182 307096417 647617406 2944804 91806302 955237870 684773651 71064321 989775547 837690663 294543693 888132062 590800670 194443183 935282304 774877087 929811845 76810687 217646561 666609886 450843886 147149151 458813384 406558501 333992856 72602794 99876847 182491439 201553736 560332302 813650352 726952747 380109185 103583369 189539401 833775865 95643594 390232044