0 1 1 3 2 7 3 23 4 31 5 47 6 199 7 83 8 61 9 257 10 139 11 953 12 991 13 647 14 1735 15 383 16 511 17 1337 18 1069 19 713 20 271 21 1937 22 3223 23 5213 24 751 25 8477 26 4339 27 353 28 1501 29 287 30 829 31 1553 32 2371 33 1811 34 11185 35 3023 36 7381 37 7937 38 6439 39 1433 40 13975 41 2897 42 4183 43 7793 44 9721 45 1307 46 3889 47 6503 48 1921 49 13577 50 3289 51 24743 52 4315 53 18587 54 2719 55 22823 56 8161 57 14537 58 2449 59 20369 60 3181 61 2477 62 12559 63 1913 64 4591 65 15839 66 36979 67 35423 68 25555 69 3347 70 2929 71 9323 72 7957 73 40277 74 9049 75 5033 76 7951 77 21299 78 16279 79 19193 80 8671 81 27461 82 33319 83 10973 84 26191 85 27191 86 141469 87 76013 88 8701 89 2417 90 7159 91 31793 92 7411 93 6407 94 10579 95 38933 96 5191 97 27047 98 29539 99 34703 100 90541 101 5507 102 69543 103 52523 104 31681 105 66557 106 23719 107 51203 108 901 109 83477 110 24289 111 40943 112 13771 113 21341 114 71809 115 36173 116 11491 117 72287 118 11539 119 20789 120 47911 121 68687 122 127609 123 15563 124 40711 125 2777 126 1627 127 10613 128 114721 129 5297 130 181819 131 99203 132 89821 133 188117 134 85063 135 141755 136 43081 137 16547 138 26029 139 35693 140 12301 141 105857 142 90619 143 28943 144 168451 145 56027 146 245299 147 97463 148 65551 149 22937 150 167989 151 50879 152 32131 153 50627 154 126073 155 43103 156 85741 157 46847 158 97789 159 89213 160 61021 161 87977 162 60739 163 105293 164 8503 165 34877 166 71749 167 50393 168 99391 169 142547 170 5359 171 67343 172 77701 173 160337 174 44179 175 11213 176 97201 177 110507 178 91867 179 120293 180 191131 181 62747 182 132679 183 65663 184 20401 185 2297 186 19843 187 75743 188 89011 189 29867 190 27859 191 22973 192 103021 193 56867 194 52639 195 151733 196 34891 197 79337 198 39679 199 77213 200 409471 201 119717 202 172129 203 21173 204 17293 205 45677 206 29929 207 73313 208 113431 209 15947 210 137959 211 86663 212 220141 213 51287 214 14269 215 78923 216 71881 217 57467 218 107329 219 199043 220 32161 221 143177 222 64069 223 18143 224 143701 225 59729 226 15289 227 187493 228 101911 229 20177 230 219547 231 169643 232 34381 233 27467 234 23209 235 43613 236 102361 237 288227 238 126829 239 187553 240 75631 241 163841 242 157849 243 273383 244 41071 245 368267 246 431569 247 112073 248 44791 249 26687 250 257743 251 29783 252 15571 253 85067 254 220639 255 29153 256 77521 257 12677 258 77359 259 473543 260 88111 261 47717 262 205999 263 96773 264 67861 265 201287 266 47179 267 51773 268 82411 269 79217 270 150559 271 209513 272 315691 273 85937 274 49639 275 111803 276 158371 277 136907 278 162889 279 73043 280 91801 281 38261 282 208939 283 176753 284 509101 285 90317 286 567559 287 23483 288 82645 289 55037 290 56755 291 664283 292 167131 293 364937 294 315859 295 18893 296 91915 297 138617 298 73303 299 44729 300 376411 301 170327 302 36889 303 397703 304 127651 305 1054937 306 64459 307 249353 308 424591 309 273137 310 195649 311 74573 312 179371 313 434267 314 68689 315 287393 316 376141 317 126557 318 457819 319 15683 320 14791 321 1141661 322 126979 323 248123 324 454681 325 54257 326 54889 327 470303 328 558403 329 717317 330 187339 331 234863 332 62761 333 433937 334 46399 335 482753 336 64711 337 218537 338 619399 339 68633 340 122641 341 191147 342 172699 343 533903 344 190681 345 911117 346 330469 347 89003 348 82561 349 754877 350 462229 351 1207043 352 262891 353 303077 354 86479 355 206573 356 419101 357 139007 358 39199 359 33653 360 328291 361 245057 362 147109 363 171953 364 642361 365 251717 366 104749 367 89123 368 72841 369 403427 370 185389 371 114503 372 457831 373 237887 374 31429 375 180923 376 119851 377 160697 378 80629 379 1351763 380 85951 381 226727 382 143599 383 237983 384 109651 385 718847 386 122149 387 514853 388 139831 389 43337 390 39133 391 71273 392 12061 393 487037 394 131179 395 935003 396 229051 397 771917 398 239125 399 697733 400 767707 401 674477 402 449809 403 475733 404 738241 405 736727 406 180319 407 208613 408 190291 409 158255 410 826699 411 24923 412 234121 413 24257 414 138589 415 349733 416 75991 417 663647 418 10699 419 374603 420 599275 421 850457 422 127549 423 485903 424 529801 425 215087 426 1030909 427 69089 428 28111 429 576035 430 2869 431 841373 432 320311 433 1225277 434 393637 435 1142543 436 44131 437 1091459 438 394549 439 729683 440 457651 441 993107 442 268789 443 144863 444 294031 445 167369 446 74179 447 48893 448 716173 449 428657 450 1120219 451 79313 452 698851 453 432257 454 95179 455 457553 456 208591 457 611237 458 500059 459 382553 460 586291 461 565367 462 1183129 463 162053 464 37231 465 26267 466 559399 467 12563 468 827251 469 130847 470 242149 471 209993 472 654301 473 557507 474 1857679 475 130343 476 91051 477 1240097 478 130609 479 315083 480 276481 481 484049 482 139459 483 172133 484 817231 485 356607 486 325519 487 482033 488 379441 489 1492517 490 203269 491 992633 492 975511 493 272117 494 1216249 495 136673 496 2298061 497 144737 498 16579 499 187673 500 324661 501 1055477 502 708109 503 609923 504 126481 505 2386547 506 639799 507 328703 508 477091 509 204797 510 91789 511 245213 512 144841 513 908567 514 270409 515 413363 516 143335 517 1127387 518 30499 519 100343 520 1170961 521 616307 522 1884319 523 20663 524 941821 525 25877 526 214519 527 195713 528 422791 529 176717 530 291799 531 159383 532 210661 533 129827 534 333343 535 311723 536 387091 537 159827 538 353149 539 64013 540 617881 541 303737 542 221149 543 268133 544 16831 545 1731377 546 1251799 547 409973 548 242521 549 153797 550 262609 551 153893 552 938311 553 501587 554 208339 555 561251 556 665461 557 545477 558 456109 559 3471533 560 125551 561 309827 562 92569 563 50483 564 111121 565 742157 566 147529 567 371633 568 956941 569 177617 570 565639 571 458243 572 716911 573 84437 574 360109 575 134693 576 791941 577 606329 578 778129 579 443453 580 142561 581 505517 582 565309 583 112223 584 110851 585 140507 586 1000369 587 1123673 588 861871 589 309857 590 228619 591 3350513 592 757861 593 131087 594 1036369 595 141893 596 857581 597 198677 598 240019 599 312293 600 533011 601 1206407 602 235879 603 1565453 604 936121 605 1243157 606 1130479 607 544553 608 444781 609 471497 610 782599 611 887153 612 541231 613 139877 614 227779 615 687863 616 361591 617 425597 618 258319 619 269543 620 1228861 621 686747 622 922729 623 214073 624 238171 625 393557 626 284269 627 199673 628 997831 629 1258577 630 175249 631 102203 632 448291 633 464627 634 678289 635 506693 636 1668481 637 1036997 638 459499 639 565463 640 494521 641 666167 642 1198249 643 491873 644 842581 645 98537 646 1187689 647 770993 648 1173091 649 1056887 650 666409 651 186413 652 692761 653 273167 654 274699 655 170033 656 54781 657 354707 658 942229 659 352673 660 298111 661 880547 662 245629 663 65903 664 573751 665 395897 666 1232689 667 140003 668 626911 669 94127 670 2733079 671 30683 672 633601 673 1436417 674 1322179 675 1750313 676 850261 677 993767 678 272149 679 305063 680 1307101 681 521447 682 2734369 683 1625993 684 1530751 685 876137 686 140089 687 390533 688 915061 689 210377 690 588409 691 81503 692 2502541 693 858107 694 1619059 695 220703 696 351391 697 1152959 698 1802089 699 53813 700 715291 701 1111067 702 1240879 703 1118603 704 305941 705 244037 706 345229 707 373253 708 23761 709 562037 710 8839 711 1222763 712 967711 713 235877 714 253309 715 245573 716 561391 717 287927 718 540679 719 711323 720 83611 721 16127 722 1102219 723 414383 724 403441 725 421547 726 107929 727 114113 728 534331 729 64307 730 1697779 731 188963 732 233971 733 916547 734 2547145 735 1148393 736 689191 737 439367 738 1725349 739 867593 740 1464301 741 342557 742 212479 743 182453 744 937711 745 716507 746 2363689 747 1348193 748 124501 749 1477859 750 2094109 751 789221 752 1045561 753 1115627 754 367993 755 1371593 756 1573621 757 702047 758 219259 759 473663 760 222175 761 267587 762 1707709 763 1186013 764 461341 765 1377407 766 287449 767 235913 768 866491 769 554627 770 1163059 771 494453 772 1427131 773 830927 774 6062569 775 1125623 776 245671 777 774707 778 265729 779 281273 780 2291371 781 1045187 782 712399 783 935723 784 649081 785 370907 786 1950679 787 1277303 788 784141 789 184397 790 221059 791 465743 792 1031551 793 762947 794 1111969 795 902333 796 145141 797 2553647 798 141235 799 408383 800 311131 801 705287 802 2593489 803 341123 804 265471 805 110807 806 713389 807 1931963 808 1088341 809 358097 810 694879 811 943013 812 44041 813 1044767 814 2125819 815 1413053 816 507451 817 1154387 818 106237 819 1810889 820 95641 821 62705 822 774193 823 223463 824 124681 825 88247 826 899389 827 523853 828 239851 829 52307 830 1013899 831 296693 832 650401 833 671417 834 51769 835 983063 836 421531 837 225197 838 295609 839 473213 840 802231 841 775457 842 3335149 843 3363923 844 2743051 845 633197 846 519769 847 301629 848 375751 849 1360427 850 1436119 851 142553 852 1350571 853 865847 854 1220749 855 280373 856 96391 857 1431317 858 1826989 859 1505783 860 837535 861 1260077 862 923929 863 781913 864 448621 865 1932497 866 625519 867 1501883 868 1777621 869 237557 870 2603179 871 2380583 872 1214821 873 4963007 874 3288169 875 1361813 876 394501 877 3821747 878 151789 879 400853 880 2751961 881 164729 882 1120759 883 2964383 884 1054891 885 433457 886 81619 887 3866813 888 951865 889 1071767 890 552319 891 22223 892 105811 893 464147 894 168109 895 1120853 896 427411 897 323447 898 801979 899 252803 900 517891 901 423587 902 576109 903 1185563 904 443701 905 669797 906 173149 907 381023 908 502111 909 624527 910 282859 911 1500413 912 586141 913 1764647 914 580939 915 551813 916 456421 917 160517 918 989539 919 334613 920 1001491 921 788807 922 713779 923 1338833 924 1139611 925 70667 926 1099579 927 3886583 928 1820191 929 3342287 930 1879699 931 277673 932 519451 933 987647 934 122989 935 1937213 936 2170717 937 1376747 938 565129 939 1624613 940 417451 941 570737 942 2145277 943 154913 944 233791 945 1564937 946 662749 947 1388483 948 46141 949 89027 950 3652249 951 6915473 952 655441 953 843737 954 3878299 955 773 956 1658341 957 3493787 958 1253419 959 3265505 960 2383267 961 2198087 962 956359 963 711713 964 1488871 965 532811 966 2064169 967 446543 968 1232971 969 702287 970 1348699 971 459113 972 2387701 973 1097897 974 4366999 975 437153 976 177481 977 851957 978 134899 979 245633 980 846271 981 32147 982 304279 983 1564043 984 560551 985 1440701 986 1039639 987 2277593 988 2876161 989 1576187 990 102319 991 685313 992 172741 993 684617 994 20149 995 5659883 996 466921 997 595967 998 730129 999 570563 1000 217801 1001 2383337 1002 944149 1003 693353 1004 1395841 1005 1088117 1006 224209 1007 2445833 1008 1922821 1009 441917 1010 2619619 1011 1636793 1012 3836041 1013 620387 1014 5648695 1015 1898963 1016 1373941 1017 1696007 1018 99199 1019 578093 1020 632551 1021 236309 1022 201529 1023 109373 1024 405541 1025 3206627 1026 2028619 1027 2812553 1028 2947411 1029 962657 1030 603469 1031 1064873 1032 156511 1033 103487 1034 393979 1035 4523963 1036 40351 1037 789647 1038 65089 1039 1088933 1040 1695301 1041 1496177 1042 1061059 1043 894353 1044 586591 1045 2851187 1046 766849 1047 139613 1048 252031 1049 322187 1050 3551389 1051 133433 1052 2130133 1053 246617 1054 2579569 1055 260993 1056 1561291 1057 1539077 1058 3276349 1059 2525603 1060 1391701 1061 400127 1062 1656289 1063 649103 1064 2102071 1065 3600347 1066 376669 1067 1200113 1068 904111 1069 1684817 1070 7004659 1071 2178893 1072 272341 1073 224657 1074 7565269 1075 1296623 1076 1769461 1077 1503617 1078 788959 1079 1196873 1080 1921111 1081 143027 1082 1447129 1083 446675 1084 452131 1085 2200547 1086 129859 1087 40613