1000000000 909107105 657355356 1000
90722426 58432815 680303429 656802978 821714069 81032229 404049008 508394045 815033128 537356713 111806335 80898026 295991237 78868790 550351734 549534112 766404863 359634541 285022912 417815753 284604425 900505912 411877558 12589604 66352005 634143645 90909857 163123786 358612713 291020488 287352580 917840183 764936086 369961443 976822839 462905306 789983491 434894062 303924276 265460745 201481379 789575760 24618490 372367785 618031943 958224092 892453794 371391689 318913824 939207282 178258107 244325187 384693248 539908245 45740123 374918989 546444631 381113628 506777021 481264751 119530438 830845835 13551034 118970259 225876059 621585943 560759976 460940175 466780826 427596897 67040000 386115551 822243053 381731729 157782293 778453036 989806931 203026234 984158385 830935904 453590490 736895827 469988946 659378562 86147997 485415904 94731978 874980222 898326724 293486841 937149754 926875736 154128017 564311840 27576307 692282627 127720946 196042648 648887244 925967248 991305957 701094276 48734046 881850018 394871158 875100082 765338501 690891003 361024898 30432894 384549875 277721881 115964019 165866083 277499981 681458013 734543443 661910124 758179414 627208430 568610113 327956847 453964310 842510605 642328547 215604363 857624855 190707724 105382523 563813916 248902227 1601639 75217892 392992987 447192967 853182095 683176452 625326885 83996180 827049584 634461483 64112409 574217495 81945653 723589050 161287195 629540657 37910236 428451923 478809873 736318605 432286800 507086605 315733922 107943720 660170551 512205238 445244469 317039318 572897822 450771432 866909638 547491197 790879214 456924994 136869292 407221513 141602808 506529986 624314800 253761164 61377212 774668330 731029179 653475369 729164428 451118193 252470824 923202722 698815885 410530558 995889125 420987560 653054281 94397756 626428589 346724308 198585228 432347961 461269305 137260271 535954625 169241840 105522831 774486825 901691711 682332812 404904707 931483432 286271800 24267952 923326560 632677504 145548414 248328568 23782834 286149502 25069464 435695039 881034429 645918944 429873029 741026701 104369737 721780386 901584229 281531974 801421080 466665979 644838612 526335701 639001520 132844799 413302543 339992382 871738237 97376004 215977020 678428516 283661472 84671967 373841634 692950146 609294544 137638691 453608624 233213524 462058899 523064747 424910641 16283591 947907574 375177755 600549096 255523975 697904051 117722049 722055462 156077443 42326497 564356325 775235702 603173971 348391740 305819037 972204394 709938565 518327626 265004529 50051831 481292623 587966738 310980702 751211942 562765287 878214027 488062764 557101638 178537349 642578187 116336549 862081481 592048116 187215640 469735431 693519251 510574271 950869511 764329033 904631503 259385626 102429578 325791182 562846250 91475521 904548825 715373065 587914128 500506255 315199292 786102125 699026934 736397227 679953334 141473834 486339212 580384005 643255764 766954953 405519895 533529913 219296549 635169194 147442724 947483856 769942093 754058859 92508845 18014293 832623885 906208149 686352525 318494621 336113402 102230787 205927912 360528246 273137318 372616566 504326916 104539309 350559923 239257123 31345656 692963683 836819306 551688545 468746699 182019476 110894787 866629739 138204402 297828586 894422375 171336028 942802195 468418782 39427575 160556328 157019047 835470992 439153441 752412449 338583386 813062582 704378216 481080627 246183840 484569741 905655966 326570980 784017758 26809117 683013775 38698193 786734936 597271579 115908642 308886668 990262680 346606913 373002706 551730955 107789745 219804777 587022602 549005899 478663560 424728064 168945826 499133054 858130202 94148568 733293167 49616039 673120840 198113887 26712538 133560749 635114134 295799531 78083115 230413891 653258899 312178608 483331841 501373716 935964210 432780001 206381224 463158669 753288138 23902880 156278977 208282964 213448144 51540701 808660369 804570146 779677293 91057860 327362935 135761737 46155628 496051632 608269773 94181670 215896657 401509399 774858522 706352249 372656730 105613037 143095420 896789526 227603819 669019029 786231744 730049820 299516008 263894694 724407809 88122042 377202094 263876317 415537167 316354128 868069550 714787762 414403019 582081515 182277099 145797254 135615154 803752214 991329471 22552250 4818861 459968467 822654299 851092310 993631729 61905214 102703711 638177219 237453194 851232238 124184558 889520052 456113776 461372072 790715013 918432661 897476814 191350905 177907355 791695667 220415263 110050972 643283143 153380386 883779505 611504462 772516922 5786695 620227153 272146336 897051268 331734319 591160224 296800325 792308924 863740847 976720439 375429008 528390973 822211269 921279864 593596184 435799156 483445201 259131589 127788610 259529673 375935457 450344728 137738047 380270525 295397009 829097029 686131246 894425762 228261337 982505820 973563360 123261227 403473060 492120824 41430950 545291828 333306430 170084213 304650540 660628138 686677182 406295702 687624684 224826060 154130330 603186431 557798556 80486520 895994256 820144634 547092175 526958997 377319157 83878914 968404849 201744933 924160544 690802887 783106762 821835101 343802113 477377744 288846619 258349892 948459240 299181750 14729606 599877040 771438841 140098731 997303208 565160424 331083890 396818256 313971236 547259579 119300958 415233438 580289942 136089150 180268398 745289495 882188144 709045723 544717661 346949669 764993681 264210381 661441697 401519590 946138659 709786004 101726949 327865637 710104198 80895986 261704957 428720049 690244664 235423560 25170129 347263264 666875728 463223609 770992894 161260266 176944954 722749413 8143438 501567688 974826144 750267648 798134978 595609824 993041704 882764870 738411597 175723169 589295161 89199366 230167159 801401469 137063902 456797909 148435344 450587424 995504249 394827569 142491356 407962290 780673385 726257155 980704763 767977822 387457638 830120968 715613247 329685708 519901902 954065901 798956184 915098427 855133001 186057066 324926633 385248307 205116850 687661321 840592523 617370674 581694244 115864343 638103602 73914099 345366716 207067241 181877926 953089407 493157282 281319784 456369220 459652086 873939546 587554368 896470876 240762386 634247360 760314442 3393623 128321922 632969869 764351271 204652149 393624379 321571672 512510435 205981331 184599556 524618003 760680469 786500295 948619183 524021756 403225148 620422730 337991908 535759844 116774640 905071348 907490941 771401199 581191460 255516647 574742355 313333085 559273957 181489186 861987168 493666720 253509662 129341989 597366762 457127612 321036144 101825927 917638656 599097268 550712719 174166469 195650428 499296645 386378669 949491581 154037816 122053860 512350538 739817922 189515730 472642415 159075458 53083492 968553345 550041961 711896822 144756496 897214851 933581749 119205444 957404883 8918416 641721052 742854133 753239899 286900234 831462129 707927880 10749763 282648796 244495611 27783945 960829022 650105944 332492507 449132461 164269628 289426384 338783836 960791858 25482192 929971997 653387519 326419705 389014076 145628847 526424175 507082863 252833724 580020485 976026065 516245248 699966062 414202574 434436274 126065721 293963484 358162471 239995959 637802250 377800152 651769115 714892686 30385443 660791145 205101957 437354670 857173639 123313176 202846483 110566975 725802573 856737854 315267446 857816176 185014300 919969088 38212019 131801283 54789903 657173788 611466798 139489670 424499796 627404441 641741520 13117985 356916884 780251720 81776037 20336585 347101028 87667327 250991450 755425845 518864254 694176737 823523238 422964554 594395911 991900559 473236581 481538605 427227322 298035512 77260363 361064732 699922932 763050084 884180534 909147924 703027069 320939695 628291231 513635521 861690733 880192793 459177994 422076470 700753652 766317419 808761349 354257359 105038212 145679653 306578794 856530008 43225194 636379678 90961069 848080245 835729382 486946877 55991425 450050992 569626213 225671968 412653977 176961855 266179506 470537447 214358458 318794166 1865503 215012846 579675047 538967120 334371197 885754006 510954644 901355985 740402360 348480381 721874904 342664608 686675628 380177624 881493549 846156020 707526109 774368927 923731198 990977429 548241701 519689656 608072849 5713876 470108447 520339819 797935752 944558575 996868207 770299785 323328958 235133318 515781952 429542955 562173697 599037309 616723630 444235567 540292580 62799123 790893373 694895307 15627346 655807691 200052812 401978712 72667525 478647758 159143850 39821418 337424688 666178119 549660801 748191643 266457295 844369876 752583362 992922513 479625704 489346516 658285032 306665613 168213294 418340618 189323254 458923754 444023680 200333241 820181621 94982457 789813481 798761463 863639647 349585459 235455309 558767168 253821051 567475951 593440533 367414156 40501346 217322900 750046979 310584969 542586756 699617377 996304720 963450187 680611335 463078406 478041317 704099795 96626174 498486092 722058103 200464730 882633597 679581529 334998140 685366772 930813126 831590513 718194121 756770490 569734475 971497982 648423736 651972653 169086960 723680142 618520212 574626587 515095553 704386617 622276234 351320754 141641858 89093109 591797810 275298396 186632513 332796354 187171469 801095258 359284742 848402060 875756566 590627952 743362804 712538808 197205367 863344251 753574004 533493852 686952742 742656925 659990514 707540446 761150343 93738025 275739503 84133501 987528387 562251276 829157335 625952365 932762128 302479002 670810971 30859653 40904027 279223152 651755372 812204083 234237632 494364476 169526292 591340301 102137397 783814232 901123332 51437263 143919726 792265166 128308545 408142630 590422295 779329504 688227481 692367231 475926954 601481029 886144780 636242321 556095525 448665334 903192324 465239051 284788236 768591919 610254331 162651448 588350635 320686640 670154736 812678067