0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 21 9 28 10 38 11 49 12 65 13 82 14 105 15 131 16 164 17 201 18 248 19 300 20 364 21 436 22 522 23 618 24 733 25 860 26 1009 27 1175 28 1367 29 1579 30 1824 31 2093 32 2400 33 2738 34 3120 35 3539 36 4011 37 4526 38 5102 39 5731 40 6430 41 7190 42 8033 43 8946 44 9953 45 11044 46 12241 47 13534 48 14950 49 16475 50 18138 51 19928 52 21873 53 23961 54 26226 55 28652 56 31275 57 34082 58 37108 59 40340 60 43819 61 47527 62 51508 63 55748 64 60289 65 65117 66 70281 67 75762 68 81612 69 87816 70 94425 71 101423 72 108869 73 116742 74 125104 75 133939 76 143307 77 153192 78 163662 79 174696 80 186366 81 198655 82 211634 83 225286 84 239691 85 254826 86 270775 87 287521 88 305146 89 323633 90 343074 91 363446 92 384845 93 407254 94 430768 95 455370 96 481165 97 508130 98 536375 99 565883 100 596763 101 628998 102 662708 103 697870 104 734609 105 772909 106 812893 107 854546 108 898003 109 943242 110 990404 111 1039474 112 1090592 113 1143743 114 1199080 115 1256582 116 1316407 117 1378542 118 1443144 119 1510201 120 1579883 121 1652171 122 1727242 123 1805085 124 1885876 125 1969605 126 2056462 127 2146430 128 2239706 129 2336282 130 2436354 131 2539915 132 2647176 133 2758123 134 2872974 135 2991725 136 3114593 137 3241575 138 3372904 139 3508570 140 3648814 141 3793635 142 3943274 143 4097732 144 4257266 145 4421870 146 4591809 147 4767088 148 4947971 149 5134465 150 5326852 151 5525131 152 5729593 153 5940248 154 6157387 155 6381022 156 6611462 157 6848712 158 7093090 159 7344613 160 7603599 161 7870067 162 8144354 163 8426472 164 8716768 165 9015266 166 9322313 167 9637936 168 9962502 169 10296030 170 10638898 171 10991138 172 11353128 173 11724903 174 12106862 175 12499033 176 12901825 177 13315280 178 13739808 179 14175454 180 14622650 181 15081433 182 15552247 183 16035143 184 16530566 185 17038571 186 17559625 187 18093776 188 18641503 189 19202869 190 19778354 191 20368025 192 20972386 193 21591496 194 22225872 195 22875589 196 23541165 197 24222679 198 24920674 199 25635222 200 26366879 201 27115733 202 27882342 203 28666799 204 29469687 205 30291092 206 31131611 207 31991347 208 32870899 209 33770375 210 34690401 211 35631077 212 36593044 213 37576420 214 38581848 215 39609452 216 40659902 217 41733315 218 42830376 219 43951221 220 45096538 221 46266468 222 47461728 223 48682452 224 49929373 225 51202644 226 52503001 227 53830604 228 55186218 229 56569996 230 57982720 231 59424563 232 60896310 233 62398141 234 63930872 235 65494676 236 67090386 237 68718196 238 70378943 239 72072828 240 73800720 241 75562813 242 77359994 243 79192479 244 81061159 245 82966258 246 84908699 247 86888700 248 88907203 249 90964448 250 93061382 251 95198253 252 97376042 253 99594990 254 101856098 255 104159631 256 106506594 257 108897261 258 111332672 259 113813095 260 116339590 261 118912449 262 121532738 263 124200758 264 126917611 265 129683592 266 132499824 267 135366627 268 138285130 269 141255663 270 144279392 271 147356641 272 150488598 273 153675613 274 156918880 275 160218760 276 163576485 277 166992410 278 170467790 279 174003007 280 177599323 281 181257130 282 184977730 283 188761510 284 192609795 285 196523000 286 200502457 287 204548593 288 208662780 289 212845440 290 217097970 291 221420820 292 225815395 293 230282157 294 234822553 295 239437040 296 244127090 297 248893190 298 253736820 299 258658480 300 263659693 301 268740954 302 273903812 303 279148793 304 284477455 305 289890337 306 295389041 307 300974102 308 306647149 309 312408748 310 318260538 311 324203099 312 330238115 313 336366162 314 342588952 315 348907094 316 355322309 317 361835221 318 368447598 319 375160060 320 381974404 321 388891283 322 395912505 323 403038738 324 410271838 325 417612470 326 425062519 327 432622685 328 440294864 329 448079772 330 455979354 331 463994323 332 472126655 333 480377098 334 488747640 335 497239046 336 505853354 337 514591326 338 523455032 339 532445271 340 541564125 341 550812410 342 560192260 343 569704489 344 579351263 345 589133434 346 599053181 347 609111374 348 619310245 349 629650662 350 640134891 351 650763838 352 661539783 353 672463651 354 683537776 355 694763082 356 706141937 357 717675305 358 729365568 359 741213710 360 753222169 361 765391927 362 777725458 363 790223785 364 802889397 365 815723337 366 828728151 367 841904882 368 855256112 369 868782926 370 882487922 371 896372206 372 910438434 373 924687712 374 939122734 375 953744649 376 968556167 377 983558459 378 998754295 379 1014144846 380 1029732921 381 1045519735 382 1061508114 383 1077699296 384 1094096168 385 1110699969 386 1127513625 387 1144538421 388 1161777301 389 1179231573 390 1196904244 391 1214796623 392 1232911758 393 1251251004 394 1269817428 395 1288612410 396 1307639080 397 1326898820 398 1346394802 399 1366128456 400 1386102973 401 1406319808 402 1426782218 403 1447491660 404 1468451434 405 1489663046 406 1511129816 407 1532853276 408 1554836813 409 1577081962 410 1599592154 411 1622368974 412 1645415874 413 1668734466 414 1692328270 415 1716198902 416 1740349927 417 1764783012 418 1789501744 419 1814507818 420 1839804891 421 1865394661 422 1891280832 423 1917465155 424 1943951356 425 1970741215 426 1997838529 427 2025245083 428 2052964721 429 2080999282 430 2109352634 431 2138026645 432 2167025256 433 2196350340 434 2226005887 435 2255993825 436 2286318168 437 2316980875 438 2347986034 439 2379335610 440 2411033741 441 2443082448 442 2475485894 443 2508246132 444 2541367401 445 2574851760 446 2608703499 447 2642924735 448 2677519784 449 2712490795 450 2747842162 451 2783576041 452 2819696878 453 2856206888 454 2893110544 455 2930410095 456 2968110092 457 3006212792 458 3044722800 459 3083642433 460 3122976324 461 3162726824 462 3202898647 463 3243494152 464 3284518108 465 3325972936 466 3367863433 467 3410192056 468 3452963684 469 3496180783 470 3539848288 471 3583968728 472 3628547068 473 3673585873 474 3719090192 475 3765062600 476 3811508203 477 3858429640 478 3905832048 479 3953718104 480 4002093030 481 4050959513 482 4100322834 483 4150185746 484 4200553561 485 4251429071 486 4302817675 487 4354722176 488 4407148033 489 4460098116 490 4513577917 491 4567590345 492 4622140981 493 4677232746 494 4732871282 495 4789059579 496 4845803312 497 4903105512 498 4960971944 499 5019405652 500 5078412464 501 5137995493 502 5198160602 503 5258910946 504 5320252480 505 5382188372 506 5444724641 507 5507864527 508 5571614084 509 5635976595 510 5700958208 511 5766562220 512 5832794844 513 5899659450 514 5967162288 515 6035306772 516 6104099247 517 6173543142 518 6243644869 519 6314407931 520 6385838778 521 6457940958 522 6530721018 523 6604182522 524 6678332085 525 6753173347 526 6828712961 527 6904954614 528 6981905058 529 7059567996 530 7137950250 531 7217055600 532 7296890908 533 7377460001 534 7458769842 535 7540824276 536 7623630336 537 7707191946 538 7791516180 539 7876607011 540 7962471615 541 8049113983 542 8136541364 543 8224757829 544 8313770669 545 8403584005 546 8494205232 547 8585638490 548 8677891248 549 8770967728 550 8864875442 551 8959618663 552 9055205009 553 9151638773 554 9248927648 555 9347076011 556 9446091599 557 9545978841 558 9646745582 559 9748396272 560 9850938833 561 9954377799 562 10058721138 563 10163973438 564 10270142776 565 10377233762 566 10485254551 567 10594209840 568 10704107830 569 10814953273 570 10926754482 571 11039516231 572 11153246913 573 11267951390 574 11383638103 575 11500311970 576 11617981545 577 11736651770 578 11856331280 579 11977025107 580 12098741935 581 12221486853 582 12345268660 583 12470092470 584 12595967165 585 12722897950 586 12850893757 587 12979959850 588 13110105278 589 13241335330 590 13373659140 591 13507082090 592 13641613365 593 13777258407 594 13914026520 595 14051923173 596 14190957755 597 14331135830 598 14472466840 599 14614956410 600 14758614103 601 14903445571 602 15049460465 603 15196664533 604 15345067480 605 15494675117 606 15645497271 607 15797539782 608 15950812566 609 16105321561 610 16261076738 611 16418084099 612 16576353740 613 16735891692 614 16896708142 615 17058809221 616 17222205172 617 17386902191 618 17552910648 619 17720236770 620 17888891019 621 18058879723 622 18230213402 623 18402898451 624 18576945518 625 18752361030 626 18929155729 627 19107336145 628 19286913079 629 19467893129 630 19650287227 631 19834102003 632 20019348485 633 20206033408 634 20394167860 635 20583758646 636 20774816986 637 20967349719 638 21161368162 639 21356879261 640 21553894395 641 21752420580 642 21952469330 643 22154047696 644 22357167291 645 22561835274 646 22768063321 647 22975858664 648 23185233115 649 23396193942 650 23608753058 651 23822917841 652 24038700268 653 24256107791 654 24475152526 655 24695841962 656 24918188317 657 25142199192 658 25367886871 659 25595259030 660 25824328094 661 26055101777 662 26287592608 663 26521808415 664 26757761794 665 26995460650 666 27234917721 667 27476140952 668 27719143187 669 27963932486 670 28210521762 671 28458919153 672 28709137717 673 28961185632 674 29215076064 675 29470817309 676 29728422602 677 29987900319 678 30249263842 679 30512521589 680 30777687051 681 31044768765 682 31313780294 683 31584730256 684 31857632363 685 32132495276 686 32409332818 687 32688153771 688 32968972031 689 33251796463 690 33536641114 691 33823514893 692 34112431960 693 34403401347 694 34696437288 695 34991548900 696 35288750570 697 35588051460 698 35889466072 699 36193003693 700 36498678901 701 36806501068 702 37116484928 703 37428639900 704 37742980834 705 38059517276 706 38378264153 707 38699231099 708 39022433198 709 39347880132 710 39675587104 711 40005563924 712 40337825874 713 40672382853 714 41009250303 715 41348438172 716 41689962022 717 42033831932 718 42380063544 719 42728667028 720 43079658188 721 43433047244 722 43788850122 723 44147077175 724 44507744411 725 44870862275 726 45236446939 727 45604508900 728 45975064454 729 46348124232 730 46723704614 731 47101816325 732 47482475911 733 47865694150 734 48251487714 735 48639867518 736 49030850318 737 49424447125 738 49820674864 739 50219544600 740 50621073386 741 51025272425 742 51432158857 743 51841743982 744 52254045111 745 52669073600 746 53086846889 747 53507376475 748 53930679886 749 54356768718 750 54785660672 751 55217367401 752 55651906738 753 56089290478 754 56529536544 755 56972656832 756 57418669440 757 57867586322 758 58319425710 759 58774199703 760 59231926624 761 59692618674 762 60156294354 763 60622965925 764 61092652023 765 61565365056 766 62041123753 767 62519940626 768 63001834584 769 63486818200 770 63974910521 771 64466124268 772 64960478583 773 65457986293 774 65958666722 775 66462532760 776 66969603870 777 67479893093 778 67993419988 779 68510197704 780 69030245985 781 69553578043 782 70080213764 783 70610166513 784 71143456274 785 71680096521 786 72220107425 787 72763502526 788 73310302138 789 73860519956 790 74414176394 791 74971285258 792 75531867151 793 76095935946 794 76663512392 795 77234610519 796 77809251177 797 78387448509 798 78969223557 799 79554590532 800 80143570624 801 80736178203 802 81332434562 803 81932354186 804 82535958562 805 83143262245 806 83754286871 807 84369047157 808 84987564844 809 85609854765 810 86235938858 811 86865832027 812 87499556362 813 88137126930 814 88778565928 815 89423888542 816 90073117167 817 90726267062 818 91383360776 819 92044413734 820 92709448593 821 93378480898 822 94051533508 823 94728622042 824 95409769515 825 96094991714 826 96784311764 827 97477745574 828 98175316473 829 98877040446 830 99582940980 831 100293034230 832 101007343795 833 101725885954 834 102448684512 835 103175755826 836 103907123861 837 104642805146 838 105382823760 839 106127196358 840 106875947228 841 107629093103 842 108386658434 843 109148660129 844 109915122754 845 110686063345 846 111461506679 847 112241469873 848 113025977868 849 113815047958 850 114608705202 851 115406967023 852 116209858694 853 117017397720 854 117829609541 855 118646511841 856 119468130179 857 120294482371 858 121125594192 859 121961483542 860 122802176365 861 123647690742 862 124498052738 863 125353280568 864 126213400516 865 127078430882 866 127948398121 867 128823320717 868 129703225248 869 130588130333 870 131478062772 871 132373041271 872 133273092803 873 134178236260 874 135088498740 875 136003899273 876 136924465180 877 137850215580 878 138781177970 879 139717371657 880 140658824265 881 141605555240 882 142557592433 883 143514955380 884 144477672110 885 145445762350 886 146419254257 887 147398167700 888 148382531065 889 149372364313 890 150367696010 891 151368546310 892 152374943910 893 153386909107 894 154404470830 895 155427649470 896 156456474138 897 157490965420 898 158531152560 899 159577056290 900 160628706088 901 161686122781 902 162749336032 903 163818366866 904 164893245080 905 165973991847 906 167060637201 907 168153202412 908 169251717701 909 170356204538 910 171466693281 911 172583205549 912 173705771940 913 174834414172 914 175969163032 915 177110040441 916 178257077324 917 179410295754 918 180569726898 919 181735392930 920 182907325209 921 184085546113 922 185270087142 923 186460970828 924 187658228916 925 188861884040 926 190071968139 927 191288504055 928 192511523869 929 193741050579 930 194977116514 931 196219744776 932 197468967890 933 198724809168 934 199987301280 935 201256467696 936 202532341336 937 203814945776 938 205104314135 939 206400470201 940 207703447240 941 209013269200 942 210329969600 943 211653572496 944 212984111608 945 214321611207 946 215666105161 947 217017617904 948 218376183560 949 219741826672 950 221114581568 951 222494473008 952 223881535471 953 225275793881 954 226677282976 955 228086027792 956 229502063272 957 230925414672 958 232356117088 959 233794195943 960 235239686594 961 236692614577 962 238153015458 963 239620914995 964 241096348909 965 242579343127 966 244069933634 967 245568146472 968 247074017837 969 248587573996 970 250108851302 971 251637876193 972 253174685289 973 254719305145 974 256271772594 975 257832114419 976 259400367612 977 260976559129 978 262560726232 979 264152895996 980 265753105899 981 267361383245 982 268977765674 983 270602280666 984 272234966133 985 273875849676 986 275524969425 987 277182353214 988 278848039336 989 280522055803 990 282204441184 991 283895223613 992 285594441880 993 287302124354 994 289018309991 995 290743027340 996 292476315635 997 294218203550 998 295968730542 999 297727925523 1000 299495828118