0 5 1 6 2 13 3 32 4 69 5 130 6 221 7 348 8 517 9 734 10 1005 11 1336 12 1733 13 2202 14 2749 15 3380 16 4101 17 4918 18 5837 19 6864 20 8005 21 9266 22 10653 23 12172 24 13829 25 15630 26 17581 27 19688 28 21957 29 24394 30 27005 31 29796 32 32773 33 35942 34 39309 35 42880 36 46661 37 50658 38 54877 39 59324 40 64005 41 68926 42 74093 43 79512 44 85189 45 91130 46 97341 47 103828 48 110597 49 117654 50 125005 51 132656 52 140613 53 148882 54 157469 55 166380 56 175621 57 185198 58 195117 59 205384 60 216005 61 226986 62 238333 63 250052 64 262149 65 274630 66 287501 67 300768 68 314437 69 328514 70 343005 71 357916 72 373253 73 389022 74 405229 75 421880 76 438981 77 456538 78 474557 79 493044 80 512005 81 531446 82 551373 83 571792 84 592709 85 614130 86 636061 87 658508 88 681477 89 704974 90 729005 91 753576 92 778693 93 804362 94 830589 95 857380 96 884741 97 912678 98 941197 99 970304 100 1000005 101 1030306 102 1061213 103 1092732 104 1124869 105 1157630 106 1191021 107 1225048 108 1259717 109 1295034 110 1331005 111 1367636 112 1404933 113 1442902 114 1481549 115 1520880 116 1560901 117 1601618 118 1643037 119 1685164 120 1728005 121 1771566 122 1815853 123 1860872 124 1906629 125 1953130 126 2000381 127 2048388 128 2097157 129 2146694 130 2197005 131 2248096 132 2299973 133 2352642 134 2406109 135 2460380 136 2515461 137 2571358 138 2628077 139 2685624 140 2744005 141 2803226 142 2863293 143 2924212 144 2985989 145 3048630 146 3112141 147 3176528 148 3241797 149 3307954 150 3375005 151 3442956 152 3511813 153 3581582 154 3652269 155 3723880 156 3796421 157 3869898 158 3944317 159 4019684 160 4096005 161 4173286 162 4251533 163 4330752 164 4410949 165 4492130 166 4574301 167 4657468 168 4741637 169 4826814 170 4913005 171 5000216 172 5088453 173 5177722 174 5268029 175 5359380 176 5451781 177 5545238 178 5639757 179 5735344 180 5832005 181 5929746 182 6028573 183 6128492 184 6229509 185 6331630 186 6434861 187 6539208 188 6644677 189 6751274 190 6859005 191 6967876 192 7077893 193 7189062 194 7301389 195 7414880 196 7529541 197 7645378 198 7762397 199 7880604 200 8000005 201 8120606 202 8242413 203 8365432 204 8489669 205 8615130 206 8741821 207 8869748 208 8998917 209 9129334 210 9261005 211 9393936 212 9528133 213 9663602 214 9800349 215 9938380 216 10077701 217 10218318 218 10360237 219 10503464 220 10648005 221 10793866 222 10941053 223 11089572 224 11239429 225 11390630 226 11543181 227 11697088 228 11852357 229 12008994 230 12167005 231 12326396 232 12487173 233 12649342 234 12812909 235 12977880 236 13144261 237 13312058 238 13481277 239 13651924 240 13824005 241 13997526 242 14172493 243 14348912 244 14526789 245 14706130 246 14886941 247 15069228 248 15252997 249 15438254 250 15625005 251 15813256 252 16003013 253 16194282 254 16387069 255 16581380 256 16777221 257 16974598 258 17173517 259 17373984 260 17576005 261 17779586 262 17984733 263 18191452 264 18399749 265 18609630 266 18821101 267 19034168 268 19248837 269 19465114 270 19683005 271 19902516 272 20123653 273 20346422 274 20570829 275 20796880 276 21024581 277 21253938 278 21484957 279 21717644 280 21952005 281 22188046 282 22425773 283 22665192 284 22906309 285 23149130 286 23393661 287 23639908 288 23887877 289 24137574 290 24389005 291 24642176 292 24897093 293 25153762 294 25412189 295 25672380 296 25934341 297 26198078 298 26463597 299 26730904 300 27000005 301 27270906 302 27543613 303 27818132 304 28094469 305 28372630 306 28652621 307 28934448 308 29218117 309 29503634 310 29791005 311 30080236 312 30371333 313 30664302 314 30959149 315 31255880 316 31554501 317 31855018 318 32157437 319 32461764 320 32768005 321 33076166 322 33386253 323 33698272 324 34012229 325 34328130 326 34645981 327 34965788 328 35287557 329 35611294 330 35937005 331 36264696 332 36594373 333 36926042 334 37259709 335 37595380 336 37933061 337 38272758 338 38614477 339 38958224 340 39304005 341 39651826 342 40001693 343 40353612 344 40707589 345 41063630 346 41421741 347 41781928 348 42144197 349 42508554 350 42875005 351 43243556 352 43614213 353 43986982 354 44361869 355 44738880 356 45118021 357 45499298 358 45882717 359 46268284 360 46656005 361 47045886 362 47437933 363 47832152 364 48228549 365 48627130 366 49027901 367 49430868 368 49836037 369 50243414 370 50653005 371 51064816 372 51478853 373 51895122 374 52313629 375 52734380 376 53157381 377 53582638 378 54010157 379 54439944 380 54872005 381 55306346 382 55742973 383 56181892 384 56623109 385 57066630 386 57512461 387 57960608 388 58411077 389 58863874 390 59319005 391 59776476 392 60236293 393 60698462 394 61162989 395 61629880 396 62099141 397 62570778 398 63044797 399 63521204 400 64000005 401 64481206 402 64964813 403 65450832 404 65939269 405 66430130 406 66923421 407 67419148 408 67917317 409 68417934 410 68921005 411 69426536 412 69934533 413 70445002 414 70957949 415 71473380 416 71991301 417 72511718 418 73034637 419 73560064 420 74088005 421 74618466 422 75151453 423 75686972 424 76225029 425 76765630 426 77308781 427 77854488 428 78402757 429 78953594 430 79507005 431 80062996 432 80621573 433 81182742 434 81746509 435 82312880 436 82881861 437 83453458 438 84027677 439 84604524 440 85184005 441 85766126 442 86350893 443 86938312 444 87528389 445 88121130 446 88716541 447 89314628 448 89915397 449 90518854 450 91125005 451 91733856 452 92345413 453 92959682 454 93576669 455 94196380 456 94818821 457 95443998 458 96071917 459 96702584 460 97336005 461 97972186 462 98611133 463 99252852 464 99897349 465 100544630 466 101194701 467 101847568 468 102503237 469 103161714 470 103823005 471 104487116 472 105154053 473 105823822 474 106496429 475 107171880 476 107850181 477 108531338 478 109215357 479 109902244 480 110592005 481 111284646 482 111980173 483 112678592 484 113379909 485 114084130 486 114791261 487 115501308 488 116214277 489 116930174 490 117649005 491 118370776 492 119095493 493 119823162 494 120553789 495 121287380 496 122023941 497 122763478 498 123505997 499 124251504 500 125000005 501 125751506 502 126506013 503 127263532 504 128024069 505 128787630 506 129554221 507 130323848 508 131096517 509 131872234 510 132651005 511 133432836 512 134217733 513 135005702 514 135796749 515 136590880 516 137388101 517 138188418 518 138991837 519 139798364 520 140608005 521 141420766 522 142236653 523 143055672 524 143877829 525 144703130 526 145531581 527 146363188 528 147197957 529 148035894 530 148877005 531 149721296 532 150568773 533 151419442 534 152273309 535 153130380 536 153990661 537 154854158 538 155720877 539 156590824 540 157464005 541 158340426 542 159220093 543 160103012 544 160989189 545 161878630 546 162771341 547 163667328 548 164566597 549 165469154 550 166375005 551 167284156 552 168196613 553 169112382 554 170031469 555 170953880 556 171879621 557 172808698 558 173741117 559 174676884 560 175616005 561 176558486 562 177504333 563 178453552 564 179406149 565 180362130 566 181321501 567 182284268 568 183250437 569 184220014 570 185193005 571 186169416 572 187149253 573 188132522 574 189119229 575 190109380 576 191102981 577 192100038 578 193100557 579 194104544 580 195112005 581 196122946 582 197137373 583 198155292 584 199176709 585 200201630 586 201230061 587 202262008 588 203297477 589 204336474 590 205379005 591 206425076 592 207474693 593 208527862 594 209584589 595 210644880 596 211708741 597 212776178 598 213847197 599 214921804 600 216000005 601 217081806 602 218167213 603 219256232 604 220348869 605 221445130 606 222545021 607 223648548 608 224755717 609 225866534 610 226981005 611 228099136 612 229220933 613 230346402 614 231475549 615 232608380 616 233744901 617 234885118 618 236029037 619 237176664 620 238328005 621 239483066 622 240641853 623 241804372 624 242970629 625 244140630 626 245314381 627 246491888 628 247673157 629 248858194 630 250047005 631 251239596 632 252435973 633 253636142 634 254840109 635 256047880 636 257259461 637 258474858 638 259694077 639 260917124 640 262144005 641 263374726 642 264609293 643 265847712 644 267089989 645 268336130 646 269586141 647 270840028 648 272097797 649 273359454 650 274625005 651 275894456 652 277167813 653 278445082 654 279726269 655 281011380 656 282300421 657 283593398 658 284890317 659 286191184 660 287496005 661 288804786 662 290117533 663 291434252 664 292754949 665 294079630 666 295408301 667 296740968 668 298077637 669 299418314 670 300763005 671 302111716 672 303464453 673 304821222 674 306182029 675 307546880 676 308915781 677 310288738 678 311665757 679 313046844 680 314432005 681 315821246 682 317214573 683 318611992 684 320013509 685 321419130 686 322828861 687 324242708 688 325660677 689 327082774 690 328509005 691 329939376 692 331373893 693 332812562 694 334255389 695 335702380 696 337153541 697 338608878 698 340068397 699 341532104 700 343000005 701 344472106 702 345948413 703 347428932 704 348913669 705 350402630 706 351895821 707 353393248 708 354894917 709 356400834 710 357911005 711 359425436 712 360944133 713 362467102 714 363994349 715 365525880 716 367061701 717 368601818 718 370146237 719 371694964 720 373248005 721 374805366 722 376367053 723 377933072 724 379503429 725 381078130 726 382657181 727 384240588 728 385828357 729 387420494 730 389017005 731 390617896 732 392223173 733 393832842 734 395446909 735 397065380 736 398688261 737 400315558 738 401947277 739 403583424 740 405224005 741 406869026 742 408518493 743 410172412 744 411830789 745 413493630 746 415160941 747 416832728 748 418508997 749 420189754 750 421875005 751 423564756 752 425259013 753 426957782 754 428661069 755 430368880 756 432081221 757 433798098 758 435519517 759 437245484 760 438976005 761 440711086 762 442450733 763 444194952 764 445943749 765 447697130 766 449455101 767 451217668 768 452984837 769 454756614 770 456533005 771 458314016 772 460099653 773 461889922 774 463684829 775 465484380 776 467288581 777 469097438 778 470910957 779 472729144 780 474552005 781 476379546 782 478211773 783 480048692 784 481890309 785 483736630 786 485587661 787 487443408 788 489303877 789 491169074 790 493039005 791 494913676 792 496793093 793 498677262 794 500566189 795 502459880 796 504358341 797 506261578 798 508169597 799 510082404 800 512000005 801 513922406 802 515849613 803 517781632 804 519718469 805 521660130 806 523606621 807 525557948 808 527514117 809 529475134 810 531441005 811 533411736 812 535387333 813 537367802 814 539353149 815 541343380 816 543338501 817 545338518 818 547343437 819 549353264 820 551368005 821 553387666 822 555412253 823 557441772 824 559476229 825 561515630 826 563559981 827 565609288 828 567663557 829 569722794 830 571787005 831 573856196 832 575930373 833 578009542 834 580093709 835 582182880 836 584277061 837 586376258 838 588480477 839 590589724 840 592704005 841 594823326 842 596947693 843 599077112 844 601211589 845 603351130 846 605495741 847 607645428 848 609800197 849 611960054 850 614125005 851 616295056 852 618470213 853 620650482 854 622835869 855 625026380 856 627222021 857 629422798 858 631628717 859 633839784 860 636056005 861 638277386 862 640503933 863 642735652 864 644972549 865 647214630 866 649461901 867 651714368 868 653972037 869 656234914 870 658503005 871 660776316 872 663054853 873 665338622 874 667627629 875 669921880 876 672221381 877 674526138 878 676836157 879 679151444 880 681472005 881 683797846 882 686128973 883 688465392 884 690807109 885 693154130 886 695506461 887 697864108 888 700227077 889 702595374 890 704969005 891 707347976 892 709732293 893 712121962 894 714516989 895 716917380 896 719323141 897 721734278 898 724150797 899 726572704 900 729000005 901 731432706 902 733870813 903 736314332 904 738763269 905 741217630 906 743677421 907 746142648 908 748613317 909 751089434 910 753571005 911 756058036 912 758550533 913 761048502 914 763551949 915 766060880 916 768575301 917 771095218 918 773620637 919 776151564 920 778688005 921 781229966 922 783777453 923 786330472 924 788889029 925 791453130 926 794022781 927 796597988 928 799178757 929 801765094 930 804357005 931 806954496 932 809557573 933 812166242 934 814780509 935 817400380 936 820025861 937 822656958 938 825293677 939 827936024 940 830584005 941 833237626 942 835896893 943 838561812 944 841232389 945 843908630 946 846590541 947 849278128 948 851971397 949 854670354 950 857375005 951 860085356 952 862801413 953 865523182 954 868250669 955 870983880 956 873722821 957 876467498 958 879217917 959 881974084 960 884736005 961 887503686 962 890277133 963 893056352 964 895841349 965 898632130 966 901428701 967 904231068 968 907039237 969 909853214 970 912673005 971 915498616 972 918330053 973 921167322 974 924010429 975 926859380 976 929714181 977 932574838 978 935441357 979 938313744 980 941192005 981 944076146 982 946966173 983 949862092 984 952763909 985 955671630 986 958585261 987 961504808 988 964430277 989 967361674 990 970299005 991 973242276 992 976191493 993 979146662 994 982107789 995 985074880 996 988047941 997 991026978 998 994011997 999 997003004 1000 1000000005