1 1 2 2 3 3 4 5 5 7 6 10 7 13 8 18 9 23 10 30 11 37 12 47 13 57 14 70 15 83 16 101 17 119 18 142 19 165 20 195 21 225 22 262 23 299 24 346 25 393 26 450 27 507 28 577 29 647 30 730 31 813 32 914 33 1015 34 1134 35 1253 36 1395 37 1537 38 1702 39 1867 40 2062 41 2257 42 2482 43 2707 44 2969 45 3231 46 3530 47 3829 48 4175 49 4521 50 4914 51 5307 52 5757 53 6207 54 6714 55 7221 56 7798 57 8375 58 9022 59 9669 60 10399 61 11129 62 11942 63 12755 64 13669 65 14583 66 15598 67 16613 68 17747 69 18881 70 20134 71 21387 72 22782 73 24177 74 25714 75 27251 76 28953 77 30655 78 32522 79 34389 80 36451 81 38513 82 40770 83 43027 84 45509 85 47991 86 50698 87 53405 88 56374 89 59343 90 62574 91 65805 92 69335 93 72865 94 76694 95 80523 96 84698 97 88873 98 93394 99 97915 100 102829 101 107743 102 113050 103 118357 104 124114 105 129871 106 136078 107 142285 108 148999 109 155713 110 162934 111 170155 112 177953 113 185751 114 194126 115 202501 116 211523 117 220545 118 230214 119 239883 120 250282 121 260681 122 271810 123 282939 124 294881 125 306823 126 319578 127 332333 128 346002 129 359671 130 374254 131 388837 132 404435 133 420033 134 436646 135 453259 136 471006 137 488753 138 507634 139 526515 140 546649 141 566783 142 588170 143 609557 144 632339 145 655121 146 679298 147 703475 148 729189 149 754903 150 782154 151 809405 152 838358 153 867311 154 897966 155 928621 156 961143 157 993665 158 1028054 159 1062443 160 1098894 161 1135345 162 1173858 163 1212371 164 1253141 165 1293911 166 1336938 167 1379965 168 1425474 169 1470983 170 1518974 171 1566965 172 1617663 173 1668361 174 1721766 175 1775171 176 1831545 177 1887919 178 1947262 179 2006605 180 2069179 181 2131753 182 2197558 183 2263363 184 2332698 185 2402033 186 2474898 187 2547763 188 2624457 189 2701151 190 2781674 191 2862197 192 2946895 193 3031593 194 3120466 195 3209339 196 3302733 197 3396127 198 3494042 199 3591957 200 3694786 201 3797615 202 3905358 203 4013101 204 4126151 205 4239201 206 4357558 207 4475915 208 4600029 209 4724143 210 4854014 211 4983885 212 5119963 213 5256041 214 5398326 215 5540611 216 5689610 217 5838609 218 5994322 219 6150035 220 6312969 221 6475903 222 6646058 223 6816213 224 6994166 225 7172119 226 7357870 227 7543621 228 7737747 229 7931873 230 8134374 231 8336875 232 8548398 233 8759921 234 8980466 235 9201011 236 9431225 237 9661439 238 9901322 239 10141205 240 10391487 241 10641769 242 10902450 243 11163131 244 11434941 245 11706751 246 11989690 247 12272629 248 12567510 249 12862391 250 13169214 251 13476037 252 13795615 253 14115193 254 14447526 255 14779859 256 15125861 257 15471863 258 15831534 259 16191205 260 16565459 261 16939713 262 17328550 263 17717387 264 18121822 265 18526257 266 18946290 267 19366323 268 19802969 269 20239615 270 20692874 271 21146133 272 21617139 273 22088145 274 22576898 275 23065651 276 23573285 277 24080919 278 24607434 279 25133949 280 25680598 281 26227247 282 26794030 283 27360813 284 27948983 285 28537153 286 29146710 287 29756267 288 30388606 289 31020945 290 31676066 291 32331187 292 33010485 293 33689783 294 34393258 295 35096733 296 35825922 297 36555111 298 37310014 299 38064917 300 38847071 301 39629225 302 40438630 303 41248035 304 42086393 305 42924751 306 43792062 307 44659373 308 45557339 309 46455305 310 47383926 311 48312547 312 49273690 313 50234833 314 51228498 315 52222163 316 53250217 317 54278271 318 55340714 319 56403157 320 57502051 321 58600945 322 59736290 323 60871635 324 62045493 325 63219351 326 64431722 327 65644093 328 66897234 329 68150375 330 69444286 331 70738197 332 72075135 333 73412073 334 74792038 335 76172003 336 77597477 337 79022951 338 80493934 339 81964917 340 83483891 341 85002865 342 86569830 343 88136795 344 89754458 345 91372121 346 93040482 347 94708843 348 96430609 349 98152375 350 99927546 351 101702717 352 103534262 353 105365807 354 107253726 355 109141645 356 111088907 357 113036169 358 115042774 359 117049379 360 119118558 361 121187737 362 123319490 363 125451243 364 127648801 365 129846359 366 132109722 367 134373085 368 136705783 369 139038481 370 141440514 371 143842547 372 146317445 373 148792343 374 151340106 375 153887869 376 156512326 377 159136783 378 161837934 379 164539085 380 167320759 381 170102433 382 172964630 383 175826827 384 178773722 385 181720617 386 184752210 387 187783803 388 190904269 389 194024735 390 197234074 391 200443413 392 203746146 393 207048879 394 210445006 395 213841133 396 217335175 397 220829217 398 224421174 399 228013131 400 231707917 401 235402703 402 239200318 403 242997933 404 246903291 405 250808649 406 254821750 407 258834851 408 262961002 409 267087153 410 271326354 411 275565555 412 279923113 413 284280671 414 288756586 415 293232501 416 297832530 417 302432559 418 307156702 419 311880845 420 316734859 421 321588873 422 326572758 423 331556643 424 336676606 425 341796569 426 347052610 427 352308651 428 357706977 429 363105303 430 368645914 431 374186525 432 379876135 433 385565745 434 391404354 435 397242963 436 403237285 437 409231607 438 415381642 439 421531677 440 427844646 441 434157615 442 440633518 443 447109421 444 453755479 445 460401537 446 467217750 447 474033963 448 481028129 449 488022295 450 495194414 451 502366533 452 509724403 453 517082273 454 524625894 455 532169515 456 539907262 457 547645009 458 555576882 459 563508755 460 571643129 461 579777503 462 588114378 463 596451253 464 604999651 465 613548049 466 622307970 467 631067891 468 640048357 469 649028823 470 658229834 471 667430845 472 676862070 473 686293295 474 695954734 475 705616173 476 715517495 477 725418817 478 735560022 479 745701227 480 756092714 481 766484201 482 777125970 483 787767739 484 798670189 485 809572639 486 820735770 487 831898901 488 843333842 489 854768783 490 866475534 491 878182285 492 890171975 493 902161665 494 914434294 495 926706923 496 939274433 497 951841943 498 964704334 499 977566725 500 990735939 501 1003905153 502 1017381190 503 1030857227 504 1044652842 505 1058448457 506 1072563650 507 1086678843 508 1101126369 509 1115573895 510 1130353754 511 1145133613 512 1160259474 513 1175385335 514 1190857198 515 1206329061 516 1222160595 517 1237992129 518 1254183334 519 1270374539 520 1286939998 521 1303505457 522 1320445170 523 1337384883 524 1354713433 525 1372041983 526 1389759370 527 1407476757 528 1425598579 529 1443720401 530 1462246658 531 1480772915 532 1499719205 533 1518665495 534 1538031818 535 1557398141 536 1577201110 537 1597004079 538 1617243694 539 1637483309 540 1658176183 541 1678869057 542 1700015190 543 1721161323 544 1742778462 545 1764395601 546 1786483746 547 1808571891 548 1831148789 549 1853725687 550 1876791338 551 1899856989 552 1923430274 553 1947003559 554 1971084478 555 1995165397 556 2019772831 557 2044380265 558 2069514214 559 2094648163 560 2120328761 561 2146009359 562 2172236606 563 2198463853 564 2225257883 565 2252051913 566 2279412726 567 2306773539 568 2334722522 569 2362671505 570 2391208658 571 2419745811 572 2448892521 573 2478039231 574 2507795498 575 2537551765 576 2567940371 577 2598328977 578 2629349922 579 2660370867 580 2692046933 581 2723722999 582 2756054186 583 2788385373 584 2821395858 585 2854406343 586 2888096126 587 2921785909 588 2956179167 589 2990572425 590 3025669158 591 3060765891 592 3096591813 593 3132417735 594 3168972846 595 3205527957 596 3242837971 597 3280147985 598 3318212902 599 3356277819 600 3395124890 601 3433971961 602 3473601186 603 3513230411 604 3553669041 605 3594107671 606 3635355706 607 3676603741 608 3718690134 609 3760776527 610 3803701278 611 3846626029 612 3890418091 613 3934210153 614 3978869526 615 4023528899 616 4069086238 617 4114643577 618 4161098882 619 4207554187 620 4254938113 621 4302322039 622 4350634586 623 4398947133 624 4448220823 625 4497494513 626 4547729346 627 4597964179 628 4649192677 629 4700421175 630 4752643338 631 4804865501 632 4858115718 633 4911365935 634 4965644206 635 5019922477 636 5075263191 637 5130603905 638 5187007062 639 5243410219 640 5300912270 641 5358414321 642 5417015266 643 5475616211 644 5535352501 645 5595088791 646 5655960426 647 5716832061 648 5778877554 649 5840923047 650 5904142398 651 5967361749 652 6031793471 653 6096225193 654 6161869286 655 6227513379 656 6294410613 657 6361307847 658 6429458222 659 6497608597 660 6567052883 661 6636497169 662 6707235366 663 6777973563 664 6850048698 665 6922123833 666 6995535906 667 7068947979 668 7143740017 669 7218532055 670 7294704058 671 7370876061 672 7448473538 673 7526071015 674 7605093966 675 7684116917 676 7764610851 677 7845104785 678 7927069702 679 8009034619 680 8092518510 681 8176002401 682 8261005266 683 8346008131 684 8432577961 685 8519147791 686 8607284586 687 8695421381 688 8785175839 689 8874930297 690 8966302418 691 9057674539 692 9150715021 693 9243755503 694 9338464346 695 9433173189 696 9529603798 697 9626034407 698 9724186782 699 9822339157 700 9922266703 701 10022194249 702 10123896966 703 10225599683 704 10329133945 705 10432668207 706 10538034014 707 10643399821 708 10750653547 709 10857907273 710 10967048918 711 11076190563 712 11187279470 713 11298368377 714 11411404546 715 11524440715 716 11639483489 717 11754526263 718 11871575642 719 11988625021 720 12107743579 721 12226862137 722 12348049874 723 12469237611 724 12592557101 725 12715876591 726 12841327834 727 12966779077 728 13094427878 729 13222076679 730 13351923038 731 13481769397 732 13613879119 733 13745988841 734 13880361926 735 14014735011 736 14151440794 737 14288146577 738 14427185058 739 14566223539 740 14707664053 741 14849104567 742 14992947114 743 15136789661 744 15283107106 745 15429424551 746 15578216894 747 15727009237 748 15878349343 749 16029689449 750 16183577318 751 16337465187 752 16493977513 753 16650489839 754 16809626622 755 16968763405 756 17130601339 757 17292439273 758 17456978358 759 17621517443 760 17788838202 761 17956158961 762 18126261394 763 18296363827 764 18469328457 765 18642293087 766 18818119914 767 18993946741 768 19172720463 769 19351494185 770 19533214802 771 19714935419 772 19899687629 773 20084439839 774 20272223642 775 20460007445 776 20650911714 777 20841815983 778 21035840718 779 21229865453 780 21427099527 781 21624333601 782 21824777014 783 22025220427 784 22228966573 785 22432712719 786 22639761598 787 22846810477 788 23057255483 789 23267700489 790 23481541622 791 23695382755 792 23912717930 793 24130053105 794 24350882322 795 24571711539 796 24796132713 797 25020553887 798 25248567018 799 25476580149 800 25708288066 801 25939995983 802 26175398686 803 26410801389 804 26650001707 805 26889202025 806 27132199958 807 27375197891 808 27622101182 809 27869004473 810 28119813122 811 28370621771 812 28625443521 813 28880265271 814 29139100122 815 29397934973 816 29660895975 817 29923856977 818 30190944130 819 30458031283 820 30729357637 821 31000683991 822 31276249546 823 31551815101 824 31831738214 825 32111661327 826 32395941998 827 32680222669 828 32968979255 829 33257735841 830 33550968342 831 33844200843 832 34142033373 833 34439865903 834 34742298462 835 35044731021 836 35351887723 837 35659044425 838 35970925270 839 36282806115 840 36599540974 841 36916275833 842 37237864706 843 37559453579 844 37886026337 845 38212599095 846 38544155738 847 38875712381 848 39212388987 849 39549065593 850 39890862162 851 40232658731 852 40579711341 853 40926763951 854 41279072602 855 41631381253 856 41989088230 857 42346795207 858 42709900510 859 43073005813 860 43441651727 861 43810297641 862 44184484166 863 44558670691 864 44938546826 865 45318422961 866 45703988706 867 46089554451 868 46480958805 869 46872363159 870 47269606122 871 47666849085 872 48070086370 873 48473323655 874 48882555262 875 49291786869 876 49707168511 877 50122550153 878 50544081830 879 50965613507 880 51393458153 881 51821302799 882 52255460414 883 52689618029 884 53130251547 885 53570885065 886 54017994486 887 54465103907 888 54918859386 889 55372614865 890 55833016402 891 56293417939 892 56760635689 893 57227853439 894 57701887402 895 58175921365 896 58656949494 897 59137977623 898 59625999918 899 60114022213 900 60609216627 901 61104411041 902 61606777574 903 62109144107 904 62618868510 905 63128592913 906 63645675186 907 64162757459 908 64687383353 909 65212009247 910 65744178762 911 66276348277 912 66816255539 913 67356162801 914 67903807810 915 68451452819 916 69007029701 917 69562606583 918 70126115338 919 70689624093 920 71261267222 921 71832910351 922 72412687854 923 72992465357 924 73580579735 925 74168694113 926 74765145366 927 75361596619 928 75966596270 929 76571595921 930 77185143970 931 77798692019 932 78420999989 933 79043307959 934 79674375850 935 80305443741 936 80945492098 937 81585540455 938 82234569278 939 82883598101 940 83541827935 941 84200057769 942 84867488614 943 85534919459 944 86211781529 945 86888643599 946 87574936894 947 88261230189 948 88957184923 949 89653139657 950 90358755830 951 91064372003 952 91779889498 953 92495406993 954 93220825810 955 93946244627 956 94681804649 957 95417364671 958 96163065898 959 96908767125 960 97664859839 961 98420952553 962 99187436754 963 99953920955 964 100731046925 965 101508172895 966 102295940634 967 103083708373 968 103882378562 969 104681048751 970 105490621390 971 106300194029 972 107120929799 973 107941665569 974 108773564470 975 109605463371 976 110448797213 977 111292131055 978 112146899838 979 113001668621 980 113868144155 981 114734619689 982 115612801974 983 116490984259 984 117381156234 985 118271328209 986 119173489874 987 120075651539 988 120990085833 989 121904520127 990 122831227050 991 123757933973 992 124697208406 993 125636482839 994 126588324782 995 127540166725 996 128504871059 997 129469575393 998 130447142118 999 131424708843 1000 132415444782