0 0 1 1 2 4 3 13 4 32 5 65 6 116 7 189 8 288 9 417 10 580 11 781 12 1024 13 1313 14 1652 15 2045 16 2496 17 3009 18 3588 19 4237 20 4960 21 5761 22 6644 23 7613 24 8672 25 9825 26 11076 27 12429 28 13888 29 15457 30 17140 31 18941 32 20864 33 22913 34 25092 35 27405 36 29856 37 32449 38 35188 39 38077 40 41120 41 44321 42 47684 43 51213 44 54912 45 58785 46 62836 47 67069 48 71488 49 76097 50 80900 51 85901 52 91104 53 96513 54 102132 55 107965 56 114016 57 120289 58 126788 59 133517 60 140480 61 147681 62 155124 63 162813 64 170752 65 178945 66 187396 67 196109 68 205088 69 214337 70 223860 71 233661 72 243744 73 254113 74 264772 75 275725 76 286976 77 298529 78 310388 79 322557 80 335040 81 347841 82 360964 83 374413 84 388192 85 402305 86 416756 87 431549 88 446688 89 462177 90 478020 91 494221 92 510784 93 527713 94 545012 95 562685 96 580736 97 599169 98 617988 99 637197 100 656800 101 676801 102 697204 103 718013 104 739232 105 760865 106 782916 107 805389 108 828288 109 851617 110 875380 111 899581 112 924224 113 949313 114 974852 115 1000845 116 1027296 117 1054209 118 1081588 119 1109437 120 1137760 121 1166561 122 1195844 123 1225613 124 1255872 125 1286625 126 1317876 127 1349629 128 1381888 129 1414657 130 1447940 131 1481741 132 1516064 133 1550913 134 1586292 135 1622205 136 1658656 137 1695649 138 1733188 139 1771277 140 1809920 141 1849121 142 1888884 143 1929213 144 1970112 145 2011585 146 2053636 147 2096269 148 2139488 149 2183297 150 2227700 151 2272701 152 2318304 153 2364513 154 2411332 155 2458765 156 2506816 157 2555489 158 2604788 159 2654717 160 2705280 161 2756481 162 2808324 163 2860813 164 2913952 165 2967745 166 3022196 167 3077309 168 3133088 169 3189537 170 3246660 171 3304461 172 3362944 173 3422113 174 3481972 175 3542525 176 3603776 177 3665729 178 3728388 179 3791757 180 3855840 181 3920641 182 3986164 183 4052413 184 4119392 185 4187105 186 4255556 187 4324749 188 4394688 189 4465377 190 4536820 191 4609021 192 4681984 193 4755713 194 4830212 195 4905485 196 4981536 197 5058369 198 5135988 199 5214397 200 5293600 201 5373601 202 5454404 203 5536013 204 5618432 205 5701665 206 5785716 207 5870589 208 5956288 209 6042817 210 6130180 211 6218381 212 6307424 213 6397313 214 6488052 215 6579645 216 6672096 217 6765409 218 6859588 219 6954637 220 7050560 221 7147361 222 7245044 223 7343613 224 7443072 225 7543425 226 7644676 227 7746829 228 7849888 229 7953857 230 8058740 231 8164541 232 8271264 233 8378913 234 8487492 235 8597005 236 8707456 237 8818849 238 8931188 239 9044477 240 9158720 241 9273921 242 9390084 243 9507213 244 9625312 245 9744385 246 9864436 247 9985469 248 10107488 249 10230497 250 10354500 251 10479501 252 10605504 253 10732513 254 10860532 255 10989565 256 11119616 257 11250689 258 11382788 259 11515917 260 11650080 261 11785281 262 11921524 263 12058813 264 12197152 265 12336545 266 12476996 267 12618509 268 12761088 269 12904737 270 13049460 271 13195261 272 13342144 273 13490113 274 13639172 275 13789325 276 13940576 277 14092929 278 14246388 279 14400957 280 14556640 281 14713441 282 14871364 283 15030413 284 15190592 285 15351905 286 15514356 287 15677949 288 15842688 289 16008577 290 16175620 291 16343821 292 16513184 293 16683713 294 16855412 295 17028285 296 17202336 297 17377569 298 17553988 299 17731597 300 17910400 301 18090401 302 18271604 303 18454013 304 18637632 305 18822465 306 19008516 307 19195789 308 19384288 309 19574017 310 19764980 311 19957181 312 20150624 313 20345313 314 20541252 315 20738445 316 20936896 317 21136609 318 21337588 319 21539837 320 21743360 321 21948161 322 22154244 323 22361613 324 22570272 325 22780225 326 22991476 327 23204029 328 23417888 329 23633057 330 23849540 331 24067341 332 24286464 333 24506913 334 24728692 335 24951805 336 25176256 337 25402049 338 25629188 339 25857677 340 26087520 341 26318721 342 26551284 343 26785213 344 27020512 345 27257185 346 27495236 347 27734669 348 27975488 349 28217697 350 28461300 351 28706301 352 28952704 353 29200513 354 29449732 355 29700365 356 29952416 357 30205889 358 30460788 359 30717117 360 30974880 361 31234081 362 31494724 363 31756813 364 32020352 365 32285345 366 32551796 367 32819709 368 33089088 369 33359937 370 33632260 371 33906061 372 34181344 373 34458113 374 34736372 375 35016125 376 35297376 377 35580129 378 35864388 379 36150157 380 36437440 381 36726241 382 37016564 383 37308413 384 37601792 385 37896705 386 38193156 387 38491149 388 38790688 389 39091777 390 39394420 391 39698621 392 40004384 393 40311713 394 40620612 395 40931085 396 41243136 397 41556769 398 41871988 399 42188797 400 42507200 401 42827201 402 43148804 403 43472013 404 43796832 405 44123265 406 44451316 407 44780989 408 45112288 409 45445217 410 45779780 411 46115981 412 46453824 413 46793313 414 47134452 415 47477245 416 47821696 417 48167809 418 48515588 419 48865037 420 49216160 421 49568961 422 49923444 423 50279613 424 50637472 425 50997025 426 51358276 427 51721229 428 52085888 429 52452257 430 52820340 431 53190141 432 53561664 433 53934913 434 54309892 435 54686605 436 55065056 437 55445249 438 55827188 439 56210877 440 56596320 441 56983521 442 57372484 443 57763213 444 58155712 445 58549985 446 58946036 447 59343869 448 59743488 449 60144897 450 60548100 451 60953101 452 61359904 453 61768513 454 62178932 455 62591165 456 63005216 457 63421089 458 63838788 459 64258317 460 64679680 461 65102881 462 65527924 463 65954813 464 66383552 465 66814145 466 67246596 467 67680909 468 68117088 469 68555137 470 68995060 471 69436861 472 69880544 473 70326113 474 70773572 475 71222925 476 71674176 477 72127329 478 72582388 479 73039357 480 73498240 481 73959041 482 74421764 483 74886413 484 75352992 485 75821505 486 76291956 487 76764349 488 77238688 489 77714977 490 78193220 491 78673421 492 79155584 493 79639713 494 80125812 495 80613885 496 81103936 497 81595969 498 82089988 499 82585997 500 83084000 501 83584001 502 84086004 503 84590013 504 85096032 505 85604065 506 86114116 507 86626189 508 87140288 509 87656417 510 88174580 511 88694781 512 89217024 513 89741313 514 90267652 515 90796045 516 91326496 517 91859009 518 92393588 519 92930237 520 93468960 521 94009761 522 94552644 523 95097613 524 95644672 525 96193825 526 96745076 527 97298429 528 97853888 529 98411457 530 98971140 531 99532941 532 100096864 533 100662913 534 101231092 535 101801405 536 102373856 537 102948449 538 103525188 539 104104077 540 104685120 541 105268321 542 105853684 543 106441213 544 107030912 545 107622785 546 108216836 547 108813069 548 109411488 549 110012097 550 110614900 551 111219901 552 111827104 553 112436513 554 113048132 555 113661965 556 114278016 557 114896289 558 115516788 559 116139517 560 116764480 561 117391681 562 118021124 563 118652813 564 119286752 565 119922945 566 120561396 567 121202109 568 121845088 569 122490337 570 123137860 571 123787661 572 124439744 573 125094113 574 125750772 575 126409725 576 127070976 577 127734529 578 128400388 579 129068557 580 129739040 581 130411841 582 131086964 583 131764413 584 132444192 585 133126305 586 133810756 587 134497549 588 135186688 589 135878177 590 136572020 591 137268221 592 137966784 593 138667713 594 139371012 595 140076685 596 140784736 597 141495169 598 142207988 599 142923197 600 143640800 601 144360801 602 145083204 603 145808013 604 146535232 605 147264865 606 147996916 607 148731389 608 149468288 609 150207617 610 150949380 611 151693581 612 152440224 613 153189313 614 153940852 615 154694845 616 155451296 617 156210209 618 156971588 619 157735437 620 158501760 621 159270561 622 160041844 623 160815613 624 161591872 625 162370625 626 163151876 627 163935629 628 164721888 629 165510657 630 166301940 631 167095741 632 167892064 633 168690913 634 169492292 635 170296205 636 171102656 637 171911649 638 172723188 639 173537277 640 174353920 641 175173121 642 175994884 643 176819213 644 177646112 645 178475585 646 179307636 647 180142269 648 180979488 649 181819297 650 182661700 651 183506701 652 184354304 653 185204513 654 186057332 655 186912765 656 187770816 657 188631489 658 189494788 659 190360717 660 191229280 661 192100481 662 192974324 663 193850813 664 194729952 665 195611745 666 196496196 667 197383309 668 198273088 669 199165537 670 200060660 671 200958461 672 201858944 673 202762113 674 203667972 675 204576525 676 205487776 677 206401729 678 207318388 679 208237757 680 209159840 681 210084641 682 211012164 683 211942413 684 212875392 685 213811105 686 214749556 687 215690749 688 216634688 689 217581377 690 218530820 691 219483021 692 220437984 693 221395713 694 222356212 695 223319485 696 224285536 697 225254369 698 226225988 699 227200397 700 228177600 701 229157601 702 230140404 703 231126013 704 232114432 705 233105665 706 234099716 707 235096589 708 236096288 709 237098817 710 238104180 711 239112381 712 240123424 713 241137313 714 242154052 715 243173645 716 244196096 717 245221409 718 246249588 719 247280637 720 248314560 721 249351361 722 250391044 723 251433613 724 252479072 725 253527425 726 254578676 727 255632829 728 256689888 729 257749857 730 258812740 731 259878541 732 260947264 733 262018913 734 263093492 735 264171005 736 265251456 737 266334849 738 267421188 739 268510477 740 269602720 741 270697921 742 271796084 743 272897213 744 274001312 745 275108385 746 276218436 747 277331469 748 278447488 749 279566497 750 280688500 751 281813501 752 282941504 753 284072513 754 285206532 755 286343565 756 287483616 757 288626689 758 289772788 759 290921917 760 292074080 761 293229281 762 294387524 763 295548813 764 296713152 765 297880545 766 299050996 767 300224509 768 301401088 769 302580737 770 303763460 771 304949261 772 306138144 773 307330113 774 308525172 775 309723325 776 310924576 777 312128929 778 313336388 779 314546957 780 315760640 781 316977441 782 318197364 783 319420413 784 320646592 785 321875905 786 323108356 787 324343949 788 325582688 789 326824577 790 328069620 791 329317821 792 330569184 793 331823713 794 333081412 795 334342285 796 335606336 797 336873569 798 338143988 799 339417597 800 340694400 801 341974401 802 343257604 803 344544013 804 345833632 805 347126465 806 348422516 807 349721789 808 351024288 809 352330017 810 353638980 811 354951181 812 356266624 813 357585313 814 358907252 815 360232445 816 361560896 817 362892609 818 364227588 819 365565837 820 366907360 821 368252161 822 369600244 823 370951613 824 372306272 825 373664225 826 375025476 827 376390029 828 377757888 829 379129057 830 380503540 831 381881341 832 383262464 833 384646913 834 386034692 835 387425805 836 388820256 837 390218049 838 391619188 839 393023677 840 394431520 841 395842721 842 397257284 843 398675213 844 400096512 845 401521185 846 402949236 847 404380669 848 405815488 849 407253697 850 408695300 851 410140301 852 411588704 853 413040513 854 414495732 855 415954365 856 417416416 857 418881889 858 420350788 859 421823117 860 423298880 861 424778081 862 426260724 863 427746813 864 429236352 865 430729345 866 432225796 867 433725709 868 435229088 869 436735937 870 438246260 871 439760061 872 441277344 873 442798113 874 444322372 875 445850125 876 447381376 877 448916129 878 450454388 879 451996157 880 453541440 881 455090241 882 456642564 883 458198413 884 459757792 885 461320705 886 462887156 887 464457149 888 466030688 889 467607777 890 469188420 891 470772621 892 472360384 893 473951713 894 475546612 895 477145085 896 478747136 897 480352769 898 481961988 899 483574797 900 485191200 901 486811201 902 488434804 903 490062013 904 491692832 905 493327265 906 494965316 907 496606989 908 498252288 909 499901217 910 501553780 911 503209981 912 504869824 913 506533313 914 508200452 915 509871245 916 511545696 917 513223809 918 514905588 919 516591037 920 518280160 921 519972961 922 521669444 923 523369613 924 525073472 925 526781025 926 528492276 927 530207229 928 531925888 929 533648257 930 535374340 931 537104141 932 538837664 933 540574913 934 542315892 935 544060605 936 545809056 937 547561249 938 549317188 939 551076877 940 552840320 941 554607521 942 556378484 943 558153213 944 559931712 945 561713985 946 563500036 947 565289869 948 567083488 949 568880897 950 570682100 951 572487101 952 574295904 953 576108513 954 577924932 955 579745165 956 581569216 957 583397089 958 585228788 959 587064317 960 588903680 961 590746881 962 592593924 963 594444813 964 596299552 965 598158145 966 600020596 967 601886909 968 603757088 969 605631137 970 607509060 971 609390861 972 611276544 973 613166113 974 615059572 975 616956925 976 618858176 977 620763329 978 622672388 979 624585357 980 626502240 981 628423041 982 630347764 983 632276413 984 634208992 985 636145505 986 638085956 987 640030349 988 641978688 989 643930977 990 645887220 991 647847421 992 649811584 993 651779713 994 653751812 995 655727885 996 657707936 997 659691969 998 661679988 999 663671997 1000 665668000