0 1 1 1 2 2 3 1 4 3 5 1 6 5 7 1 8 5 9 4 10 6 11 1 12 14 13 1 14 8 15 11 16 13 17 1 18 25 19 1 20 22 21 22 22 12 23 1 24 61 25 6 26 14 27 37 28 50 29 1 30 77 31 1 32 73 33 56 34 18 35 36 36 175 37 1 38 20 39 79 40 211 41 1 42 135 43 1 44 188 45 232 46 24 47 1 48 421 49 8 50 236 51 137 52 313 53 1 54 307 55 331 56 422 57 172 58 30 59 1 60 1423 61 1 62 32 63 295 64 601 65 716 66 727 67 1 68 715 69 254 70 1247 71 1 72 1958 73 1 74 38 75 1666 76 1008 77 463 78 1652 79 1 80 3121 81 361 82 42 83 1 84 4677 85 2381 86 44 87 407 88 1915 89 1 90 6590 91 1717 92 1818 93 466 94 48 95 3877 96 7729 97 1 98 3053 99 694 100 7206 101 1 102 6801 103 1 104 4369 105 11586 106 54 107 1 108 12673 109 1 110 7427 111 667 112 14773 113 1 114 12389 115 8856 116 3713 117 2029 118 60 119 12377 120 37686 121 12 122 62 123 821 124 4558 125 12651 126 42841 127 1 128 16465 129 904 130 15731 131 1 132 32870 133 27133 134 68 135 24976 136 25501 137 1 138 34754 139 1 140 67853 141 1082 142 72 143 287 144 95551 145 23752 146 74 147 55441 148 7845 149 1 150 86841 151 1 152 58901 153 25586 154 75692 155 31466 156 76403 157 1 158 80 159 1379 160 134881 161 100948 162 126001 163 1 164 10743 165 45409 166 84 167 1 168 362625 169 14 170 70772 171 77179 172 12428 173 1 174 120496 175 229461 176 191885 177 1712 178 90 179 1 180 393417 181 1 182 230414 183 1831 184 260430 185 66046 186 171896 187 19449 188 16310 189 501454 190 166289 191 1 192 571257 193 1 194 98 195 84787 196 395277 197 1 198 603109 199 1 200 759751 201 2212 202 102 203 475021 204 313838 205 101271 206 104 207 492661 208 681825 209 92379 210 1326894 211 1 212 23533 213 2486 214 108 215 123411 216 2059786 217 736282 218 110 219 2629 220 844273 221 6189 222 438710 223 1 224 2118625 225 1233361 226 114 227 1 228 609749 229 1 230 980491 231 1463211 232 1591753 233 1 234 2159717 235 178366 236 32628 237 3082 238 1347404 239 1 240 4401474 241 1 242 646768 243 2223316 244 36113 245 1835037 246 752843 247 50389 248 2667520 249 3404 250 2273401 251 1 252 6311173 253 1144067 254 128 255 254151 256 3407665 257 1 258 966383 259 2324785 260 3565056 261 4295887 262 132 263 1 264 8074465 265 292826 266 2787947 267 3917 268 48040 269 1 270 12084961 271 1 272 5430006 273 3560649 274 138 275 3609816 276 2779551 277 1 278 140 279 7893004 280 17969491 281 1 282 1538452 283 1 284 57298 285 411104 286 5958525 287 4496389 288 23139589 289 18 290 10439421 291 4657 292 62343 293 1 294 7361061 295 455127 296 10360445 297 22325293 298 150 299 1352079 300 21482331 301 6096455 302 152 303 5051 304 12694585 305 521856 306 20510723 307 1 308 20752887 309 5254 310 20718076 311 1 312 28491802 313 1 314 158 315 32398286 316 79238 317 1 318 2875410 319 20030011 320 47425561 321 5672 322 10511047 323 970 324 46552024 325 5877341 326 164 327 5887 328 22570665 329 10737574 330 73137527 331 1 332 92048 333 38614126 334 168 335 766481 336 67195913 337 1 338 9657870 339 6329 340 53369427 341 44352166 342 53097383 343 13983817 344 32326627 345 1688247 346 174 347 1 348 39292246 349 1 350 92615531 351 78914395 352 103113265 353 1 354 5013467 355 971636 356 113743 357 18036831 358 180 359 1 360 279632384 361 20 362 182 363 92568301 364 61302543 365 1088431 366 5956712 367 1 368 54140759 369 95555749 370 125554432 371 22957481 372 91280896 373 1 374 131202941 375 5680601 376 63025732 377 51895936 378 170958547 379 1 380 164433412 381 8002 382 192 383 1 384 211736769 385 213922347 386 194 387 145016770 388 147635 389 1 390 317760951 391 245158 392 155963473 393 8516 394 198 395 1502502 396 634085159 397 1 398 200 399 36298361 400 378335541 401 1 402 9666761 403 141120526 404 166853 405 237284281 406 108339477 407 348330137 408 413213544 409 1 410 352092831 411 9317 412 177058 413 45057475 414 272281936 415 1837621 416 367485873 417 9592 418 472741281 419 1 420 1087288147 421 1 422 212 423 314467366 424 154336213 425 4067761 426 13030134 427 55525373 428 198700 429 990572870 430 566045766 431 1 432 1187191027 433 1 434 267727812 435 79795096 436 210153 437 33650 438 15031139 439 1 440 1762068232 441 518934340 442 553665997 443 1 444 871333832 445 2441627 446 224 447 11027 448 691935673 449 1 450 1589372016 451 1121099409 452 234363 453 11326 454 228 455 919723351 456 1486569729 457 1 458 230 459 649812574 460 1104766476 461 1 462 2155238241 463 1 464 378486541 465 268114196 466 234 467 1 468 3704779989 469 99795697 470 1365698882 471 12247 472 341416599 473 1917334784 474 22550156 475 3664246 476 1068132917 477 886335272 478 240 479 1 480 5029366401 481 1852482997 482 242 483 119892124 484 2481545023 485 3464841 486 1074536956 487 1 488 436566265 489 13204 490 3665521945 491 1 492 3187063538 493 67863916 494 2709037671 495 5230340743 496 792646720 497 143219000 498 29048341 499 1 500 2509850026 501 13862 502 252 503 1 504 8774051233 505 4082926 506 4076350929 507 3910811633 508 333630 509 1 510 4616776378 511 170230453 512 1187280545 513 1657112836 514 258 515 4421276 516 5787195120 517 5178066752 518 3747718346 519 14879 520 9967733387 521 1 522 2005658416 523 1 524 366408 525 2526167536 526 264 527 300540196 528 16065570889 529 24 530 4436581506 531 2217486976 532 5647075919 533 7898654921 534 41523663 535 5160611 536 870040561 537 15932 538 270 539 8454916317 540 21995155879 541 1 542 272 543 16291 544 3426902127 545 5563252 546 19484145360 547 1 548 419495 549 2944844419 550 16636466331 551 34597291 552 14469303498 553 277962686 554 278 555 6113092826 556 438268 557 1 558 3698269838 559 15338678265 560 24369974941 561 13944532372 562 282 563 1 564 17472499806 565 6438741 566 284 567 4198340710 568 1330358170 569 1 570 18817141436 571 1 572 36911250091 573 18146 574 17970238460 575 6915641 576 34689730777 577 1 578 2203961720 579 18529 580 10676562136 581 377447149 582 64465037 583 19499099621 584 1629856985 585 48899340322 586 294 587 1 588 55132686127 589 206253076 590 12573345392 591 19307 592 11164308517 593 1 594 30912927355 595 4505223262 596 540573 597 19702 598 38910632905 599 1 600 77467342342 601 1 602 37047003547 603 6522381661 604 562778 605 29257144841 606 79229350 607 1 608 18129485665 609 515016888 610 17350547201 611 52251400852 612 64743403027 613 1 614 308 615 35249252261 616 90471098741 617 1 618 87562670 619 1 620 20437702042 621 8361555724 622 312 623 581106989 624 157947613669 625 9691401 626 314 627 44220199937 628 633025 629 12875774671 630 164271298187 631 1 632 2899398988 633 22156 634 318 635 10334626 636 76325773980 637 92930298735 638 52183774820 639 10639148219 640 71301357809 641 1 642 106331679 643 1 644 102480358849 645 78389992742 646 24443936184 647 1 648 119878788016 649 62828356306 650 153377760512 651 846941236 652 708888 653 1 654 116852252 655 11716641 656 67234753805 657 13442149921 658 141491065542 659 1 660 347985883592 661 1 662 332 663 196464675201 664 4152667621 665 5419132881 666 31105032943 667 1560781 668 762690 669 24754 670 42770544647 671 90177170227 672 446320152633 673 1 674 338 675 183755649646 676 206380197479 677 1 678 140390297 679 988172369 680 118938420221 681 25652 682 107563286238 683 1 684 241369077313 685 14043871 686 263649402500 687 26107 688 156906691261 689 266783135711 690 296723437737 691 1 692 848393 693 150541320238 694 348 695 14891627 696 233697397174 697 103077446707 698 350 699 27029 700 425162256926 701 1 702 417642465593 703 17672631901 704 387863087241 705 341659579486 706 354 707 1267339921 708 280047669118 709 1 710 74490114341 711 26088811402 712 6891193105 713 20160076 714 645691081441 715 617760242464 716 940288 717 28442 718 360 719 1 720 1389000744955 721 1429840336 722 33578000972 723 28921 724 972333 725 17784976 726 211534188647 727 1 728 1203009230571 729 32164282981 730 97100185691 731 265182149219 732 418302475614 733 1 734 368 735 680124861627 736 520564848625 737 247994680649 738 187442052499 739 1 740 128217008610 741 769644696952 742 843098871588 743 1 744 517979070526 745 19720002 746 374 747 39443257843 748 708396246702 749 1807245623 750 1063696695301 751 1 752 761853262690 753 31376 754 891794813469 755 20811576 756 2031690220499 757 1 758 380 759 340226017927 760 302264785806 761 1 762 254264288 763 2025023365 764 1143518 765 1987479089476 766 384 767 1119487075981 768 1849068863153 769 1 770 2013694419188 771 32897 772 1180003 773 1 774 474507275389 775 25759606 776 12847439317 777 18169645279 778 390 779 202112640601 780 4314993458998 781 461738052777 782 992042202986 783 58433597155 784 3481721492201 785 24359336 786 297637241 787 1 788 1255285 789 34454 790 205836506206 791 2526561577 792 2381783565476 793 1742058970276 794 398 795 2404005576182 796 1294098 797 1 798 2838559525194 799 1503232609099 800 2630057967981 801 70625288375 802 402 803 621324937377 804 1285398574183 805 4317031461 806 2160153859826 807 36047 808 17200967005 809 1 810 4687219241668 811 1 812 3158550142323 813 36586 814 731282733919 815 28342441 816 6995696586352 817 608359048207 818 410 819 2825462239783 820 537745224422 821 1 822 373604755 823 1 824 19814938018 825 5182548456746 826 4050671496783 827 1 828 3670771727389 829 1 830 328724066361 831 38227 832 7786844296025 833 3351579101179 834 402112823 835 31256556 836 2012840069077 837 101841649966 838 420 839 1 840 14115895345855 841 30 842 422 843 39341 844 1543888 845 4027843280007 846 2852936274319 847 1100836727915 848 6274719384765 849 39904 850 5335586340121 851 9364199761 852 2560997084513 853 1 854 6570264389081 855 9532114553066 856 26077583539 857 1 858 6244032821599 859 1 860 1260365716231 861 273378382344 862 432 863 1 864 16084313212933 865 36041956 866 434 867 7174519312312 868 8312748429806 869 1440680596356 870 10656392656752 871 5996962277489 872 29798475809 873 144520251016 874 2841193073698 875 5145604326 876 3559014991826 877 1 878 440 879 42779 880 15689519062207 881 1 882 17644322038946 883 1 884 17645274351108 885 13298561865646 886 444 887 1 888 4220447572608 889 5169379426 890 635667708913 891 2049597586081 892 1823918 893 4568648125691 894 571924730 895 41356877 896 29431761862625 897 8866104810850 898 450 899 4496 900 35424097398791 901 14844575908436 902 2408409179342 903 966255140971 904 38622197229 905 43252666 906 611906210 907 1 908 1924280 909 202095500854 910 27849926840352 911 1 912 35152231649105 913 2432332329571 914 458 915 22512807336656 916 1975813 917 6249655777 918 36085960063639 919 1 920 5180243886427 921 46972 922 462 923 12802736917881 924 32198120647316 925 3609706311 926 464 927 237762069007 928 29799255764865 929 1 930 30041567037183 931 11561115063345 932 2081623 933 48206 934 468 935 32878463319582 936 45433759287580 937 1 938 25378941461959 939 48829 940 8036929587139 941 1 942 745445264 943 244662670201 944 39948291373937 945 40843589279278 946 4592944085580 947 1 948 9037768463946 949 18385569737809 950 19238243379751 951 50087 952 73081561198507 953 1 954 32611157246472 955 53727346 956 2247318 957 4000751333284 958 480 959 8218472725 960 124514954917289 961 32 962 21945919589894 963 325949708186 964 2304443 965 56031761 966 44782214766621 967 1 968 6589426893721 969 85803109665834 970 1429201499082 971 1 972 59630683816243 973 8979650479 974 488 975 87141647486271 976 70606973872317 977 1 978 901343057 979 5085018206137 980 67900651732110 981 379908900841 982 492 983 1 984 14276632113515 985 60862166 986 79960184146743 987 9772278422971 988 73699513470781 989 1052049481861 990 157297973407026 991 1 992 93128027590434 993 54616 994 58114960074389 995 63391252 996 16142832876877 997 1 998 500 999 442382463046 1000 32450835185201