0 0 1 1 2 2 3 6 4 16 5 35 6 66 7 112 8 176 9 261 10 370 11 506 12 672 13 871 14 1106 15 1380 16 1696 17 2057 18 2466 19 2926 20 3440 21 4011 22 4642 23 5336 24 6096 25 6925 26 7826 27 8802 28 9856 29 10991 30 12210 31 13516 32 14912 33 16401 34 17986 35 19670 36 21456 37 23347 38 25346 39 27456 40 29680 41 32021 42 34482 43 37066 44 39776 45 42615 46 45586 47 48692 48 51936 49 55321 50 58850 51 62526 52 66352 53 70331 54 74466 55 78760 56 83216 57 87837 58 92626 59 97586 60 102720 61 108031 62 113522 63 119196 64 125056 65 131105 66 137346 67 143782 68 150416 69 157251 70 164290 71 171536 72 178992 73 186661 74 194546 75 202650 76 210976 77 219527 78 228306 79 237316 80 246560 81 256041 82 265762 83 275726 84 285936 85 296395 86 307106 87 318072 88 329296 89 340781 90 352530 91 364546 92 376832 93 389391 94 402226 95 415340 96 428736 97 442417 98 456386 99 470646 100 485200 101 500051 102 515202 103 530656 104 546416 105 562485 106 578866 107 595562 108 612576 109 629911 110 647570 111 665556 112 683872 113 702521 114 721506 115 740830 116 760496 117 780507 118 800866 119 821576 120 842640 121 864061 122 885842 123 907986 124 930496 125 953375 126 976626 127 1000252 128 1024256 129 1048641 130 1073410 131 1098566 132 1124112 133 1150051 134 1176386 135 1203120 136 1230256 137 1257797 138 1285746 139 1314106 140 1342880 141 1372071 142 1401682 143 1431716 144 1462176 145 1493065 146 1524386 147 1556142 148 1588336 149 1620971 150 1654050 151 1687576 152 1721552 153 1755981 154 1790866 155 1826210 156 1862016 157 1898287 158 1935026 159 1972236 160 2009920 161 2048081 162 2086722 163 2125846 164 2165456 165 2205555 166 2246146 167 2287232 168 2328816 169 2370901 170 2413490 171 2456586 172 2500192 173 2544311 174 2588946 175 2634100 176 2679776 177 2725977 178 2772706 179 2819966 180 2867760 181 2916091 182 2964962 183 3014376 184 3064336 185 3114845 186 3165906 187 3217522 188 3269696 189 3322431 190 3375730 191 3429596 192 3484032 193 3539041 194 3594626 195 3650790 196 3707536 197 3764867 198 3822786 199 3881296 200 3940400 201 4000101 202 4060402 203 4121306 204 4182816 205 4244935 206 4307666 207 4371012 208 4434976 209 4499561 210 4564770 211 4630606 212 4697072 213 4764171 214 4831906 215 4900280 216 4969296 217 5038957 218 5109266 219 5180226 220 5251840 221 5324111 222 5397042 223 5470636 224 5544896 225 5619825 226 5695426 227 5771702 228 5848656 229 5926291 230 6004610 231 6083616 232 6163312 233 6243701 234 6324786 235 6406570 236 6489056 237 6572247 238 6656146 239 6740756 240 6826080 241 6912121 242 6998882 243 7086366 244 7174576 245 7263515 246 7353186 247 7443592 248 7534736 249 7626621 250 7719250 251 7812626 252 7906752 253 8001631 254 8097266 255 8193660 256 8290816 257 8388737 258 8487426 259 8586886 260 8687120 261 8788131 262 8889922 263 8992496 264 9095856 265 9200005 266 9304946 267 9410682 268 9517216 269 9624551 270 9732690 271 9841636 272 9951392 273 10061961 274 10173346 275 10285550 276 10398576 277 10512427 278 10627106 279 10742616 280 10858960 281 10976141 282 11094162 283 11213026 284 11332736 285 11453295 286 11574706 287 11696972 288 11820096 289 11944081 290 12068930 291 12194646 292 12321232 293 12448691 294 12577026 295 12706240 296 12836336 297 12967317 298 13099186 299 13231946 300 13365600 301 13500151 302 13635602 303 13771956 304 13909216 305 14047385 306 14186466 307 14326462 308 14467376 309 14609211 310 14751970 311 14895656 312 15040272 313 15185821 314 15332306 315 15479730 316 15628096 317 15777407 318 15927666 319 16078876 320 16231040 321 16384161 322 16538242 323 16693286 324 16849296 325 17006275 326 17164226 327 17323152 328 17483056 329 17643941 330 17805810 331 17968666 332 18132512 333 18297351 334 18463186 335 18630020 336 18797856 337 18966697 338 19136546 339 19307406 340 19479280 341 19652171 342 19826082 343 20001016 344 20176976 345 20353965 346 20531986 347 20711042 348 20891136 349 21072271 350 21254450 351 21437676 352 21621952 353 21807281 354 21993666 355 22181110 356 22369616 357 22559187 358 22749826 359 22941536 360 23134320 361 23328181 362 23523122 363 23719146 364 23916256 365 24114455 366 24313746 367 24514132 368 24715616 369 24918201 370 25121890 371 25326686 372 25532592 373 25739611 374 25947746 375 26157000 376 26367376 377 26578877 378 26791506 379 27005266 380 27220160 381 27436191 382 27653362 383 27871676 384 28091136 385 28311745 386 28533506 387 28756422 388 28980496 389 29205731 390 29432130 391 29659696 392 29888432 393 30118341 394 30349426 395 30581690 396 30815136 397 31049767 398 31285586 399 31522596 400 31760800 401 32000201 402 32240802 403 32482606 404 32725616 405 32969835 406 33215266 407 33461912 408 33709776 409 33958861 410 34209170 411 34460706 412 34713472 413 34967471 414 35222706 415 35479180 416 35736896 417 35995857 418 36256066 419 36517526 420 36780240 421 37044211 422 37309442 423 37575936 424 37843696 425 38112725 426 38383026 427 38654602 428 38927456 429 39201591 430 39477010 431 39753716 432 40031712 433 40311001 434 40591586 435 40873470 436 41156656 437 41441147 438 41726946 439 42014056 440 42302480 441 42592221 442 42883282 443 43175666 444 43469376 445 43764415 446 44060786 447 44358492 448 44657536 449 44957921 450 45259650 451 45562726 452 45867152 453 46172931 454 46480066 455 46788560 456 47098416 457 47409637 458 47722226 459 48036186 460 48351520 461 48668231 462 48986322 463 49305796 464 49626656 465 49948905 466 50272546 467 50597582 468 50924016 469 51251851 470 51581090 471 51911736 472 52243792 473 52577261 474 52912146 475 53248450 476 53586176 477 53925327 478 54265906 479 54607916 480 54951360 481 55296241 482 55642562 483 55990326 484 56339536 485 56690195 486 57042306 487 57395872 488 57750896 489 58107381 490 58465330 491 58824746 492 59185632 493 59547991 494 59911826 495 60277140 496 60643936 497 61012217 498 61381986 499 61753246 500 62126000 501 62500251 502 62876002 503 63253256 504 63632016 505 64012285 506 64394066 507 64777362 508 65162176 509 65548511 510 65936370 511 66325756 512 66716672 513 67109121 514 67503106 515 67898630 516 68295696 517 68694307 518 69094466 519 69496176 520 69899440 521 70304261 522 70710642 523 71118586 524 71528096 525 71939175 526 72351826 527 72766052 528 73181856 529 73599241 530 74018210 531 74438766 532 74860912 533 75284651 534 75709986 535 76136920 536 76565456 537 76995597 538 77427346 539 77860706 540 78295680 541 78732271 542 79170482 543 79610316 544 80051776 545 80494865 546 80939586 547 81385942 548 81833936 549 82283571 550 82734850 551 83187776 552 83642352 553 84098581 554 84556466 555 85016010 556 85477216 557 85940087 558 86404626 559 86870836 560 87338720 561 87808281 562 88279522 563 88752446 564 89227056 565 89703355 566 90181346 567 90661032 568 91142416 569 91625501 570 92110290 571 92596786 572 93084992 573 93574911 574 94066546 575 94559900 576 95054976 577 95551777 578 96050306 579 96550566 580 97052560 581 97556291 582 98061762 583 98568976 584 99077936 585 99588645 586 100101106 587 100615322 588 101131296 589 101649031 590 102168530 591 102689796 592 103212832 593 103737641 594 104264226 595 104792590 596 105322736 597 105854667 598 106388386 599 106923896 600 107461200 601 108000301 602 108541202 603 109083906 604 109628416 605 110174735 606 110722866 607 111272812 608 111824576 609 112378161 610 112933570 611 113490806 612 114049872 613 114610771 614 115173506 615 115738080 616 116304496 617 116872757 618 117442866 619 118014826 620 118588640 621 119164311 622 119741842 623 120321236 624 120902496 625 121485625 626 122070626 627 122657502 628 123246256 629 123836891 630 124429410 631 125023816 632 125620112 633 126218301 634 126818386 635 127420370 636 128024256 637 128630047 638 129237746 639 129847356 640 130458880 641 131072321 642 131687682 643 132304966 644 132924176 645 133545315 646 134168386 647 134793392 648 135420336 649 136049221 650 136680050 651 137312826 652 137947552 653 138584231 654 139222866 655 139863460 656 140506016 657 141150537 658 141797026 659 142445486 660 143095920 661 143748331 662 144402722 663 145059096 664 145717456 665 146377805 666 147040146 667 147704482 668 148370816 669 149039151 670 149709490 671 150381836 672 151056192 673 151732561 674 152410946 675 153091350 676 153773776 677 154458227 678 155144706 679 155833216 680 156523760 681 157216341 682 157910962 683 158607626 684 159306336 685 160007095 686 160709906 687 161414772 688 162121696 689 162830681 690 163541730 691 164254846 692 164970032 693 165687291 694 166406626 695 167128040 696 167851536 697 168577117 698 169304786 699 170034546 700 170766400 701 171500351 702 172236402 703 172974556 704 173714816 705 174457185 706 175201666 707 175948262 708 176696976 709 177447811 710 178200770 711 178955856 712 179713072 713 180472421 714 181233906 715 181997530 716 182763296 717 183531207 718 184301266 719 185073476 720 185847840 721 186624361 722 187403042 723 188183886 724 188966896 725 189752075 726 190539426 727 191328952 728 192120656 729 192914541 730 193710610 731 194508866 732 195309312 733 196111951 734 196916786 735 197723820 736 198533056 737 199344497 738 200158146 739 200974006 740 201792080 741 202612371 742 203434882 743 204259616 744 205086576 745 205915765 746 206747186 747 207580842 748 208416736 749 209254871 750 210095250 751 210937876 752 211782752 753 212629881 754 213479266 755 214330910 756 215184816 757 216040987 758 216899426 759 217760136 760 218623120 761 219488381 762 220355922 763 221225746 764 222097856 765 222972255 766 223848946 767 224727932 768 225609216 769 226492801 770 227378690 771 228266886 772 229157392 773 230050211 774 230945346 775 231842800 776 232742576 777 233644677 778 234549106 779 235455866 780 236364960 781 237276391 782 238190162 783 239106276 784 240024736 785 240945545 786 241868706 787 242794222 788 243722096 789 244652331 790 245584930 791 246519896 792 247457232 793 248396941 794 249339026 795 250283490 796 251230336 797 252179567 798 253131186 799 254085196 800 255041600 801 256000401 802 256961602 803 257925206 804 258891216 805 259859635 806 260830466 807 261803712 808 262779376 809 263757461 810 264737970 811 265720906 812 266706272 813 267694071 814 268684306 815 269676980 816 270672096 817 271669657 818 272669666 819 273672126 820 274677040 821 275684411 822 276694242 823 277706536 824 278721296 825 279738525 826 280758226 827 281780402 828 282805056 829 283832191 830 284861810 831 285893916 832 286928512 833 287965601 834 289005186 835 290047270 836 291091856 837 292138947 838 293188546 839 294240656 840 295295280 841 296352421 842 297412082 843 298474266 844 299538976 845 300606215 846 301675986 847 302748292 848 303823136 849 304900521 850 305980450 851 307062926 852 308147952 853 309235531 854 310325666 855 311418360 856 312513616 857 313611437 858 314711826 859 315814786 860 316920320 861 318028431 862 319139122 863 320252396 864 321368256 865 322486705 866 323607746 867 324731382 868 325857616 869 326986451 870 328117890 871 329251936 872 330388592 873 331527861 874 332669746 875 333814250 876 334961376 877 336111127 878 337263506 879 338418516 880 339576160 881 340736441 882 341899362 883 343064926 884 344233136 885 345403995 886 346577506 887 347753672 888 348932496 889 350113981 890 351298130 891 352484946 892 353674432 893 354866591 894 356061426 895 357258940 896 358459136 897 359662017 898 360867586 899 362075846 900 363286800 901 364500451 902 365716802 903 366935856 904 368157616 905 369382085 906 370609266 907 371839162 908 373071776 909 374307111 910 375545170 911 376785956 912 378029472 913 379275721 914 380524706 915 381776430 916 383030896 917 384288107 918 385548066 919 386810776 920 388076240 921 389344461 922 390615442 923 391889186 924 393165696 925 394444975 926 395727026 927 397011852 928 398299456 929 399589841 930 400883010 931 402178966 932 403477712 933 404779251 934 406083586 935 407390720 936 408700656 937 410013397 938 411328946 939 412647306 940 413968480 941 415292471 942 416619282 943 417948916 944 419281376 945 420616665 946 421954786 947 423295742 948 424639536 949 425986171 950 427335650 951 428687976 952 430043152 953 431401181 954 432762066 955 434125810 956 435492416 957 436861887 958 438234226 959 439609436 960 440987520 961 442368481 962 443752322 963 445139046 964 446528656 965 447921155 966 449316546 967 450714832 968 452116016 969 453520101 970 454927090 971 456336986 972 457749792 973 459165511 974 460584146 975 462005700 976 463430176 977 464857577 978 466287906 979 467721166 980 469157360 981 470596491 982 472038562 983 473483576 984 474931536 985 476382445 986 477836306 987 479293122 988 480752896 989 482215631 990 483681330 991 485149996 992 486621632 993 488096241 994 489573826 995 491054390 996 492537936 997 494024467 998 495513986 999 497006496 1000 498502000