1000000000 1 766455601 1000
558055814 109246028 38835513 947196933 242586123 147273834 256441677 15594213 98941360 755103145 463954471 169688646 98806912 642927659 621211739 713955885 391698389 163712447 588561728 647301220 39465644 800390415 324148500 871577287 613523228 342178732 36750461 263457917 899689535 649664621 32690378 745128044 316156430 766593138 302746996 880010432 615462138 717175993 824962370 988135961 36320855 559271043 132513588 215348383 850344692 239584465 164281936 496286940 268124035 939973242 166837541 498667235 545294630 380399644 318007992 747274387 956271459 286814071 457062412 298961568 609089622 988490335 623575556 714180735 949518465 605868801 543234559 116524699 999280255 507401228 234885162 639982951 521619860 836756772 574421431 288264131 132158891 696406845 723984571 366357701 538281564 623399967 984281882 759074739 642550176 719297495 302275433 470643855 929015890 690224523 970647193 307865122 558506643 170136267 105771891 665470951 475448284 72667104 471572011 422406430 877682254 140488541 32655517 159210813 91526735 691560699 879187335 740322968 87880861 618631917 304568875 361817903 473566047 650164550 918804317 863000468 344330644 770463673 930310927 981074912 546612721 766708637 96446638 702250011 145819368 507285152 431479477 897044246 213715565 251109750 596218701 489027611 667157814 909275717 703360373 554070906 780632153 33262527 697559875 775606958 400422622 763016886 326213344 141938623 781863574 328660628 471243115 263352072 194486040 256771949 197766599 632302467 284744092 26663711 386658780 288616444 684774365 637896685 891227374 160045396 159711107 983775229 833683953 469151622 545117800 629634901 548118917 603551019 242978131 293309753 108315385 464301669 636327911 294654923 168017685 612833912 567996375 750272113 873178233 677077063 118360791 719965618 465541107 292141259 870531374 214724210 23537089 450880581 553893234 931136236 893399569 160913165 785669388 942217343 302479226 674567336 887052042 852200823 297056897 809547234 677724672 265315422 980263188 862619562 384886040 558937919 976141058 301448952 538629797 33701057 551732417 132361579 881758591 648848581 276158207 678840688 768585335 499597043 66450334 139275501 46178480 880125196 396817039 293517117 372265066 34676678 842867212 193363051 710057052 362263391 444690098 663402332 67915506 68367768 153334034 104741441 526558573 89843930 325944475 991766458 924541818 656424064 895757412 60724593 543519032 602695116 890201939 105436930 404490541 413054815 471395180 671633283 966555555 259181960 974374007 667393853 581415896 806387028 177500185 390840418 776187783 498663582 483907063 505445055 643482079 275672267 27839873 827060691 821145236 184332409 329654072 105306079 352761431 732780080 16097418 696439436 197999685 254803171 394519685 336602489 806114828 971335499 65064005 461572518 938393868 465852714 934945866 497333166 672175241 411558846 24714541 912963522 407273245 963635243 569613653 14584451 307749005 123180042 112738589 716897072 432096013 521754967 960008071 811017789 697280617 377076643 302905007 314475838 438170805 615310878 322441224 94676966 702836053 331750850 869005144 333188767 340014223 165069697 851275781 856011759 996699066 75030645 467158129 326469074 145017036 981134933 481652248 189733172 905964639 888638846 678070063 701592842 911940043 385530868 659152283 578044138 917860377 30586417 817335692 581844215 488943293 323767012 902359412 425139176 636054269 676062769 250990709 742971858 584360327 901314964 50970816 894287989 60194173 218676277 947675925 776811902 250821784 51333030 539559342 624178343 107803609 452808621 746206809 193348786 470296794 464662377 256304730 935151454 731433615 980174062 438420703 520379270 387255289 650458392 488706097 632172730 251746384 558699701 193636602 992516236 641167186 23962859 90595803 77772104 371969535 367086731 979920312 468611747 61373263 708289084 712787870 88214703 860813697 98492446 726406715 273134213 320430831 665748571 846440330 117215161 792723434 314226056 535052025 31629169 89249153 667456853 566515073 550091339 468051044 301314353 423908051 345631041 77649355 456402335 603043849 308906529 250333087 427737139 276595243 507911976 229092210 988344625 322119636 58464971 147015901 216320636 11131687 259202926 253016149 424803586 364493853 351101110 745044040 477571293 320607595 415387245 961843357 518156709 613636384 96507977 659424357 855816158 930458530 240604659 130804915 488702103 565053976 689496001 537537998 785108453 104508982 914595858 998390406 584094614 730435464 338583775 819600505 331766806 63435813 207988955 640747999 494879714 239205173 231972233 775709 152447684 240242520 486785683 568029337 230531027 474480004 978654320 665912270 376503952 341372185 439758737 460138415 457736461 890284876 425608862 973127630 120638664 349479886 340686263 722636145 251940213 595158233 919352935 419946783 340584418 84669054 324882843 328786610 441138942 34915329 558915678 602344974 374082866 452369076 874958355 530808055 643927553 246561021 381391463 881390976 195945029 81938131 597166796 317532924 278999276 110296910 481795815 455188498 603225890 147244146 831208881 746547635 552902250 466391987 334830765 19787198 777221727 696299618 434694665 173884367 823071232 342292476 874712449 692833207 791392821 499191659 769354210 537185689 458639841 796740567 184445507 83000107 192186429 261915518 746384902 524139953 242286883 486664675 681739932 104046958 665551254 751367385 875243976 546404392 778558578 616176081 905264339 929865208 638606028 106409269 640456358 961986948 784015403 99991127 144926114 526759106 238976591 685153450 566727339 896420531 468347391 987051088 56479747 67352661 272308264 397358097 797152739 669360966 356687559 147211915 289510867 684956197 472721638 416834596 647406861 741223704 194173687 375772599 934415792 178322439 251819691 717028626 495648848 281130026 488331985 786923287 541661366 519407132 154650872 762001237 436069777 736813458 159346583 225929478 445665656 953478286 586587291 748926686 809173341 836164366 281521797 630376241 122918415 10549297 134650608 698754944 460036995 900654168 756124099 443267577 377403599 429345381 462781353 854189067 427477277 204061903 137036268 471698948 408344538 762672984 988703371 982854541 392066266 977912069 2059771 258849651 757974165 398805554 428492194 81902746 2451101 393482020 76436010 464807567 549021009 732625734 643229666 328334270 354861730 599016794 271928025 449123762 18057132 691031700 578227327 903190617 436549502 209616945 85080114 791125726 305084884 444454982 702784767 543528872 768067592 387833433 703656592 163914521 763593976 361688563 447223910 299507676 123858770 782710253 600159279 146320597 341506367 547471964 467630183 744087887 14115311 759482927 28061646 259432208 885333252 955534931 792881454 822576146 611316662 837387792 442556336 234736170 283366457 495072383 256159182 636418269 739551602 8442784 163966792 568370849 601614093 975067781 516501816 717137144 172027227 748623730 12350740 346723647 187475801 547285661 557652729 850789198 194195639 744719863 972051128 281472146 869642111 301266498 693342486 760910386 355756423 603744919 280638364 814911742 644705858 442622870 279239688 929684327 113485123 379000531 425444321 395917167 201753942 1841387 883437057 224698447 156822286 749734336 424694782 683317076 841302402 737155372 537194467 606171687 265138847 160050810 250712609 363912452 243162511 170950539 906339513 746703626 351188549 67147666 48182770 206488874 124940169 704163843 99347490 64745694 480420255 958471695 758950121 695570693 629421613 184612972 750100715 139984098 144408200 412113096 750059703 524437237 943771777 658056103 408157877 846687027 886118462 193907292 193430724 773695340 484105198 614274529 84392757 336838401 476128921 774723331 581689162 30459573 832943828 914772629 748163536 867813173 700826817 922259750 956412834 515411646 648252550 996083425 465370593 348122580 77014211 518963766 219191274 419229720 100075039 481501678 880337056 736330992 640475109 203393182 708994076 750436759 419158085 964207620 525877481 453882341 538607849 738562844 570256254 77361223 982485332 629229947 184516384 200488023 200368821 344424454 199636292 917719836 889747704 260185629 663178117 594501295 615614204 51723785 664527686 728129185 231658268 92675071 664291028 296369713 185572385 768836057 418522806 30131500 687730034 921710090 308211802 385208053 602301292 713661316 809577920 119722451 990822101 85119248 375109040 519406318 140969974 607898780 301353260 4076177 862580361 799785060 887365250 747578561 699814760 18745104 442617045 181338913 483832504 326082169 84755642 706425536 530649515 126829420 244559099 21084938 39759614 372426684 534197209 697122186 935552296 729368216 654957639 945614377 488121422 469216417 560377138 469032850 696400443 616377754 607359037 893577474 206277463 866722786 628295104 578729032 745411964 793032576 141266533 223456775 762877452 130229753 485639184 626181871 495102176 756898537 574336757 637022976 165443916 698331977 867414987 450957252 768760907 229218580 964761568 172413509 798414363 398639064 851528638 810803661 319656791 541360173 825965498 667847484 689399349 173017646 214735090 206405653 873728469 261208700 678054835 445647442 647355588 953220217 544188902 50031744 143682010 18197825 908175304 462321678 644624106 142367233 469319079 138342128 465114225 334312898 979664537 464760213 826884155 1579927 784046131 503682531 11778849 398636425 807174965 535447059 228506262 804001404 884506910 365682961 896257920 956578188 73299257 358749247 438272183 171678874 262563976 907608677 602698101 940370834 406723748 365592638 564761202 63810677 871716889 812321992 68442144 329638046 792580088 52493481 715914880 30522422 815505147 954387281 831689130 228166393 460532239 634285488 327381511 447960166 862593806 942258335 991440173 809387344 137945493 241312317 213261266 131899222 627108853 30895580 644729116 833520076 936104757 647469783 725020338 594624494