1 1 2 2 3 3 4 4 5 4 6 8 7 5 8 9 9 10 10 13 11 7 12 23 13 8 14 19 15 25 16 25 17 10 18 43 19 11 20 48 21 40 22 34 23 13 24 86 25 35 26 43 27 60 28 87 29 16 30 148 31 17 32 98 33 86 34 64 35 111 36 242 37 20 38 76 39 119 40 259 41 22 42 308 43 23 44 228 45 341 46 103 47 25 48 509 49 146 50 310 51 210 52 343 53 28 54 583 55 359 56 645 57 270 58 151 59 31 60 1358 61 32 62 169 63 891 64 682 65 601 66 1037 67 35 68 702 69 424 70 1406 71 37 72 2380 73 38 74 229 75 1448 76 965 77 1196 78 1762 79 41 80 2714 81 1345 82 274 83 43 84 4178 85 1502 86 298 87 755 88 2974 89 46 90 6079 91 2323 92 1713 93 896 94 349 95 2261 96 6200 97 50 98 2772 99 4421 100 5457 101 52 102 4582 103 53 104 5815 105 8734 106 433 107 55 108 11034 109 56 110 8110 111 1425 112 10957 113 58 114 7078 115 4727 116 3585 117 9025 118 526 119 7636 120 27202 121 4430 122 559 123 1876 124 4468 125 6603 126 26498 127 65 128 11907 129 2134 130 17582 131 67 132 26417 133 13048 134 664 135 26705 136 19555 137 70 138 15724 139 71 140 40005 141 2720 142 739 143 21017 144 58785 145 12167 146 778 147 24522 148 8132 149 76 150 58157 151 77 152 34023 153 33701 154 46611 155 16111 156 59158 157 80 158 901 159 3789 160 76237 161 34506 162 63816 163 83 164 11613 165 72472 166 988 167 85 168 154065 169 27218 170 71755 171 62115 172 13728 173 88 174 44858 175 80753 176 112006 177 5110 178 1126 179 91 180 263648 181 92 182 121108 183 5611 184 94354 185 34484 186 61534 187 102011 188 18822 189 192752 190 136935 191 97 192 228991 193 98 194 1324 195 181818 196 142625 197 100 198 299755 199 101 200 297518 201 7310 202 1429 203 121343 204 259989 205 54137 206 1483 207 193455 208 307045 209 210570 210 654754 211 107 212 28998 213 8616 214 1594 215 66879 216 694818 217 176638 218 1651 219 9324 220 520784 221 304549 222 146260 223 113 224 609199 225 580106 226 1768 227 115 228 519554 229 116 230 453952 231 681648 232 362578 233 118 234 849969 235 99575 236 42870 237 11680 238 675595 239 121 240 1793138 241 122 242 435460 243 541431 244 48453 245 474694 246 245635 247 674645 248 544816 249 13454 250 792621 251 127 252 2354488 253 803840 254 2209 255 994707 256 796651 257 130 258 313553 259 490711 260 1606886 261 873510 262 2344 263 133 264 2667805 265 171530 266 1488063 267 16440 268 68527 269 136 270 3578172 271 137 272 1893414 273 2126882 274 2554 275 1697695 276 1922055 277 140 278 2626 279 1378523 280 4267140 281 142 282 497414 283 143 284 85023 285 2224191 286 3045568 287 901419 288 5725167 289 1081721 290 2244130 291 21070 292 94313 293 148 294 3778384 295 280235 296 1666545 297 4828890 298 3001 299 2971315 300 8051625 301 1199372 302 3079 303 23681 304 4378137 305 326739 306 5524986 307 155 308 6386898 309 25064 310 3651006 311 157 312 9073410 313 158 314 3319 315 9643249 316 126810 317 160 318 937420 319 4735817 320 8997116 321 27990 322 6515108 323 5344788 324 11254770 325 6374853 326 3568 327 29535 328 3260752 329 2055566 330 16569715 331 167 332 152733 333 4819231 334 3739 335 504457 336 23456516 337 170 338 6110318 339 32794 340 12289660 341 8103324 342 13088808 343 2651848 344 4474512 345 10374712 346 4003 347 175 348 11499424 349 176 350 22147924 351 18574763 352 19525480 353 178 354 1665283 355 660815 356 198855 357 16157210 358 4276 359 181 360 52096193 361 6907082 362 4369 363 13579853 364 25917825 365 752357 366 1994042 367 185 368 21161477 369 10205974 370 13981186 371 4299955 372 19987402 373 188 374 27907516 375 21647305 376 8143375 377 21681650 378 55436043 379 191 380 31265364 381 46080 382 4849 383 193 384 44024442 385 28508533 386 4948 387 14533745 388 275772 389 196 390 67597154 391 29363102 392 37631602 393 50446 394 5149 395 1089447 396 89736323 397 200 398 5251 399 41148629 400 75897610 401 202 402 3322852 403 39767147 404 321708 405 64473969 406 48505728 407 35448163 408 80540680 409 206 410 31424818 411 57500 412 346723 413 8385708 414 66780218 415 1374533 416 89153865 417 59990 418 75755749 419 211 420 227381070 421 212 422 5884 423 28361251 424 18557206 425 67317985 426 4567348 427 10337351 428 401112 429 126905030 430 46074400 431 217 432 222474724 433 218 434 90228910 435 87690550 436 430595 437 82676320 438 5322559 439 221 440 176314587 441 95948776 442 141760873 443 223 444 93124656 445 1911203 446 6553 447 73525 448 191606159 449 226 450 299929499 451 86043296 452 494418 453 76456 454 6784 455 141810558 456 217615004 457 230 458 6901 459 196167445 460 180115659 461 232 462 366337674 463 233 464 184595677 465 170173851 466 7138 467 235 468 432389775 469 18698536 470 95171818 471 85715 472 39211063 473 130737022 474 8241158 475 196175636 476 318585125 477 71091430 478 7501 479 241 480 734721902 481 212349771 482 7624 483 244219386 484 196086727 485 2874780 486 310290639 487 245 488 49588404 489 95694 490 426526522 491 247 492 237314386 493 303790793 494 425048111 495 612704386 496 362792788 497 27043402 498 10848206 499 251 500 413585121 501 102760 502 8254 503 253 504 1189240240 505 3484268 506 481991923 507 355625080 508 774992 509 256 510 836902652 511 32294671 512 378267908 513 566552521 514 8644 515 3825535 516 369738033 517 288696980 518 509838094 519 113999 520 918690880 521 262 522 649115465 523 263 524 873543 525 1173805105 526 9043 527 627246733 528 1682016694 529 286098026 530 258783928 531 163729235 532 989597727 533 583904281 534 16025773 535 4588271 536 96529330 537 126030 538 9451 539 465850461 540 2775916569 541 272 542 9589 543 130221 544 1362776497 545 5012765 546 2085014743 547 275 548 1038657 549 212726676 550 1506445829 551 981821117 552 1391303443 553 53613518 554 10009 555 1081085608 556 1098580 557 280 558 1331829658 559 941967857 560 3246620906 561 1867119817 562 10294 563 283 564 858717972 565 5955986 566 10438 567 1613653954 568 146234545 569 286 570 2615594050 571 287 572 2352633936 573 152576 574 1465714211 575 1441735173 576 4011307764 577 290 578 1284844171 579 157334 580 2036050784 581 73731704 582 26000084 583 859574561 584 178597074 585 3762245584 586 11173 587 295 588 4160898554 589 2129406696 590 643388371 591 167145 592 2420952523 593 298 594 5364609657 595 2572257124 596 1438050 597 172200 598 3186151898 599 301 600 7520636114 601 302 602 2419969143 603 447040801 604 1514433 605 1217051495 606 32662676 607 305 608 4672798997 609 3055889290 610 856617170 611 2333747387 612 7170303798 613 308 614 12244 615 3330704885 616 5856807931 617 310 618 36493780 619 311 620 4380384389 621 4079315753 622 12559 623 115900993 624 10712591887 625 1862148959 626 12718 627 6188546816 628 1761937 629 4753121161 630 16851548249 631 317 632 316308153 633 204686 634 13039 635 10432703 636 2754593589 637 3725375899 638 6115140688 639 710356427 640 9169853839 641 322 642 45286873 643 323 644 7939367367 645 5679250348 646 9422364938 647 325 648 13327951859 649 2319426278 650 9638462206 651 6843510288 652 2038643 653 328 654 50305858 655 12112121 656 7760987756 657 887744880 658 6284348826 659 331 660 25854627342 661 332 662 14194 663 14363427334 664 453218323 665 9496709052 666 10234058477 667 8418888575 668 2240427 669 241024 670 1931350040 671 3168399233 672 30407656689 673 338 674 14704 675 19941199213 676 8165247567 677 340 678 61743082 679 203089766 680 19318339593 681 254030 682 13654433833 683 343 684 25580541968 685 15030269 686 9901653373 687 260705 688 13515108307 689 8167483264 690 21350494946 691 347 692 2570763 693 20680764438 694 15574 695 16118983 696 18282908910 697 16356347126 698 15751 699 274404 700 40051434558 701 352 702 39632471156 703 18774348583 704 28758565704 705 15665938093 706 16108 707 264568295 708 7984352459 709 356 710 3208688710 711 1679232835 712 755474353 713 19751848294 714 47267555580 715 17871341254 716 2936385 717 295840 718 16651 719 361 720 99352914943 721 300867370 722 19035297879 723 303226 724 3066518 725 23002928226 726 30013519624 727 365 728 42119352107 729 14090014033 730 4097489592 731 29417906797 732 11161431512 733 368 734 17389 735 57706882809 736 44507070664 737 7683331046 738 36185696884 739 371 740 38781955774 741 54710718441 742 23593364458 743 373 744 41633254474 745 22549214 746 17953 747 2507993595 748 61942755186 749 386423116 750 56859779137 751 377 752 38932457953 753 342006 754 48800653822 755 24052023 756 138239396624 757 380 758 18526 759 55547654935 760 78765418761 761 382 762 120254206 763 436499083 764 3783288 765 95504205571 766 18913 767 25601330545 768 85498701057 769 386 770 106679375834 771 366790 772 3940528 773 388 774 66172284788 775 55591321291 776 1424596500 777 68029622667 778 19501 779 71428698501 780 198849652825 781 13359258428 782 99923460199 783 64441016031 784 117922529253 785 29047351 786 143631244 787 395 788 4269672 789 392744 790 8248727370 791 553524528 792 228677177548 793 36676644262 794 20299 795 63849768372 796 4441775 797 400 798 194503811764 799 89949945551 800 205317902597 801 4434943995 802 20704 803 17438245110 804 28935290719 805 102727460228 806 115457275580 807 419895 808 1921598653 809 406 810 264864592335 811 407 812 131940455367 813 429216 814 135998021002 815 34840241 816 297401188548 817 134961484210 818 21526 819 197553664719 820 150666193665 821 412 822 185720375 823 413 824 2222653951 825 253658344591 826 79158059723 827 415 828 265009115781 829 416 830 12816923803 831 458005 832 242211048935 833 154015977023 834 201849373 835 39190367 836 278261203280 837 156950288818 838 22576 839 421 840 769793632938 841 78378960782 842 22789 843 477896 844 5586253 845 73190950645 846 209911350850 847 30033160357 848 169460345769 849 488054 850 311353353534 851 224707841395 852 52494789174 853 428 854 115925593616 855 409758674625 856 2950840420 857 430 858 550715260494 859 431 860 288680569222 861 282876927294 862 23869 863 433 864 774199101482 865 46520117 866 24088 867 256879917945 868 319489457406 869 37384611252 870 365369313882 871 101936461679 872 3387561813 873 9001075526 874 482269653643 875 308041759774 876 69953501210 877 440 878 24751 879 541009 880 854494867877 881 442 882 817648204453 883 443 884 564599066907 885 230742945750 886 25198 887 445 888 450141752317 889 1199132926 890 23985645721 891 425263081725 892 6938988 893 454351279648 894 301099948 895 54907757 896 662355958257 897 625007832145 898 25876 899 396782952467 900 1672029186670 901 424116476975 902 574232312221 903 559087825456 904 4433605405 905 57957626 906 325163756 907 455 908 7440267 909 12571049155 910 884979370902 911 457 912 1352989204329 913 60442905050 914 26794 915 345898620022 916 7700860 917 1473502248 918 1453909713287 919 461 920 1048919799468 921 621390 922 27259 923 193165343539 924 2034019485558 925 700687246921 926 27493 927 14788936755 928 892255781392 929 466 930 893738183441 931 812751064919 932 8242533 933 645736 934 27964 935 766562324100 936 2275116511619 937 470 938 343443801280 939 658144 940 1003830003047 941 472 942 407180218 943 1020970647533 944 653157596597 945 2492737260181 946 1147818867676 947 475 948 159200238724 949 262874746925 950 1586055157071 951 683435 952 1598332129685 953 478 954 1050261139977 955 75306527 956 9108030 957 1084042923893 958 29401 959 1985277911 960 3771989795190 961 511738761026 962 1384691745408 963 20293289641 964 9411138 965 79228144 966 2609425381622 967 485 968 1179156750268 969 2531731330740 970 52262823268 971 487 972 2209050024796 973 2186657068 974 30379 975 2675943389946 976 999865341976 977 490 978 505760992 979 119708457359 980 3604688069078 981 23674878035 982 30874 983 493 984 2036736999119 985 87561440 986 2237759253343 987 2058205478824 988 2932324638034 989 2108339253256 990 6146337226238 991 497 992 2264299964190 993 777046 994 677891303920 995 91983119 996 267375733150 997 500 998 31876 999 2098293302471 1000 3461192237933