1 1 2 6 3 21 4 44 5 85 6 138 7 217 8 312 9 441 10 590 11 781 12 996 13 1261 14 1554 15 1905 16 2288 17 2737 18 3222 19 3781 20 4380 21 5061 22 5786 23 6601 24 7464 25 8425 26 9438 27 10557 28 11732 29 13021 30 14370 31 15841 32 17376 33 19041 34 20774 35 22645 36 24588 37 26677 38 28842 39 31161 40 33560 41 36121 42 38766 43 41581 44 44484 45 47565 46 50738 47 54097 48 57552 49 61201 50 64950 51 68901 52 72956 53 77221 54 81594 55 86185 56 90888 57 95817 58 100862 59 106141 60 111540 61 117181 62 122946 63 128961 64 135104 65 141505 66 148038 67 154837 68 161772 69 168981 70 176330 71 183961 72 191736 73 199801 74 208014 75 216525 76 225188 77 234157 78 243282 79 252721 80 262320 81 272241 82 282326 83 292741 84 303324 85 314245 86 325338 87 336777 88 348392 89 360361 90 372510 91 385021 92 397716 93 410781 94 424034 95 437665 96 451488 97 465697 98 480102 99 494901 100 509900 101 525301 102 540906 103 556921 104 573144 105 589785 106 606638 107 623917 108 641412 109 659341 110 677490 111 696081 112 714896 113 734161 114 753654 115 773605 116 793788 117 814437 118 835322 119 856681 120 878280 121 900361 122 922686 123 945501 124 968564 125 992125 126 1015938 127 1040257 128 1064832 129 1089921 130 1115270 131 1141141 132 1167276 133 1193941 134 1220874 135 1248345 136 1276088 137 1304377 138 1332942 139 1362061 140 1391460 141 1421421 142 1451666 143 1482481 144 1513584 145 1545265 146 1577238 147 1609797 148 1642652 149 1676101 150 1709850 151 1744201 152 1778856 153 1814121 154 1849694 155 1885885 156 1922388 157 1959517 158 1996962 159 2035041 160 2073440 161 2112481 162 2151846 163 2191861 164 2232204 165 2273205 166 2314538 167 2356537 168 2398872 169 2441881 170 2485230 171 2529261 172 2573636 173 2618701 174 2664114 175 2710225 176 2756688 177 2803857 178 2851382 179 2899621 180 2948220 181 2997541 182 3047226 183 3097641 184 3148424 185 3199945 186 3251838 187 3304477 188 3357492 189 3411261 190 3465410 191 3520321 192 3575616 193 3631681 194 3688134 195 3745365 196 3802988 197 3861397 198 3920202 199 3979801 200 4039800 201 4100601 202 4161806 203 4223821 204 4286244 205 4349485 206 4413138 207 4477617 208 4542512 209 4608241 210 4674390 211 4741381 212 4808796 213 4877061 214 4945754 215 5015305 216 5085288 217 5156137 218 5227422 219 5299581 220 5372180 221 5445661 222 5519586 223 5594401 224 5669664 225 5745825 226 5822438 227 5899957 228 5977932 229 6056821 230 6136170 231 6216441 232 6297176 233 6378841 234 6460974 235 6544045 236 6627588 237 6712077 238 6797042 239 6882961 240 6969360 241 7056721 242 7144566 243 7233381 244 7322684 245 7412965 246 7503738 247 7595497 248 7687752 249 7781001 250 7874750 251 7969501 252 8064756 253 8161021 254 8257794 255 8355585 256 8453888 257 8553217 258 8653062 259 8753941 260 8855340 261 8957781 262 9060746 263 9164761 264 9269304 265 9374905 266 9481038 267 9588237 268 9695972 269 9804781 270 9914130 271 10024561 272 10135536 273 10247601 274 10360214 275 10473925 276 10588188 277 10703557 278 10819482 279 10936521 280 11054120 281 11172841 282 11292126 283 11412541 284 11533524 285 11655645 286 11778338 287 11902177 288 12026592 289 12152161 290 12278310 291 12405621 292 12533516 293 12662581 294 12792234 295 12923065 296 13054488 297 13187097 298 13320302 299 13454701 300 13589700 301 13725901 302 13862706 303 14000721 304 14139344 305 14279185 306 14419638 307 14561317 308 14703612 309 14847141 310 14991290 311 15136681 312 15282696 313 15429961 314 15577854 315 15727005 316 15876788 317 16027837 318 16179522 319 16332481 320 16486080 321 16640961 322 16796486 323 16953301 324 17110764 325 17269525 326 17428938 327 17589657 328 17751032 329 17913721 330 18077070 331 18241741 332 18407076 333 18573741 334 18741074 335 18909745 336 19079088 337 19249777 338 19421142 339 19593861 340 19767260 341 19942021 342 20117466 343 20294281 344 20471784 345 20650665 346 20830238 347 21011197 348 21192852 349 21375901 350 21559650 351 21744801 352 21930656 353 22117921 354 22305894 355 22495285 356 22685388 357 22876917 358 23069162 359 23262841 360 23457240 361 23653081 362 23849646 363 24047661 364 24246404 365 24446605 366 24647538 367 24849937 368 25053072 369 25257681 370 25463030 371 25669861 372 25877436 373 26086501 374 26296314 375 26507625 376 26719688 377 26933257 378 27147582 379 27363421 380 27580020 381 27798141 382 28017026 383 28237441 384 28458624 385 28681345 386 28904838 387 29129877 388 29355692 389 29583061 390 29811210 391 30040921 392 30271416 393 30503481 394 30736334 395 30970765 396 31205988 397 31442797 398 31680402 399 31919601 400 32159600 401 32401201 402 32643606 403 32887621 404 33132444 405 33378885 406 33626138 407 33875017 408 34124712 409 34376041 410 34628190 411 34881981 412 35136596 413 35392861 414 35649954 415 35908705 416 36168288 417 36429537 418 36691622 419 36955381 420 37219980 421 37486261 422 37753386 423 38022201 424 38291864 425 38563225 426 38835438 427 39109357 428 39384132 429 39660621 430 39937970 431 40217041 432 40496976 433 40778641 434 41061174 435 41345445 436 41630588 437 41917477 438 42205242 439 42494761 440 42785160 441 43077321 442 43370366 443 43665181 444 43960884 445 44258365 446 44556738 447 44856897 448 45157952 449 45460801 450 45764550 451 46070101 452 46376556 453 46684821 454 46993994 455 47304985 456 47616888 457 47930617 458 48245262 459 48561741 460 48879140 461 49198381 462 49518546 463 49840561 464 50163504 465 50488305 466 50814038 467 51141637 468 51470172 469 51800581 470 52131930 471 52465161 472 52799336 473 53135401 474 53472414 475 53811325 476 54151188 477 54492957 478 54835682 479 55180321 480 55525920 481 55873441 482 56221926 483 56572341 484 56923724 485 57277045 486 57631338 487 57987577 488 58344792 489 58703961 490 59064110 491 59426221 492 59789316 493 60154381 494 60520434 495 60888465 496 61257488 497 61628497 498 62000502 499 62374501 500 62749500 501 63126501 502 63504506 503 63884521 504 64265544 505 64648585 506 65032638 507 65418717 508 65805812 509 66194941 510 66585090 511 66977281 512 67370496 513 67765761 514 68162054 515 68560405 516 68959788 517 69361237 518 69763722 519 70168281 520 70573880 521 70981561 522 71390286 523 71801101 524 72212964 525 72626925 526 73041938 527 73459057 528 73877232 529 74297521 530 74718870 531 75142341 532 75566876 533 75993541 534 76421274 535 76851145 536 77282088 537 77715177 538 78149342 539 78585661 540 79023060 541 79462621 542 79903266 543 80346081 544 80789984 545 81236065 546 81683238 547 82132597 548 82583052 549 83035701 550 83489450 551 83945401 552 84402456 553 84861721 554 85322094 555 85784685 556 86248388 557 86714317 558 87181362 559 87650641 560 88121040 561 88593681 562 89067446 563 89543461 564 90020604 565 90500005 566 90980538 567 91463337 568 91947272 569 92433481 570 92920830 571 93410461 572 93901236 573 94394301 574 94888514 575 95385025 576 95882688 577 96382657 578 96883782 579 97387221 580 97891820 581 98398741 582 98906826 583 99417241 584 99928824 585 100442745 586 100957838 587 101475277 588 101993892 589 102514861 590 103037010 591 103561521 592 104087216 593 104615281 594 105144534 595 105676165 596 106208988 597 106744197 598 107280602 599 107819401 600 108359400 601 108901801 602 109445406 603 109991421 604 110538644 605 111088285 606 111639138 607 112192417 608 112746912 609 113303841 610 113861990 611 114422581 612 114984396 613 115548661 614 116114154 615 116682105 616 117251288 617 117822937 618 118395822 619 118971181 620 119547780 621 120126861 622 120707186 623 121290001 624 121874064 625 122460625 626 123048438 627 123638757 628 124230332 629 124824421 630 125419770 631 126017641 632 126616776 633 127218441 634 127821374 635 128426845 636 129033588 637 129642877 638 130253442 639 130866561 640 131480960 641 132097921 642 132716166 643 133336981 644 133959084 645 134583765 646 135209738 647 135838297 648 136468152 649 137100601 650 137734350 651 138370701 652 139008356 653 139648621 654 140290194 655 140934385 656 141579888 657 142228017 658 142877462 659 143529541 660 144182940 661 144838981 662 145496346 663 146156361 664 146817704 665 147481705 666 148147038 667 148815037 668 149484372 669 150156381 670 150829730 671 151505761 672 152183136 673 152863201 674 153544614 675 154228725 676 154914188 677 155602357 678 156291882 679 156984121 680 157677720 681 158374041 682 159071726 683 159772141 684 160473924 685 161178445 686 161884338 687 162592977 688 163302992 689 164015761 690 164729910 691 165446821 692 166165116 693 166886181 694 167608634 695 168333865 696 169060488 697 169789897 698 170520702 699 171254301 700 171989300 701 172727101 702 173466306 703 174208321 704 174951744 705 175697985 706 176445638 707 177196117 708 177948012 709 178702741 710 179458890 711 180217881 712 180978296 713 181741561 714 182506254 715 183273805 716 184042788 717 184814637 718 185587922 719 186364081 720 187141680 721 187922161 722 188704086 723 189488901 724 190275164 725 191064325 726 191854938 727 192648457 728 193443432 729 194241321 730 195040670 731 195842941 732 196646676 733 197453341 734 198261474 735 199072545 736 199885088 737 200700577 738 201517542 739 202337461 740 203158860 741 203983221 742 204809066 743 205637881 744 206468184 745 207301465 746 208136238 747 208973997 748 209813252 749 210655501 750 211499250 751 212346001 752 213194256 753 214045521 754 214898294 755 215754085 756 216611388 757 217471717 758 218333562 759 219198441 760 220064840 761 220934281 762 221805246 763 222679261 764 223554804 765 224433405 766 225313538 767 226196737 768 227081472 769 227969281 770 228858630 771 229751061 772 230645036 773 231542101 774 232440714 775 233342425 776 234245688 777 235152057 778 236059982 779 236971021 780 237883620 781 238799341 782 239716626 783 240637041 784 241559024 785 242484145 786 243410838 787 244340677 788 245272092 789 246206661 790 247142810 791 248082121 792 249023016 793 249967081 794 250912734 795 251861565 796 252811988 797 253765597 798 254720802 799 255679201 800 256639200 801 257602401 802 258567206 803 259535221 804 260504844 805 261477685 806 262452138 807 263429817 808 264409112 809 265391641 810 266375790 811 267363181 812 268352196 813 269344461 814 270338354 815 271335505 816 272334288 817 273336337 818 274340022 819 275346981 820 276355580 821 277367461 822 278380986 823 279397801 824 280416264 825 281438025 826 282461438 827 283488157 828 284516532 829 285548221 830 286581570 831 287618241 832 288656576 833 289698241 834 290741574 835 291788245 836 292836588 837 293888277 838 294941642 839 295998361 840 297056760 841 298118521 842 299181966 843 300248781 844 301317284 845 302389165 846 303462738 847 304539697 848 305618352 849 306700401 850 307784150 851 308871301 852 309960156 853 311052421 854 312146394 855 313243785 856 314342888 857 315445417 858 316549662 859 317657341 860 318766740 861 319879581 862 320994146 863 322112161 864 323231904 865 324355105 866 325480038 867 326608437 868 327738572 869 328872181 870 330007530 871 331146361 872 332286936 873 333431001 874 334576814 875 335726125 876 336877188 877 338031757 878 339188082 879 340347921 880 341509520 881 342674641 882 343841526 883 345011941 884 346184124 885 347359845 886 348537338 887 349718377 888 350901192 889 352087561 890 353275710 891 354467421 892 355660916 893 356857981 894 358056834 895 359259265 896 360463488 897 361671297 898 362880902 899 364094101 900 365309100 901 366527701 902 367748106 903 368972121 904 370197944 905 371427385 906 372658638 907 373893517 908 375130212 909 376370541 910 377612690 911 378858481 912 380106096 913 381357361 914 382610454 915 383867205 916 385125788 917 386388037 918 387652122 919 388919881 920 390189480 921 391462761 922 392737886 923 394016701 924 395297364 925 396581725 926 397867938 927 399157857 928 400449632 929 401745121 930 403042470 931 404343541 932 405646476 933 406953141 934 408261674 935 409573945 936 410888088 937 412205977 938 413525742 939 414849261 940 416174660 941 417503821 942 418834866 943 420169681 944 421506384 945 422846865 946 424189238 947 425535397 948 426883452 949 428235301 950 429589050 951 430946601 952 432306056 953 433669321 954 435034494 955 436403485 956 437774388 957 439149117 958 440525762 959 441906241 960 443288640 961 444674881 962 446063046 963 447455061 964 448849004 965 450246805 966 451646538 967 453050137 968 454455672 969 455865081 970 457276430 971 458691661 972 460108836 973 461529901 974 462952914 975 464379825 976 465808688 977 467241457 978 468676182 979 470114821 980 471555420 981 472999941 982 474446426 983 475896841 984 477349224 985 478805545 986 480263838 987 481726077 988 483190292 989 484658461 990 486128610 991 487602721 992 489078816 993 490558881 994 492040934 995 493526965 996 495014988 997 496506997 998 498001002 999 499499001 1000 500999000