999 999 98358284862100296
110450588 195553637 867752411 24318980 265669043 333388296 53037146 158929563 348047480 140604798 487699646 479981950 216656561 878949382 236276613 933668813 679900964 393660592 295509326 691824282 754222810 581924255 528212250 210287400 460611420 391124041 455054989 345317167 492785401 122775477 527469613 570607381 604648190 65974971 33090978 912464437 384323067 586643015 210975732 204296988 748810244 494634390 76752848 190555590 807491821 195817591 627602371 790808037 573962381 700478859 266959996 486592282 896954619 61330054 10090254 93687609 316650708 289072235 584333099 725589129 817853298 207533010 98361705 447726593 218627381 260912933 973093249 975187852 672618942 32143581 56018058 836278853 760433199 214798282 16753474 830896827 919713644 208925000 318075973 992824622 648293468 634605963 323566675 777535439 840183335 594042835 548939918 32878340 764665977 254247095 138795705 237609889 474920893 836457054 422161273 127956271 401710947 790371009 444172951 949555752 930449947 360266219 570373436 917916216 541603863 855380536 805476404 353502333 531041612 100095640 96043563 701761992 369854384 109455565 580863474 902193370 312373629 965417896 955614394 293437095 908383084 474620751 680160343 510359701 82573563 457006970 768650110 672392381 571231911 361921457 401955846 197938217 367425586 906384783 449464619 155851028 124314845 167470850 619971014 591235373 63115694 681075335 736704661 42619347 483241388 887576946 106561657 838291033 943902749 798725668 979888306 439132739 174608590 420935250 147668773 303390087 402693707 815611717 320815766 296949965 613316641 962699284 299250413 874421167 270984995 733162987 370104181 967792889 8433058 278133830 830194456 737109225 302176691 803639094 676230308 616948591 777235821 858815386 221704456 39203950 64753447 833919847 255837591 536707577 270721470 150932449 960320067 524880022 512597196 285102047 858932194 686680446 576683762 845779466 46464621 18505946 55545870 631096093 549328187 376070151 664108421 532024358 788373322 165457363 650321018 684801219 577904502 96494269 378500116 209742694 208464575 743096632 674134460 26260369 730817671 540871656 353122140 191057946 281993425 787249122 262689184 83412840 809240707 712346864 688866872 504980915 135799716 91737035 399362068 187932487 748417438 182800478 200838054 611878081 862595452 557317641 243305763 249206096 184538157 565273051 540788417 689834228 110169279 470557911 444335866 19193538 722995876 28081199 301465800 549556510 580375024 509499787 205533670 770273280 244772248 853881155 442823445 713144111 810088883 720015008 566865491 594350216 916017085 762586655 893908773 909123127 383379151 768983981 707452110 163203835 860576744 395444459 225258133 549129830 831907878 434594667 152315395 267008795 551973133 775644912 181392674 615431438 520359102 198265266 174699710 262006215 294452800 261567639 309838503 141029534 363027387 560522619 14267885 797664512 515677880 644807016 225936162 829444776 197223521 449482462 928323227 37221862 231573446 419998220 374240943 579419611 729875478 631147284 514295797 935926970 76357857 997385290 493840266 124158473 798427229 833754741 827799368 942186717 956592029 378884365 507132432 758279201 272680155 446638714 323611649 101341903 905707950 362730587 693278397 386128948 324302676 751162300 855009194 283804208 201819369 194656606 195900975 977409907 323689390 635114994 113961970 66607041 141572931 734658142 38115104 848223278 66861548 926563318 288531621 537309539 665196238 244494019 721375855 91890646 274461235 292454847 664720815 264547861 77465538 532418327 663873303 833665788 782062279 552102503 661614876 213102585 530618992 420407041 47455285 191043918 981316110 775157286 855545625 835658831 876622160 687153482 295952133 875058079 668021899 617001555 218716659 516322679 805544180 673243 86844644 312696287 28156643 499584873 24905239 528981746 418982929 32136635 918124878 649384222 905837018 637706495 24807951 149798753 327702396 248267029 340578785 131794829 418446934 822085582 688119434 350946948 359356969 435410223 403592279 22260859 988273498 299178414 922305620 167938363 191695149 454939763 666002063 68641883 906413579 120430488 52424281 410720647 804645820 638121577 270451844 834497724 270289837 339266469 63328165 135785608 889136939 324822970 396072019 782438478 126048166 262260492 702776166 266749568 147271918 753917998 938442808 959696611 642932601 853571622 519776487 335871182 760360602 209228461 601430672 662330218 206575819 572828780 522479509 405793778 887813604 937577792 705313752 50686964 70967648 474750583 12864253 424083343 249158815 637288720 707431083 979766195 281375518 466024959 913342155 976391267 282860736 14187109 258357703 589385461 757205512 6955483 131910860 128058960 752758876 13096616 81728008 106278188 617912387 731082246 762261227 787984469 251436967 348214881 991295082 31038696 392608276 319925143 191856439 398980244 489347830 480030520 665287178 274328026 227424734 915979462 481525210 832332365 193874110 347421174 192714788 558154450 970578983 665073389 492807971 341937633 22455186 244286596 450575893 956605377 720068500 615685252 535358332 690645199 703623719 822824426 433359194 931828663 967689959 806518563 933750131 677138873 529006930 337216081 801461646 417492197 32559367 296401283 81470388 542704735 598573575 216845056 802372719 73884315 594309367 916660093 994529548 51099553 667131739 622355553 374279641 873939786 688842204 518312968 797103207 691558784 771492483 196855293 559167944 350650497 341623547 139697469 594907857 710995229 635980498 804217466 166537817 60968179 595227063 609367126 610221432 74659511 941764029 968668579 172975560 396386927 743781783 821301673 61565863 846866352 771414233 626040416 590412914 351732197 288986685 446221489 92161739 854903432 119301083 129279160 768974036 801648487 305522543 561244164 386760817 536218847 748289686 716339669 877100938 348353060 550455056 682589533 693802053 816873847 946401535 852070399 480488272 258582637 955705638 20781971 72030740 234601007 982222635 408531103 25715970 347891124 260985814 729537694 197725642 222036999 110016847 380189757 878289822 471750791 249482082 397500312 827745140 813730081 306211262 220652673 302963777 28552856 931429425 897248441 850605373 96867006 483725037 412954165 283371557 457479863 856248518 605822297 735960436 856518972 779706738 425516864 130842280 288549589 529056711 370076145 87003267 34770462 471783935 86485675 503624519 955538434 557005302 894779930 290210040 723957763 49435498 122179742 173528990 815559279 376162874 196957323 62932352 193077932 842767528 722354275 141833577 476995948 221368726 318935837 943519973 49726713 192616140 999072865 847827588 257935210 277827888 650202314 308256790 178770667 929469707 8657442 523126510 745063929 424767050 618699688 939927071 772567971 871806651 266580045 316471489 754728906 163808331 318983921 918606892 34996065 240063310 773137579 381895738 458189997 49809591 37395198 700030857 567903109 620826714 910375460 150998967 107511186 194300721 950393671 873798052 235316368 810193812 415919810 574473138 505013899 477512575 447552612 434314760 577088034 181234895 978773420 2648778 781190855 78977925 297567757 190731874 389015805 794877953 175781163 429401018 295346840 716755783 737538844 675511423 832387328 849376573 819050664 24167775 930336621 22309610 363307913 921256523 382147883 701167800 262269611 977478837 637775832 401993907 668453484 867152851 632785313 112601800 269586653 98681562 98862472 495438086 753819646 353285443 527755168 775647711 673117701 801330440 929729870 310095463 541379991 698826983 112813450 56066708 834115085 160386718 839021851 826257788 831232433 711580973 72748254 593258393 430536189 46157590 149221376 169058568 764550114 258385056 593642558 728205252 130727422 702998543 735911468 68911087 819715812 5928941 658977130 896470026 222144856 667062084 186916080 405710648 972047504 400419809 966285123 216047486 718124147 510934674 840430269 519284229 931669981 434845544 728771016 731432790 10800857 84319734 933935907 49098652 556290789 166275471 704925723 533096677 295146801 384962443 850782931 90816353 712353503 95321986 609904252 39065505 918149956 476250510 200642973 920551128 390945317 407793293 285656651 657244445 809499643 958780509 743861873 775612839 618965551 282746398 388509193 853905167 727262046 576444019 57025377 459405201 641767829 249446848 391863127 616847178 475593877 771273837 37816221 643925115 163593744 16410401 618823925 375491524 74946025 450109703 619605876 223629417 885990520 252397068 884617923 467890320 584842947 352881438 181665369 615138689 286097606 145267822 197679554 665588196 259517355 612988846 621062874 909641222 425832466 198038100 490569746 840845843 534357578 7828949 703248042 251755101 991371413 35384810 435560692 837999507 972960104 823260877 737910935 406624522 71456679 992431996 913931465 440241912 612074733 221496821 864289427 927486131 951701442 629019000 581481745 449714421 410679778 248262856 774702511 92262939 140649084 670476905 100881516 607591009 310182512 351328483 923173402 945420327 645122192 219451133 275561115 496112686 262989279 315500546 541518117 606311387 180114900 766089215 551138431 382528883 671870616 658316802 171314497 41599069 862154051 537946716 57530391 457001827 113290274 708276447 663911935 151512816 354851572 322479905 700608133 93110610 951591 201555127 553134093 216344825 785444383 454928762 112218633 930900150 833219952 423289285 784534334 4365308 389814046 104391860 726758916 888893730 495600611 773880421 568983682 4472735 20946281 395814458 70084341 578213452 702808203 717077 531650537 977743781 250587032 537662875 358791806 959834120 835653776 461965937 151536804 888113139 174134116 896979585 618975071 663955017 718632505 516785461 481940227 553764494 540887461 807954106 358810488 682152742 334420720 924053055 849847926 354646937 586864724 704183347 930813386 260059858