100 4000000 0 0 1000000000 1000000000 52515 15153865 411236277 648089981 726429026 214687 320560555 477873222 513480525 772244402 380953 507736121 156169023 670515700 568439309 199439 119080256 513077551 165345002 902587975 35531 746505722 796671968 808655513 922187074 205710 314312700 557109718 480796400 991244120 269993 424955872 773018284 708224395 850197622 213417 845306229 102960830 890673476 588074735 317169 529108788 794596268 726142423 919116039 377796 175359281 59297185 471950432 915855277 325684 343999088 566677486 567556406 945622508 15951 77544970 361711024 543954290 401849945 438994 716301612 114790772 780329889 880846381 168577 384791678 913449607 840294765 981635877 431025 60539081 104777644 459048048 720552529 255362 684868581 498623971 874185415 866871526 159428 5998865 38659485 648393318 214453941 305300 431410815 238137794 546755559 816758627 352591 212287111 214836433 376688085 732115488 402018 167181046 799137397 887129477 903213040 486235 57269649 251295465 215525185 674338646 396682 209301961 159827935 873527988 979662002 124644 30391932 751024275 818491331 843559978 91438 254458056 36589208 567474392 360208595 433851 146675791 454766544 159983913 993078326 3792 656929762 560208976 694540004 598059285 429967 439994564 52946440 904266183 995419105 65801 319255639 108046823 612376045 108353044 451816 352637094 588807582 494900517 864239978 368492 510061220 45227185 818206107 637184295 465317 79432432 79034769 443806842 643866041 451931 222193706 14756896 653002362 728533188 14861 704720273 390694821 800730513 861298300 330862 577988750 743094866 991691777 981364447 330348 10699072 578143596 855184791 775711545 393876 72768272 699238609 126314904 891130939 216174 410610124 22397053 729087351 52374834 13732 508085554 98535259 780516194 998908800 180140 814645049 176583850 946705899 579687064 349990 373102007 253583666 974110545 866160988 49144 49762495 406393454 871624464 425605099 337577 458220412 434089536 740865887 622760697 205842 61584396 238668015 809900044 754804297 354088 11733184 217101927 50349414 907022759 67301 319136535 106572118 822130494 637411054 208822 119722181 723982215 176637913 771497407 142057 86970760 71430377 737510981 428666553 99165 17329234 190766373 806898912 342126686 467162 271056481 3397730 469647189 626439458 127944 98528226 487787864 834144586 839976508 153157 209823813 151290394 279704469 340659911 497104 422773116 317351268 520848968 558238582 272510 21394286 205159052 434883800 736974331 428461 130556417 667110434 404884591 680880125 421830 41655832 325580830 169122774 822878081 203881 37778706 644178608 191199306 877526194 21803 398856907 291556855 998393520 710139822 358110 2282102 192881664 78429337 286556631 455575 149201102 155000197 208311108 479426124 130362 26359649 83479778 737790549 475162459 232061 100438737 151689411 576231796 369525981 324882 22506907 109442655 949679331 955030191 121038 35382494 797945545 165897051 968073279 469060 50097590 176588700 103863940 884501409 355108 198728733 228941347 820585229 696727640 2184 164072181 822013869 992288156 985121898 278326 2372602 221599361 42366891 243233073 295008 25174269 635634587 172338463 684574678 211099 227861954 712501471 643390619 885954082 114717 276527767 447551055 453444490 769547067 332785 60679728 375430134 555428321 765356117 285831 227971427 197925919 881730009 599080156 323335 85703020 52404416 683346342 242108582 393450 321666894 757390210 505132401 832126537 176674 591371530 518301939 923076527 626969588 495120 335689414 285419007 695525345 733961372 261830 38579813 18322536 295191348 593744460 98452 844947987 322579906 964578845 524438477 238308 113346684 109882895 436224137 785697062 54210 132318926 238597830 780758711 879551185 238440 55411223 330299333 278309615 874496127 145430 194957247 350176446 420965153 379383586 313721 167147034 73687882 665378774 331573356 313521 28026130 580683538 554582420 736231411 33857 500201694 638859893 692965230 862786123 267911 275951613 493572294 453891980 501549011 195476 114573040 39542971 460951989 922225885 256991 367958086 49422928 772706792 666114882 48542 796055917 488659403 921103287 920800226 216679 114871490 57316971 414322264 372290667 140935 829553815 254330281 981117022 640110959 295022 534258793 311682864 838733942 451384422 234282 321406366 1450463 335604244 748399735 101841 241965088 122241122 755589520 520673438 165854 42654619 222617398 407073690 597587067 284891 410138686 169336169 899673274 571367311 493434 232457257 636347700 375188567 782241171 215034 205156411 281240952 753320155 352529435 310551 597916006 98311722 703165689 296204160 201953