999 999 891993273978281580
935828233 883198746 848928208 970581906 656337428 348595488 869919812 799744303 225642185 589310463 476712842 404839164 630586763 248663084 64197808 676816065 807033760 58978510 754056645 30659094 796985711 359698433 230393880 495155880 310115010 992321295 286535805 577070194 839471365 846078136 155982727 421037060 574192516 479482731 133870542 210047168 574765488 842883466 858939435 77341975 462401882 750461866 592670199 14757071 859763446 690797263 682579279 80657728 84251097 110502068 159901010 443081105 832490107 139337729 619262560 633021183 401167030 737770130 920755292 532326679 502558724 958624694 112086763 31639031 961792452 490984557 935040947 559444112 833054068 181668777 613889180 145527014 176495352 582906509 791006738 369255501 987561169 555138737 56964928 416062382 252438119 543289947 229782613 68809664 639687744 20255942 206006979 781027150 904387141 400946270 961834874 251875703 729926659 509749506 508751665 648802792 288524007 940628033 104599197 60544804 962894977 884981661 542545592 207128764 818498241 31969482 54234363 572091799 685532221 712053743 156765091 35124779 575756905 318028259 228877295 5533889 642846684 561117297 90034783 806997428 807764625 900375700 253275382 886157746 384496675 580488379 57070457 877969401 750895119 314238213 882291630 229725339 477468149 212470150 150168989 728804538 418002903 240290944 60888018 203011787 350789208 898065066 329698200 280073431 143700222 125415788 465329982 925675701 411215985 691775776 492837974 808712785 523649209 724925778 522256880 194656744 718817666 86604033 419134691 934582857 910841435 30455515 692126212 396378388 794916594 307389316 332233837 479820542 455323481 439565263 979717559 193085451 986945604 655714562 540957759 700123602 54109512 981138710 315925348 961225661 596982045 181022965 8099270 519999301 314410973 589494458 453153161 909047353 927452994 811123700 109475983 83026168 991754475 845602786 228332737 858786993 328342679 964759991 846752327 706609066 124914791 683223255 912015818 750846838 816926496 523546904 611835064 46627645 246588518 369080578 394313088 628085751 86441730 243877903 459398609 709762224 906731293 981216491 808837855 797952197 597416066 187441588 962684318 731359270 892689119 273958458 426702084 25412498 60155908 218495040 108134475 370933469 517040673 647107000 770096428 473918252 519814668 584534283 803494436 993317174 524413816 118527822 976132786 200737669 515022655 178592910 879386006 421075635 379228569 376534533 355141908 592843181 814273634 805119585 102566190 505311731 114929495 316143619 448184813 11645909 884927065 933521725 828769689 415509687 432783784 987417747 548104443 126093133 734521384 160336635 600408482 517485023 249569695 274186780 555530266 155790982 433586420 104171666 163585078 249025900 978392689 910721064 103350086 911407376 571978242 288572955 498567777 729052287 876298612 224003421 143828636 448538011 893973686 329710288 350921041 620658520 587488282 543991686 64993881 713629177 970099860 514674439 311388753 644261207 326315001 916969867 942243544 446549274 842963777 70638139 18753743 202807549 830174406 563384180 586045079 944900365 652473986 815607555 982314582 739988970 508727892 502187113 406332978 917071109 21533243 579201304 225109139 373316320 88692889 282090163 359541349 807143760 334407280 571622738 976470867 393695678 567291816 268041659 441125389 332589921 976485703 687414697 53046402 123585925 498543030 493172233 268861990 442450374 428338946 681623352 339809325 96345685 534976281 699322693 129337805 891502129 346604040 774358580 162753152 772026223 304003139 42747449 187244095 201749363 487280861 936612857 408822727 399324980 133167050 678863052 747585751 298424699 699905572 956013309 266927728 284697379 813747299 247313415 251527955 65853786 339789987 356185817 950977798 688059358 216628961 316273171 80443023 854633281 99542846 839578695 369228342 451615013 803249722 414584888 202392839 754388608 570090233 181999389 951200461 775487961 947628929 572757726 732044888 618924424 454150394 51102293 509031351 460384761 298385388 929321871 438809214 118761961 53983876 474550280 938286081 770579623 904009422 870504178 11679638 186995284 495161595 679799150 361894103 21495331 607873437 362968272 272155101 259169945 1705958 689766111 698411909 437979597 306286572 929307666 993026991 694137257 577735399 668637139 154407289 50475046 134931825 17986751 553773448 872924052 525998532 425489124 473728574 401545423 806909951 300951042 402435076 36791690 461613153 239105482 598804866 124371592 194021772 787339809 265084897 237321181 434345155 256094045 605159184 880302385 993753643 514794630 634148860 671132668 361667853 40956310 473835221 295025099 49254418 342472633 31159119 784946809 119656325 968081805 849937630 816933494 52481940 30813027 305769208 716990211 46167183 242119547 102626135 70913651 381509415 82658891 578900020 850868844 905445552 612806841 497820812 792232995 511035230 665395804 234743391 392788131 962482315 444379070 302348011 552575238 221721839 649203868 614480116 311616697 487950054 493762596 578749695 265063868 766063790 198643509 721877394 928913120 905547941 599474338 458807670 285247494 996825486 614707567 471544821 207278182 469991117 949912338 694721307 683385029 407811750 136112562 130237432 700631997 435370113 504063595 710976731 568954873 641724201 847898504 478905240 347132021 374865159 167588039 76283331 575354050 280253547 303614360 696511219 93871423 30711235 973165918 173084927 281224544 959218658 52021163 619779651 769743339 970873402 519074440 95420892 424268086 407464225 497934506 511497191 292565866 542593551 725638589 169625541 753962690 575643614 616043165 361878106 101622732 960030984 165363607 995534409 910298022 728163820 358211244 780986937 407497281 653339914 692195790 659928338 897231010 295091009 762179873 672975424 181785883 729895959 767863611 827278319 361942422 160034801 227575651 166418764 231869898 886717526 720294357 81944266 191423363 106448944 427467259 684423258 624927966 57871882 807446709 9296817 722511497 910145618 111449234 119995013 430127111 847170968 740724756 665501904 204740586 321925837 838295024 181165323 984495639 142099333 457915211 200127604 770013701 250580532 451506173 963045704 312833277 743057524 431723217 638105864 85125723 911629629 666985411 386112696 603089355 744355115 753010752 606982939 397570956 812548284 767468905 740091128 550513328 269751950 799424591 846733143 199817561 857546661 671337016 196220868 997992189 826471842 759330008 344489099 354838179 181644044 686561432 39568633 677393187 23653259 806607059 447521697 953953642 693784615 146544659 524154004 968673971 520810893 3619928 638996391 737042638 240414282 444153168 500633265 706435676 781023501 773925535 308683721 994653456 911953129 349096473 169091467 650374639 181930896 106936835 407053652 761936784 590029208 82843989 537288065 764607581 189483705 91533817 810036148 655775440 196216845 612676877 489869582 336843190 810586191 474487069 974420597 678829167 434081820 1616489 753860303 254645547 161041972 973040421 392041285 685106478 390931385 821392307 853412225 565345548 585415278 526462698 561368559 696168685 140466936 218492498 38199807 144753865 364869920 899307621 361378401 557653677 803667471 438682319 360198983 505782516 349228177 517253807 359873702 799713423 601777490 336082643 288364660 358919485 932464931 456656895 440000235 199889362 996311861 738538278 199797956 572159604 32152411 586378671 563746173 130232536 865840716 299721137 711721875 622377609 956296159 599189046 826657992 570345761 438979405 478949755 329378397 564731534 648066418 941916974 407495512 48575822 491096844 958528686 508376255 98551474 666635002 131935055 911533019 70266142 22903421 359174291 670202486 616767559 279590778 45330545 944505116 296118131 230110389 288899472 622185821 870873020 530524182 945959308 932231177 213892685 84064488 884589872 4023666 927928994 503327253 110028474 158149037 540072652 146588266 328412699 279392465 488450475 844543193 192263987 918760757 363525937 306132657 560250392 866685366 563343013 638096360 588784464 961960942 462521053 527216465 52691473 56118909 871236226 349128422 291864712 503804740 268347471 201044478 567204878 624128421 466676562 352082327 722592628 362801348 86209833 217078413 700991800 11878856 250555974 852815328 300004813 480243738 702524971 236437746 207711191 19548067 49007022 962196422 21270124 987779346 46597430 357902146 410368339 22341140 701593851 356503405 594934088 558857626 685922121 749829041 526948918 714052630 51191997 741512985 757430651 162396605 646166150 806579860 245849639 611520197 413258917 354842928 747735356 648972712 925967405 374349919 3112943 215759199 42288003 792662580 52667365 918413736 964057758 356656550 884618614 677090112 583146311 717344460 249410541 81224745 397417306 969681183 628520390 214715877 352374531 540320700 438520558 872626104 650951426 598801822 892641030 668295401 376345319 550924775 745614240 828857089 779908437 795185687 229042304 902973961 797948482 979798611 664226267 880346832 521202485 425469855 57698971 611177251 966237063 223072292 749460632 905096723 341040802 711277418 642606815 361836594 974278724 524662942 494622191 395127253 498351804 185839821 455711735 375029075 249274667 163366183 436715289 305317187 380910533 933638460 424215978 415872194 640436237 748769090 135661167 897264554 208152859 439002188 170927840 780761308 457364953 763856532 299886952 87002742 462949185 638949809 783329186 482554909 812742816 738620641 606399133 975960372 660128214 101622080 280459033 462236450 831837588 610075150 111268807 744587152 666739099 141411565 445641101 842861736 485984003 238601248 970293183 429052247 592459889 87788237 415379046 267767691 848834143 436240187 990004861 777826932 346477911 589039380 38561838 33892039 661125688 409545124 894553880 293287670 733071471 677336087 908110988 292711288 789954623 668401086 557700555 520404231