0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 18 9 4 10 4 11 4 12 4 13 4 14 4 15 36 16 76 17 52 18 20 19 20 20 20 21 20 22 112 23 220 24 344 25 276 26 192 27 92 28 92 29 212 30 348 31 500 32 668 33 580 34 476 35 356 36 516 37 844 38 1204 39 1596 40 2020 41 1804 42 1556 43 1452 44 1332 45 1196 46 1420 47 1660 48 1916 49 1788 50 2256 51 2756 52 3288 53 3852 54 4448 55 5300 56 6200 57 6220 58 6224 59 6212 60 6184 61 6140 62 6080 63 6004 64 7472 65 7964 66 8472 67 8996 68 9536 69 10092 70 10664 71 11828 72 13040 73 13116 74 13176 75 13220 76 13248 77 13260 78 14836 79 16476 80 18180 81 18636 82 20088 83 21588 84 23136 85 25420 86 27784 87 30228 88 32752 89 31756 90 30680 91 30260 92 32024 93 33836 94 35696 95 37604 96 39560 97 39996 98 40416 99 42020 100 45676 101 49444 102 53324 103 57316 104 61420 105 60548 106 61308 107 62052 108 62780 109 64372 110 65980 111 67604 112 69244 113 69988 114 70716 115 71428 116 72124 117 72804 118 76324 119 79924 120 87476 121 91332 122 95268 123 99284 124 103380 125 107556 126 111812 127 119220 128 126804 129 130404 130 134052 131 137748 132 141492 133 145284 134 153984 135 162876 136 174152 137 176852 138 179552 139 182252 140 184952 141 189924 142 194960 143 200060 144 205224 145 209284 146 213376 147 217500 148 225232 149 233092 150 241080 151 249196 152 257440 153 254724 154 256808 155 261980 156 267200 157 272468 158 277784 159 283148 160 288560 161 288836 162 296204 163 305636 164 315212 165 324932 166 334796 167 344804 168 354956 169 359812 170 364684 171 369572 172 380704 173 391996 174 403448 175 415060 176 433912 177 445964 178 458176 179 470548 180 483080 181 498684 182 514512 183 534980 184 555768 185 560508 186 565216 187 569892 188 574536 189 579148 190 595188 191 611436 192 627892 193 638348 194 648884 195 659500 196 670196 197 685724 198 701428 199 721308 200 741444 201 745676 202 749844 203 753948 204 769468 205 785148 206 800988 207 816988 208 842344 209 857956 210 873712 211 893004 212 912504 213 932212 214 952128 215 972252 216 992584 217 1000916 218 1022372 219 1044052 220 1065956 221 1088084 222 1110436 223 1133012 224 1155812 225 1175220 226 1203868 227 1232836 228 1262124 229 1291732 230 1321660 231 1351908 232 1391796 233 1405956 234 1420148 235 1440036 236 1460052 237 1480196 238 1500468 239 1528548 240 1556884 241 1577732 242 1598708 243 1619812 244 1649864 245 1680188 246 1722640 247 1765556 248 1808936 249 1822780 250 1836608 251 1850420 252 1864216 253 1890188 254 1916336 255 1942660 256 1969160 257 1979324 258 1989408 259 1999412 260 2028128 261 2057052 262 2100912 263 2145204 264 2189928 265 2213804 266 2237792 267 2271540 268 2305544 269 2339804 270 2374320 271 2413444 272 2452888 273 2475116 274 2510608 275 2546356 276 2582360 277 2618620 278 2655136 279 2691908 280 2745796 281 2782132 282 2818708 283 2855524 284 2892580 285 2929876 286 2967412 287 3005188 288 3066324 289 3123380 290 3180932 291 3238980 292 3297524 293 3356564 294 3416100 295 3483236 296 3550964 297 3576372 298 3613756 299 3651316 300 3689052 301 3726964 302 3790504 303 3854556 304 3919120 305 3962164 306 4005432 307 4058780 308 4112480 309 4178932 310 4245896 311 4313372 312 4381360 313 4419716 314 4458200 315 4496812 316 4565984 317 4635668 318 4705864 319 4776572 320 4847792 321 4898916 322 4950296 323 5016188 324 5082512 325 5157092 326 5232200 327 5307836 328 5384000 329 5407892 330 5462124 331 5516612 332 5571356 333 5626356 334 5705732 335 5785652 336 5866116 337 5941716 338 6017796 339 6094356 340 6171396 341 6248916 342 6326916 343 6417780 344 6538248 345 6601548 346 6665136 347 6729012 348 6793176 349 6857628 350 6922368 351 7001476 352 7097976 353 7166796 354 7235936 355 7305396 356 7375176 357 7445276 358 7538672 359 7632644 360 7727192 361 7799148 362 7871424 363 7944020 364 8016936 365 8107740 366 8199056 367 8290884 368 8383224 369 8443516 370 8533648 371 8624260 372 8754144 373 8884924 374 9016600 375 9149172 376 9282640 377 9347452 378 9412424 379 9500356 380 9588688 381 9677420 382 9766552 383 9856084 384 9946016 385 10011644 386 10108376 387 10205572 388 10335908 389 10467044 390 10598980 391 10731716 392 10865252 393 10952308 394 11039684 395 11127380 396 11215396 397 11319652 398 11424388 399 11529604 400 11664172 401 11767348 402 11870972 403 11975044 404 12079564 405 12184532 406 12309484 407 12457924 408 12607228 409 12704916 410 12802956 411 12901348 412 13000092 413 13099188 414 13246776 415 13413484 416 13581184 417 13709748 418 13838920 419 13968700 420 14099088 421 14243588 422 14388824 423 14534796 424 14720604 425 14818908 426 14917484 427 15016332 428 15166932 429 15318284 430 15470388 431 15623244 432 15776852 433 15913852 434 16051444 435 16215788 436 16380964 437 16546972 438 16713812 439 16881484 440 17049988 441 17148604 442 17316520 443 17485252 444 17654800 445 17825164 446 17996344 447 18168340 448 18341152 449 18500380 450 18660296 451 18838980 452 19018512 453 19198892 454 19380120 455 19562196 456 19788992 457 19951068 458 20113800 459 20277188 460 20470736 461 20665196 462 20860568 463 21075412 464 21291328 465 21456124 466 21621544 467 21787588 468 21954256 469 22144108 470 22396948 471 22651132 472 22906660 473 23053564 474 23200884 475 23348620 476 23496772 477 23675932 478 23905580 479 24136316 480 24368140 481 24570204 482 24773100 483 24976828 484 25224068 485 25472492 486 25722100 487 25990460 488 26260148 489 26413564 490 26567348 491 26745116 492 26923444 493 27102332 494 27281780 495 27461788 496 27682116 497 27843564 498 28075272 499 28307940 500 28541568 501 28776156 502 29011704 503 29248212 504 29485680 505 29699820 506 29914728 507 30130404 508 30346848 509 30564060 510 30782040 511 31000788 512 31294176 513 31523116 514 31789968 515 32057940 516 32327032 517 32597244 518 32868576 519 33178468 520 33489768 521 33702252 522 33915376 523 34158484 524 34402456 525 34647292 526 34935152 527 35224196 528 35514424 529 35763436 530 36013312 531 36264052 532 36577484 533 36930692 534 37285516 535 37641956 536 38000012 537 38217652 538 38435852 539 38654612 540 38938852 541 39241476 542 39545268 543 39850228 544 40156356 545 40393764 546 40631828 547 40896852 548 41162724 549 41429444 550 41763132 551 42098148 552 42434492 553 42674660 554 43002032 555 43330652 556 43660520 557 43991636 558 44324000 559 44691212 560 45059912 561 45412116 562 45765680 563 46120604 564 46476888 565 46834532 566 47193536 567 47553900 568 48018044 569 48324668 570 48632252 571 48940796 572 49250300 573 49560764 574 49872188 575 50230652 576 50590396 577 50932924 578 51276604 579 51621436 580 51967420 581 52314556 582 52758456 583 53204164 584 53651680 585 53932236 586 54269800 587 54608404 588 54948048 589 55317052 590 55687288 591 56058756 592 56431456 593 56719852 594 57008904 595 57322452 596 57713232 597 58105340 598 58498776 599 58893540 600 59289632 601 59590732 602 59892520 603 60245732 604 60679828 605 61115476 606 61552676 607 61991428 608 62431732 609 62785748 610 63209172 611 63634020 612 64060292 613 64527284 614 64995956 615 65466308 616 65938340 617 66313172 618 66689044 619 67065956 620 67443908 621 67822900 622 68257756 623 68694004 624 69241644 625 69731284 626 70222636 627 70715700 628 71210476 629 71706964 630 72205164 631 72765748 632 73328428 633 73695396 634 74063212 635 74431876 636 74801388 637 75171748 638 75634972 639 76099620 640 76655432 641 77131052 642 77608144 643 78086708 644 78566744 645 79105100 646 79645280 647 80187284 648 80731112 649 81167564 650 81605168 651 82043924 652 82562192 653 83082092 654 83603624 655 84126788 656 84651584 657 85072732 658 85589768 659 86169092 660 86750352 661 87333548 662 87918680 663 88505748 664 89094752 665 89467244 666 89936408 667 90454868 668 90974816 669 91496252 670 92019176 671 92543588 672 93069488 673 93575308 674 94082488 675 94591028 676 95155088 677 95720828 678 96288248 679 96857348 680 97558880 681 98088268 682 98619080 683 99151316 684 99684976 685 100269452 686 100855640 687 101501332 688 102149072 689 102682940 690 103218184 691 103754804 692 104292800 693 104832172 694 105539720 695 106249604 696 106961824 697 107520028 698 108079672 699 108640756 700 109203280 701 109823404 702 110445288 703 111102724 704 111762112 705 112310492 706 112860184 707 113411188 708 114105304 709 114801532 710 115499872 711 116200324 712 117014116 713 117579316 714 118145844 715 118759524 716 119374788 717 119991636 718 120610068 719 121230084 720 121851684 721 122451764 722 123200792 723 123952092 724 124705664 725 125461508 726 126219624 727 126980012 728 127742672 729 128367444 730 129072668 731 129779828 732 130488924 733 131199956 734 131912924 735 132627828 736 133415420 737 134075444 738 134737084 739 135459540 740 136183932 741 136910260 742 137638524 743 138446100 744 139256028 745 139889268 746 140523900 747 141159924 748 141920176 749 142682476 750 143606036 751 144532492 752 145461844 753 146255356 754 147051028 755 147848860 756 148648852 757 149541964 758 150437716 759 151336108 760 152237140 761 152921356 762 153607060 763 154294252 764 155148172 765 156004444 766 156961244 767 157920908 768 158883436 769 159750268 770 160619452 771 161552748 772 162488716 773 163427356 774 164368668 775 165377836 776 166390012 777 167106444 778 167936524 779 168768652 780 169602828 781 170439052 782 171277324 783 172117644 784 173047932 785 173924124 786 174802524 787 175683132 788 176565948 789 177450972 790 178338204 791 179227644 792 180296924 793 181242268 794 182190076 795 183140348 796 184093084 797 185048284 798 186005948 799 187023676 800 188044156 801 188939068 802 189977420 803 191018588 804 192062572 805 193109372 806 194301020 807 195496188 808 196694876 809 197573084 810 198453212 811 199374236 812 200297372 813 201313788 814 202332764 815 203354300 816 204378396 817 205300348 818 206224348 819 207150396 820 208314940 821 209482684 822 210653628 823 211827772 824 213005116 825 213848652 826 214693756 827 215636476 828 216581228 829 217601052 830 218623260 831 219647852 832 220674828 833 221544060 834 222575228 835 223608780 836 224644716 837 225683036 838 226824420 839 227968668 840 229115780 841 230157980 842 231202532 843 232249436 844 233298692 845 234350300 846 235404260 847 236538588 848 237862416 849 239013044 850 240166440 851 241322604 852 242481536 853 243643236 854 244807704 855 246077660 856 247474272 857 248510916 858 249549688 859 250590588 860 251633616 861 252678772 862 253864136 863 255052268 864 256243168 865 257367556 866 258494392 867 259623676 868 260755408 869 261993988 870 263235496 871 264479932 872 265727296 873 266600020 874 267641944 875 268685836 876 269907096 877 271131124 878 272357920 879 273587484 880 274819816 881 275913796 882 277009904 883 278246044 884 279484936 885 280726580 886 281970976 887 283218124 888 284468024 889 285464356 890 286686820 891 287911892 892 289246732 893 290584660 894 291925676 895 293269780 896 294616972 897 295909780 898 297205420 899 298503892 900 299805196 901 301181492 902 302560940 903 303943540 904 305481332 905 306617060 906 307754820 907 308894612 908 310036436 909 311180292 910 312508380 911 313926852 912 315348540 913 316641828 914 317937756 915 319236324 916 320537532 917 321841380 918 323386808 919 324994796 920 326606720 921 327898036 922 329191880 923 330488252 924 331787152 925 333162660 926 334541016 927 335922220 928 337495788 929 338864700 930 340236380 931 341610828 932 343189572 933 344771948 934 346357956 935 347947596 936 349540868 937 350957676 938 352377348 939 353923964 940 355473972 941 357027372 942 358584164 943 360144348 944 361707924 945 363055420 946 364632660 947 366213324 948 367797412 949 369384924 950 370975860 951 372570220 952 374168004 953 375524988 954 376884372 955 378345580 956 379809604 957 381276444 958 382746100 959 384218572 960 385955252 961 387572700 962 389193540 963 390817772 964 392649976 965 394486420 966 396327104 967 398257212 968 400191912 969 401704404 970 403219728 971 404737884 972 406258872 973 407852820 974 409718988 975 411589380 976 413463996 977 415108116 978 416755500 979 418406148 980 420060060 981 421811508 982 423778932 983 425750868 984 427727316 985 429392756 986 431061428 987 432733332 988 434590444 989 436451524 990 438316572 991 440264948 992 442217612 993 443936004 994 445657724 995 447522212 996 449390588 997 451262852 998 453139004 999 455019044 1000 457047116