0 0 1 4 2 3 3 24 4 23 5 44 6 43 7 112 8 111 9 180 10 76 11 264 12 248 13 348 14 164 15 480 16 479 17 411 18 611 19 327 20 183 21 115 22 139 23 943 24 1103 25 747 26 787 27 1111 28 1447 29 323 30 699 31 1984 32 1983 33 1851 34 2243 35 2008 36 1576 37 1388 38 1684 39 1072 40 976 41 1268 42 499 43 3383 44 3271 45 4124 46 4068 47 3679 48 4511 49 4315 50 3804 51 4999 52 3464 53 3532 54 5428 55 6160 56 6128 57 5716 58 6572 59 5783 60 1176 61 3452 62 2692 63 8064 64 8063 65 7803 66 8579 67 8600 68 9111 69 8876 70 6827 71 9968 72 10512 73 6708 74 5939 75 9352 76 6791 77 6620 78 12324 79 11935 80 12639 81 3867 82 13539 83 13767 84 5175 85 5875 86 10740 87 9519 88 10959 89 15979 90 7571 91 16599 92 16088 93 15420 94 17467 95 14527 96 18239 97 19012 98 13891 99 17240 100 17064 101 12307 102 11755 103 12976 104 11600 105 11659 106 10099 107 9800 108 14407 109 21148 110 12644 111 8480 112 7904 113 9124 114 9820 115 6151 116 5623 117 25932 118 7092 119 24208 120 29040 121 4907 122 21715 123 29928 124 10008 125 23292 126 11003 127 32512 128 32511 129 31995 130 33539 131 31463 132 30440 133 35539 134 36139 135 32624 136 37008 137 29259 138 29875 139 26615 140 31224 141 40028 142 36260 143 24800 144 24352 145 39780 146 26467 147 42567 148 41911 149 44403 150 36980 151 21328 152 19632 153 30740 154 18924 155 38056 156 29016 157 49084 158 50244 159 47423 160 50879 161 13764 162 19907 163 53031 164 13015 165 52332 166 14228 167 17615 168 19247 169 8203 170 41740 171 7624 172 38855 173 39196 174 4836 175 37024 176 36704 177 61988 178 47068 179 31608 180 43383 181 65228 182 66507 183 67344 184 63247 185 64340 186 66387 187 60823 188 60312 189 59516 190 71803 191 57727 192 73343 193 72571 194 56451 195 58727 196 70504 197 77740 198 53163 199 62960 200 67055 201 80692 202 49203 203 82824 204 49543 205 47324 206 83236 207 77920 208 77728 209 79332 210 76316 211 75064 212 73527 213 56307 214 89844 215 76240 216 55759 217 85867 218 44179 219 63528 220 87512 221 83651 222 32452 223 96703 224 99903 225 31931 226 102588 227 101464 228 104023 229 105196 230 30955 231 40527 232 41391 233 22900 234 21107 235 28343 236 101191 237 108643 238 82843 239 114720 240 114656 241 115035 242 79011 243 48888 244 111368 245 86604 246 112308 247 119407 248 8816 249 106964 250 22060 251 86551 252 93671 253 18947 254 43524 255 130560 256 130559 257 129531 258 132611 259 127463 260 134679 261 134611 262 137771 263 135567 264 138863 265 137908 266 140876 267 139511 268 127736 269 143523 270 133796 271 146400 272 148512 273 149604 274 117660 275 118968 276 150199 277 113036 278 154251 279 139856 280 138672 281 107755 282 153875 283 134568 284 137127 285 103612 286 98491 287 99776 288 96832 289 161083 290 103107 291 160216 292 171048 293 89964 294 91284 295 92720 296 170543 297 103156 298 96268 299 105271 300 147143 301 145891 302 113124 303 144479 304 150431 305 75483 306 178979 307 189048 308 73847 309 154675 310 143563 311 144912 312 116239 313 113579 314 64428 315 194408 316 194200 317 192643 318 202884 319 189055 320 204159 321 58491 322 70780 323 69528 324 208488 325 67756 326 81748 327 214256 328 84752 329 77771 330 175411 331 178824 332 55160 333 173020 334 43483 335 207712 336 201888 337 194843 338 170723 339 164807 340 226871 341 96499 342 101387 343 30928 344 100559 345 25707 346 235411 347 42711 348 174887 349 26172 350 238020 351 17728 352 15040 353 86084 354 242620 355 21848 356 106664 357 255468 358 185323 359 159567 360 102224 361 136075 362 261772 363 264119 364 261560 365 257180 366 264036 367 255199 368 269087 369 271963 370 257955 371 267768 372 263159 373 278348 374 278091 375 244880 376 250736 377 247508 378 278828 379 271080 380 272103 381 266492 382 265988 383 230143 384 294143 385 292603 386 227587 387 299800 388 231656 389 286931 390 284884 391 302448 392 216431 393 288692 394 290483 395 312840 396 248824 397 250460 398 313435 399 318176 400 304416 401 203419 402 291171 403 275384 404 308663 405 195724 406 329332 407 192848 408 332111 409 201195 410 203795 411 190120 412 340135 413 185788 414 180667 415 181440 416 179008 417 340027 418 350268 419 210215 420 351447 421 207251 422 339348 423 321231 424 190767 425 165364 426 161036 427 298952 428 161336 429 286492 430 287515 431 169311 432 174751 433 238555 434 311843 435 280952 436 208759 437 305971 438 173620 439 288016 440 365839 441 307540 442 330067 443 393320 444 130456 445 131708 446 126340 447 385919 448 400511 449 141691 450 397692 451 387224 452 391831 453 115283 454 376235 455 119792 456 140271 457 384715 458 124467 459 143752 460 145287 461 119516 462 359204 463 161183 464 166495 465 162788 466 433123 467 366392 468 373047 469 112115 470 114443 471 116688 472 339919 473 438932 474 75411 475 418344 476 87079 477 191683 478 396484 479 328768 480 326592 481 332100 482 333123 483 57767 484 452695 485 200467 486 317716 487 49231 488 342096 489 81035 490 306291 491 304311 492 205496 493 222819 494 306587 495 326176 496 361952 497 97115 498 27996 499 355576 500 498423 501 236620 502 486580 503 166800 504 244623 505 150484 506 406572 507 435223 508 74776 509 224252 510 175099 511 523264 512 523263 513 521211 514 527363 515 517095 516 531479 517 512979 518 529364 519 521103 520 508816 521 505012 522 504908 523 511240 524 531207 525 502435 526 502948 527 523744 528 557600 529 558491 530 487011 531 490168 532 549704 533 500851 534 494452 535 475055 536 505776 537 536852 538 477420 539 581544 540 513624 541 519491 542 534852 543 459712 544 457792 545 592699 546 595139 547 582616 548 600616 549 577171 550 580244 551 571343 552 479184 553 440564 554 614924 555 431816 556 585528 557 435171 558 426980 559 488031 560 495007 561 557860 562 416476 563 430200 564 431735 565 474675 566 637236 567 568303 568 613360 569 449108 570 583084 571 413032 572 655512 573 394883 574 650884 575 648319 576 662399 577 386436 578 669059 579 390552 580 407447 581 635219 582 383316 583 385776 584 388368 585 668107 586 670924 587 358263 588 429703 589 427484 590 435236 591 365215 592 676512 593 633627 594 375011 595 348615 596 612296 597 613644 598 664075 599 626384 600 721200 601 456084 602 594323 603 584488 604 336600 605 340028 606 587716 607 574272 608 572608 609 448068 610 442947 611 567128 612 700072 613 599059 614 293355 615 358064 616 431791 617 679540 618 566412 619 365128 620 496711 621 673436 622 340635 623 777504 624 762592 625 348068 626 677283 627 263160 628 790024 629 780620 630 270260 631 793232 632 800112 633 782123 634 280364 635 250088 636 805656 637 762115 638 782596 639 754943 640 817919 641 231675 642 300803 643 237848 644 304407 645 284371 646 278827 647 277360 648 283792 649 837195 650 808780 651 242696 652 205319 653 718755 654 717220 655 859360 656 844576 657 192356 658 328860 659 211527 660 700343 661 735603 662 828532 663 845999 664 198832 665 361492 666 359916 667 755543 668 221863 669 746563 670 682052 671 672448 672 671040 673 838084 674 908860 675 910119 676 373032 677 130963 678 916587 679 659663 680 384815 681 912372 682 118540 683 672200 684 408519 685 118044 686 893211 687 666784 688 388255 689 97828 690 619555 691 422023 692 156296 693 432844 694 948276 695 901904 696 118000 697 645291 698 106668 699 124520 700 632935 701 328579 702 848772 703 976255 704 989823 705 462715 706 968835 707 704152 708 45207 709 992172 710 334932 711 176624 712 737775 713 558900 714 224204 715 92040 716 760440 717 879836 718 474843 719 445536 720 439200 721 433691 722 1007132 723 723256 724 1047752 725 1052684 726 1053963 727 1039824 728 1052111 729 1051796 730 1029996 731 1027031 732 1066535 733 1039043 734 1069764 735 1016384 736 1015232 737 1021764 738 1073987 739 1028184 740 1096279 741 1031916 742 1035499 743 997967 744 1088080 745 1045131 746 1113715 747 1117512 748 1107783 749 973923 750 1118308 751 998432 752 1096735 753 1127076 754 1095516 755 1107207 756 988936 757 1081779 758 1146187 759 944528 760 1022351 761 953812 762 1029587 763 1062423 764 1029656 765 991740 766 1121796 767 919039 768 1178111 769 1175035 770 913923 771 1185255 772 1168872 773 1195564 774 902699 775 1157744 776 940655 777 1199796 778 1178188 779 1211144 780 1206535 781 1205084 782 956068 783 1226720 784 866271 785 1135716 786 1171356 787 1233735 788 927415 789 853388 790 847499 791 853584 792 1104304 793 1249515 794 998675 795 872023 796 836696 797 972611 798 1084228 799 1081792 800 1080896 801 1152708 802 1024316 803 822744 804 1064919 805 967827 806 1067156 807 1270223 808 1225168 809 874763 810 783347 811 788680 812 1318200 813 774684 814 1323547 815 804768 816 1296287 817 1334564 818 1290019 819 763512 820 752520 821 747571 822 1350859 823 1339920 824 754191 825 1325140 826 768083 827 1320087 828 830823 829 1284988 830 1379460 831 727424 832 714368 833 855940 834 835459 835 736359 836 1222039 837 828588 838 1248427 839 1409264 840 1281808 841 685108 842 1218252 843 1405303 844 670855 845 806876 846 701915 847 1333407 848 1337183 849 916196 850 651548 851 1433543 852 648648 853 670476 854 1161227 855 928976 856 1416399 857 905108 858 1471596 859 1477335 860 1468632 861 694844 862 963131 863 704191 864 704831 865 1420356 866 944195 867 939687 868 851112 869 586220 870 1368043 871 731983 872 996527 873 1001355 874 862860 875 1254472 876 1479096 877 598172 878 1215643 879 944351 880 956191 881 554404 882 705628 883 1520120 884 647176 885 1076403 886 914868 887 1574767 888 518287 889 1579732 890 511276 891 1556759 892 539928 893 509180 894 498436 895 1541887 896 1603839 897 496379 898 1532668 899 1535768 900 1617128 901 1622828 902 1616683 903 1562992 904 521872 905 1506379 906 1641804 907 1629687 908 446471 909 462428 910 1520731 911 1616159 912 469280 913 1526116 914 1541475 915 1478584 916 1662536 917 561011 918 558475 919 1553744 920 546127 921 514580 922 1656851 923 1705303 924 1698648 925 384579 926 1699259 927 409407 928 409791 929 1684420 930 1727427 931 678183 932 423720 933 1739372 934 1402475 935 701135 936 1393360 937 1757684 938 597747 939 351287 940 1502663 941 1375459 942 1500955 943 1631904 944 579936 945 1525796 946 1749468 947 1630855 948 617608 949 1605427 950 299572 951 434448 952 1617648 953 287403 954 767315 955 1461143 956 387480 957 690563 958 1832571 959 268416 960 255872 961 782980 962 1817219 963 773272 964 1334935 965 1847724 966 1278379 967 749583 968 827408 969 1334580 970 1877452 971 313975 972 1778808 973 845532 974 788260 975 719263 976 722527 977 727067 978 329699 979 1227576 980 731848 981 321036 982 1790731 983 230447 984 160719 985 1220244 986 363884 987 179752 988 184280 989 1335100 990 389316 991 1966144 992 1966016 993 1710779 994 644796 995 1719719 996 1192872 997 121619 998 1727211 999 138319 1000 422992