0 0 1 1 2 2 3 3 4 5 5 7 6 7 7 7 8 12 9 18 10 18 11 22 12 23 13 25 14 19 15 26 16 37 17 49 18 55 19 64 20 67 21 78 22 80 23 93 24 101 25 110 26 106 27 122 28 114 29 129 30 136 31 158 32 197 33 237 34 256 35 287 36 311 37 337 38 367 39 403 40 424 41 453 42 492 43 525 44 571 45 638 46 684 47 754 48 809 49 853 50 896 51 955 52 995 53 1075 54 1149 55 1226 56 1295 57 1412 58 1506 59 1650 60 1789 61 1953 62 2076 63 2275 64 2460 65 2672 66 2858 67 3063 68 3269 69 3511 70 3728 71 3959 72 4229 73 4505 74 4826 75 5160 76 5507 77 5845 78 6200 79 6548 80 6926 81 7333 82 7785 83 8261 84 8838 85 9393 86 10014 87 10681 88 11399 89 12145 90 12981 91 13779 92 14629 93 15479 94 16322 95 17249 96 18200 97 19204 98 20230 99 21387 100 22550 101 23802 102 25139 103 26566 104 28081 105 29737 106 31416 107 33165 108 35050 109 36950 110 38974 111 41221 112 43512 113 46036 114 48719 115 51529 116 54476 117 57620 118 60813 119 64237 120 67782 121 71435 122 75158 123 79117 124 83074 125 87362 126 91756 127 96571 128 101598 129 107072 130 112508 131 118442 132 124517 133 130996 134 137655 135 144840 136 152100 137 159836 138 167821 139 176165 140 184969 141 194250 142 203920 143 214235 144 225009 145 236265 146 247979 147 260222 148 272959 149 286146 150 299987 151 314208 152 329121 153 344534 154 360670 155 377439 156 395371 157 413909 158 433606 159 454253 160 475852 161 498399 162 522027 163 546634 164 572519 165 599461 166 627535 167 656768 168 687357 169 719005 170 752262 171 786868 172 823307 173 861067 174 900746 175 941754 176 984562 177 1028851 178 1074891 179 1122572 180 1172492 181 1223867 182 1277605 183 1333289 184 1391474 185 1451917 186 1515401 187 1581460 188 1651017 189 1723241 190 1798625 191 1877062 192 1958729 193 2043491 194 2131553 195 2223469 196 2318825 197 2418112 198 2521180 199 2628511 200 2740044 201 2856489 202 2977367 203 3103635 204 3235095 205 3371428 206 3512884 207 3660008 208 3812251 209 3970653 210 4134957 211 4305803 212 4483445 213 4668132 214 4859903 215 5059787 216 5267947 217 5484560 218 5710279 219 5945241 220 6189611 221 6442831 222 6705879 223 6978403 224 7261188 225 7554649 226 7858647 227 8174438 228 8502036 229 8841481 230 9193490 231 9559176 232 9938227 233 10331925 234 10740191 235 11163573 236 11602500 237 12056907 238 12527409 239 13015181 240 13520955 241 14045368 242 14589199 243 15154038 244 15739843 245 16347794 246 16978868 247 17634066 248 18314200 249 19020177 250 19751775 251 20510271 252 21296181 253 22109058 254 22950745 255 23822892 256 24725748 257 25661429 258 26629906 259 27633841 260 28673122 261 29750451 262 30865176 263 32021571 264 33218316 265 34458674 266 35741125 267 37070166 268 38444028 269 39866469 270 41337863 271 42862374 272 44439929 273 46075325 274 47766614 275 49520189 276 51334683 277 53214069 278 55158498 279 57172995 280 59255722 281 61411153 282 63638274 283 65941225 284 68321103 285 70780909 286 73323121 287 75952493 288 78671344 289 81482869 290 84389348 291 87396294 292 90504812 293 93719605 294 97043391 295 100480768 296 104033699 297 107706924 298 111501410 299 115424353 300 119479326 301 123669849 302 128003037 303 132483946 304 137117069 305 141907098 306 146858625 307 151976930 308 157267767 309 162734245 310 168382472 311 174216807 312 180243235 313 186463735 314 192886486 315 199516948 316 206364607 317 213432558 318 220734614 319 228273344 320 236061837 321 244102513 322 252406552 323 260980630 324 269836461 325 278976849 326 288415111 327 298157294 328 308213338 329 318590628 330 329300891 331 340354821 332 351766559 333 363544093 334 375702596 335 388251925 336 401205802 337 414571624 338 428363201 339 442593754 340 457275096 341 472417694 342 488036780 343 504143807 344 520754348 345 537881851 346 555543055 347 573758120 348 592547874 349 611924599 350 631914674 351 652531792 352 673799260 353 695730452 354 718350061 355 741675663 356 765732370 357 790534711 358 816108750 359 842474270 360 869658001 361 897679507 362 926568991 363 956354833 364 987065886 365 1018723910 366 1051363023 367 1085003953 368 1119680441 369 1155413513 370 1192236058 371 1230178352 372 1269274700 373 1309548429 374 1351040446 375 1393781778 376 1437813283 377 1483169581 378 1529898023 379 1578039440 380 1627643664 381 1678742903 382 1731390841 383 1785622674 384 1841493656 385 1899035695 386 1958307368 387 2019353228 388 2082228102 389 2146973027 390 2213650851 391 2282309574 392 2353014567 393 2425820556 394 2500791589 395 2577996013 396 2657496825 397 2739349320 398 2823624095 399 2910384317 400 2999697842 401 3091632171 402 3186260131 403 3283662577 404 3383913090 405 3487092246 406 3593280427 407 3702574653 408 3815061550 409 3930839758 410 4050000944 411 4172659198 412 4298900026 413 4428825860 414 4562535298 415 4700133674 416 4841725636 417 4987420005 418 5137323293 419 5291564012 420 5450251801 421 5613507327 422 5781456456 423 5954240327 424 6131985046 425 6314838657 426 6502931801 427 6696425046 428 6895447229 429 7100149455 430 7310672622 431 7527183640 432 7749835885 433 7978797273 434 8214233923 435 8456342836 436 8705290179 437 8961274561 438 9224487963 439 9495146668 440 9773454509 441 10059632970 442 10353885947 443 10656455507 444 10967547074 445 11287382742 446 11616196271 447 11954228614 448 12301725088 449 12658931958 450 13026113560 451 13403540689 452 13791489170 453 14190232565 454 14600070899 455 15021308980 456 15454260250 457 15899228253 458 16356533902 459 16826513141 460 17309482223 461 17805774845 462 18315746501 463 18839757273 464 19378189211 465 19931418658 466 20499842457 467 21083886995 468 21683964603 469 22300503166 470 22933954839 471 23584787948 472 24253459369 473 24940443790 474 25646207111 475 26371255135 476 27116062286 477 27881135129 478 28666991472 479 29474180073 480 30303256365 481 31154773854 482 32029323293 483 32927519256 484 33849968075 485 34797299548 486 35770175085 487 36769264418 488 37795252134 489 38848820369 490 39930663673 491 41041528795 492 42182135138 493 43353238839 494 44555635320 495 45790148165 496 47057614210 497 48358885673 498 49694848807 499 51066428385 500 52474546081 501 53920151388 502 55404221135 503 56927765420 504 58491789647 505 60097304730 506 61745347764 507 63437014491 508 65173370489 509 66955541088 510 68784694638 511 70662025814 512 72588776694 513 74566174894 514 76595523289 515 78678157264 516 80815438731 517 83008727092 518 85259478842 519 87569136145 520 89939192954 521 92371124228 522 94866486181 523 97426872810 524 100053910742 525 102749260853 526 105514670610 527 108351921588 528 111262855171 529 114249295658 530 117313175596 531 120456467832 532 123681158346 533 126989277128 534 130382917811 535 133864205585 536 137435294411 537 141098364879 538 144855644402 539 148709497532 540 152662254033 541 156716362860 542 160874331473 543 165138770439 544 169512304042 545 173997627456 546 178597507471 547 183314825533 548 188152463568 549 193113395624 550 198200650290 551 203417361528 552 208766674516 553 214251810182 554 219876069220 555 225642940655 556 231555867094 557 237618491472 558 243834491099 559 250207707049 560 256741988469 561 263441297594 562 270309648808 563 277351266372 564 284570309900 565 291971109305 566 299558028041 567 307335610683 568 315308366867 569 323480995928 570 331858241728 571 340445142378 572 349246674361 573 358268093337 574 367514676023 575 376991967787 576 386705507181 577 396660998276 578 406864268857 579 417321381186 580 428038382912 581 439021527548 582 450277181073 583 461811884387 584 473632283485 585 485745169471 586 498157524905 587 510876628805 588 523909796108 589 537264581738 590 550948712040 591 564970126220 592 579336865285 593 594057121571 594 609139312565 595 624592080345 596 640424153136 597 656644457870 598 673262116087 599 690286500762 600 707727138786 601 725593769111 602 743896431542 603 762645545535 604 781851595124 605 801525443512 606 821678147892 607 842321098130 608 863465856961 609 885124218162 610 907308285247 611 930030517339 612 953303506639 613 977140122631 614 1001553577145 615 1026557384076 616 1052165341200 617 1078391530249 618 1105250476572 619 1132757122361 620 1160926622885 621 1189774509555 622 1219316645227 623 1249569286244 624 1280548964875 625 1312272467049 626 1344757077319 627 1378020470453 628 1412080567424 629 1446955683807 630 1482664601525 631 1519226532908 632 1556661149040 633 1594988510410 634 1634229289419 635 1674404766207 636 1715536518651 637 1757646656560 638 1800757803778 639 1844893114622 640 1890076178737 641 1936330995312 642 1983682266033 643 2032155189708 644 2081775469284 645 2132569245390 646 2184563431052 647 2237785454063 648 2292263505612 649 2348026144620 650 2405102968475 651 2463524112836 652 2523320353049 653 2584522973471 654 2647164136880 655 2711276498425 656 2776893579731 657 2844049240718 658 2912778484985 659 2983116872582 660 3055100825213 661 3128767277485 662 3204154402956 663 3281301015992 664 3360247072183 665 3441033110469 666 3523701052053 667 3608293593015 668 3694854373497 669 3783427792358 670 3874059402730 671 3966795636180 672 4061683997549 673 4158772654395 674 4258111249994 675 4359750305952 676 4463741437336 677 4570137172652 678 4678991550043 679 4790359607658 680 4904297863880 681 5020863674207 682 5140116119946 683 5262115403423 684 5386922912158 685 5514601110423 686 5645214016829 687 5778826879980 688 5915506367294 689 6055320253939 690 6198338181949 691 6344631158763 692 6494271706800 693 6647333790223 694 6803893309780 695 6964027873025 696 7127816890981 697 7295341248712 698 7466683991668 699 7641929948810 700 7821165400153 701 8004478506180 702 8191959266922 703 8383699720364 704 8579793676013 705 8780336766524 706 8985426891312 707 9195164143452 708 9409650467537 709 9628989983557 710 9853289326752 711 10082657495506 712 10317205827983 713 10557047757532 714 10802299513873 715 11053079665210 716 11309508969947 717 11571710592059 718 11839810387866 719 12113936949117 720 12394221494341 721 12680797668154 722 12973802513565 723 13273375922305 724 13579660658905 725 13892802501107 726 14212950798797 727 14540258114248 728 14874880415947 729 15216976526059 730 15566709095607 731 15924244098591 732 16289750535095 733 16663400826020 734 17045371094678 735 17435841288633 736 17834994834111 737 18243018770571 738 18660104452790 739 19086447281509 740 19522246505903 741 19967705550561 742 20423032448721 743 20888439754264 744 21364144388958 745 21850367253196 746 22347334372447 747 22855276259965 748 23374427687120 749 23905028240659 750 24447322621439 751 25001560804508 752 25567997829178 753 26146893736169 754 26738514603662 755 27343132236925 756 27961023882689 757 28592472636555 758 29237768027326 759 29897205799143 760 30571087653940 761 31259721055760 762 31963420228057 763 32682505741017 764 33417304067272 765 34168148430092 766 34935378829286 767 35719342785534 768 36520394399569 769 37338894889217 770 38175213410220 771 39029727007636 772 39902819942938 773 40794884651562 774 41706321944564 775 42637541088718 776 43588959469096 777 44561002273730 778 45554103928273 779 46568707548185 780 47605264700706 781 48664236038148 782 49746092096624 783 50851313320135 784 51980389834860 785 53133821376664 786 54312119008657 787 55515804203146 788 56745409151767 789 58001476679974 790 59284561518196 791 60595229564835 792 61934058126205 793 63301634871988 794 64698560403858 795 66125446780994 796 67582917949407 797 69071610138058 798 70592172950300 799 72145269276702 800 73731575239843 801 75351779945659 802 77006587558091 803 78696716519428 804 80422899540877 805 82185883871927 806 83986432674354 807 85825324307779 808 87703352476299 809 89621325538535 810 91580069203722 811 93580425190916 812 95623251865123 813 97709424589342 814 99839837146219 815 102015401816456 816 104237049079719 817 106505727500673 818 108822406292907 819 111188074197402 820 113603739511502 821 116070430612019 822 118589197102952 823 121161109405937 824 123787258634678 825 126468756174135 826 129206736368455 827 132002355908956 828 134856793502878 829 137771251429947 830 140746956225283 831 143785159861761 832 146887138102222 833 150054192162954 834 153287649901279 835 156588866380765 836 159959222419584 837 163400126719821 838 166913015745210 839 170499355183952 840 174160638100076 841 177898386236637 842 181714152193319 843 185609519693704 844 189586102516866 845 193645547253994 846 197789533324571 847 202019774922048 848 206338019005330 849 210746047106444 850 215245676925063 851 219838762930077 852 224527194680509 853 229312899014527 854 234197840535565 855 239184022658838 856 244273486070123 857 249468310203429 858 254770615962670 859 260182565967672 860 265706363819397 861 271344256923451 862 277098536769073 863 282971541634833 864 288965653736387 865 295083302129900 866 301326964334787 867 307699167543462 868 314202486217045 869 320839545797417 870 327613022316213 871 334525644920796 872 341580193604917 873 348779501766204 874 356126458981500 875 363624012281305 876 371275164556587 877 379082978406376 878 387050576464093 879 395181144404302 880 403477927722454 881 411944235353596 882 420583441368483 883 429398986309639 884 438394374903627 885 447573179748588 886 456939041448143 887 466495671714621 888 476246850701254 889 486196430355789 890 496348338066695 891 506706578040597 892 517275229588155 893 528058452285937 894 539060485704397 895 550285654023088 896 561738361820168 897 573423099324701 898 585344443593241 899 597507061887176 900 609915707508910 901 622575225998779 902 635490554459153 903 648666726601657 904 662108868787972 905 675822205791276 906 689812063817877 907 704083873218564 908 718643166349332 909 733495583351137 910 748646872274957 911 764102894323993 912 779869619351767 913 795953131235641 914 812359630967553 915 829095438544833 916 846166990486785 917 863580845259346 918 881343684856813 919 899462318711930 920 917943682402922 921 936794841640416 922 956022999142846 923 975635495526080 924 995639809552213 925 1016043562574612 926 1036854522087245 927 1058080605320062 928 1079729876932808 929 1101810554006838 930 1124331011482471 931 1147299783320513 932 1170725561939728 933 1194617203131217 934 1218983729968882 935 1243834337082511 936 1269178390105554 937 1295025429992825 938 1321385182523414 939 1348267557862517 940 1375682652444681 941 1403640753095568 942 1432152342399960 943 1461228101641679 944 1490878910374963 945 1521115850125087 946 1551950213185985 947 1583393502481568 948 1615457433049922 949 1648153936243120 950 1681495167563580 951 1715493509640335 952 1750161574534778 953 1785512207911472 954 1821558501812613 955 1858313793411363 956 1895791669474525 957 1934005970114111 958 1972970796826028 959 2012700516648302 960 2053209761735629 961 2094513435261847 962 2136626721746811 963 2179565088331932 964 2223344285964582 965 2267980357277718 966 2313489643792050 967 2359888792810775 968 2407194758368742 969 2455424808691640 970 2504596538891291 971 2554727872643401 972 2605837064738707 973 2657942708037038 974 2711063741928108 975 2765219458496780 976 2820429501701240 977 2876713876081819 978 2934092958366530 979 2992587500084969 980 3052218630743526 981 3113007866627479 982 3174977121871186 983 3238148716733482 984 3302545380640288 985 3368190260663608 986 3435106939333502 987 3503319435051952 988 3572852208405015 989 3643730169762576 990 3715978691584711 991 3789623615477237 992 3864691254137578 993 3941208400973713 994 4019202345682318 995 4098700878419802 996 4179732294119277 997 4262325404293083 998 4346509551029657 999 4432314617541546 1000 4519771031733817