0 0 1 0 2 1 3 5 4 13 5 30 6 57 7 101 8 164 9 255 10 377 11 540 12 748 13 1014 14 1342 15 1747 16 2233 17 2818 18 3507 19 4319 20 5260 21 6351 22 7599 23 9027 24 10642 25 12470 26 14518 27 16814 28 19366 29 22204 30 25337 31 28796 32 32591 33 36756 34 41301 35 46262 36 51649 37 57501 38 63829 39 70673 40 78045 41 85987 42 94512 43 103664 44 113456 45 123935 46 135114 47 147042 48 159733 49 173238 50 187572 51 202787 52 218899 53 235963 54 253995 55 273052 56 293150 57 314349 58 336666 59 360162 60 384855 61 410808 62 438040 63 466616 64 496555 65 527925 66 560745 67 595085 68 630965 69 668457 70 707582 71 748413 72 790972 73 835335 74 881524 75 929617 76 979636 77 1031662 78 1085718 79 1141886 80 1200190 81 1260714 82 1323483 83 1388583 84 1456039 85 1525940 86 1598311 87 1673243 88 1750762 89 1830961 90 1913867 91 1999574 92 2088110 93 2179572 94 2273988 95 2371457 96 2472007 97 2575740 98 2682685 99 2792945 100 2906550 101 3023605 102 3144141 103 3268265 104 3396008 105 3527480 106 3662712 107 3801816 108 3944824 109 4091850 110 4242927 111 4398170 112 4557613 113 4721374 114 4889487 115 5062072 116 5239163 117 5420883 118 5607267 119 5798439 120 5994435 121 6195381 122 6401314 123 6612362 124 6828562 125 7050045 126 7276848 127 7509104 128 7746851 129 7990224 130 8239262 131 8494101 132 8754781 133 9021441 134 9294121 135 9572962 136 9858004 137 10149391 138 10447164 139 10751468 140 11062345 141 11379942 142 11704302 143 12035574 144 12373801 145 12719135 146 13071619 147 13431407 148 13798543 149 14173183 150 14555372 151 14945267 152 15342914 153 15748473 154 16161990 155 16583627 156 17013430 157 17451564 158 17898076 159 18353132 160 18816780 161 19289188 162 19770405 163 20260601 164 20759825 165 21268250 166 21785925 167 22313025 168 22849600 169 23395827 170 23951757 171 24517568 172 25093312 173 25679170 174 26275194 175 26881567 176 27498341 177 28125702 178 28763703 179 29412531 180 30072240 181 30743019 182 31424923 183 32118143 184 32822734 185 33538890 186 34266666 187 35006258 188 35757722 189 36521256 190 37296917 191 38084904 192 38885275 193 39698232 194 40523833 195 41362282 196 42213637 197 43078105 198 43955745 199 44846765 200 45751225 201 46669335 202 47601156 203 48546900 204 49506628 205 50480555 206 51468742 207 52471406 208 53488609 209 54520570 210 55567352 211 56629175 212 57706103 213 58798359 214 59906007 215 61029272 216 62168218 217 63323073 218 64493902 219 65680934 220 66884235 221 68104036 222 69340404 223 70593572 224 71863607 225 73150745 226 74455053 227 75776769 228 77115961 229 78472869 230 79847562 231 81240281 232 82651096 233 84080251 234 85527816 235 86994037 236 88478984 237 89982906 238 91505874 239 93048138 240 94609770 241 96191022 242 97791967 243 99412859 244 101053771 245 102714960 246 104396499 247 106098647 248 107821478 249 109565253 250 111330047 251 113116122 252 114923554 253 116752608 254 118603360 255 120476077 256 122370835 257 124287904 258 126227361 259 128189477 260 130174330 261 132182193 262 134213145 263 136267461 264 138345220 265 140446700 266 142571980 267 144721340 268 146894860 269 149092822 270 151315307 271 153562598 272 155834777 273 158132130 274 160454739 275 162802892 276 165176671 277 167576367 278 170002063 279 172454051 280 174932415 281 177437449 282 179969238 283 182528078 284 185114054 285 187727465 286 190368396 287 193037148 288 195733807 289 198458676 290 201211842 291 203993609 292 206804065 293 209643517 294 212512053 295 215409982 296 218337392 297 221294595 298 224281680 299 227298960 300 230346525 301 233424690 302 236533546 303 239673410 304 242844373 305 246046755 306 249280647 307 252546371 308 255844019 309 259173915 310 262536152 311 265931055 312 269358718 313 272819469 314 276313402 315 279840847 316 283401898 317 286996888 318 290625912 319 294289304 320 297987160 321 301719816 322 305487369 323 309290157 324 313128277 325 317002070 326 320911633 327 324857309 328 328839196 329 332857639 330 336912737 331 341004836 332 345134036 333 349300686 334 353504886 335 357746987 336 362027089 337 366345546 338 370702459 339 375098183 340 379532820 341 384006727 342 388520007 343 393073019 344 397665866 345 402298910 346 406972254 347 411686262 348 416441038 349 421236948 350 426074097 351 430952852 352 435873319 353 440835868 354 445840605 355 450887902 356 455977865 357 461110869 358 466287021 359 471506697 360 476770005 361 482077323 362 487428760 363 492824696 364 498265240 365 503750775 366 509281410 367 514857530 368 520479245 369 526146942 370 531860732 371 537621003 372 543427867 373 549281715 374 555182659 375 561131092 376 567127126 377 573171157 378 579263298 379 585403946 380 591593215 381 597831504 382 604118928 383 610455888 384 616842499 385 623279165 386 629766001 387 636303413 388 642891517 389 649530721 390 656221142 391 662963189 392 669756980 393 676602927 394 683501148 395 690452057 396 697455772 397 704512710 398 711622990 399 718787030 400 726004950 401 733277170 402 740603811 403 747985295 404 755421743 405 762913580 406 770460927 407 778064211 408 785723554 409 793439385 410 801211827 411 809041310 412 816927958 413 824872204 414 832874172 415 840934297 416 849052703 417 857229828 418 865465797 419 873761049 420 882115710 421 890530221 422 899004709 423 907539617 424 916135072 425 924791520 426 933509088 427 942288224 428 951129056 429 960032034 430 968997287 431 978025266 432 987116101 433 996270246 434 1005487831 435 1014769312 436 1024114819 437 1033524811 438 1042999419 439 1052539103 440 1062143995 441 1071814557 442 1081550922 443 1091353554 444 1101222586 445 1111158485 446 1121161384 447 1131231752 448 1141369723 449 1151575768 450 1161850022 451 1172192957 452 1182604709 453 1193085753 454 1203636225 455 1214256602 456 1224947020 457 1235707959 458 1246539556 459 1257442292 460 1268416305 461 1279462078 462 1290579750 463 1301769806 464 1313032385 465 1324367975 466 1335776715 467 1347259095 468 1358815255 469 1370445687 470 1382150532 471 1393930283 472 1405785082 473 1417715425 474 1429721454 475 1441803667 476 1453962206 477 1466197572 478 1478509908 479 1490899716 480 1503367140 481 1515912684 482 1528536493 483 1541239073 484 1554020569 485 1566881490 486 1579821981 487 1592842553 488 1605943352 489 1619124891 490 1632387317 491 1645731144 492 1659156520 493 1672663962 494 1686253618 495 1699926007 496 1713681277 497 1727519950 498 1741442175 499 1755448475 500 1769539000 501 1783714275 502 1797974451 503 1812320055 504 1826751238 505 1841268530 506 1855872082 507 1870562426 508 1885339714 509 1900204480 510 1915156877 511 1930197440 512 1945326323 513 1960544064 514 1975850817 515 1991247122 516 2006733133 517 2022309393 518 2037976057 519 2053733669 520 2069582385 521 2085522751 522 2101554924 523 2117679452 524 2133896492 525 2150206595 526 2166609918 527 2183107014 528 2199698041 529 2216383554 530 2233163712 531 2250039071 532 2267009791 533 2284076431 534 2301239151 535 2318498512 536 2335854674 537 2353308201 538 2370859254 539 2388508398 540 2406255795 541 2424102012 542 2442047212 543 2460091964 544 2478236431 545 2496481185 546 2514826389 547 2533272617 548 2551820033 549 2570469213 550 2589220322 551 2608073937 552 2627030224 553 2646089763 554 2665252720 555 2684519677 556 2703890800 557 2723366674 558 2742947466 559 2762633762 560 2782425730 561 2802323958 562 2822328615 563 2842440291 564 2862659155 565 2882985800 566 2903420395 567 2923963535 568 2944615390 569 2965376557 570 2986247207 571 3007227938 572 3028318922 573 3049520760 574 3070833624 575 3092258117 576 3113794411 577 3135443112 578 3157204393 579 3179078861 580 3201066690 581 3223168489 582 3245384433 583 3267715133 584 3290160764 585 3312721940 586 3335398836 587 3358192068 588 3381101812 589 3404128686 590 3427272867 591 3450534974 592 3473915185 593 3497414122 594 3521031963 595 3544769332 596 3568626407 597 3592603815 598 3616701735 599 3640920795 600 3665261175 601 3689723505 602 3714307966 603 3739015190 604 3763845358 605 3788799105 606 3813876612 607 3839078516 608 3864404999 609 3889856700 610 3915433802 611 3941136945 612 3966966313 613 3992922549 614 4019005837 615 4045216822 616 4071555688 617 4098023083 618 4124619192 619 4151344664 620 4178199685 621 4205184906 622 4232300514 623 4259547162 624 4286925037 625 4314434795 626 4342076623 627 4369851179 628 4397758651 629 4425799699 630 4453974512 631 4482283751 632 4510727606 633 4539306741 634 4568021346 635 4596872087 636 4625859154 637 4654983216 638 4684244464 639 4713643568 640 4743180720 641 4772856592 642 4802671377 643 4832625749 644 4862719901 645 4892954510 646 4923329769 647 4953846357 648 4984504468 649 5015304783 650 5046247497 651 5077333292 652 5108562364 653 5139935398 654 5171452590 655 5203114627 656 5234921705 657 5266874514 658 5298973251 659 5331218607 660 5363610780 661 5396150463 662 5428837855 663 5461673651 664 5494658050 665 5527791750 666 5561074950 667 5594508350 668 5628092150 669 5661827052 670 5695713257 671 5729751468 672 5763941887 673 5798285220 674 5832781669 675 5867431942 676 5902236241 677 5937195277 678 5972309253 679 6007578881 680 6043004365 681 6078586419 682 6114325248 683 6150221568 684 6186275584 685 6222488015 686 6258859066 687 6295389458 688 6332079397 689 6368929606 690 6405940292 691 6443112179 692 6480445475 693 6517940907 694 6555598683 695 6593419532 696 6631403662 697 6669551805 698 6707864170 699 6746341490 700 6784983975 701 6823792360 702 6862766856 703 6901908200 704 6941216603 705 6980692805 706 7020337017 707 7060149981 708 7100131909 709 7140283545 710 7180605102 711 7221097325 712 7261760428 713 7302595159 714 7343601732 715 7384780897 716 7426132868 717 7467658398 718 7509357702 719 7551231534 720 7593280110 721 7635504186 722 7677903979 723 7720480247 724 7763233207 725 7806163620 726 7849271703 727 7892558219 728 7936023386 729 7979667969 730 8023492187 731 8067496806 732 8111682046 733 8156048676 734 8200596916 735 8245327537 736 8290240759 737 8335337356 738 8380617549 739 8426082113 740 8471731270 741 8517565797 742 8563585917 743 8609792409 744 8656185496 745 8702765960 746 8749534024 747 8796490472 748 8843635528 749 8890969978 750 8938494047 751 8986208522 752 9034113629 753 9082210158 754 9130498335 755 9178978952 756 9227652235 757 9276518979 758 9325579411 759 9374834327 760 9424283955 761 9473929093 762 9523769970 763 9573807386 764 9624041570 765 9674473325 766 9725102880 767 9775931040 768 9826958035 769 9878184672 770 9929611182 771 9981238373 772 10033066477 773 10085096305 774 10137328089 775 10189762642 776 10242400196 777 10295241567 778 10348286988 779 10401537276 780 10454992665 781 10508653974 782 10562521438 783 10616595878 784 10670877529 785 10725367215 786 10780065171 787 10834972223 788 10890088607 789 10945415151 790 11000952092 791 11056700259 792 11112659890 793 11168831817 794 11225216278 795 11281814107 796 11338625542 797 11395651420 798 11452891980 799 11510348060 800 11568019900 801 11625908340 802 11684013621 803 11742336585 804 11800877473 805 11859637130 806 11918615797 807 11977814321 808 12037232944 809 12096872515 810 12156733277 811 12216816080 812 12277121168 813 12337649394 814 12398401002 815 12459376847 816 12520577173 817 12582002838 818 12643654087 819 12705531779 820 12767636160 821 12829968091 822 12892527819 823 12955316207 824 13018333502 825 13081580570 826 13145057658 827 13208765634 828 13272704746 829 13336875864 830 13401279237 831 13465915736 832 13530785611 833 13595889736 834 13661228361 835 13726802362 836 13792611989 837 13858658121 838 13924941009 839 13991461533 840 14058219945 841 14125217127 842 14192453332 843 14259929444 844 14327645716 845 14395603035 846 14463801654 847 14532242462 848 14600925713 849 14669852298 850 14739022472 851 14808437127 852 14878096519 853 14948001543 854 15018152455 855 15088550152 856 15159194890 857 15230087569 858 15301228446 859 15372618422 860 15444257755 861 15516147348 862 15588287460 863 15660678996 864 15733322215 865 15806218025 866 15879366685 867 15952769105 868 16026425545 869 16100336917 870 16174503482 871 16248926153 872 16323605192 873 16398541515 874 16473735384 875 16549187717 876 16624898776 877 16700869482 878 16777100098 879 16853591546 880 16930344090 881 17007358654 882 17084635503 883 17162175563 884 17239979099 885 17318047040 886 17396379651 887 17474977863 888 17553841942 889 17632972821 890 17712370767 891 17792036714 892 17871970930 893 17952174352 894 18032647248 895 18113390557 896 18194404547 897 18275690160 898 18357247665 899 18439078005 900 18521181450 901 18603558945 902 18686210761 903 18769137845 904 18852340468 905 18935819580 906 19019575452 907 19103609036 908 19187920604 909 19272511110 910 19357380827 911 19442530710 912 19527961033 913 19613672754 914 19699666147 915 19785942172 916 19872501103 917 19959343903 918 20046470847 919 20133882899 920 20221580335 921 20309564121 922 20397834534 923 20486392542 924 20575238422 925 20664373145 926 20753796988 927 20843510924 928 20933515231 929 21023810884 930 21114398162 931 21205278041 932 21296450801 933 21387917421 934 21479678181 935 21571734062 936 21664085344 937 21756733011 938 21849677344 939 21942919328 940 22036459245 941 22130298082 942 22224436122 943 22318874354 944 22413613061 945 22508653235 946 22603995159 947 22699639827 948 22795587523 949 22891839243 950 22988395272 951 23085256607 952 23182423534 953 23279897053 954 23377677450 955 23475765727 956 23574162170 957 23672867784 958 23771882856 959 23871208392 960 23970844680 961 24070792728 962 24171052825 963 24271625981 964 24372512485 965 24473713350 966 24575228865 967 24677060045 968 24779207180 969 24881671287 970 24984452657 971 25087552308 972 25190970532 973 25294708350 974 25398766054 975 25503144667 976 25607844481 977 25712866522 978 25818211083 979 25923879191 980 26029871140 981 26136187959 982 26242829943 983 26349798123 984 26457092794 985 26564714990 986 26672665006 987 26780943878 988 26889551902 989 26998490116 990 27107758817 991 27217359044 992 27327291095 993 27437556012 994 27548154093 995 27659086382 996 27770353177 997 27881955525 998 27993893725 999 28106168825 1000 28218781125