1 0 2 1 3 7 4 18 5 40 6 71 7 119 8 180 9 264 10 365 11 495 12 646 13 832 14 1043 15 1295 16 1576 17 1904 18 2265 19 2679 20 3130 21 3640 22 4191 23 4807 24 5468 25 6200 26 6981 27 7839 28 8750 29 9744 30 10795 31 11935 32 13136 33 14432 34 15793 35 17255 36 18786 37 20424 38 22135 39 23959 40 25860 41 27880 42 29981 43 32207 44 34518 45 36960 46 39491 47 42159 48 44920 49 47824 50 50825 51 53975 52 57226 53 60632 54 64143 55 67815 56 71596 57 75544 58 79605 59 83839 60 88190 61 92720 62 97371 63 102207 64 107168 65 112320 66 117601 67 123079 68 128690 69 134504 70 140455 71 146615 72 152916 73 159432 74 166093 75 172975 76 180006 77 187264 78 194675 79 202319 80 210120 81 218160 82 226361 83 234807 84 243418 85 252280 86 261311 87 270599 88 280060 89 289784 90 299685 91 309855 92 320206 93 330832 94 341643 95 352735 96 364016 97 375584 98 387345 99 399399 100 411650 101 424200 102 436951 103 450007 104 463268 105 476840 106 490621 107 504719 108 519030 109 533664 110 548515 111 563695 112 579096 113 594832 114 610793 115 627095 116 643626 117 660504 118 677615 119 695079 120 712780 121 730840 122 749141 123 767807 124 786718 125 806000 126 825531 127 845439 128 865600 129 886144 130 906945 131 928135 132 949586 133 971432 134 993543 135 1016055 136 1038836 137 1062024 138 1085485 139 1109359 140 1133510 141 1158080 142 1182931 143 1208207 144 1233768 145 1259760 146 1286041 147 1312759 148 1339770 149 1367224 150 1394975 151 1423175 152 1451676 153 1480632 154 1509893 155 1539615 156 1569646 157 1600144 158 1630955 159 1662239 160 1693840 161 1725920 162 1758321 163 1791207 164 1824418 165 1858120 166 1892151 167 1926679 168 1961540 169 1996904 170 2032605 171 2068815 172 2105366 173 2142432 174 2179843 175 2217775 176 2256056 177 2294864 178 2334025 179 2373719 180 2413770 181 2454360 182 2495311 183 2536807 184 2578668 185 2621080 186 2663861 187 2707199 188 2750910 189 2795184 190 2839835 191 2885055 192 2930656 193 2976832 194 3023393 195 3070535 196 3118066 197 3166184 198 3214695 199 3263799 200 3313300 201 3363400 202 3413901 203 3465007 204 3516518 205 3568640 206 3621171 207 3674319 208 3727880 209 3782064 210 3836665 211 3891895 212 3947546 213 4003832 214 4060543 215 4117895 216 4175676 217 4234104 218 4292965 219 4352479 220 4412430 221 4473040 222 4534091 223 4595807 224 4657968 225 4720800 226 4784081 227 4848039 228 4912450 229 4977544 230 5043095 231 5109335 232 5176036 233 5243432 234 5311293 235 5379855 236 5448886 237 5518624 238 5588835 239 5659759 240 5731160 241 5803280 242 5875881 243 5949207 244 6023018 245 6097560 246 6172591 247 6248359 248 6324620 249 6401624 250 6479125 251 6557375 252 6636126 253 6715632 254 6795643 255 6876415 256 6957696 257 7039744 258 7122305 259 7205639 260 7289490 261 7374120 262 7459271 263 7545207 264 7631668 265 7718920 266 7806701 267 7895279 268 7984390 269 8074304 270 8164755 271 8256015 272 8347816 273 8440432 274 8533593 275 8627575 276 8722106 277 8817464 278 8913375 279 9010119 280 9107420 281 9205560 282 9304261 283 9403807 284 9503918 285 9604880 286 9706411 287 9808799 288 9911760 289 10015584 290 10119985 291 10225255 292 10331106 293 10437832 294 10545143 295 10653335 296 10762116 297 10871784 298 10982045 299 11093199 300 11204950 301 11317600 302 11430851 303 11545007 304 11659768 305 11775440 306 11891721 307 12008919 308 12126730 309 12245464 310 12364815 311 12485095 312 12605996 313 12727832 314 12850293 315 12973695 316 13097726 317 13222704 318 13348315 319 13474879 320 13602080 321 13730240 322 13859041 323 13988807 324 14119218 325 14250600 326 14382631 327 14515639 328 14649300 329 14783944 330 14919245 331 15055535 332 15192486 333 15330432 334 15469043 335 15608655 336 15748936 337 15890224 338 16032185 339 16175159 340 16318810 341 16463480 342 16608831 343 16755207 344 16902268 345 17050360 346 17199141 347 17348959 348 17499470 349 17651024 350 17803275 351 17956575 352 18110576 353 18265632 354 18421393 355 18578215 356 18735746 357 18894344 358 19053655 359 19214039 360 19375140 361 19537320 362 19700221 363 19864207 364 20028918 365 20194720 366 20361251 367 20528879 368 20697240 369 20866704 370 21036905 371 21208215 372 21380266 373 21553432 374 21727343 375 21902375 376 22078156 377 22255064 378 22432725 379 22611519 380 22791070 381 22971760 382 23153211 383 23335807 384 23519168 385 23703680 386 23888961 387 24075399 388 24262610 389 24450984 390 24640135 391 24830455 392 25021556 393 25213832 394 25406893 395 25601135 396 25796166 397 25992384 398 26189395 399 26387599 400 26586600 401 26786800 402 26987801 403 27190007 404 27393018 405 27597240 406 27802271 407 28008519 408 28215580 409 28423864 410 28632965 411 28843295 412 29054446 413 29266832 414 29480043 415 29694495 416 29909776 417 30126304 418 30343665 419 30562279 420 30781730 421 31002440 422 31223991 423 31446807 424 31670468 425 31895400 426 32121181 427 32348239 428 32576150 429 32805344 430 33035395 431 33266735 432 33498936 433 33732432 434 33966793 435 34202455 436 34438986 437 34676824 438 34915535 439 35155559 440 35396460 441 35638680 442 35881781 443 36126207 444 36371518 445 36618160 446 36865691 447 37114559 448 37364320 449 37615424 450 37867425 451 38120775 452 38375026 453 38630632 454 38887143 455 39145015 456 39403796 457 39663944 458 39925005 459 40187439 460 40450790 461 40715520 462 40981171 463 41248207 464 41516168 465 41785520 466 42055801 467 42327479 468 42600090 469 42874104 470 43149055 471 43425415 472 43702716 473 43981432 474 44261093 475 44542175 476 44824206 477 45107664 478 45392075 479 45677919 480 45964720 481 46252960 482 46542161 483 46832807 484 47124418 485 47417480 486 47711511 487 48006999 488 48303460 489 48601384 490 48900285 491 49200655 492 49502006 493 49804832 494 50108643 495 50413935 496 50720216 497 51027984 498 51336745 499 51646999 500 51958250 501 52271000 502 52584751 503 52900007 504 53216268 505 53534040 506 53852821 507 54173119 508 54494430 509 54817264 510 55141115 511 55466495 512 55792896 513 56120832 514 56449793 515 56780295 516 57111826 517 57444904 518 57779015 519 58114679 520 58451380 521 58789640 522 59128941 523 59469807 524 59811718 525 60155200 526 60499731 527 60845839 528 61193000 529 61541744 530 61891545 531 62242935 532 62595386 533 62949432 534 63304543 535 63661255 536 64019036 537 64378424 538 64738885 539 65100959 540 65464110 541 65828880 542 66194731 543 66562207 544 66930768 545 67300960 546 67672241 547 68045159 548 68419170 549 68794824 550 69171575 551 69549975 552 69929476 553 70310632 554 70692893 555 71076815 556 71461846 557 71848544 558 72236355 559 72625839 560 73016440 561 73408720 562 73802121 563 74197207 564 74593418 565 74991320 566 75390351 567 75791079 568 76192940 569 76596504 570 77001205 571 77407615 572 77815166 573 78224432 574 78634843 575 79046975 576 79460256 577 79875264 578 80291425 579 80709319 580 81128370 581 81549160 582 81971111 583 82394807 584 82819668 585 83246280 586 83674061 587 84103599 588 84534310 589 84966784 590 85400435 591 85835855 592 86272456 593 86710832 594 87150393 595 87591735 596 88034266 597 88478584 598 88924095 599 89371399 600 89819900 601 90270200 602 90721701 603 91175007 604 91629518 605 92085840 606 92543371 607 93002719 608 93463280 609 93925664 610 94389265 611 94854695 612 95321346 613 95789832 614 96259543 615 96731095 616 97203876 617 97678504 618 98154365 619 98632079 620 99111030 621 99591840 622 100073891 623 100557807 624 101042968 625 101530000 626 102018281 627 102508439 628 102999850 629 103493144 630 103987695 631 104484135 632 104981836 633 105481432 634 105982293 635 106485055 636 106989086 637 107495024 638 108002235 639 108511359 640 109021760 641 109534080 642 110047681 643 110563207 644 111080018 645 111598760 646 112118791 647 112640759 648 113164020 649 113689224 650 114215725 651 114744175 652 115273926 653 115805632 654 116338643 655 116873615 656 117409896 657 117948144 658 118487705 659 119029239 660 119572090 661 120116920 662 120663071 663 121211207 664 121760668 665 122312120 666 122864901 667 123419679 668 123975790 669 124533904 670 125093355 671 125654815 672 126217616 673 126782432 674 127348593 675 127916775 676 128486306 677 129057864 678 129630775 679 130205719 680 130782020 681 131360360 682 131940061 683 132521807 684 133104918 685 133690080 686 134276611 687 134865199 688 135455160 689 136047184 690 136640585 691 137236055 692 137832906 693 138431832 694 139032143 695 139634535 696 140238316 697 140844184 698 141451445 699 142060799 700 142671550 701 143284400 702 143898651 703 144515007 704 145132768 705 145752640 706 146373921 707 146997319 708 147622130 709 148249064 710 148877415 711 149507895 712 150139796 713 150773832 714 151409293 715 152046895 716 152685926 717 153327104 718 153969715 719 154614479 720 155260680 721 155909040 722 156558841 723 157210807 724 157864218 725 158519800 726 159176831 727 159836039 728 160496700 729 161159544 730 161823845 731 162490335 732 163158286 733 163828432 734 164500043 735 165173855 736 165849136 737 166526624 738 167205585 739 167886759 740 168569410 741 169254280 742 169940631 743 170629207 744 171319268 745 172011560 746 172705341 747 173401359 748 174098870 749 174798624 750 175499875 751 176203375 752 176908376 753 177615632 754 178324393 755 179035415 756 179747946 757 180462744 758 181179055 759 181897639 760 182617740 761 183340120 762 184064021 763 184790207 764 185517918 765 186247920 766 186979451 767 187713279 768 188448640 769 189186304 770 189925505 771 190667015 772 191410066 773 192155432 774 192902343 775 193651575 776 194402356 777 195155464 778 195910125 779 196667119 780 197425670 781 198186560 782 198949011 783 199713807 784 200480168 785 201248880 786 202019161 787 202791799 788 203566010 789 204342584 790 205120735 791 205901255 792 206683356 793 207467832 794 208253893 795 209042335 796 209832366 797 210624784 798 211418795 799 212215199 800 213013200 801 213813600 802 214615601 803 215420007 804 216226018 805 217034440 806 217844471 807 218656919 808 219470980 809 220287464 810 221105565 811 221926095 812 222748246 813 223572832 814 224399043 815 225227695 816 226057976 817 226890704 818 227725065 819 228561879 820 229400330 821 230241240 822 231083791 823 231928807 824 232775468 825 233624600 826 234475381 827 235328639 828 236183550 829 237040944 830 237899995 831 238761535 832 239624736 833 240490432 834 241357793 835 242227655 836 243099186 837 243973224 838 244848935 839 245727159 840 246607060 841 247489480 842 248373581 843 249260207 844 250148518 845 251039360 846 251931891 847 252826959 848 253723720 849 254623024 850 255524025 851 256427575 852 257332826 853 258240632 854 259150143 855 260062215 856 260975996 857 261892344 858 262810405 859 263731039 860 264653390 861 265578320 862 266504971 863 267434207 864 268365168 865 269298720 866 270234001 867 271171879 868 272111490 869 273053704 870 273997655 871 274944215 872 275892516 873 276843432 874 277796093 875 278751375 876 279708406 877 280668064 878 281629475 879 282593519 880 283559320 881 284527760 882 285497961 883 286470807 884 287445418 885 288422680 886 289401711 887 290383399 888 291366860 889 292352984 890 293340885 891 294331455 892 295323806 893 296318832 894 297315643 895 298315135 896 299316416 897 300320384 898 301326145 899 302334599 900 303344850 901 304357800 902 305372551 903 306390007 904 307409268 905 308431240 906 309455021 907 310481519 908 311509830 909 312540864 910 313573715 911 314609295 912 315646696 913 316686832 914 317728793 915 318773495 916 319820026 917 320869304 918 321920415 919 322974279 920 324029980 921 325088440 922 326148741 923 327211807 924 328276718 925 329344400 926 330413931 927 331486239 928 332560400 929 333637344 930 334716145 931 335797735 932 336881186 933 337967432 934 339055543 935 340146455 936 341239236 937 342334824 938 343432285 939 344532559 940 345634710 941 346739680 942 347846531 943 348956207 944 350067768 945 351182160 946 352298441 947 353417559 948 354538570 949 355662424 950 356788175 951 357916775 952 359047276 953 360180632 954 361315893 955 362454015 956 363594046 957 364736944 958 365881755 959 367029439 960 368179040 961 369331520 962 370485921 963 371643207 964 372802418 965 373964520 966 375128551 967 376295479 968 377464340 969 378636104 970 379809805 971 380986415 972 382164966 973 383346432 974 384529843 975 385716175 976 386904456 977 388095664 978 389288825 979 390484919 980 391682970 981 392883960 982 394086911 983 395292807 984 396500668 985 397711480 986 398924261 987 400139999 988 401357710 989 402578384 990 403801035 991 405026655 992 406254256 993 407484832 994 408717393 995 409952935 996 411190466 997 412430984 998 413673495 999 414918999 1000 416166500