0 1 1 4 2 8 3 16 4 32 5 52 6 72 7 90 8 120 9 160 10 208 11 264 12 320 13 316 14 406 15 452 16 484 17 616 18 740 19 696 20 828 21 906 22 944 23 1076 24 1176 25 1364 26 1492 27 1392 28 1586 29 1660 30 1884 31 1944 32 2276 33 2312 34 2348 35 2370 36 2636 37 2800 38 2916 39 3408 40 3456 41 3236 42 3542 43 3728 44 4076 45 4040 46 4708 47 4772 48 4592 49 4578 50 5168 51 5428 52 5420 53 6208 54 6440 55 5816 56 6238 57 6508 58 7200 59 6908 60 7936 61 8092 62 7668 63 7578 64 8428 65 8968 66 8740 67 9828 68 10096 69 9416 70 9594 71 10004 72 11308 73 10492 74 12056 75 12248 76 11620 77 11294 78 12476 79 13208 80 12968 81 14220 82 14724 83 13728 84 13686 85 14384 86 16144 87 15084 88 16944 89 17180 90 16316 91 15858 92 17200 93 18380 94 17996 95 19500 96 20148 97 18728 98 18822 99 19448 100 21800 101 20252 102 22908 103 22880 104 21752 105 21294 106 22716 107 24344 108 23840 109 25720 110 26380 111 24592 112 24430 113 25476 114 28228 115 26252 116 29760 117 29396 118 28072 119 27350 120 29196 121 31164 122 30344 123 32676 124 33672 125 31020 126 30978 127 32260 128 35472 129 33140 130 37356 131 36984 132 35064 133 34082 134 36388 135 38940 136 37524 137 40588 138 41836 139 38228 140 38226 141 39856 142 43824 143 40624 144 45828 145 45160 146 43044 147 41570 148 44328 149 47596 150 45544 151 49320 152 50792 153 46436 154 46210 155 48156 156 52760 157 49132 158 54992 159 54364 160 51864 161 49618 162 53232 163 57028 164 54520 165 58872 166 60528 167 55204 168 55134 169 57072 170 62764 171 58408 172 64940 173 64520 174 61340 175 58710 176 62776 177 67316 178 64056 179 69380 180 71076 181 64868 182 64818 183 66788 184 73620 185 68360 186 76116 187 75284 188 71604 189 68306 190 73340 191 78304 192 74492 193 80796 194 82376 195 75476 196 75134 197 77488 198 85292 199 79100 200 87708 201 87212 202 82568 203 78778 204 84680 205 90008 206 85940 207 92912 208 94816 209 86712 210 86206 211 88640 212 98040 213 90508 214 100376 215 99940 216 94252 217 90118 218 96652 219 102984 220 97948 221 105852 222 107792 223 98932 224 97922 225 100820 226 111596 227 102596 228 114064 229 113348 230 107052 231 102102 232 109412 233 116328 234 111112 235 119496 236 121756 237 111976 238 110358 239 113856 240 125832 241 115840 242 128480 243 127588 244 120188 245 115138 246 122856 247 130736 248 124964 249 133972 250 136756 251 125600 252 123902 253 127500 254 140960 255 129452 256 143996 257 142520 258 134408 259 128834 260 137020 261 146160 262 139448 263 149648 264 152476 265 139940 266 137726 267 142372 268 156740 269 144012 270 160400 271 158232 272 149520 273 143150 274 152380 275 162236 276 154672 277 165712 278 169392 279 154916 280 152586 281 157916 282 173344 283 159512 284 177412 285 175288 286 165264 287 158114 288 168060 289 179488 290 170596 291 182868 292 187052 293 170652 294 168370 295 174004 296 191240 297 175640 298 195276 299 192632 300 182156 301 173678 302 184760 303 197668 304 187136 305 200976 306 205504 307 187568 308 184674 309 190884 310 209480 311 192916 312 213800 313 211072 314 199848 315 189890 316 202472 317 216380 318 204992 319 219788 320 224648 321 204812 322 202134 323 208328 324 228892 325 210900 326 233100 327 230592 328 218028 329 207414 330 220720 331 235864 332 223144 333 239804 334 244524 335 223076 336 220322 337 226464 338 249316 339 229520 340 253732 341 250644 342 237116 343 225014 344 240124 345 256136 346 242340 347 260628 348 265096 349 242328 350 239094 351 245896 352 270348 353 248844 354 274652 355 272032 356 256656 357 243778 358 260352 359 277008 360 262596 361 282012 362 287112 363 262160 364 258510 365 265512 366 292680 367 268712 368 296840 369 294140 370 276908 371 263534 372 281060 373 299324 374 283324 375 304324 376 309312 377 283124 378 278602 379 286224 380 315748 381 289356 382 320032 383 316844 384 298556 385 283690 386 302620 387 321792 388 305312 389 327248 390 332764 391 304828 392 299214 393 308040 394 339496 395 311216 396 343848 397 340408 398 320276 399 305130 400 324672 401 345536 402 328036 403 350824 404 357356 405 327024 406 321222 407 330372 408 363992 409 333184 410 369012 411 364648 412 343176 413 327130 414 347508 415 370356 416 351208 417 375944 418 382476 419 349980 420 343294 421 353864 422 389220 423 356388 424 394880 425 389576 426 367152 427 349642 428 371668 429 395796 430 375200 431 401056 432 408984 433 373552 434 366482 435 378108 436 415136 437 380624 438 421348 439 415924 440 391672 441 372874 442 395876 443 422568 444 399740 445 427464 446 436268 447 397764 448 390706 449 402796 450 442624 451 405324 452 448572 453 442432 454 417476 455 396638 456 421304 457 450024 458 424992 459 455064 460 464000 461 423416 462 415466 463 428216 464 470080 465 431396 466 476512 467 470136 468 443992 469 420998 470 447816 471 478052 472 451712 473 483132 474 492600 475 449024 476 441510 477 454216 478 498860 479 458140 480 505124 481 499012 482 470940 483 446878 484 474768 485 506872 486 478400 487 512592 488 521836 489 475908 490 468194 491 480816 492 528828 493 485268 494 535388 495 528404 496 498612 497 472606 498 503180 499 536260 500 506276 501 542916 502 551760 503 503824 504 495294 505 508972 506 559300 507 513196 508 565556 509 559224 510 526872 511 499582 512 532216 513 566336 514 535364 515 573644 516 583304 517 532164 518 523126 519 537064 520 591200 521 541600 522 597160 523 590744 524 555756 525 527646 526 561660 527 598100 528 564812 529 605160 530 614824 531 561932 532 551442 533 566416 534 623884 535 570608 536 629872 537 622868 538 586204 539 556002 540 591956 541 629708 542 595696 543 637304 544 647692 545 592356 546 580358 547 596868 548 657040 549 601216 550 663144 551 655704 552 616468 553 585822 554 622712 555 662792 556 627196 557 670064 558 681860 559 623140 560 610830 561 627756 562 691000 563 631680 564 697828 565 689092 566 648208 567 616210 568 654060 569 697036 570 659168 571 704524 572 716380 573 654772 574 641078 575 659992 576 725644 577 663416 578 733240 579 723240 580 681000 581 646970 582 687068 583 731704 584 691912 585 738800 586 752472 587 686864 588 672650 589 692944 590 760840 591 696400 592 769132 593 758988 594 714272 595 678406 596 719812 597 767952 598 725148 599 774536 600 789228 601 719488 602 705506 603 726188 604 797768 605 729764 606 805852 607 794548 608 748908 609 710438 610 753984 611 804792 612 759016 613 811492 614 826416 615 753912 616 738546 617 760208 618 834552 619 764520 620 843184 621 831552 622 784248 623 742958 624 789336 625 842080 626 794544 627 848924 628 864472 629 787864 630 773158 631 794764 632 872732 633 799972 634 881108 635 869868 636 819900 637 777114 638 825120 639 880168 640 829712 641 887952 642 903076 643 823264 644 808322 645 829920 646 912252 647 835636 648 920916 649 908552 650 856316 651 810942 652 862340 653 918828 654 866412 655 927536 656 942336 657 859944 658 843774 659 866804 660 952124 661 872120 662 960364 663 948896 664 893232 665 846086 666 900264 667 958140 668 904236 669 967564 670 983472 671 896900 672 879950 673 903212 674 993728 675 909080 676 1001312 677 989888 678 930732 679 882450 680 938460 681 999316 682 942420 683 1008376 684 1024248 685 935416 686 916570 687 941184 688 1035916 689 946592 690 1043624 691 1031168 692 970060 693 919138 694 977388 695 1040076 696 982224 697 1049716 698 1066556 699 974572 700 953734 701 980316 702 1078544 703 985916 704 1086232 705 1073328 706 1008964 707 957318 708 1016784 709 1082404 710 1022660 711 1091672 712 1110148 713 1014012 714 992742 715 1019736 716 1121920 717 1024816 718 1130548 719 1115988 720 1049352 721 996046 722 1056788 723 1126076 724 1063312 725 1135532 726 1154156 727 1054144 728 1031230 729 1060784 730 1165852 731 1065192 732 1175560 733 1159204 734 1090992 735 1035130 736 1098612 737 1170008 738 1104792 739 1178948 740 1199800 741 1094792 742 1071218 743 1102400 744 1210360 745 1106860 746 1220908 747 1204372 748 1132928 749 1074862 750 1139956 751 1215628 752 1146684 753 1224040 754 1246124 755 1135888 756 1112490 757 1144248 758 1256904 759 1148764 760 1267012 761 1249108 762 1176508 763 1114978 764 1182856 765 1261928 766 1189128 767 1270444 768 1292760 769 1178908 770 1153938 771 1186976 772 1302856 773 1192248 774 1313784 775 1295412 776 1220632 777 1155614 778 1227088 779 1308520 780 1233480 781 1317112 782 1340280 783 1221320 784 1197062 785 1230052 786 1350508 787 1236368 788 1361004 789 1343188 790 1265004 791 1198114 792 1271576 793 1355908 794 1277240 795 1365560 796 1388236 797 1265392 798 1240690 799 1273588 800 1399628 801 1280668 802 1410308 803 1391176 804 1310164 805 1239954 806 1317716 807 1403884 808 1322580 809 1414544 810 1436912 811 1310708 812 1284462 813 1319220 814 1448964 815 1325744 816 1458972 817 1440924 818 1355832 819 1283366 820 1364408 821 1452372 822 1369308 823 1463864 824 1487496 825 1356308 826 1329062 827 1364036 828 1500136 829 1371212 830 1509384 831 1491328 832 1401916 833 1328122 834 1411316 835 1502880 836 1416308 837 1513944 838 1537488 839 1403648 840 1374010 841 1410532 842 1551860 843 1417280 844 1561200 845 1541888 846 1450140 847 1372990 848 1458940 849 1552844 850 1464968 851 1564524 852 1589236 853 1451440 854 1419510 855 1458364 856 1603848 857 1465348 858 1613296 859 1593300 860 1497516 861 1419654 862 1507088 863 1604380 864 1514212 865 1615692 866 1642396 867 1499468 868 1466942 869 1506416 870 1656688 871 1512588 872 1667260 873 1645180 874 1546608 875 1466830 876 1555644 877 1657392 878 1563640 879 1669028 880 1695788 881 1548144 882 1513694 883 1556212 884 1709956 885 1561592 886 1721784 887 1697604 888 1597128 889 1514014 890 1606380 891 1710672 892 1613768 893 1721604 894 1751056 895 1597284 896 1562018 897 1606600 898 1763824 899 1611884 900 1776556 901 1752240 902 1647744 903 1561982 904 1656276 905 1765788 906 1664356 907 1775876 908 1806972 909 1646888 910 1611746 911 1657096 912 1819856 913 1662336 914 1832172 915 1806100 916 1700172 917 1610290 918 1707952 919 1821476 920 1715344 921 1831724 922 1863056 923 1698628 924 1661570 925 1708284 926 1875168 927 1714664 928 1888168 929 1861732 930 1753216 931 1659002 932 1760976 933 1877400 934 1768576 935 1887656 936 1919992 937 1749484 938 1713198 939 1759916 940 1932276 941 1767448 942 1944732 943 1918856 944 1806356 945 1709874 946 1814128 947 1934140 948 1820888 949 1945516 950 1977364 951 1802152 952 1765290 953 1811972 954 1990916 955 1820320 956 2003564 957 1976168 958 1860252 959 1759770 960 1869164 961 1991272 962 1875044 963 2003952 964 2035216 965 1856228 966 1817550 967 1866184 968 2049636 969 1874080 970 2061524 971 2035340 972 1914544 973 1811442 974 1924704 975 2048956 976 1930596 977 2062536 978 2095392 979 1910392 980 1870494 981 1919444 982 2110400 983 1928132 984 2121352 985 2095068 986 1969284 987 1864602 988 1980308 989 2108872 990 1986308 991 2121916 992 2154664 993 1966448 994 1923770 995 1974572 996 2171660 997 1982588 998 2182768 999 2154968 1000 2026252