0 1 1 4 2 8 3 18 4 32 5 52 6 70 7 98 8 132 9 152 10 200 11 242 12 286 13 324 14 404 15 422 16 520 17 564 18 646 19 690 20 828 21 820 22 988 23 1026 24 1154 25 1188 26 1400 27 1354 28 1608 29 1620 30 1806 31 1826 32 2124 33 2016 34 2376 35 2354 36 2606 37 2596 38 2996 39 2814 40 3296 41 3220 42 3550 43 3506 44 4020 45 3740 46 4364 47 4226 48 4642 49 4548 50 5192 51 4802 52 5584 53 5364 54 5878 55 5730 56 6516 57 5992 58 6952 59 6642 60 7262 61 7044 62 7988 63 7318 64 8472 65 8052 66 8790 67 8498 68 9612 69 8772 70 10140 71 9602 72 10466 73 10084 74 11384 75 10362 76 11960 77 11284 78 12286 79 11810 80 13308 81 12080 82 13928 83 13106 84 14254 85 13668 86 15380 87 13934 88 16048 89 15060 90 16366 91 15666 92 17604 93 15916 94 18316 95 17154 96 18626 97 17796 98 19976 99 18034 100 20736 101 19380 102 21030 103 20066 104 22500 105 20280 106 23304 107 21746 108 23582 109 22468 110 25172 111 22662 112 26024 113 24244 114 26278 115 25010 116 27996 117 25172 118 28892 119 26882 120 29122 121 27684 122 30968 123 27818 124 31912 125 29652 126 32110 127 30498 128 34092 129 30592 130 35080 131 32562 132 35246 133 33444 134 37364 135 33502 136 38400 137 35604 138 38526 139 36530 140 40788 141 36540 142 41868 143 38786 144 41954 145 39748 146 44360 147 39714 148 45488 149 42100 150 45526 151 43106 152 48084 153 43016 154 49256 155 45554 156 49246 157 46596 158 51956 159 46454 160 53176 161 49140 162 53110 163 50226 164 55980 165 50020 166 57244 167 52866 168 57122 169 53988 170 60152 171 53722 172 61464 173 56724 174 61278 175 57890 176 64476 177 57552 178 65832 179 60722 180 65582 181 61924 182 68948 183 61518 184 70352 185 64852 186 70030 187 66098 188 73572 189 65612 190 75020 191 69122 192 74626 193 70404 194 78344 195 69842 196 79840 197 73524 198 79366 199 74850 200 83268 201 74200 202 84808 203 78066 204 84254 205 79428 206 88340 207 78694 208 89928 209 82740 210 89286 211 84146 212 93564 213 83316 214 95196 215 87554 216 94466 217 88996 218 98936 219 88074 220 100616 221 92500 222 99790 223 93986 224 104460 225 92960 226 106184 227 97586 228 105262 229 99108 230 110132 231 97982 232 111904 233 102804 234 110878 235 104370 236 115956 237 103132 238 117772 239 108162 240 116642 241 109764 242 121928 243 108418 244 123792 245 113652 246 122550 247 115298 248 128052 249 113832 250 129960 251 119282 252 128606 253 120964 254 134324 255 119382 256 136280 257 125044 258 134806 259 126770 260 140748 261 125060 262 142748 263 130946 264 141154 265 132708 266 147320 267 130874 268 149368 269 136980 270 147646 271 138786 272 154044 273 136816 274 156136 275 143154 276 154286 277 144996 278 160916 279 142894 280 163056 281 149460 282 161070 283 151346 284 167940 285 149100 286 170124 287 155906 288 168002 289 157828 290 175112 291 155442 292 177344 293 162484 294 175078 295 164450 296 182436 297 161912 298 184712 299 169202 300 182302 301 171204 302 189908 303 168518 304 192232 305 176052 306 189670 307 178098 308 197532 309 175252 310 199900 311 183042 312 197186 313 185124 314 205304 315 182122 316 207720 317 190164 318 204846 319 192290 320 213228 321 189120 322 215688 323 197426 324 212654 325 199588 326 221300 327 196254 328 223808 329 204820 330 220606 331 207026 332 229524 333 203516 334 232076 335 212354 336 228706 337 214596 338 237896 339 210914 340 240496 341 220020 342 236950 343 222306 344 246420 345 218440 346 249064 347 227826 348 245342 349 230148 350 255092 351 226102 352 257784 353 235764 354 253878 355 238130 356 263916 357 233892 358 266652 359 243842 360 262562 361 246244 362 272888 363 241818 364 275672 365 252052 366 271390 367 254498 368 282012 369 249872 370 284840 371 260402 372 280366 373 262884 374 291284 375 258062 376 294160 377 268884 378 289486 379 271410 380 300708 381 266380 382 303628 383 277506 384 298754 385 280068 386 310280 387 274834 388 313248 389 286260 390 308166 391 288866 392 320004 393 283416 394 323016 395 295154 396 317726 397 297796 398 329876 399 292134 400 332936 401 304180 402 327430 403 306866 404 339900 405 300980 406 343004 407 313346 408 337282 409 316068 410 350072 411 309962 412 353224 413 322644 414 347278 415 325410 416 360396 417 319072 418 363592 419 332082 420 357422 421 334884 422 370868 423 328318 424 374112 425 341652 426 367710 427 344498 428 381492 429 337692 430 384780 431 351362 432 378146 433 354244 434 392264 435 347202 436 395600 437 361204 438 388726 439 364130 440 403188 441 356840 442 406568 443 371186 444 399454 445 374148 446 414260 447 366614 448 417688 449 381300 450 410326 451 384306 452 425484 453 376516 454 428956 455 391554 456 421346 457 394596 458 436856 459 386554 460 440376 461 401940 462 432510 463 405026 464 448380 465 396720 466 451944 467 412466 468 443822 469 415588 470 460052 471 407022 472 463664 473 423124 474 455278 475 426290 476 471876 477 417452 478 475532 479 433922 480 466882 481 437124 482 483848 483 428018 484 487552 485 444852 486 478630 487 448098 488 495972 489 438712 490 499720 491 455922 492 490526 493 459204 494 508244 495 449542 496 512040 497 467124 498 502566 499 470450 500 520668 501 460500 502 524508 503 478466 504 514754 505 481828 506 533240 507 471594 508 537128 509 489940 510 527086 511 493346 512 545964 513 482816 514 549896 515 501554 516 539566 517 504996 518 558836 519 494174 520 562816 521 513300 522 552190 523 516786 524 571860 525 505660 526 575884 527 525186 528 564962 529 528708 530 585032 531 517282 532 589104 533 537204 534 577878 535 540770 536 598356 537 529032 538 602472 539 549362 540 590942 541 552964 542 611828 543 540918 544 615992 545 561652 546 604150 547 565298 548 625452 549 552932 550 629660 551 574082 552 617506 553 577764 554 639224 555 565082 556 643480 557 586644 558 631006 559 590370 560 653148 561 577360 562 657448 563 599346 564 644654 565 603108 566 667220 567 589774 568 671568 569 612180 570 658446 571 615986 572 681444 573 602316 574 685836 575 625154 576 672386 577 628996 578 695816 579 614994 580 700256 581 638260 582 686470 583 642146 584 710340 585 627800 586 714824 587 651506 588 700702 589 655428 590 725012 591 640742 592 729544 593 664884 594 715078 595 668850 596 739836 597 653812 598 744412 599 678402 600 729602 601 682404 602 754808 603 667018 604 759432 605 692052 606 744270 607 696098 608 769932 609 680352 610 774600 611 705842 612 759086 613 709924 614 785204 615 693822 616 789920 617 719764 618 774046 619 723890 620 800628 621 707420 622 805388 623 733826 624 789154 625 737988 626 816200 627 721154 628 821008 629 748020 630 804406 631 752226 632 831924 633 735016 634 836776 635 762354 636 819806 637 766596 638 847796 639 749014 640 852696 641 776820 642 835350 643 781106 644 863820 645 763140 646 868764 647 791426 648 851042 649 795748 650 879992 651 777402 652 884984 653 806164 654 866878 655 810530 656 896316 657 791792 658 901352 659 821042 660 882862 661 825444 662 912788 663 806318 664 917872 665 836052 666 898990 667 840498 668 929412 669 820972 670 934540 671 851202 672 915266 673 855684 674 946184 675 835762 676 951360 677 866484 678 931686 679 871010 680 963108 681 850680 682 968328 683 881906 684 948254 685 886468 686 980180 687 865734 688 985448 689 897460 690 964966 691 902066 692 997404 693 880916 694 1002716 695 913154 696 981826 697 917796 698 1014776 699 896234 700 1020136 701 928980 702 998830 703 933666 704 1032300 705 911680 706 1037704 707 944946 708 1015982 709 949668 710 1049972 711 927262 712 1055424 713 961044 714 1033278 715 965810 716 1067796 717 942972 718 1073292 719 977282 720 1050722 721 982084 722 1085768 723 958818 724 1091312 725 993652 726 1068310 727 998498 728 1103892 729 974792 730 1109480 731 1010162 732 1086046 733 1015044 734 1122164 735 990902 736 1127800 737 1026804 738 1103926 739 1031730 740 1140588 741 1007140 742 1146268 743 1043586 744 1121954 745 1048548 746 1159160 747 1023514 748 1164888 749 1060500 750 1140126 751 1065506 752 1177884 753 1040016 754 1183656 755 1077554 756 1158446 757 1082596 758 1196756 759 1056654 760 1202576 761 1094740 762 1176910 763 1099826 764 1215780 765 1073420 766 1221644 767 1112066 768 1195522 769 1117188 770 1234952 771 1090322 772 1240864 773 1129524 774 1214278 775 1134690 776 1254276 777 1107352 778 1260232 779 1147122 780 1233182 781 1152324 782 1273748 783 1124518 784 1279752 785 1164852 786 1252230 787 1170098 788 1293372 789 1141812 790 1299420 791 1182722 792 1271426 793 1188004 794 1313144 795 1159242 796 1319240 797 1200724 798 1290766 799 1206050 800 1333068 801 1176800 802 1339208 803 1218866 804 1310254 805 1224228 806 1353140 807 1194494 808 1359328 809 1237140 810 1329886 811 1242546 812 1373364 813 1212316 814 1379596 815 1255554 816 1349666 817 1260996 818 1393736 819 1230274 820 1400016 821 1274100 822 1369590 823 1279586 824 1414260 825 1248360 826 1420584 827 1292786 828 1389662 829 1298308 830 1434932 831 1266582 832 1441304 833 1311604 834 1409878 835 1317170 836 1455756 837 1284932 838 1462172 839 1330562 840 1430242 841 1336164 842 1476728 843 1303418 844 1483192 845 1349652 846 1450750 847 1355298 848 1497852 849 1322032 850 1504360 851 1368882 852 1471406 853 1374564 854 1519124 855 1340782 856 1525680 857 1388244 858 1492206 859 1393970 860 1540548 861 1359660 862 1547148 863 1407746 864 1513154 865 1413508 866 1562120 867 1378674 868 1568768 869 1427380 870 1534246 871 1433186 872 1583844 873 1397816 874 1590536 875 1447154 876 1555486 877 1452996 878 1605716 879 1417094 880 1612456 881 1467060 882 1576870 883 1472946 884 1627740 885 1436500 886 1634524 887 1487106 888 1598402 889 1493028 890 1649912 891 1456042 892 1656744 893 1507284 894 1620078 895 1513250 896 1672236 897 1475712 898 1679112 899 1527602 900 1641902 901 1533604 902 1694708 903 1495518 904 1701632 905 1548052 906 1663870 907 1554098 908 1717332 909 1515452 910 1724300 911 1568642 912 1685986 913 1574724 914 1740104 915 1535522 916 1747120 917 1589364 918 1708246 919 1595490 920 1763028 921 1555720 922 1770088 923 1610226 924 1730654 925 1616388 926 1786100 927 1576054 928 1793208 929 1631220 930 1753206 931 1637426 932 1809324 933 1596516 934 1816476 935 1652354 936 1775906 937 1658596 938 1832696 939 1617114 940 1839896 941 1673620 942 1798750 943 1679906 944 1856220 945 1637840 946 1863464 947 1695026 948 1821742 949 1701348 950 1879892 951 1658702 952 1887184 953 1716564 954 1844878 955 1722930 956 1903716 957 1679692 958 1911052 959 1738242 960 1868162 961 1744644 962 1927688 963 1700818 964 1935072 965 1760052 966 1891590 967 1766498 968 1951812 969 1722072 970 1959240 971 1782002 972 1915166 973 1788484 974 1976084 975 1743462 976 1983560 977 1804084 978 1938886 979 1810610 980 2000508 981 1764980 982 2008028 983 1826306 984 1962754 985 1832868 986 2025080 987 1786634 988 2032648 989 1848660 990 1986766 991 1855266 992 2049804 993 1808416 994 2057416 995 1871154 996 2010926 997 1877796 998 2074676 999 1830334 1000 2082336