-1 1 0 0 1 1 2 1 3 1 4 0 5 3 6 2 7 2 8 2 9 2 10 2 11 5 12 3 13 6 14 5 15 7 16 5 17 10 18 7 19 11 20 11 21 13 22 12 23 19 24 15 25 21 26 22 27 26 28 23 29 35 30 30 31 39 32 38 33 47 34 45 35 60 36 54 37 68 38 69 39 81 40 78 41 104 42 95 43 117 44 118 45 137 46 134 47 171 48 162 49 192 50 197 51 225 52 223 53 274 54 265 55 313 56 318 57 363 58 363 59 434 60 424 61 494 62 508 63 570 64 575 65 675 66 670 67 765 68 789 69 884 70 895 71 1035 72 1034 73 1171 74 1208 75 1344 76 1371 77 1561 78 1576 79 1764 80 1824 81 2014 82 2065 83 2331 84 2359 85 2628 86 2721 87 2988 88 3066 89 3434 90 3500 91 3861 92 4005 93 4377 94 4509 95 5002 96 5117 97 5623 98 5833 99 6351 100 6551 101 7221 102 7408 103 8097 104 8413 105 9118 106 9430 107 10327 108 10623 109 11554 110 12018 111 12987 112 13437 113 14650 114 15102 115 16357 116 17012 117 18331 118 19003 119 20609 120 21286 121 22971 122 23908 123 25677 124 26639 125 28795 126 29773 127 32031 128 33340 129 35718 130 37080 131 39938 132 41352 133 44346 134 46181 135 49349 136 51262 137 55030 138 57038 139 61020 140 63534 141 67761 142 70417 143 75377 144 78170 145 83436 146 86903 147 92473 148 96138 149 102646 150 106525 151 113432 152 118147 153 125513 154 130505 155 139025 156 144334 157 153396 158 159759 159 169430 160 176214 161 187305 162 194546 163 206369 164 214919 165 227557 166 236703 167 251140 168 260885 169 276299 170 287718 171 304186 172 316401 173 335126 174 348226 175 368190 176 383369 177 404757 178 421029 179 445195 180 462649 181 488516 182 508556 183 536259 184 557772 185 588928 186 612041 187 645396 188 671786 189 707507 190 735868 191 775886 192 806348 193 849225 194 883802 195 929790 196 966908 197 1018232 198 1058176 199 1113157 200 1158210 201 1217222 202 1265703 203 1331258 204 1383412 205 1453722 206 1512263 207 1587709 208 1650691 209 1734343 210 1802085 211 1891785 212 1967501 213 2063770 214 2145253 215 2251657 216 2339368 217 2453445 218 2551098 219 2673557 220 2778612 221 2913605 222 3026708 223 3171528 224 3296906 225 3452372 226 3587322 227 3758214 228 3903445 229 4086816 230 4247425 231 4444161 232 4616953 233 4832800 234 5018739 235 5250285 236 5455270 237 5703818 238 5924265 239 6196319 240 6433508 241 6725328 242 6986123 243 7299292 244 7579788 245 7921844 246 8223570 247 8590455 248 8921335 249 9315000 250 9670804 251 10100107 252 10482585 253 10942983 254 11361589 255 11855400 256 12305325 257 12842973 258 13326664 259 13902972 260 14431182 261 15049286 262 15616837 263 16288668 264 16898524 265 17618730 266 18283383 267 19055518 268 19769438 269 20607446 270 21374308 271 22272373 272 23106805 273 24069257 274 24965205 275 26008363 276 26970267 277 28087883 278 29132880 279 30330406 280 31451787 281 32748055 282 33951636 283 35339901 284 36645369 285 38132471 286 39533066 287 41140593 288 42643096 289 44364340 290 45991750 291 47834800 292 49579965 293 51570300 294 53441525 295 55571829 296 57595983 297 59876236 298 62045940 299 64505682 300 66831270 301 69462972 302 71975519 303 74791515 304 77483421 305 80517974 306 83402052 307 86647846 308 89759880 309 93231707 310 96564639 311 100302130 312 103871257 313 107867581 314 111714992 315 115987715 316 120106242 317 124701916 318 129110349 319 134022354 320 138769497 321 144019705 322 149098960 323 154740884 324 160175298 325 166203367 326 172049634 327 178490213 328 184743000 329 191658161 330 198345190 331 205730982 332 212917958 333 220806202 334 228489615 335 236952703 336 245165660 337 254201376 338 263020923 339 272667434 340 282091861 341 292433606 342 302503666 343 313540585 344 324345163 345 336123994 346 347664600 347 360282953 348 372608604 349 386070761 350 399284733 351 413646118 352 427754243 353 443128514 354 458189838 355 474585939 356 490720899 357 508205315 358 525424733 359 544129926 360 562504593 361 582445594 362 602115946 363 623372953 364 644355942 365 667082575 366 689464204 367 713683025 368 737626019 369 763433597 370 788964427 371 816538627 372 843759490 373 873133749 374 902234254 375 933523482 376 964540800 377 997952891 378 1031009405 379 1066589241 380 1101905975 381 1139791255 382 1177418910 383 1217851257 384 1257936796 385 1300976273 386 1343776425 387 1389587995 388 1435169996 389 1484034554 390 1532574543 391 1584571716 392 1636367558 393 1691693588 394 1746834546 395 1805815724 396 1864511233 397 1927251222 398 1989849243 399 2056580888 400 2123195076 401 2194299281 402 2265179775 403 2340788044 404 2416339523 405 2496730519 406 2577097659 407 2662712991 408 2748194306 409 2839200786 410 2930267115 411 3026995853 412 3123830500 413 3226794921 414 3329752360 415 3439162396 416 3548790105 417 3665038870 418 3781566930 419 3905252435 420 4029100880 421 4160483757 422 4292291403 423 4431837535 424 4571889166 425 4720294964 426 4869091004 427 5026677603 428 5184959661 429 5352281167 430 5520401644 431 5698266826 432 5876818701 433 6065624893 434 6255470893 435 6455872174 436 6657446190 437 6870383774 438 7084388031 439 7310348232 440 7537787461 441 7777543671 442 8018947683 443 8273595498 444 8529794560 445 8799926775 446 9072090713 447 9358622370 448 9647394918 449 9951599107 450 10257964010 451 10580560093 452 10905876646 453 11247946018 454 11592997944 455 11956019123 456 12321965666 457 12706811934 458 13095234835 459 13503180089 460 13915026676 461 14347792542 462 14784430104 463 15243067569 464 15706336716 465 16192347750 466 16683390350 467 17198775882 468 17719204760 469 18265228753 470 18817182869 471 19395615084 472 19980466341 473 20593631985 474 21213280733 475 21862697907 476 22519628574 477 23207377817 478 23903238438 479 24632020707 480 25369044968 481 26140678659 482 26921757344 483 27738685492 484 28565786571 485 29431150316 486 30306900280 487 31222868797 488 32150626123 489 33120072025 490 34102184844 491 35128753004 492 36168307434 493 37254583586 494 38355480771 495 39504835115 496 40669873271 497 41886537505 498 43119336246 499 44406387093 500 45711476030 501 47072864349 502 48453570871 503 49894211092 504 51354776087 505 52878318347 506 54424004945 507 56035076284 508 57669829269 509 59374134995 510 61102926670 511 62904788572 512 64733723599 513 66638562194 514 68572313630 515 70586745358 516 72631132458 517 74760274374 518 76922379927 519 79172567217 520 81457918476 521 83836826460 522 86252228898 523 88765900371 524 91319572049 525 93975410057 526 96673873722 527 99480780025 528 102331987342 529 105297087346 530 108310569773 531 111442511431 532 114625953983 533 117935052932 534 121297746338 535 124792391703 536 128345380979 537 132035666674 538 135788003607 539 139685878297 540 143648398018 541 147763732902 542 151949235387 543 156293796874 544 160712921673 545 165300555981 546 169965935555 547 174808229720 548 179734693375 549 184845359474 550 190045397392 551 195440466859 552 200928800244 553 206621863287 554 212415659961 555 218422685898 556 224536589502 557 230876132882 558 237327285345 559 244015271851 560 250823539110 561 257878546833 562 265061086110 563 272504580604 564 280081330734 565 287931952053 566 295925905056 567 304205249701 568 312636469553 569 321369370955 570 330261040750 571 339469283448 572 348847992865 573 358556679208 574 368445873126 575 378683704860 576 389110321244 577 399902738768 578 410897515745 579 422273666305 580 433863976275 581 445857026619 582 458074141040 583 470713772344 584 483593209090 585 496913242748 586 510486925866 587 524525678968 588 538829884386 589 553621942620 590 568697705793 591 584282287102 592 600166794194 593 616588146191 594 633323467552 595 650621850487 596 668255356366 597 686476229127 598 705051203730 599 724245630048 600 743810819141 601 764025640221 602 784635712581 603 805923566064 604 827628859654 605 850048660462 606 872905619805 607 896511803646 608 920583500807 609 945436989040 610 970781902508 611 996950641884 612 1023634087748 613 1051181284852 614 1079275996900 615 1108272124905 616 1137845977830 617 1168369354595 618 1199497898372 619 1231621851132 620 1264388911951 621 1298194911391 622 1332679225957 623 1368257502648 624 1404546378442 625 1441981947549 626 1480171964638 627 1519558939457 628 1559741344112 629 1601183658472 630 1643459295904 631 1687055409517 632 1731535507836 633 1777394086209 634 1824184305390 635 1872424997744 636 1921641759552 637 1972378520241 638 2024149852055 639 2077508078181 640 2131956234321 641 2188073606160 642 2245332908723 643 2304341225163 644 2364558970099 645 2426602836209 646 2489920391479 647 2555158164585 648 2621730397991 649 2690314400809 650 2760310729703 651 2832407618598 652 2905991359821 653 2981783215536 654 3059132837509 655 3138795557964 656 3220105814801 657 3303831391452 658 3389290836687 659 3477288500276 660 3567102685910 661 3659575431996 662 3753968138909 663 3851136999665 664 3950325778461 665 4052431092802 666 4156652537748 667 4263928416816 668 4373439545600 669 4486140313445 670 4601191958103 671 4719593579969 672 4840457910329 673 4964830181146 674 5091802282156 675 5222437669675 676 5355806532220 677 5493021766503 678 5633100349306 679 5777206140126 680 5924333041506 681 6075665565971 682 6230173542575 683 6389096135050 684 6551344826122 685 6718215124693 686 6888592905676 687 7063797077110 688 7242686857956 689 7426641536561 690 7614456378804 691 7807572931674 692 8004758125750 693 8207479928523 694 8414475796895 695 8627280399885 696 8844561108337 697 9067921386351 698 9295997252375 699 9530422017881 700 9769799069119 701 10015835430881 702 10267057723850 703 10525248929149 704 10788901021835 705 11059830671790 706 11336493796611 707 11620788413321 708 11911086443122 709 12209369782030 710 12513972048099 711 12826913122048 712 13146486809947 713 13474802819661 714 13810062987226 715 14154469651983 716 14506182371062 717 14867446255147 718 15236376930186 719 15615318648507 720 16002286458088 721 16399726807103 722 16805608135971 723 17222425026013 724 17648097452736 725 18085229419476 726 18531630931156 727 18990018769227 728 19458151510961 729 19938800121874 730 20429669762096 731 20933652085131 732 21448332088521 733 21976725857283 734 22516361741628 735 23070316652779 736 23636060169180 737 24216802333474 738 24809881424810 739 25418644739730 740 26040368207520 741 26678467456739 742 27330153670248 743 27998989336405 744 28682042279740 745 29383026329684 746 30098940726777 747 30833575976504 748 31583860142636 749 32353745602004 750 33140003997394 751 33946754560644 752 34770693518201 753 35616026113895 754 36479370349444 755 37365109922196 756 38269692129268 757 39197684666860 758 40145451976982 759 41117658108489 760 42110581626216 761 43129083278578 762 44169255495130 763 45236161737088 764 46325803550426 765 47443352324615 766 48584715321668 767 49755280694649 768 50950752840280 769 52176743323320 770 53428856759200 771 54712825575567 772 56024151007945 773 57368804282839 774 58742065631059 775 60150152417234 776 61588235529440 777 63062667472940 778 64568505908358 779 66112366387707 780 67689065880479 781 69305491107201 782 70956339261641 783 72648648177333 784 74376990989341 785 76148695334189 786 77958072357518 787 79812748303872 788 81706903251655 789 83648332330147 790 85631079885900 791 87663260083406 792 89738632331060 793 91865639636632 794 94037898000452 795 96264039069346 796 98537530453905 797 100867355115905 798 103246670714211 799 105684822345973 800 108174810951990 801 110726192185414 802 113331804872829 803 116001591416438 804 118728053804280 805 121521533015913 806 124374359962283 807 127297110553444 808 130281938680682 809 133339845996286 810 136462620462484 811 139661702467292 812 142928693194080 813 146275295154389 814 149692916410275 815 153193727965084 816 156768740598388 817 160430608188253 818 164170137871335 819 168000275611926 820 171911618148651 821 175917626999119 822 180008467685607 823 184198133096904 824 188476566906460 825 192858087531792 826 197332409353563 827 201914418122577 828 206593360506098 829 211384706862347 830 216277462362524 831 221287459945748 832 226403455301871 833 231641905401352 834 236991058973980 835 242468016115994 836 248060762833135 837 253786802967558 838 259633851237235 839 265620097938839 840 271732708372230 841 277990580397936 842 284380593770862 843 290922095622400 844 297601671020174 845 304439422131185 846 311421339066446 847 318568302055336 848 325865991284663 849 333335786837060 850 340963048930242 851 348769988007321 852 356741320383494 853 364900112232002 854 373230743461804 855 381756836255554 856 390462423526861 857 399372040490650 858 408469023575039 859 417778848961836 860 427284488509311 861 437012036396074 862 446944088610153 863 457107743198510 864 467484843156071 865 478103521190806 866 488945225494559 867 500038775616678 868 511365212716056 869 522954460157572 870 534786745546058 871 546893129648383 872 559253413015307 873 571899419517174 874 584810509538598 875 598019720166558 876 611505533537954 877 625302237106014 878 639387851351029 879 653797511269368 880 668508761826567 881 683558071658645 882 698922037853329 883 714638503576651 884 730683567509265 885 747096013762598 886 763851427835445 887 780990059625342 888 798486472580412 889 816382427172013 890 834651949452010 891 853337844267269 892 872413584339360 893 891923585498935 894 911840219084816 895 932209561098528 896 953003403749865 897 974268982105962 898 995977492473978 899 1018177940134726 900 1040840335445569 901 1064015508129443 902 1087672845391013 903 1111864462461845 904 1136559105782688 905 1161810835793977 906 1187587122627238 907 1213944031522882 908 1240848362901078 909 1268357607734795 910 1296437877789308 911 1325148801519824 912 1354455118337028 913 1384418659419441 914 1415003445318412 915 1446272887918271 916 1478190268965818 917 1510821348548647 918 1544127934067958 919 1578178205697450 920 1612933200125268 921 1648462849711199 922 1684727399473185 923 1721799361585732 924 1759637398003482 925 1798316679915373 926 1837795044175960 927 1878149603496794 928 1919337347723506 929 1961438223669514 930 2004407523085152 931 2048328113553897 932 2093154405088029 933 2138971416287290 934 2185732652022510 935 2233526244148291 936 2282303877636068 937 2332156892916944 938 2383036033549248 939 2435035022685445 940 2488103638352493 941 2542339023288255 942 2597689006827498 943 2654254256111052 944 2711981597459823 945 2770974336302502 946 2831178270904101 947 2892700462641190 948 2955484625007553 949 3019641690645132 950 3085114306117447 951 3152016325045882 952 3220289300796122 953 3290051212544654 954 3361241385591748 955 3433982050860866 956 3508211400991766 957 3584054900181971 958 3661449581162178 959 3740525438738999 960 3821217127275364 961 3903659311265853 962 3987785444706204 963 4073733770284138 964 4161436513819798 965 4251036893804957 966 4342464599278018 967 4435867977443478 968 4531175448216495 969 4628539317746199 970 4727886708329407 971 4829375390466998 972 4932929784398926 973 5038713292662630 974 5146648997025309 975 5256904679487969 976 5369402053914369 977 5484314903135755 978 5601562066234977 979 5721323511023080 980 5843516667911073 981 5968326348883509 982 6095668546186249 983 6225734661177254 984 6358437631672638 985 6493975651028166 986 6632260179029345 987 6773494765347739 988 6917589362467923 989 7064754755815523 990 7214897656601641 991 7368236308599653 992 7524675876929792 993 7684440527635579 994 7847433850101465 995 8013887955956618 996 8183703000367784 997 8357119284610322 998 8534035351970444 999 8714698050392361 1000 8899004282260122