0 1 1 1 2 3 3 4 4 8 5 11 6 18 7 24 8 36 9 47 10 66 11 84 12 113 13 141 14 183 15 225 16 284 17 344 18 425 19 508 20 617 21 729 22 872 23 1020 24 1205 25 1397 26 1632 27 1877 28 2172 29 2480 30 2846 31 3228 32 3677 33 4146 34 4691 35 5261 36 5917 37 6603 38 7386 39 8205 40 9133 41 10103 42 11195 43 12336 44 13613 45 14947 46 16431 47 17981 48 19697 49 21488 50 23462 51 25521 52 27781 53 30137 54 32713 55 35397 56 38321 57 41366 58 44672 59 48113 60 51838 61 55712 62 59894 63 64241 64 68921 65 73783 66 79004 67 84425 68 90233 69 96260 70 102703 71 109385 72 116514 73 123903 74 131771 75 139922 76 148585 77 157555 78 167072 79 176921 80 187354 81 198145 82 209558 83 221357 84 233818 85 246694 86 260273 87 274298 88 289069 89 304318 90 320358 91 336909 92 354298 93 372233 94 391054 95 410458 96 430798 97 451759 98 473708 99 496318 100 519970 101 544324 102 569776 103 595973 104 623326 105 651469 106 680827 107 711022 108 742494 109 774851 110 808549 111 843182 112 879222 113 916249 114 954751 115 994294 116 1035382 117 1077567 118 1121369 119 1166326 120 1212975 121 1260838 122 1310470 123 1361378 124 1414134 125 1468230 126 1524255 127 1581686 128 1641130 129 1702048 130 1765065 131 1829626 132 1896375 133 1964740 134 2035384 135 2107719 136 2182426 137 2258901 138 2337844 139 2418634 140 2501991 141 2587276 142 2675229 143 2765194 144 2857931 145 2952766 146 3050479 147 3150379 148 3253266 149 3358431 150 3466695 151 3577330 152 3691179 153 3807495 154 3927142 155 4049355 156 4175019 157 4303350 158 4435255 159 4569931 160 4708307 161 4849560 162 4994642 163 5142710 164 5294739 165 5449866 166 5609088 167 5771523 168 5938191 169 6108189 170 6282561 171 6460383 172 6642723 173 6828636 174 7019214 175 7213491 176 7412583 177 7615503 178 7823391 179 8035239 180 8252212 181 8473279 182 8699631 183 8930215 184 9166247 185 9406652 186 9652671 187 9903207 188 10159527 189 10420511 190 10687452 191 10959207 192 11237096 193 11519952 194 11809122 195 12103416 196 12404207 197 12710282 198 13023041 199 13341247 200 13666328 201 13997022 202 14334785 203 14678331 204 15029144 205 15385913 206 15750150 207 16120520 208 16498563 209 16882919 210 17275157 211 17673891 212 18080720 213 18494232 214 18916055 215 19344752 216 19781980 217 20226276 218 20679327 219 21139644 220 21608944 221 22085711 222 22571693 223 23065347 224 23568452 225 24079438 226 24600114 227 25128884 228 25667588 229 26214602 230 26771798 231 27337524 232 27913684 233 28498598 234 29094202 235 29698788 236 30314324 237 30939074 238 31575038 239 32220452 240 32877349 241 33543935 242 34222277 243 34910552 244 35610860 245 36321349 246 37044152 247 37777388 248 38523224 249 39279749 250 40049164 251 40829528 252 41623077 253 42427839 254 43246085 255 44075813 256 44919328 257 45774598 258 46643963 259 47525360 260 48421165 261 49329283 262 50252126 263 51187568 264 52138057 265 53101435 266 54080186 267 55072121 268 56079760 269 57100882 270 58138044 271 59188992 272 60256321 273 61337744 274 62435893 275 63548449 276 64678081 277 65822437 278 66984224 279 68161057 280 69355681 281 70565677 282 71793829 283 73037684 284 74300065 285 75578485 286 76875805 287 78189505 288 79522485 289 80872190 290 82241560 291 83628005 292 85034505 293 86458435 294 87902815 295 89364985 296 90848005 297 92349180 298 93871610 299 95412565 300 96975186 301 98556706 302 100160308 303 101783189 304 103428573 305 105093621 306 106781598 307 108489629 308 110221021 309 111972862 310 113748501 311 115544989 312 117365718 313 119207701 314 121074373 315 122962710 316 124876189 317 126811749 318 128772910 319 130756573 320 132766302 321 134798959 322 136858152 323 138940705 324 141050270 325 143183632 326 145344487 327 147529582 328 149742657 329 151980420 330 154246656 331 156538033 332 158858382 333 161204331 334 163579756 335 165981246 336 168412722 337 170870733 338 173359246 339 175874770 340 178421318 341 180995358 342 183600950 343 186234521 344 188900178 345 191594307 346 194321061 347 197076786 348 199865682 349 202684053 350 205536147 351 208418226 352 211334586 353 214281447 354 217263153 355 220275882 356 223324026 357 226403721 358 229519407 359 232667178 360 235851523 361 239068492 362 242322624 363 245609926 364 248934986 365 252293768 366 255690909 367 259122330 368 262592718 369 266097950 370 269642763 371 273222990 372 276843419 373 280499838 374 284197086 375 287930907 376 291706190 377 295518635 378 299373182 379 303265486 380 307200539 381 311173950 382 315190763 383 319246542 384 323346383 385 327485804 386 331669953 387 335894303 388 340164054 389 344474633 390 348831293 391 353229414 392 357674303 393 362161293 394 366695744 395 371272943 396 375898303 397 380567064 398 385284693 399 390046383 400 394857655 401 399713654 402 404619956 403 409571658 404 414574391 405 419623204 406 424723782 407 429871127 408 435070979 409 440318291 410 445618859 411 450967587 412 456370327 413 461821934 414 467328316 415 472884279 416 478495787 417 484157597 418 489875729 419 495644891 420 501471160 421 507349193 422 513285125 423 519273563 424 525320699 425 531421090 426 537580985 427 543794891 428 550069115 429 556398113 430 562788250 431 569233931 432 575741580 433 582305550 434 588932324 435 595616204 436 602363731 437 609169156 438 616039079 439 622967699 440 629961676 441 637015156 442 644134859 443 651314879 444 658561996 445 665870251 446 673246484 447 680684684 448 688191751 449 695761621 450 703401255 451 711104535 452 718878484 453 726716930 454 734626957 455 742602340 456 750650224 457 758764330 458 766951865 459 775206496 460 783535492 461 791932465 462 800404747 463 808945895 464 817563304 465 826250476 466 835014868 467 843849928 468 852763176 469 861748004 470 870811996 471 879948488 472 889165128 473 898455196 474 907826404 475 917271976 476 926799688 477 936402708 478 946088876 479 955851304 480 965697897 481 975621709 482 985630711 483 995717900 484 1005891312 485 1016143887 486 1026483726 487 1036903712 488 1047412012 489 1058001451 490 1068680262 491 1079441212 492 1090292601 493 1101227137 494 1112253187 495 1123363401 496 1134566212 497 1145854212 498 1157235901 499 1168703812 500 1180266513 501 1191916477 502 1203662340 503 1215496516 504 1227427709 505 1239448273 506 1251566980 507 1263776125 508 1276084548 509 1288484484 510 1300984842 511 1313577796 512 1326272325 513 1339060542 514 1351951495 515 1364937237 516 1378026885 517 1391212431 518 1404503062 519 1417890709 520 1431384629 521 1444976691 522 1458676223 523 1472475032 524 1486382517 525 1500390423 526 1514508219 527 1528727589 528 1543058073 529 1557491292 530 1572036858 531 1586686329 532 1601449389 533 1616317533 534 1631300517 535 1646389773 536 1661595129 537 1676907954 538 1692338148 539 1707877017 540 1723534534 541 1739301940 542 1755189282 543 1771187737 544 1787307425 545 1803539459 546 1819894032 547 1836362193 548 1852954209 549 1869661064 550 1886493099 551 1903441233 552 1920515882 553 1937707899 554 1955027775 555 1972466298 556 1990034033 557 2007721703 558 2025539948 559 2043479425 560 2061550850 561 2079744813 562 2098072106 563 2116523253 564 2135109122 565 2153820170 566 2172667341 567 2191641026 568 2210752245 569 2229991322 570 2249369354 571 2268876597 572 2288524226 573 2308302429 574 2328222458 575 2348274434 576 2368469686 577 2388798267 578 2409271584 579 2429879622 580 2450633866 581 2471524232 582 2492562284 583 2513737869 584 2535062630 585 2556526345 586 2578140735 587 2599895510 588 2621802470 589 2643851255 590 2666053745 591 2688399510 592 2710900510 593 2733546245 594 2756348755 595 2779297470 596 2802404510 597 2825659235 598 2849073845 599 2872637630 600 2896362871 601 2920238786 602 2944277738 603 2968468874 604 2992824638 605 3017334106 606 3042009803 607 3066840734 608 3091839506 609 3116995052 610 3142320061 611 3167803394 612 3193457823 613 3219272136 614 3245259188 615 3271407695 616 3297730594 617 3324216529 618 3350878520 619 3377705138 620 3404709487 621 3431880064 622 3459230057 623 3486747890 624 3514446835 625 3542315242 626 3570366467 627 3598588787 628 3626995642 629 3655575235 630 3684341091 631 3713281338 632 3742409587 633 3771713891 634 3801207946 635 3830879731 636 3860743027 637 3890785738 638 3921021731 639 3951438835 640 3982051003 641 4012845988 642 4043837830 643 4075014206 644 4106389243 645 4137950542 646 4169712316 647 4201662091 648 4233814167 649 4266155993 650 4298701957 651 4331439431 652 4364382891 653 4397519632 654 4430864218 655 4464403867 656 4498153231 657 4532099451 658 4566257267 659 4600613743 660 4635183708 661 4669954147 662 4704939979 663 4740128111 664 4775533551 665 4811143128 666 4846971939 667 4883006735 668 4919262703 669 4955726515 670 4992413448 671 5029310095 672 5066431824 673 5103765148 674 5141325526 675 5179099392 676 5217102295 677 5255320590 678 5293769917 679 5332436551 680 5371336224 681 5410455130 682 5449809093 683 5489384227 684 5529196448 685 5569231789 686 5609506258 687 5650005808 688 5690746539 689 5731714323 690 5772925353 691 5814365419 692 5856050808 693 5897967228 694 5940131059 695 5982527928 696 6025174308 697 6068055744 698 6111188803 699 6154558948 700 6198182840 701 6242045859 702 6286164761 703 6330524843 704 6375142956 705 6420004314 706 6465125862 707 6510492732 708 6556121964 709 6601998606 710 6648139794 711 6694530492 712 6741187932 713 6788096994 714 6835275006 715 6882706764 716 6930409692 717 6978368502 718 7026600714 719 7075090956 720 7123856845 721 7172882923 722 7222186905 723 7271753248 724 7321599764 725 7371710825 726 7422104340 727 7472764596 728 7523709600 729 7574923553 730 7626424560 731 7678196736 732 7730258285 733 7782593235 734 7835219889 735 7888122189 736 7941318536 737 7994792786 738 8048563439 739 8102614264 740 8156963861 741 8211595911 742 8266529114 743 8321747064 744 8377268561 745 8433077111 746 8489191614 747 8545595489 748 8602307736 749 8659311686 750 8716626440 751 8774235240 752 8832157289 753 8890375740 754 8948909897 755 9007742825 756 9066893929 757 9126346185 758 9186119100 759 9246195561 760 9306595177 761 9367300745 762 9428331977 763 9489671580 764 9551339369 765 9613317961 766 9675627273 767 9738249833 768 9801205661 769 9864477194 770 9928084556 771 9992010093 772 10056274033 773 10120858631 774 10185784219 775 10251032961 776 10316625293 777 10382543288 778 10448807486 779 10515399869 780 10582341082 781 10649613014 782 10717236416 783 10785193085 784 10853503877 785 10922150497 786 10991153906 787 11060495717 788 11130196997 789 11200239266 790 11270643697 791 11341391717 792 11412504606 793 11483963697 794 11555790377 795 11627965886 796 11700511717 797 11773409017 798 11846679386 799 11920303877 800 11994304198 801 12068661307 802 12143397020 803 12218492201 804 12293968774 805 12369807508 806 12446030435 807 12522618230 808 12599593033 809 12676935424 810 12754667652 811 12832770201 812 12911265430 813 12990133727 814 13069397560 815 13149037222 816 13229075290 817 13309491961 818 13390309922 819 13471509274 820 13553112814 821 13635100546 822 13717495378 823 13800277217 824 13883469082 825 13967050783 826 14051045449 827 14135432794 828 14220236058 829 14305434857 830 14391052543 831 14477068634 832 14563506594 833 14650345843 834 14737609957 835 14825278258 836 14913374434 837 15001877709 838 15090811883 839 15180156082 840 15269934219 841 15360125320 842 15450753412 843 15541797422 844 15633281490 845 15725184444 846 15817530537 847 15910298498 848 16003512694 849 16097151754 850 16191240159 851 16285756438 852 16380725187 853 16476124834 854 16571980090 855 16668269283 856 16765017238 857 16862202183 858 16959849058 859 17057935990 860 17156488035 861 17255483218 862 17354946711 863 17454856438 864 17555237687 865 17656068280 866 17757373621 867 17859131431 868 17961367230 869 18064058637 870 18167231289 871 18270862702 872 18374978631 873 18479556489 874 18584622148 875 18690152919 876 18796174791 877 18902664972 878 19009649569 879 19117105687 880 19225059551 881 19333488162 882 19442417864 883 19551825554 884 19661737695 885 19772131080 886 19883032290 887 19994418015 888 20106314955 889 20218699695 890 20331599055 891 20444989515 892 20558898015 893 20673300930 894 20788225320 895 20903647455 896 21019594515 897 21136042665 898 21253019205 899 21370500195 900 21488513056 901 21607033741 902 21726089793 903 21845657059 904 21965763203 905 22086383966 906 22207547133 907 22329228339 908 22451455491 909 22574204117 910 22697502246 911 22821325299 912 22945701428 913 23070605946 914 23196067128 915 23322060180 916 23448613499 917 23575702184 918 23703354755 919 23831546203 920 23960305172 921 24089606544 922 24219479087 923 24349897575 924 24480890900 925 24612433727 926 24744555072 927 24877229492 928 25010486127 929 25144299425 930 25278698651 931 25413658143 932 25549207292 933 25685320326 934 25822026761 935 25959300716 936 26097171832 937 26235614118 938 26374657341 939 26514275400 940 26654498188 941 26795299493 942 26936709335 943 27078701391 944 27221305808 945 27364496152 946 27508302696 947 27652698896 948 27797715152 949 27943324808 950 28089558392 951 28236389136 952 28383847696 953 28531907192 954 28680598408 955 28829894352 956 28979825936 957 29130366056 958 29281545752 959 29433337808 960 29585773393 961 29738825177 962 29892524459 963 30046843796 964 30201814616 965 30357409363 966 30513659594 967 30670537640 968 30828075188 969 30986244455 970 31145077258 971 31304545700 972 31464681729 973 31625457333 974 31786904591 975 31948995377 976 32111761900 977 32275175920 978 32439269777 979 32604015116 980 32769444409 981 32935529185 982 33102302048 983 33269734412 984 33437859013 985 33606647149 986 33776131688 987 33946283813 988 34117136524 989 34288660888 990 34460890038 991 34633794924 992 34807408813 993 34981702538 994 35156709499 995 35332400413 996 35508808813 997 35685905299 998 35863723538 999 36042234013 1000 36221470525