0 1 1 3 2 8 3 21 4 46 5 87 6 148 7 233 8 346 9 491 10 672 11 893 12 1158 13 1471 14 1836 15 2257 16 2738 17 3283 18 3896 19 4581 20 5342 21 6183 22 7108 23 8121 24 9226 25 10427 26 11728 27 13133 28 14646 29 16271 30 18012 31 19873 32 21858 33 23971 34 26216 35 28597 36 31118 37 33783 38 36596 39 39561 40 42682 41 45963 42 49408 43 53021 44 56806 45 60767 46 64908 47 69233 48 73746 49 78451 50 83352 51 88453 52 93758 53 99271 54 104996 55 110937 56 117098 57 123483 58 130096 59 136941 60 144022 61 151343 62 158908 63 166721 64 174786 65 183107 66 191688 67 200533 68 209646 69 219031 70 228692 71 238633 72 248858 73 259371 74 270176 75 281277 76 292678 77 304383 78 316396 79 328721 80 341362 81 354323 82 367608 83 381221 84 395166 85 409447 86 424068 87 439033 88 454346 89 470011 90 486032 91 502413 92 519158 93 536271 94 553756 95 571617 96 589858 97 608483 98 627496 99 646901 100 666702 101 686903 102 707508 103 728521 104 749946 105 771787 106 794048 107 816733 108 839846 109 863391 110 887372 111 911793 112 936658 113 961971 114 987736 115 1013957 116 1040638 117 1067783 118 1095396 119 1123481 120 1152042 121 1181083 122 1210608 123 1240621 124 1271126 125 1302127 126 1333628 127 1365633 128 1398146 129 1431171 130 1464712 131 1498773 132 1533358 133 1568471 134 1604116 135 1640297 136 1677018 137 1714283 138 1752096 139 1790461 140 1829382 141 1868863 142 1908908 143 1949521 144 1990706 145 2032467 146 2074808 147 2117733 148 2161246 149 2205351 150 2250052 151 2295353 152 2341258 153 2387771 154 2434896 155 2482637 156 2530998 157 2579983 158 2629596 159 2679841 160 2730722 161 2782243 162 2834408 163 2887221 164 2940686 165 2994807 166 3049588 167 3105033 168 3161146 169 3217931 170 3275392 171 3333533 172 3392358 173 3451871 174 3512076 175 3572977 176 3634578 177 3696883 178 3759896 179 3823621 180 3888062 181 3953223 182 4019108 183 4085721 184 4153066 185 4221147 186 4289968 187 4359533 188 4429846 189 4500911 190 4572732 191 4645313 192 4718658 193 4792771 194 4867656 195 4943317 196 5019758 197 5096983 198 5174996 199 5253801 200 5333402 201 5413803 202 5495008 203 5577021 204 5659846 205 5743487 206 5827948 207 5913233 208 5999346 209 6086291 210 6174072 211 6262693 212 6352158 213 6442471 214 6533636 215 6625657 216 6718538 217 6812283 218 6906896 219 7002381 220 7098742 221 7195983 222 7294108 223 7393121 224 7493026 225 7593827 226 7695528 227 7798133 228 7901646 229 8006071 230 8111412 231 8217673 232 8324858 233 8432971 234 8542016 235 8651997 236 8762918 237 8874783 238 8987596 239 9101361 240 9216082 241 9331763 242 9448408 243 9566021 244 9684606 245 9804167 246 9924708 247 10046233 248 10168746 249 10292251 250 10416752 251 10542253 252 10668758 253 10796271 254 10924796 255 11054337 256 11184898 257 11316483 258 11449096 259 11582741 260 11717422 261 11853143 262 11989908 263 12127721 264 12266586 265 12406507 266 12547488 267 12689533 268 12832646 269 12976831 270 13122092 271 13268433 272 13415858 273 13564371 274 13713976 275 13864677 276 14016478 277 14169383 278 14323396 279 14478521 280 14634762 281 14792123 282 14950608 283 15110221 284 15270966 285 15432847 286 15595868 287 15760033 288 15925346 289 16091811 290 16259432 291 16428213 292 16598158 293 16769271 294 16941556 295 17115017 296 17289658 297 17465483 298 17642496 299 17820701 300 18000102 301 18180703 302 18362508 303 18545521 304 18729746 305 18915187 306 19101848 307 19289733 308 19478846 309 19669191 310 19860772 311 20053593 312 20247658 313 20442971 314 20639536 315 20837357 316 21036438 317 21236783 318 21438396 319 21641281 320 21845442 321 22050883 322 22257608 323 22465621 324 22674926 325 22885527 326 23097428 327 23310633 328 23525146 329 23740971 330 23958112 331 24176573 332 24396358 333 24617471 334 24839916 335 25063697 336 25288818 337 25515283 338 25743096 339 25972261 340 26202782 341 26434663 342 26667908 343 26902521 344 27138506 345 27375867 346 27614608 347 27854733 348 28096246 349 28339151 350 28583452 351 28829153 352 29076258 353 29324771 354 29574696 355 29826037 356 30078798 357 30332983 358 30588596 359 30845641 360 31104122 361 31364043 362 31625408 363 31888221 364 32152486 365 32418207 366 32685388 367 32954033 368 33224146 369 33495731 370 33768792 371 34043333 372 34319358 373 34596871 374 34875876 375 35156377 376 35438378 377 35721883 378 36006896 379 36293421 380 36581462 381 36871023 382 37162108 383 37454721 384 37748866 385 38044547 386 38341768 387 38640533 388 38940846 389 39242711 390 39546132 391 39851113 392 40157658 393 40465771 394 40775456 395 41086717 396 41399558 397 41713983 398 42029996 399 42347601 400 42666802 401 42987603 402 43310008 403 43634021 404 43959646 405 44286887 406 44615748 407 44946233 408 45278346 409 45612091 410 45947472 411 46284493 412 46623158 413 46963471 414 47305436 415 47649057 416 47994338 417 48341283 418 48689896 419 49040181 420 49392142 421 49745783 422 50101108 423 50458121 424 50816826 425 51177227 426 51539328 427 51903133 428 52268646 429 52635871 430 53004812 431 53375473 432 53747858 433 54121971 434 54497816 435 54875397 436 55254718 437 55635783 438 56018596 439 56403161 440 56789482 441 57177563 442 57567408 443 57959021 444 58352406 445 58747567 446 59144508 447 59543233 448 59943746 449 60346051 450 60750152 451 61156053 452 61563758 453 61973271 454 62384596 455 62797737 456 63212698 457 63629483 458 64048096 459 64468541 460 64890822 461 65314943 462 65740908 463 66168721 464 66598386 465 67029907 466 67463288 467 67898533 468 68335646 469 68774631 470 69215492 471 69658233 472 70102858 473 70549371 474 70997776 475 71448077 476 71900278 477 72354383 478 72810396 479 73268321 480 73728162 481 74189923 482 74653608 483 75119221 484 75586766 485 76056247 486 76527668 487 77001033 488 77476346 489 77953611 490 78432832 491 78914013 492 79397158 493 79882271 494 80369356 495 80858417 496 81349458 497 81842483 498 82337496 499 82834501 500 83333502 501 83834503 502 84337508 503 84842521 504 85349546 505 85858587 506 86369648 507 86882733 508 87397846 509 87914991 510 88434172 511 88955393 512 89478658 513 90003971 514 90531336 515 91060757 516 91592238 517 92125783 518 92661396 519 93199081 520 93738842 521 94280683 522 94824608 523 95370621 524 95918726 525 96468927 526 97021228 527 97575633 528 98132146 529 98690771 530 99251512 531 99814373 532 100379358 533 100946471 534 101515716 535 102087097 536 102660618 537 103236283 538 103814096 539 104394061 540 104976182 541 105560463 542 106146908 543 106735521 544 107326306 545 107919267 546 108514408 547 109111733 548 109711246 549 110312951 550 110916852 551 111522953 552 112131258 553 112741771 554 113354496 555 113969437 556 114586598 557 115205983 558 115827596 559 116451441 560 117077522 561 117705843 562 118336408 563 118969221 564 119604286 565 120241607 566 120881188 567 121523033 568 122167146 569 122813531 570 123462192 571 124113133 572 124766358 573 125421871 574 126079676 575 126739777 576 127402178 577 128066883 578 128733896 579 129403221 580 130074862 581 130748823 582 131425108 583 132103721 584 132784666 585 133467947 586 134153568 587 134841533 588 135531846 589 136224511 590 136919532 591 137616913 592 138316658 593 139018771 594 139723256 595 140430117 596 141139358 597 141850983 598 142564996 599 143281401 600 144000202 601 144721403 602 145445008 603 146171021 604 146899446 605 147630287 606 148363548 607 149099233 608 149837346 609 150577891 610 151320872 611 152066293 612 152814158 613 153564471 614 154317236 615 155072457 616 155830138 617 156590283 618 157352896 619 158117981 620 158885542 621 159655583 622 160428108 623 161203121 624 161980626 625 162760627 626 163543128 627 164328133 628 165115646 629 165905671 630 166698212 631 167493273 632 168290858 633 169090971 634 169893616 635 170698797 636 171506518 637 172316783 638 173129596 639 173944961 640 174762882 641 175583363 642 176406408 643 177232021 644 178060206 645 178890967 646 179724308 647 180560233 648 181398746 649 182239851 650 183083552 651 183929853 652 184778758 653 185630271 654 186484396 655 187341137 656 188200498 657 189062483 658 189927096 659 190794341 660 191664222 661 192536743 662 193411908 663 194289721 664 195170186 665 196053307 666 196939088 667 197827533 668 198718646 669 199612431 670 200508892 671 201408033 672 202309858 673 203214371 674 204121576 675 205031477 676 205944078 677 206859383 678 207777396 679 208698121 680 209621562 681 210547723 682 211476608 683 212408221 684 213342566 685 214279647 686 215219468 687 216162033 688 217107346 689 218055411 690 219006232 691 219959813 692 220916158 693 221875271 694 222837156 695 223801817 696 224769258 697 225739483 698 226712496 699 227688301 700 228666902 701 229648303 702 230632508 703 231619521 704 232609346 705 233601987 706 234597448 707 235595733 708 236596846 709 237600791 710 238607572 711 239617193 712 240629658 713 241644971 714 242663136 715 243684157 716 244708038 717 245734783 718 246764396 719 247796881 720 248832242 721 249870483 722 250911608 723 251955621 724 253002526 725 254052327 726 255105028 727 256160633 728 257219146 729 258280571 730 259344912 731 260412173 732 261482358 733 262555471 734 263631516 735 264710497 736 265792418 737 266877283 738 267965096 739 269055861 740 270149582 741 271246263 742 272345908 743 273448521 744 274554106 745 275662667 746 276774208 747 277888733 748 279006246 749 280126751 750 281250252 751 282376753 752 283506258 753 284638771 754 285774296 755 286912837 756 288054398 757 289198983 758 290346596 759 291497241 760 292650922 761 293807643 762 294967408 763 296130221 764 297296086 765 298465007 766 299636988 767 300812033 768 301990146 769 303171331 770 304355592 771 305542933 772 306733358 773 307926871 774 309123476 775 310323177 776 311525978 777 312731883 778 313940896 779 315153021 780 316368262 781 317586623 782 318808108 783 320032721 784 321260466 785 322491347 786 323725368 787 324962533 788 326202846 789 327446311 790 328692932 791 329942713 792 331195658 793 332451771 794 333711056 795 334973517 796 336239158 797 337507983 798 338779996 799 340055201 800 341333602 801 342615203 802 343900008 803 345188021 804 346479246 805 347773687 806 349071348 807 350372233 808 351676346 809 352983691 810 354294272 811 355608093 812 356925158 813 358245471 814 359569036 815 360895857 816 362225938 817 363559283 818 364895896 819 366235781 820 367578942 821 368925383 822 370275108 823 371628121 824 372984426 825 374344027 826 375706928 827 377073133 828 378442646 829 379815471 830 381191612 831 382571073 832 383953858 833 385339971 834 386729416 835 388122197 836 389518318 837 390917783 838 392320596 839 393726761 840 395136282 841 396549163 842 397965408 843 399385021 844 400808006 845 402234367 846 403664108 847 405097233 848 406533746 849 407973651 850 409416952 851 410863653 852 412313758 853 413767271 854 415224196 855 416684537 856 418148298 857 419615483 858 421086096 859 422560141 860 424037622 861 425518543 862 427002908 863 428490721 864 429981986 865 431476707 866 432974888 867 434476533 868 435981646 869 437490231 870 439002292 871 440517833 872 442036858 873 443559371 874 445085376 875 446614877 876 448147878 877 449684383 878 451224396 879 452767921 880 454314962 881 455865523 882 457419608 883 458977221 884 460538366 885 462103047 886 463671268 887 465243033 888 466818346 889 468397211 890 469979632 891 471565613 892 473155158 893 474748271 894 476344956 895 477945217 896 479549058 897 481156483 898 482767496 899 484382101 900 486000302 901 487622103 902 489247508 903 490876521 904 492509146 905 494145387 906 495785248 907 497428733 908 499075846 909 500726591 910 502380972 911 504038993 912 505700658 913 507365971 914 509034936 915 510707557 916 512383838 917 514063783 918 515747396 919 517434681 920 519125642 921 520820283 922 522518608 923 524220621 924 525926326 925 527635727 926 529348828 927 531065633 928 532786146 929 534510371 930 536238312 931 537969973 932 539705358 933 541444471 934 543187316 935 544933897 936 546684218 937 548438283 938 550196096 939 551957661 940 553722982 941 555492063 942 557264908 943 559041521 944 560821906 945 562606067 946 564394008 947 566185733 948 567981246 949 569780551 950 571583652 951 573390553 952 575201258 953 577015771 954 578834096 955 580656237 956 582482198 957 584311983 958 586145596 959 587983041 960 589824322 961 591669443 962 593518408 963 595371221 964 597227886 965 599088407 966 600952788 967 602821033 968 604693146 969 606569131 970 608448992 971 610332733 972 612220358 973 614111871 974 616007276 975 617906577 976 619809778 977 621716883 978 623627896 979 625542821 980 627461662 981 629384423 982 631311108 983 633241721 984 635176266 985 637114747 986 639057168 987 641003533 988 642953846 989 644908111 990 646866332 991 648828513 992 650794658 993 652764771 994 654738856 995 656716917 996 658698958 997 660684983 998 662674996 999 664669001 1000 666667002