1000000000 1 873712850 1000
278171983 164635568 206054551 341466272 947345526 592513430 491563677 341146136 935528892 632574736 565810285 515879482 994979438 164263680 189449944 440718937 492084059 497263419 573679235 699086245 659495381 975774703 586571408 481989509 489369682 258500183 253174606 940515141 684607850 859460380 975605341 961329745 475814413 857496493 180811237 205108157 541549667 789565686 929038192 949134292 591532534 111771958 576857207 424170474 461198704 24411088 107787842 187812652 840039704 989818153 391634388 161797867 622470373 392989457 387855853 6727709 329722098 57766809 224158822 751012919 439002793 639889489 24545850 225249129 822191668 591854261 150320126 989597213 973263102 250032921 751564698 49076035 187208200 344682948 249177656 335769548 765527550 647012076 548523150 955044109 59828864 521387258 148640429 676217145 698104494 265333676 213316343 987378367 188340379 45870981 6965200 26274445 286716059 957258375 767775527 847806096 523066030 446465618 439795914 11230430 845034704 115179096 932317331 342968588 426958371 72743349 679288306 775508296 889694035 159028990 256853045 487005248 433368705 437044537 748552601 964369284 21738858 292783222 922593683 126373824 103541488 760043149 812481290 598279983 773255833 613512217 157108451 190608777 589863941 506997051 958083491 676856434 705216482 611173584 580151090 500827257 341562385 415233070 574113370 479392022 856820436 629489700 255209357 778836846 998059063 383921930 461276905 264985068 796704224 647370529 130600184 269013657 859464667 751945300 3402908 284366513 123144399 587428511 928675924 345125078 163872205 52388964 33031081 28864020 860038548 832255580 84806728 491294518 112349714 623525888 953152482 479516984 809573123 39107675 152714549 430483684 266887051 551086204 8869520 893659400 232917085 848509340 531336283 931912558 403574490 49371187 852860570 648006491 81795283 343795704 369653277 92452574 146009420 480263645 473811072 473332431 206022596 878140411 324532072 875829354 137302719 175636338 203668367 303758166 694875446 755556939 574677465 296460275 445797691 783849733 424046816 530362345 669072348 874585547 707474940 988121771 871571349 513714859 47640852 762157863 920999312 173326014 28766949 302299671 878011921 312492693 393440915 459326098 763776751 212362517 59018711 863789493 720563534 851038908 96104315 317536467 338554880 333962240 454864648 942114246 717211594 349558150 582319084 953882215 932979456 733885228 336708854 446316139 74986008 790694297 570250446 902507824 772007610 35714499 31913759 577394393 862712584 874573374 502883329 538234541 906817826 195767226 314828581 998004885 547094108 559446928 941129136 266603580 81747997 622810129 734551028 789391219 144263373 125489354 270648130 412773370 36124763 484769866 136659150 96590390 970797824 692036692 289258695 741660283 15564176 667851324 753938229 212564082 225496196 679679443 906896914 451265822 586179376 335558626 441778563 47607241 197257786 670608560 923905270 695380063 646720270 921099039 775695880 821184449 843393704 452179507 910106046 700047767 713676686 626107170 313352696 888876034 369529889 166145702 682080817 464592036 147816963 794867788 920903559 711480587 665287616 615362409 114780917 682573819 160550465 58479606 392977942 194331652 883198303 506927263 858898398 120316858 309595562 19742256 21881533 543238300 179399686 103490617 978796075 900913311 816581610 792881519 823677004 859834472 820527047 531856525 11943440 669925574 182369400 623349934 143377251 264822429 210722602 414246314 95824227 978798165 936039941 631849095 181113653 992846575 824457238 14575201 152284255 714725191 436514045 687432969 223905929 795615965 610612516 813957625 714988791 571880355 530072739 96631600 589672471 279224915 681394516 741099591 255681740 128234936 244737990 880230731 23068540 92170303 770581437 762086828 800864294 772448492 339244730 117102728 842714921 855042088 805565922 335806945 320317105 901839336 274148029 179767167 911043070 342482783 851968324 684413498 716798088 915955572 228791891 235850486 758064470 842819865 471352249 861795345 490923030 311201839 172894207 287579464 436120681 518606759 661425566 130405873 224454150 345889901 133342081 181178125 974880007 581801265 840832870 361923813 106103366 867862158 450375888 661452571 584270504 465401627 869711018 385644623 423548921 752184072 795218441 371877589 969233956 177902576 711375014 28801422 881695785 12005379 984692261 140121828 311752663 840666991 795212527 272472587 118464261 311502261 927119467 354740663 711735775 659273441 466862997 734894667 122489355 315522238 845146429 919207751 127331345 90477986 245097029 472139860 302559758 954326836 889531839 654217885 323737361 404023459 78992002 473692171 622446971 789248420 965466051 201490828 948385103 884814893 833409806 156530287 137082840 775097279 424173854 518006364 234271616 697723842 310174857 92276909 414833235 296537466 669396601 955605004 896856541 280183100 679482459 817403893 654356598 507603105 406614834 682558687 979960361 67973467 144678970 667977192 721918058 291411154 410825101 577555805 354338598 396671858 943697 828346756 961203221 496809192 455687214 808337302 743500598 880967323 591801822 342728080 679707709 308213349 411216885 719826955 282524117 296499305 28024674 711794031 564640210 177781780 828631886 384665610 75396379 171606929 127134588 4808557 286797543 179267912 36257049 560625425 347025165 960121533 570489976 784293003 357892941 4980946 539530225 134800520 800767514 219608855 515395422 375575782 847746347 592614814 48032515 902378559 746942805 752081903 151805882 190894541 23990372 553006794 75979348 305890501 25807792 949848755 788352117 933678655 674162762 529836168 415550097 533668638 403355573 665000462 84132425 969444055 487819402 761883798 609756151 379683179 87549199 413097801 120119059 206404836 859997150 333422319 65746223 116441982 682805863 839288503 175543004 782495880 218409335 756149025 862190455 689085859 86732345 642876328 832233445 786534010 441533768 228304970 642112231 874948645 367612085 145876982 401870230 396894198 516586607 504512570 3600617 386036206 562425058 528685938 410987310 82576997 597169423 361684913 385878360 56999386 210990746 625983631 384516370 788353573 958158051 856244530 613913969 466911778 481015111 218789848 708988478 656351173 744420198 230557170 913873808 674064518 848357522 127206400 138011018 268849169 242398498 215085930 734256012 126024601 676609871 856207838 714897715 114907846 668385875 74460474 547978947 398550472 436304717 390482744 133461579 42097364 598622966 95320173 23363755 758881514 616234668 816185821 583315141 514734635 7146908 932757154 218872581 549100588 996359760 814757240 195474391 761859853 207320940 150829725 964501421 95090174 452729453 489363653 946298187 169756033 157638398 507485014 569343044 835159702 576011528 169487226 983759521 569679597 49155032 441177359 680589848 101946397 794894299 292732112 63587913 348956215 129273951 527593919 311034976 589661640 879911205 21495772 502204114 933828094 262522400 208840845 999811120 839706291 754863383 729241831 678296994 220654865 915807912 968295741 515458827 367490197 244789013 664032469 994943250 629802191 138536477 510303994 703291266 466331380 389950740 855746762 837861781 892696694 158853099 521870075 747144580 922080454 90460205 885225348 215734226 892757052 99548181 216533860 373561985 287848293 659362390 888078613 925910444 36592725 833622839 515758851 41284448 230507958 86759321 22520137 538829090 161984634 540229468 75825966 949224697 484869502 575038379 993632756 79157599 35663883 254952471 756312735 392438955 799245151 403049275 885750690 455214229 375062768 815454637 105465711 888212808 636274884 477171958 51426787 955259833 464276662 216035262 583559987 334894063 9886457 805450383 541426619 868990000 78663559 322268191 407736806 212189268 368439835 99227527 196002796 831621674 168175225 432535526 392448790 964541996 777025795 624495964 77359042 945820862 737280943 500174214 103286919 776477663 1976028 998864697 62731710 991137923 24430485 433793221 55692185 789433429 853686843 576541500 486792042 674913454 261806327 518049072 952056569 314109789 728427800 955513279 428984693 843149078 635726023 916133139 675350889 97592011 625172795 715439424 629468018 964541807 773849272 923765078 486656766 548804965 322799696 750815156 336433926 120568537 244597221 661801392 4454110 772057755 878501514 209920148 886045641 43754972 950415533 650505148 200783962 879248300 691211496 378833228 834808271 38211425 121826328 983195911 760771142 162957759 789413991 526983974 797099193 843155168 738072249 914760677 547286272 567930209 711970378 307270365 668603746 514992901 52856276 370959504 571364890 456587072 899865179 380496262 868124894 571212546 43633515 252931827 81345555 301418376 24730562 108478242 313268270 543670076 993799573 735375675 690589643 664768092 473665533 174742105 206679865 113708839 917761469 515731712 658892695 510107512 622252166 460575328 284740487 380557707 827097589 367548098 144189297 573521950 203072493 687891574 415487400 553661982 350305829 263666559 111359931 94378763 307204834 640974456 5983623 708770578 215331343 563953412 445936256 132734965 714797748 582246124 801385319 939372675 810534611 92700735 21884053 585583537 635227476 53246474 486566349 102908270 854966458 608185932 832549630 731946188 376048058 195354491 894192604 604542125 794369321 59353051 40582528 244506980 218862728 860140815 600516327 778525619 62225765 3904669 127529052 192114064 119427190 389322611 551044542 382406513 761458746 982108355 735828449 784177900 570832064 91315078 355466971 33884046 406003070 64317550 800805215 853249562 743352498 539325866 995114505 286851102 5692202 105825125 486432965 8615432 918178081 1536831 59731659 941713749 428517859 513262805 368564331 44139748 974903227 972068209 568552513 433615471 289473405 55332363 110614193 445653675 752113619 684856694 947858364 621847108