0 1 1 0 2 1 3 0 4 2 5 0 6 3 7 0 8 5 9 0 10 7 11 1 12 11 13 1 14 15 15 2 16 22 17 3 18 30 19 5 20 42 21 7 22 56 23 11 24 76 25 15 26 99 27 22 28 131 29 30 30 169 31 42 32 219 33 56 34 278 35 76 36 355 37 99 38 445 39 131 40 560 41 169 42 695 43 219 44 863 45 278 46 1060 47 355 48 1303 49 445 50 1586 51 560 52 1930 53 695 54 2331 55 863 56 2812 57 1060 58 3370 59 1303 60 4035 61 1586 62 4802 63 1930 64 5708 65 2331 66 6751 67 2812 68 7972 69 3370 70 9373 71 4035 72 11004 73 4802 74 12866 75 5708 76 15021 77 6751 78 17475 79 7972 80 20298 81 9373 82 23501 83 11004 84 27169 85 12866 86 31316 87 15021 88 36043 89 17475 90 41373 91 20298 92 47420 93 23501 94 54218 95 27169 96 61903 97 31316 98 70515 99 36043 100 80215 101 41373 102 91058 103 47420 104 103226 105 54218 106 116792 107 61903 108 131970 109 70515 110 148847 111 80215 112 167672 113 91058 114 188556 115 103226 116 211782 117 116792 118 237489 119 131970 120 266006 121 148847 122 297495 123 167672 124 332337 125 188556 126 370733 127 211782 128 413112 129 237489 130 459718 131 266006 132 511045 133 297495 134 567377 135 332337 136 629281 137 370733 138 697097 139 413112 140 771464 141 459718 142 852785 143 511045 144 941790 145 567377 146 1038944 147 629281 148 1145078 149 697097 150 1260740 151 771464 152 1386861 153 852785 154 1524081 155 941790 156 1673457 157 1038944 158 1835721 159 1145078 160 2012069 161 1260740 162 2203348 163 1386861 164 2410895 165 1524081 166 2635689 167 1673457 168 2879236 169 1835721 170 3142647 171 2012069 172 3427615 173 2203348 174 3735414 175 2410895 176 4067930 177 2635689 178 4426616 179 2879236 180 4813587 181 3142647 182 5230481 183 3427615 184 5679662 185 3735414 186 6162991 187 4067930 188 6683091 189 4426616 190 7242069 191 4813587 192 7842848 193 5230481 194 8487789 195 5679662 196 9180146 197 6162991 198 9922579 199 6683091 200 10718685 201 7242069 202 11571451 203 7842848 204 12484869 205 8487789 206 13462270 207 9180146 208 14508075 209 9922579 210 15626011 211 10718685 212 16820948 213 11571451 214 18097047 215 12484869 216 19459689 217 13462270 218 20913488 219 14508075 220 22464381 221 15626011 222 24117499 223 16820948 224 25879361 225 18097047 226 27755663 227 19459689 228 29753578 229 20913488 230 31879397 231 22464381 232 34141000 233 24117499 234 36545347 235 25879361 236 39101065 237 27755663 238 41815841 239 29753578 240 44699133 241 31879397 242 47759392 243 34141000 244 51006974 245 36545347 246 54451188 247 39101065 248 58103334 249 41815841 250 61973647 251 44699133 252 66074473 253 47759392 254 70417024 255 51006974 256 75014774 257 54451188 258 79880017 259 58103334 260 85027416 261 61973647 262 90470433 263 66074473 264 96225037 265 70417024 266 102305924 267 75014774 268 108730467 269 79880017 270 115514722 271 85027416 272 122677540 273 90470433 274 130236438 275 96225037 276 138211888 277 102305924 278 146622950 279 108730467 280 155491832 281 115514722 282 164839281 283 122677540 284 174689336 285 130236438 286 185064559 287 138211888 288 195990980 289 146622950 290 207493074 291 155491832 292 219599002 293 164839281 294 232335324 295 174689336 296 245732448 297 185064559 298 259819164 299 195990980 300 274628317 301 207493074 302 290191050 303 219599002 304 306542807 305 232335324 306 323717285 307 245732448 308 341752667 309 259819164 310 360685378 311 274628317 312 380556557 313 290191050 314 401405504 315 306542807 316 423276511 317 323717285 318 446211984 319 341752667 320 470259534 321 360685378 322 495464875 323 380556557 324 521879190 325 401405504 326 549551684 327 423276511 328 578537336 329 446211984 330 608889106 331 470259534 332 640665969 333 495464875 334 673924880 335 521879190 336 708729103 337 549551684 338 745139797 339 578537336 340 783224779 341 608889106 342 823049720 343 640665969 344 864687223 345 673924880 346 908207751 347 708729103 348 953689028 349 745139797 350 1001206560 351 783224779 352 1050843495 353 823049720 354 1102680731 355 864687223 356 1156807122 357 908207751 358 1213309282 359 953689028 360 1272282150 361 1001206560 362 1333818347 363 1050843495 364 1398019251 365 1102680731 366 1464983897 367 1156807122 368 1534820423 369 1213309282 370 1607634648 371 1272282150 372 1683541906 373 1333818347 374 1762655144 375 1398019251 376 1845097299 377 1464983897 378 1930988902 379 1534820423 380 2020460870 381 1607634648 382 2113641746 383 1683541906 384 2210670920 385 1762655144 386 2311685347 387 1845097299 388 2416833355 389 1930988902 390 2526260833 391 2020460870 392 2640125479 393 2113641746 394 2758582603 395 2210670920 396 2881799840 397 2311685347 398 3009942381 399 2416833355 400 3143188326 401 2526260833 402 3281713335 403 2640125479 404 3425706473 405 2758582603 406 3575354434 407 2881799840 408 3730857880 409 3009942381 410 3892415064 411 3143188326 412 4060238850 413 3281713335 414 4234539718 415 3425706473 416 4415543308 417 3575354434 418 4603472960 419 3730857880 420 4798567807 421 3892415064 422 5001064654 423 4060238850 424 5211216809 425 4234539718 426 5429275296 427 4415543308 428 5655508252 429 4603472960 430 5890181641 431 4798567807 432 6133579232 433 5001064654 434 6385982615 435 5211216809 436 6647691970 437 5429275296 438 6919005360 439 5655508252 440 7200240116 441 5890181641 442 7491711584 443 6133579232 444 7793755151 445 6385982615 446 8106704235 447 6647691970 448 8430913148 449 6919005360 450 8766734325 451 7200240116 452 9114541845 453 7491711584 454 9474708078 455 7793755151 456 9847627884 457 8106704235 458 10233694450 459 8430913148 460 10633324399 461 8766734325 462 11046932797 463 9114541845 464 11474958976 465 9474708078 466 11917840913 467 9847627884 468 12376041781 469 10233694450 470 12850023467 471 10633324399 472 13340274081 473 11046932797 474 13847280602 475 11474958976 476 14371557152 477 11917840913 478 14913616956 479 12376041781 480 15474001405 481 12850023467 482 16053251090 483 13340274081 484 16651935901 485 13847280602 486 17270625121 487 14371557152 488 17909918335 489 14913616956 490 18570414804 491 15474001405 492 19252745210 493 16053251090 494 19957540052 495 16651935901 496 20685462483 497 17270625121 498 21437175703 499 17909918335 500 22213376679 501 18570414804 502 23014762750 503 19252745210 504 23842066249 505 19957540052 506 24696020064 507 20685462483 508 25577393421 509 21437175703 510 26486956385 511 22213376679 512 27425516570 513 23014762750 514 28393882812 515 23842066249 516 29392902842 517 24696020064 518 30423425839 519 25577393421 520 31486341342 521 26486956385 522 32582540670 523 27425516570 524 33712956839 525 28393882812 526 34878525088 527 29392902842 528 36080223811 529 30423425839 530 37319033910 531 31486341342 532 38595981036 533 32582540670 534 39912093745 535 33712956839 536 41268446799 537 34878525088 538 42666118368 539 36080223811 540 44106234428 541 37319033910 542 45589924702 543 38595981036 544 47118368453 545 39912093745 546 48692749154 547 41268446799 548 50314301408 549 42666118368 550 51984264609 551 44106234428 552 53703931011 553 45589924702 554 55474598072 555 47118368453 556 57297617996 557 48692749154 558 59174348721 559 50314301408 560 61106204667 561 51984264609 562 63094606641 563 53703931011 564 65141033825 565 55474598072 566 67246972275 567 57297617996 568 69413968455 569 59174348721 570 71643576320 571 61106204667 572 73937412122 573 63094606641 574 76297100350 575 65141033825 576 78724329840 577 67246972275 578 81220798227 579 69413968455 580 83788269707 581 71643576320 582 86428517974 583 73937412122 584 89143385338 585 76297100350 586 91934724449 587 78724329840 588 94804458794 589 81220798227 590 97754522858 591 83788269707 592 100786924347 593 86428517974 594 103903682767 595 89143385338 596 107106893081 597 91934724449 598 110398662992 599 94804458794 600 113781178067 601 97754522858 602 117256637363 603 100786924347 604 120827320389 605 103903682767 606 124495521052 607 107106893081 608 128263616125 609 110398662992 610 132133997837 611 113781178067 612 136109143886 613 117256637363 614 140191548291 615 120827320389 616 144383793328 617 124495521052 618 148688478610 619 128263616125 620 153108294635 621 132133997837 622 157645950412 623 136109143886 624 162304248649 625 140191548291 626 167086011548 627 144383793328 628 171994158015 629 148688478610 630 177031627599 631 153108294635 632 182201459382 633 157645950412 634 187506714404 635 162304248649 636 192950556281 637 167086011548 638 198536171691 639 171994158015 640 204266853127 641 177031627599 642 210145917422 643 182201459382 644 216176790295 645 187506714404 646 222362923263 647 192950556281 648 228707879998 649 198536171691 650 235215251220 651 204266853127 652 241888743289 653 210145917422 654 248732091045 655 216176790295 656 255749148277 657 222362923263 658 262943798861 659 228707879998 660 270320049156 661 235215251220 662 277881937002 663 241888743289 664 285633626471 665 248732091045 666 293579314708 667 255749148277 668 301723328655 669 262943798861 670 310070030110 671 270320049156 672 318623914458 673 277881937002 674 327389513504 675 285633626471 676 336371496673 677 293579314708 678 345574571567 679 301723328655 680 355003587250 681 310070030110 682 364663432919 683 318623914458 684 374559143321 685 327389513504 686 384695795077 687 336371496673 688 395078614673 689 345574571567 690 405712872418 691 355003587250 692 416603992619 693 364663432919 694 427757445564 695 374559143321 696 439178859923 697 384695795077 698 450873912271 699 395078614673 700 462848442206 701 405712872418 702 475108339372 703 416603992619 704 487659660880 705 427757445564 706 500508516254 707 439178859923 708 513661187188 709 450873912271 710 527124009925 711 462848442206 712 540903497836 713 475108339372 714 555006221205 715 487659660880 716 569438932221 717 500508516254 718 584208442570 719 513661187188 720 599321750887 721 527124009925 722 614785917651 723 540903497836 724 630608195613 725 555006221205 726 646795901962 727 569438932221 728 663356551269 729 584208442570 730 680297725375 731 599321750887 732 697627208904 733 614785917651 734 715352856341 735 630608195613 736 733482730641 737 646795901962 738 752024967452 739 663356551269 740 770987916384 741 680297725375 742 790380002821 743 697627208904 744 810209871890 745 715352856341 746 830486247337 747 733482730641 748 851218078727 749 752024967452 750 872414397347 751 770987916384 752 894084466170 753 790380002821 754 916237633254 755 810209871890 756 938883484531 757 830486247337 758 962031694125 759 851218078727 760 985692180525 761 872414397347 762 1009874953789 763 894084466170 764 1034590274631 765 916237633254 766 1059848498990 767 938883484531 768 1085660240058 769 962031694125 770 1112036209656 771 985692180525 772 1138987383782 773 1009874953789 774 1166524840750 775 1034590274631 776 1194659929768 777 1059848498990 778 1223404106320 779 1085660240058 780 1252769103842 781 1112036209656 782 1282766765750 783 1138987383782 784 1313409220798 785 1166524840750 786 1344708711726 787 1194659929768 788 1376677773785 789 1223404106320 790 1409329060513 791 1252769103842 792 1442675525472 793 1282766765750 794 1476730244552 795 1313409220798 796 1511506601544 797 1344708711726 798 1547018106906 799 1376677773785 800 1583278586653 801 1409329060513 802 1620301998113 803 1442675525472 804 1658102622195 805 1476730244552 806 1696694875513 807 1511506601544 808 1736093506632 809 1547018106906 810 1776313404533 811 1583278586653 812 1817369798310 813 1620301998113 814 1859278062503 815 1658102622195 816 1902053920304 817 1696694875513 818 1945713245107 819 1736093506632 820 1990272267880 821 1776313404533 822 2035747374880 823 1817369798310 824 2082155318637 825 1859278062503 826 2129513012399 827 1902053920304 828 2177837744773 829 1945713245107 830 2227146970244 831 1990272267880 832 2277458528127 833 2035747374880 834 2328790429120 835 2082155318637 836 2381161078019 837 2129513012399 838 2434589056846 839 2177837744773 840 2489093351387 841 2227146970244 842 2544693130225 843 2277458528127 844 2601407975786 845 2328790429120 846 2659257659233 847 2381161078019 848 2718262375415 849 2434589056846 850 2778442514218 851 2489093351387 852 2839818899485 853 2544693130225 854 2902412556122 855 2601407975786 856 2966244953686 857 2659257659233 858 3031337769188 859 2718262375415 860 3097713134771 861 2778442514218 862 3165393396797 863 2839818899485 864 3234401367671 865 2902412556122 866 3304760080514 867 2966244953686 868 3376493045837 869 3031337769188 870 3449624001753 871 3097713134771 872 3524177174883 873 3165393396797 874 3600177026726 875 3234401367671 876 3677648518876 877 3304760080514 878 3756616854793 879 3376493045837 880 3837107750067 881 3449624001753 882 3919147169545 883 3524177174883 884 4002761602024 885 3600177026726 886 4087977793365 887 3677648518876 888 4174823025651 889 3756616854793 890 4263324845555 891 3837107750067 892 4353511348724 893 3919147169545 894 4445410903340 895 4002761602024 896 4539052439091 897 4087977793365 898 4634465166556 899 4174823025651 900 4731678870847 901 4263324845555 902 4830723626041 903 4353511348724 904 4931630094256 905 4445410903340 906 5034429235095 907 4539052439091 908 5139152609486 909 4634465166556 910 5245832084798 911 4731678870847 912 5354500143507 913 4830723626041 914 5465189583203 915 4931630094256 916 5577933830889 917 5034429235095 918 5692766637798 919 5139152609486 920 5809722398652 921 5245832084798 922 5928835841973 923 5354500143507 924 6050142354380 925 5465189583203 926 6173677665586 927 5577933830889 928 6299478178518 929 5692766637798 930 6427580648961 931 5809722398652 932 6558022520816 933 5928835841973 934 6690841601078 935 6050142354380 936 6826076400305 937 6173677665586 938 6963765802089 939 6299478178518 940 7103949409585 941 6427580648961 942 7246667209409 943 6558022520816 944 7391959923512 945 6690841601078 946 7539868668232 947 6826076400305 948 7690435311573 949 6963765802089 950 7843702126567 951 7103949409585 952 7999712154800 953 7246667209409 954 8158508854031 955 7391959923512 956 8320136467260 957 7539868668232 958 8484639665303 959 7690435311573 960 8652063921478 961 7843702126567 962 8822455148275 963 7999712154800 964 8995860078540 965 8158508854031 966 9172325896182 967 8320136467260 968 9351900623083 969 8484639665303 970 9534632744605 971 8652063921478 972 9720571602312 973 8822455148275 974 9909767013378 975 8995860078540 976 10102269670015 977 9172325896182 978 10298130752709 979 9351900623083 980 10497402335612 981 9534632744605 982 10700136994359 983 9720571602312 984 10906388217495 985 9909767013378 986 11116210007982 987 10102269670015 988 11329657301560 989 10298130752709 990 11546785561883 991 10497402335612 992 11767651205029 993 10700136994359 994 11992311189053 995 10906388217495 996 12220823444744 997 11116210007982 998 12453246458635 999 11329657301560 1000 12689639710944