1 0 2 1 3 3 4 7 5 13 6 25 7 40 8 65 9 99 10 146 11 208 12 294 13 399 14 538 15 711 16 926 17 1188 18 1513 19 1896 20 2361 21 2910 22 3557 23 4312 24 5199 25 6214 26 7392 27 8739 28 10276 29 12019 30 14002 31 16224 32 18732 33 21537 34 24669 35 28152 36 32031 37 36309 38 41047 39 46263 40 51997 41 58282 42 65176 43 72688 44 80894 45 89820 46 99518 47 110032 48 121434 49 133740 50 147043 51 161379 52 176813 53 193401 54 211231 55 230328 56 250803 57 272703 58 296108 59 321088 60 347748 61 376123 62 406344 63 438471 64 472600 65 508816 66 547243 67 587928 68 631023 69 676602 70 724779 71 775656 72 829377 73 886002 74 945706 75 1008579 76 1074754 77 1144351 78 1217536 79 1294384 80 1375094 81 1459773 82 1548575 83 1641640 84 1739157 85 1841217 86 1948045 87 2059767 88 2176559 89 2298582 90 2426050 91 2559072 92 2697900 93 2842680 94 2993612 95 3150880 96 3314724 97 3485272 98 3662805 99 3847491 100 4039555 101 4239205 102 4446709 103 4662216 104 4886037 105 5118363 106 5359446 107 5609520 108 5868882 109 6137703 110 6416326 111 6704967 112 7003906 113 7313404 114 7633789 115 7965256 116 8308181 117 8662806 118 9029441 119 9408376 120 9799971 121 10204446 122 10622212 123 11053539 124 11498768 125 11958219 126 12432286 127 12921216 128 13425456 129 13945305 130 14481137 131 15033304 132 15602235 133 16188205 134 16791699 135 17413047 136 18052657 137 18710914 138 19388284 139 20085072 140 20801802 141 21538836 142 22296618 143 23075568 144 23876190 145 24698820 146 25544023 147 26412195 148 27303817 149 28219345 150 29159323 151 30124120 152 31114343 153 32130423 154 33172880 155 34242208 156 35338992 157 36463635 158 37616788 159 38798919 160 40010588 161 41252328 162 42524767 163 43828344 164 45163755 165 46531506 166 47932199 167 49366408 168 50834805 169 52337866 170 53876334 171 55450755 172 57061774 173 58710007 174 60396172 175 62120784 176 63884634 177 65688309 178 67532499 179 69417864 180 71345169 181 73314969 182 75328105 183 77385207 184 79487011 185 81634222 186 83827654 187 86067904 188 88355864 189 90692208 190 93077720 191 95513152 192 97999368 193 100537008 194 103127017 195 105770115 196 108467135 197 111218877 198 114026257 199 116889960 200 119810985 201 122790099 202 125828186 203 128926096 204 132084798 205 135305023 206 138587826 207 141934023 208 145344550 209 148820308 210 152362321 211 155971368 212 159648561 213 163394766 214 167210973 215 171098136 216 175057335 217 179089398 218 183195496 219 187376547 220 191633596 221 195967651 222 200379850 223 204871072 224 209442548 225 214095249 226 218830277 227 223648696 228 228551703 229 233540229 230 238615567 231 243778743 232 249030917 233 254373210 234 259806880 235 265332912 236 270952662 237 276667212 238 282477782 239 288385552 240 294391842 241 300497692 242 306704523 243 313013475 244 319425829 245 325942825 246 332565847 247 339295992 248 346134747 249 353083311 250 360143028 251 367315200 252 374601276 253 382002411 254 389520160 255 397155783 256 404910688 257 412786240 258 420783955 259 428905048 260 437151143 261 445523562 262 454023779 263 462653224 264 471413481 265 480305826 266 489331954 267 498493251 268 507791258 269 517227471 270 526803544 271 536520816 272 546381054 273 556385709 274 566536391 275 576834664 276 587282253 277 597880561 278 608631429 279 619536375 280 630597079 281 641815174 282 653192458 283 664730400 284 676430916 285 688295592 286 700326180 287 712524384 288 724892076 289 737430792 290 750142525 291 763028931 292 776091835 293 789333013 294 802754413 295 816357640 296 830144765 297 844117515 298 858277790 299 872627440 300 887168490 301 901902615 302 916831966 303 931958343 304 947283722 305 962810028 306 978539365 307 994473480 308 1010614605 309 1026964614 310 1043525561 311 1060299448 312 1077288459 313 1094494414 314 1111919628 315 1129566051 316 1147435816 317 1165531003 318 1183853878 319 1202406336 320 1221190776 321 1240209225 322 1259463897 323 1278956952 324 1298690739 325 1318667229 326 1338888907 327 1359357879 328 1380076441 329 1401046834 330 1422271492 331 1443752464 332 1465492322 333 1487493252 334 1509757634 335 1532287792 336 1555086246 337 1578155124 338 1601497087 339 1625114403 340 1649009537 341 1673184897 342 1697643091 343 1722386328 344 1747417359 345 1772738535 346 1798352408 347 1824261472 348 1850468424 349 1876975555 350 1903785708 351 1930901319 352 1958325028 353 1986059416 354 2014107271 355 2042470968 356 2071153443 357 2100157218 358 2129485023 359 2159139528 360 2189123613 361 2219439738 362 2250090934 363 2281079811 364 2312409190 365 2344081831 366 2376100708 367 2408468368 368 2441187938 369 2474262117 370 2507693819 371 2541485896 372 2575641417 373 2610163017 374 2645053921 375 2680316919 376 2715955019 377 2751971166 378 2788368526 379 2825149824 380 2862318384 381 2899877088 382 2937829040 383 2976177280 384 3014925072 385 3054075232 386 3093631185 387 3133595907 388 3173972599 389 3214764397 390 3255974665 391 3297606312 392 3339662865 393 3382147395 394 3425063202 395 3468413520 396 3512201814 397 3556431087 398 3601104970 399 3646226631 400 3691799470 401 3737826820 402 3784312249 403 3831258856 404 3878670377 405 3926550078 406 3974901461 407 4023727960 408 4073033247 409 4122820518 410 4173093616 411 4223855907 412 4275110996 413 4326862419 414 4379113954 415 4431868896 416 4485131196 417 4538904321 418 4593191981 419 4647997816 420 4703325711 421 4759179061 422 4815561927 423 4872477879 424 4929930733 425 4987924234 426 5046462376 427 5105548656 428 5165187246 429 5225381820 430 5286136302 431 5347454544 432 5409340650 433 5471798220 434 5534831539 435 5598444387 436 5662640797 437 5727424729 438 5792800399 439 5858771512 440 5925342467 441 5992517151 442 6060299708 443 6128694208 444 6197704980 445 6267335835 446 6337591288 447 6408475335 448 6479992232 449 6552146160 450 6624941563 451 6698382360 452 6772473183 453 6847218138 454 6922621595 455 6998687848 456 7075421457 457 7152826450 458 7230907578 459 7309669059 460 7389115378 461 7469250943 462 7550080432 463 7631607984 464 7713838470 465 7796776221 466 7880425839 467 7964791848 468 8049879045 469 8135691681 470 8222234749 471 8309512695 472 8397530239 473 8486292022 474 8575802962 475 8666067424 476 8757090524 477 8848876824 478 8941431164 479 9034758304 480 9128863284 481 9223750584 482 9319425445 483 9415892547 484 9513156851 485 9611223237 486 9710096869 487 9809782344 488 9910285029 489 10011609723 490 10113761510 491 10216745392 492 10320566658 493 10425230023 494 10530740982 495 10637104455 496 10744325650 497 10852409692 498 10961361997 499 11071187400 500 11181891525 501 11293479414 502 11405956401 503 11519327736 504 11633598963 505 11748775038 506 11864861716 507 11981864163 508 12099787840 509 12218638123 510 12338420686 511 12459140608 512 12580803776 513 12703415481 514 12826981313 515 12951506776 516 13076997675 517 13203459213 518 13330897411 519 13459317687 520 13588725761 521 13719127266 522 13850528140 523 13982933712 524 14116350138 525 14250782964 526 14386238042 527 14522721136 528 14660238318 529 14798795044 530 14938397607 531 15079051683 532 15220763257 533 15363538225 534 15507382795 535 15652302552 536 15798303927 537 15945392727 538 16093575072 539 16242856992 540 16393244832 541 16544744307 542 16697361988 543 16851103815 544 17005976044 545 17161984840 546 17319136687 547 17477437432 548 17636893787 549 17797511826 550 17959297943 551 18122258440 552 18286399941 553 18451728426 554 18618250750 555 18785973123 556 18954902078 557 19125044055 558 19296405820 559 19468993488 560 19642814058 561 19817873877 562 19994179619 563 20171737864 564 20350555521 565 20530638841 566 20711994969 567 20894630391 568 21078551923 569 21263766286 570 21450280534 571 21638101056 572 21827235144 573 22017689424 574 22209470856 575 22402586304 576 22597042968 577 22792847376 578 22990006969 579 23188528515 580 23388419119 581 23589685789 582 23792335873 583 23996376040 584 24201813881 585 24408656307 586 24616910570 587 24826583824 588 25037683566 589 25250216607 590 25464190690 591 25679612871 592 25896490550 593 26114831028 594 26334641953 595 26555930280 596 26778703905 597 27002970030 598 27228736205 599 27456009880 600 27684798855 601 27915110230 602 28146952056 603 28380331683 604 28615256812 605 28851735043 606 29089774330 607 29329381920 608 29570566020 609 29813334129 610 30057694101 611 30303653688 612 30551220999 613 30800403429 614 31051209343 615 31303646391 616 31557722581 617 31813445818 618 32070824368 619 32329865776 620 32590578566 621 32852970540 622 33117049862 623 33382824592 624 33650303154 625 33919493244 626 34190403547 627 34463042019 628 34737416981 629 35013536649 630 35291409607 631 35571043704 632 35852447787 633 36135629967 634 36420598724 635 36707362432 636 36995929836 637 37286308939 638 37578508752 639 37872537543 640 38168403952 641 38466116512 642 38765684131 643 39067114968 644 39370418199 645 39675602250 646 39982675923 647 40291647912 648 40602527289 649 40915322370 650 41230042498 651 41546696259 652 41865292618 653 42185840431 654 42508348936 655 42832826608 656 43159282958 657 43487726733 658 43818167063 659 44150612968 660 44485073853 661 44821558353 662 45160076149 663 45500636151 664 45843247655 665 46187919846 666 46534662298 667 46883483808 668 47234394228 669 47587402632 670 47942518484 671 48299751136 672 48659110332 673 49020605032 674 49384245261 675 49750040259 676 50117999659 677 50488132981 678 50860450141 679 51234960264 680 51611673549 681 51990599403 682 52371747630 683 52755127920 684 53140750362 685 53528624247 686 53918759950 687 54311167047 688 54705855514 689 55102835212 690 55502116405 691 55903708552 692 56307622205 693 56713867110 694 57122453417 695 57533391160 696 57946690779 697 58362361902 698 58780415260 699 59200860771 700 59623708760 701 60048969435 702 60476653414 703 60906770496 704 61339331592 705 61774346793 706 62211826601 707 62651781400 708 63094221987 709 63539158333 710 63986601531 711 64436561847 712 64889049961 713 65344076434 714 65801652244 715 66261787536 716 66724493586 717 67189780836 718 67657660146 719 68128142256 720 68601238326 721 69076958676 722 69555314767 723 70036317219 724 70519977073 725 71006305249 726 71495313091 727 71987011096 728 72481410911 729 72978523335 730 73478359592 731 73980930784 732 74486248440 733 74994323235 734 75505167004 735 76018790727 736 76535205812 737 77054423544 738 77576455639 739 78101312952 740 78629007507 741 79159550466 742 79692953423 743 80229227848 744 80768385645 745 81310437850 746 81855396678 747 82403273475 748 82954080022 749 83507827975 750 84064529428 751 84624195600 752 85186838898 753 85752470853 754 86321103435 755 86892748488 756 87467418297 757 88045124265 758 88625878993 759 89209694199 760 89796582043 761 90386554558 762 90979624222 763 91575802624 764 92175102560 765 92777535936 766 93383115104 767 93991852288 768 94603760160 769 95218850496 770 95837136289 771 96458629635 772 97083343079 773 97711289037 774 98342480377 775 98976929064 776 99614648289 777 100255650339 778 100899947954 779 101547553744 780 102198480774 781 102852741199 782 103510348410 783 104171314887 784 104835653566 785 105503377252 786 106174499209 787 106849031784 788 107526988569 789 108208382238 790 108893225925 791 109581532632 792 110273315823 793 110968588038 794 111667363072 795 112369653795 796 113075473540 797 113784835507 798 114497753362 799 115214239840 800 115934308940 801 116657973729 802 117385247741 803 118116144376 804 118850677503 805 119588860053 806 120330706231 807 121076229303 808 121825443005 809 122578360938 810 123334997176 811 124095364848 812 124859478366 813 125627351196 814 126398997278 815 127174430416 816 127953664890 817 128736714028 818 129523592451 819 130314313827 820 131108892301 821 131907341881 822 132709677055 823 133515911352 824 134326059603 825 135140135679 826 135958153932 827 136780128576 828 137606074308 829 138436004859 830 139269935272 831 140107879623 832 140949852472 833 141795868240 834 142645941835 835 143500087192 836 144358319567 837 145220653242 838 146087102987 839 146957683432 840 147832409697 841 148711295922 842 149594357578 843 150481609155 844 151373065634 845 152268741855 846 153168653152 847 154072813872 848 154981239702 849 155893945341 850 156810945983 851 157732256680 852 158657892981 853 159587869441 854 160522201965 855 161460905463 856 162403995343 857 163351486870 858 164303395810 859 165259736928 860 166220526348 861 167185779192 862 168155511084 863 169129737504 864 170108474436 865 171091736856 866 172079541109 867 173071902531 868 174068836963 869 175070360101 870 176076488149 871 177087236296 872 178102621109 873 179122658139 874 180147363446 875 181176752944 876 182210843058 877 183249649191 878 184293188134 879 185341475655 880 186394528034 881 187452361404 882 188514992413 883 189582436680 884 190654711221 885 191731832022 886 192813815585 887 193900678264 888 194992436931 889 196089107422 890 197190706980 891 198297251811 892 199408758640 893 200525244043 894 201646725118 895 202773217920 896 203904739920 897 205041307545 898 206182937745 899 207329647320 900 208481453595 901 209638372845 902 210800422771 903 211967620023 904 213139981777 905 214317525058 906 215500267420 907 216688225360 908 217881416810 909 219079858644 910 220283568266 911 221492562928 912 222706860414 913 223926477444 914 225151432183 915 226381741731 916 227617423721 917 228858495633 918 230104975483 919 231356880216 920 232614228231 921 233877036855 922 235145323952 923 236419107232 924 237698404944 925 238983234259 926 240273613812 927 241569561159 928 242871094396 929 244178231464 930 245490990847 931 246809389944 932 248133447627 933 249463181682 934 250798610439 935 252139752072 936 253486625301 937 254839247754 938 256197638542 939 257561815683 940 258931797742 941 260307603127 942 261689250796 943 263076758608 944 264470145914 945 265869430965 946 267274632563 947 268685769352 948 270102860529 949 271525924185 950 272954979913 951 274390046199 952 275831142083 953 277278286446 954 278731498726 955 280190797248 956 281656201848 957 283127731248 958 284605404728 959 286089241408 960 287579260968 961 289075481968 962 290577924489 963 292086607491 964 293601550495 965 295122772861 966 296650294513 967 298184134248 968 299724312393 969 301270848147 970 302823761274 971 304383071376 972 305948798622 973 307520962047 974 309099582226 975 310684678599 976 312276271174 977 313874379796 978 315479024881 979 317090225704 980 318708003089 981 320332376718 982 321963366845 983 323600993560 984 325245277527 985 326896238262 986 328553896840 987 330218273187 988 331889387804 989 333567261027 990 335251913770 991 336943365792 992 338641638420 993 340346751825 994 342058726757 995 343777583800 996 345503344119 997 347236027717 998 348975656175 999 350722249911 1000 352475829925