1000000000 1 605325981 1000
300766868 885995664 277533356 168649814 892768488 291744630 646838712 856019873 59320837 572912057 690027481 880187770 374756433 903619161 122904149 844522459 95811969 772786363 239314288 992117811 387289152 145852010 767518940 830315681 766920764 440439657 93192393 768978891 671641794 35849705 156845758 70486416 327979198 829609163 703641200 978954597 343967095 28996344 936515965 42449875 490486724 494399661 760888990 856041797 427797505 217433185 456131731 763133353 136198970 952271314 702111937 617751540 540449761 557064947 635613535 99297550 299137534 345324714 297920583 293132307 347205934 777072242 331380466 12670374 350103168 78760199 872746444 936183701 900531364 839649322 871118820 424252720 769773806 73142897 952032198 978248215 282964879 188201878 939301741 692088696 89556503 863859600 825118463 390365541 311122808 992112241 293665758 722990706 842337822 959590136 229243588 311337604 307221319 918029448 724679067 227591915 468948501 352480220 301425693 147715784 168102562 285038712 683366353 595767521 422238116 196312503 889372935 131010408 721197484 768418323 913851829 304663465 877858613 957070607 833192625 801344918 260353068 256099920 714135255 185136105 952462458 693443674 314093455 453910665 43446798 65910812 735214062 121843599 199719381 166713012 553191979 863223492 871461138 808890632 379641497 460733245 791367859 79655325 884743597 708871354 835323348 105184380 454841582 554435580 467265533 682675264 791786353 670833042 401798547 265859840 466620103 947542503 681880399 317392180 61006918 993588013 400912225 401839919 961199044 426614757 740073792 194955526 631238790 661135753 628219496 381727199 81654987 133324479 959083135 298003966 620800161 239015380 263346753 105089607 58805605 503342421 738001020 791356698 965805818 543245679 303418539 355473574 144869070 641762422 364417899 148284055 55356848 522133588 881040277 744197877 788967014 530834299 11268638 413446333 609187265 482092589 74351595 865524837 895469311 587320204 182093595 282870996 757793944 591056677 703977947 196210485 248498233 727858842 619901432 166471010 780823255 23896774 53655435 917522935 801649664 13518376 643837480 880179353 233300318 847055430 791532853 705225836 768386262 375002602 877986499 958958559 351738781 724962302 692955266 695346384 80677317 881493965 853139328 675609100 142376994 633363803 942749068 649255116 666341011 66169578 789326930 137491570 128429624 295642139 654029645 381204748 964497441 28198314 408927637 899141465 28195122 355288097 248774198 823662798 621065827 409096548 516803172 413309915 463901990 361373899 527383583 305749525 877658034 807156421 223786454 935083287 659492669 930202522 232853900 860309272 210556059 836391987 885922473 121154043 421511748 873147409 159018095 73732376 121995919 612286378 940768557 648803268 588316036 812923070 507092082 407785861 553547263 569698840 372572133 831283309 923717207 755830692 880685245 145892574 663916570 120778984 560354479 88211441 805980860 867218970 377733407 603727723 978539452 882817844 555003791 353511399 452581970 158108922 899397521 36761020 440931434 842295667 251091051 281944608 220376357 529891250 267571447 242569717 945288419 378454433 910851647 346461892 83126810 174191699 619691038 925346346 219474051 397219837 620900566 852780392 374196669 217564046 508028911 46935108 711870110 769549736 602157297 441020998 200114168 359447180 357272055 307168179 24913871 251173899 600620717 385524702 555511918 303658896 100194783 346547036 440391791 362450354 365751769 18050448 578702115 293026348 713845071 676731138 746850257 270361087 957142383 965790034 277963991 963881318 410437288 502033655 216398925 253184683 36137457 698117924 491060090 467285612 321592208 857650583 623126623 685164972 760377593 649857715 56804169 151204098 814129088 375533558 138087579 481876476 737107698 809670969 609863574 37649490 341052791 440421300 858416521 611336304 93760659 656157545 711339873 447791065 167996946 657434247 694033917 570622741 868199115 744894666 688748082 852165247 772872889 619814946 860384455 400406513 492272923 450275196 42863950 656307635 12685436 603250202 555855930 716759463 266785197 986709673 760760380 553886581 903915752 812733389 540340582 869577141 283057531 671662218 379124277 357751293 845520077 756658746 839145118 986896780 684242258 284717327 650566179 152798559 768689527 103276743 605449631 913483632 558827427 192852241 714799567 612809654 160292169 12257624 929215086 816877821 402590679 694320482 18219982 206834583 566562214 268656706 228906731 18482719 327688048 231218407 216124009 374226187 713673072 571412044 175370930 37931809 791020930 691270563 297830474 926145587 767424059 309392537 902476778 250225891 773586017 794205587 528709587 808447649 450618980 452132521 120403940 699440912 177941112 285307743 910003076 43181204 970781572 418880924 680311608 794275834 635609092 24624049 465797898 13653354 764920675 110948766 700112969 735776473 984350688 841746954 692548072 294087767 299494801 981210469 677435573 775129243 961401205 603109213 333745857 39349441 994850241 140333348 645543833 567824990 17288065 650224513 852860634 649090543 47837844 851768533 547751632 873034561 409865406 554089292 15912235 75227996 562819319 712579624 883199879 533406692 295796445 26225116 531393783 824581638 798343994 289697508 600606013 138394574 272823920 474045498 118362919 755730914 277449819 912127102 308206011 287878716 96931524 261786021 717420874 645701639 55866781 502642931 792824245 934814710 440477921 736295441 42969452 633091178 655716391 813057359 616603658 575358214 913392224 96274995 991199602 831085805 825501353 383155234 460310711 132298266 891390420 752875871 611124176 823492657 982739914 613013924 372232588 493259611 927421463 736235521 109644239 249772553 670527016 627128682 302035704 736494250 163126845 410016922 953143461 327892633 448461435 697495705 770835188 731920995 609841352 737906159 270769694 308415871 593778669 281590677 714300577 816227715 213685775 824179447 714459385 264088301 757126784 115525196 306760687 692380188 693695253 247406011 624494688 55904906 69676386 672440290 571270095 773468292 963076756 846799056 777613926 845528866 904375469 847471363 265926020 505157136 99394740 858876444 825069400 639513927 154934660 162925439 246211751 953661514 444883220 687969912 658372342 354477633 585949456 766252076 791749531 51965688 435224113 482382315 648817586 828967066 649326752 796585440 798443085 881369718 912412050 802351349 843281239 709463899 56817332 372426235 526659270 708508182 100209065 586593013 845104744 218599553 731917480 550773150 116088463 109912744 467568794 786073191 212741599 21556903 455882604 871031562 31449338 288055007 912370714 107617197 541016011 410352285 147138461 128702909 593775840 234052077 596975465 323049874 660581105 969926971 14254026 123005148 394520601 351997701 781663448 186376820 330322993 493332662 7705973 665286197 591521680 637599533 191961004 768164837 948479921 330937372 81782280 125262686 756006348 611710167 896865913 437689901 48941711 77116782 95390916 138591129 355106738 421898956 938501324 124382059 987693888 122601112 46346894 489433823 325154178 594138257 956485479 662614337 782727247 885769033 763513433 81752589 699979469 639534023 492688132 986250322 556640887 424273894 51903401 462108328 280067723 887824867 956168716 707487714 129064162 222895667 996003304 192510366 337615559 652921545 10987451 286494092 447884476 664222203 962585521 106813579 993243587 328355180 706287696 361464686 979490465 760365983 869643210 319745794 963491770 305754993 969550306 126096312 808114825 225546726 455203733 198664900 697653441 200687073 324585104 693387951 451290414 999505524 922570261 806462093 365375817 141876125 805201511 653610613 854726689 873355643 437573059 232661864 853985691 230562315 162791604 144338956 322071012 314974823 234677112 364520475 798528660 172153500 723410394 379832870 455922189 462586430 799335273 843987905 775247706 804925199 304602123 920617039 190914644 361869896 273670574 745123974 247751940 702906234 437549497 910405557 365228430 885976690 602458200 129588601 447215755 162446591 788156406 865597752 754442662 100634925 227829269 163189885 395788379 184697673 26195179 28234221 98900704 71797753 892775283 405956598 357012873 246063599 611162901 400601909 555059621 218095982 858334271 302710781 271344927 312672087 187298806 793764570 632721229 880426085 85157748 818066785 180021225 886020178 689540154 205884049 697064629 122977088 996666408 599889462 980223799 200600235 739673146 977490969 440824836 124444905 970196383 247294216 893048173 697451534 28461595 538924110 685252354 81523220 66200157 229517956 627664883 724022920 59110549 259827112 6283612 381984987 119330609 913569391 926437117 298451248 622084374 347946801 343930432 486551530 927587160 299879530 325088564 565105583 483113026 44975481 908284192 144927051 542498862 636558698 952266562 622236669 760093623 587055984 36323753 607969326 413278059 718826884 654199996 23068535 92077864 290709391 427446015 752383293 922300318 564488983 857335061 688857487 543451435 540325757 620404962 39365132 184818651 985722198 270395407 460225203 842648957 820118560 108866457 62483958 48387126 419874695 202751629 663839444 971997546 454661296 745594249 635471101 926626379 258152212 847268547 78414575 432552993 686025062 183533097 854260993 562604139 317274835 236264747 204347929 649299553 339443443 235655052 694622299 795882604 797038491 896686881 649924547 106307770 8304489 387595347 997104081 439658405 921342138 566485075 45923357 887240229 793834261 730284446 661352854 491490594 186573575 415967211 27919275 14086458 527915242 342801520 840271965 598469889 743780505 216646751 123428971 1529401 335569519 624865617 921407895 597929554 252304748 279447037 119631676 604901746 396076930 739415440 941185117 133734423 332827582 712020465 75349154 451629774 260678103 350245644 325870684 825294541 128483017 119268063 936108996 718714656