1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 1 9 0 10 0 11 1 12 0 13 1 14 3 15 0 16 1 17 3 18 1 19 3 20 6 21 1 22 3 23 8 24 3 25 7 26 12 27 3 28 9 29 16 30 7 31 15 32 22 33 9 34 19 35 30 36 16 37 29 38 40 39 20 40 38 41 54 42 32 43 54 44 69 45 41 46 70 47 93 48 61 49 95 50 118 51 78 52 124 53 156 54 110 55 163 56 195 57 141 58 211 59 255 60 192 61 271 62 317 63 245 64 349 65 409 66 323 67 441 68 506 69 412 70 562 71 644 72 532 73 703 74 795 75 673 76 888 77 1000 78 856 79 1101 80 1229 81 1075 82 1378 83 1532 84 1350 85 1697 86 1876 87 1684 88 2108 89 2318 90 2093 91 2580 92 2826 93 2594 94 3180 95 3468 96 3198 97 3871 98 4213 99 3936 100 4741 101 5135 102 4816 103 5744 104 6213 105 5895 106 6990 107 7529 108 7169 109 8432 110 9078 111 8722 112 10204 113 10945 114 10549 115 12261 116 13144 117 12766 118 14763 119 15775 120 15366 121 17669 122 18878 123 18505 124 21177 125 22561 126 22171 127 25256 128 26904 129 26579 130 30142 131 32028 132 31718 133 35826 134 38067 135 37861 136 42588 137 45156 138 45009 139 50458 140 53498 141 53516 142 59765 143 63250 144 63399 145 70593 146 74706 147 75101 148 83333 149 88052 150 88681 151 98145 152 103692 153 104688 154 115496 155 121864 156 123239 157 135646 158 143109 159 145018 160 159160 161 167728 162 170218 163 186435 164 196441 165 199696 166 218151 167 229640 168 233763 169 254888 170 268267 171 273463 172 297476 173 312838 174 319281 175 346734 176 364564 177 372512 178 403680 179 424142 180 433857 181 469432 182 493122 183 504912 184 545260 185 572436 186 586680 187 632671 188 664049 189 681133 190 733252 191 769214 192 789672 193 848992 194 890420 195 914737 196 981892 197 1029336 198 1058230 199 1134569 200 1189101 201 1223189 202 1309544 203 1371931 204 1412186 205 1510215 206 1581769 207 1628973 208 1739777 209 1821557 210 1876987 211 2002613 212 2096225 213 2160901 214 2302788 215 2409653 216 2485231 217 2645901 218 2768005 219 2855803 220 3037133 221 3176360 222 3278519 223 3483615 224 3642415 225 3760642 226 3991939 227 4172786 228 4309827 229 4571139 230 4777073 231 4935139 232 5229607 233 5463848 234 5646425 235 5978755 236 6245065 237 6455022 238 6829248 239 7131781 240 7373546 241 7795428 242 8138869 243 8416137 244 8890853 245 9280531 246 9598871 247 10133506 248 10575245 249 10939442 250 11540585 251 12041155 252 12458202 253 13134557 254 13701233 255 14177276 256 14937191 257 15578557 258 16122353 259 16976534 260 17701649 261 18321058 262 19280067 263 20099748 264 20805722 265 21882697 266 22808239 267 23610824 268 24819052 269 25864053 270 26776871 271 28132511 272 29311047 273 30346883 274 31866611 275 33195686 276 34371488 277 36075138 278 37572291 279 38904266 280 40812703 281 42499147 282 44008321 283 46145913 284 48043480 285 49750348 286 52143096 287 54278158 288 56208764 289 58886601 290 61286316 291 63466467 292 66461719 293 69158809 294 71620731 295 74970143 296 77998317 297 80774407 298 84518086 299 87917840 300 91047913 301 95230912 302 99044065 303 102568695 304 107240630 305 111517201 306 115485454 307 120701602 308 125493378 309 129955918 310 135777525 311 141146123 312 146163415 313 152658189 314 158667670 315 164302775 316 171546158 317 178272341 318 184599621 319 192674539 320 200196515 321 207294279 322 216293472 323 224704323 324 232663930 325 242688865 326 252086097 327 261004554 328 272169005 329 282666763 330 292656163 331 305084159 332 316802451 333 327982642 334 341813577 335 354892112 336 367400461 337 382785795 338 397372050 339 411356361 340 428466516 341 444731261 342 460359619 343 479379432 344 497503622 345 514957867 346 536095377 347 556287429 348 575773059 349 599253558 350 621735138 351 643475387 352 669552471 353 694577648 354 718823409 355 747771413 356 775611275 357 802636111 358 834763694 359 865727520 360 895837364 361 931478218 362 965897065 363 999426524 364 1038955802 365 1077205712 366 1114527382 367 1158350541 368 1200835165 369 1242357557 370 1290930003 371 1338105940 372 1384282332 373 1438096155 374 1490454870 375 1541783210 376 1601390423 377 1659485734 378 1716516704 379 1782513979 380 1846943378 381 1910282881 382 1983338564 383 2054772932 384 2125089322 385 2205925987 386 2285090667 387 2363120066 388 2452545923 389 2540252769 390 2626805297 391 2725694437 392 2822822799 393 2918791448 394 3028120080 395 3135651206 396 3242016766 397 3362841154 398 3481839653 399 3599683882 400 3733181745 401 3864832342 402 3995341327 403 4142787614 404 4288377523 405 4432859732 406 4595673767 407 4756631801 408 4916519953 409 5096238981 410 5274119462 411 5450994204 412 5649326776 413 5845851099 414 6041441024 415 6260238677 416 6477281335 417 6693493331 418 6934810651 419 7174443308 420 7413360693 421 7679425266 422 7943905767 423 8207826077 424 8501106071 425 8792925088 426 9084356272 427 9407528897 428 9729402764 429 10051109673 430 10407136880 431 10762056852 432 11117055314 433 11509151348 434 11900381560 435 12291994820 436 12723710578 437 13154839949 438 13586690657 439 14061881108 440 14536827537 441 15012905318 442 15535823394 443 16058888515 444 16583540330 445 17158804686 446 17734685812 447 18312696066 448 18945395402 449 19579243444 450 20215822573 451 20911484981 452 21608925655 453 22309804728 454 23074513271 455 23841708330 456 24613126405 457 25453491049 458 26297170874 459 27145985671 460 28069271329 461 28996799895 462 29930474454 463 30944576942 464 31963997889 465 32990729436 466 34104317128 467 35224422839 468 36353129452 469 37575625191 470 38806018952 471 40046489001 472 41388226359 473 42739396291 474 44102276094 475 45574489422 476 47057889437 477 48554855507 478 50169852634 479 51797982095 480 53441731430 481 55212893947 482 56999400668 483 58803848683 484 60745822845 485 62705589597 486 64685864216 487 66814574697 488 68963847903 489 71136516731 490 73469377448 491 75825861752 492 78208932167 493 80764876909 494 83347893979 495 85961072678 496 88760788297 497 91591381195 498 94456082992 499 97522060950 500 100623187566 501 103762831377 502 107119625911 503 110516275271 504 113956304713 505 117630610098 506 121350035945 507 125118256379 508 129139192882 509 133211044714 510 137337659244 511 141736881739 512 146193484436 513 150711476895 514 155523492663 515 160399995374 516 165345186741 517 170607501282 518 175942210196 519 181353693406 520 187107164148 521 192941713282 522 198861934869 523 205150962139 524 211530707156 525 218005960714 526 224878882030 527 231853097438 528 238933637403 529 246442972113 530 254065315153 531 261805915890 532 270008805933 533 278337546269 534 286797655940 535 295756173823 536 304854737432 537 314099111193 538 323880754225 539 333817992553 540 343916895426 541 354594968534 542 365445793968 543 376475718267 544 388129889330 545 399975592196 546 412019519958 547 424736290613 548 437665279382 549 450813494821 550 464686826714 551 478795002640 552 493145427285 553 508277315471 554 523668932627 555 539328045505 556 555829226441 557 572617335911 558 589700595587 559 607691241099 560 625998687704 561 644631575165 562 664242094740 563 684202044689 564 704520590007 565 725892464909 566 747649558671 567 769801522747 568 793088218123 569 816799198459 570 840944724500 571 866312686099 572 892147728852 573 918460682459 574 946090376680 575 974233838460 576 1002902607039 577 1032989706361 578 1063641658692 579 1094870672708 580 1127627243793 581 1161004363471 582 1195015070529 583 1230670978531 584 1267008313956 585 1304040906219 586 1342845175915 587 1382397206663 588 1422711801908 589 1464934274523 590 1507976942601 591 1551855547374 592 1597788442831 593 1644620413291 594 1692368346555 595 1742328212485 596 1793273207026 597 1845221333420 598 1899550841657 599 1954959136796 600 2011465575127 601 2070535807370 602 2130786913185 603 2192239578671 604 2256452096389 605 2321956535194 606 2388775181352 607 2458564698746 608 2529767077995 609 2602406193394 610 2678242966066 611 2755624086964 612 2834575325799 613 2916968269952 614 3001048650851 615 3086844137068 616 3176343588555 617 3267685961209 618 3360901171841 619 3458102518893 620 3557315866444 621 3658573402681 622 3764120277028 623 3871862784740 624 3981835782955 625 4096424281654 626 4213407962800 627 4332824402179 628 4457206781522 629 4584200960604 630 4713847685556 631 4848837260090 632 4986673870565 633 5127401515967 634 5273876937264 635 5423454626322 636 5576182349026 637 5735093281387 638 5897383476058 639 6063104589977 640 6235476669378 641 6411528406614 642 6591315935158 643 6778257335517 644 6969204207099 645 7164217334753 646 7366924517491 647 7573990344246 648 7785480917828 649 8005246219761 650 8229753001531 651 8459072922110 652 8697291221591 653 8940665793535 654 9189274613191 655 9447452088800 656 9711235221163 657 9980708615853 658 10260470477373 659 10546324672064 660 10838363302981 661 11141463890136 662 11451183795661 663 11767623026719 664 12095954774372 665 12431476305051 666 12774296519971 667 13129901592053 668 13493313848306 669 13864651601396 670 14249732285343 671 14643288204144 672 15045448213435 673 15462380311504 674 15888510309656 675 16323978256230 676 16775323134427 677 17236647530602 678 17708103980184 679 18196623970298 680 18695968600117 681 19206303699117 682 19734976061354 683 20275386746429 684 20827716359401 685 21399750985293 686 21984511404967 687 22582193993629 688 23201049578943 689 23833698102708 690 24480353407574 691 25149757786974 692 25834107929081 693 26533636358193 694 27257605232025 695 27997765208556 696 28754369439991 697 29537229716864 698 30337625856497 699 31155833113557 700 32002244582924 701 32867644023284 702 33752331024863 703 34667313139663 704 35602850621880 705 36559269176179 706 37548226120962 707 38559430298267 708 39593236090897 709 40661987496405 710 41754811600752 711 42872093600785 712 44026903523650 713 45207755829112 714 46415069474003 715 47662681603223 716 48938460523281 717 50242861503469 718 51590532643649 719 52968661968378 720 54377744444679 721 55833284854903 722 57321753916909 723 58843689334438 724 60415501390171 725 62022905782843 726 63666486846147 727 65363611240008 728 67099198782346 729 68873884040278 730 70706044397903 731 72579762140386 732 74495726547245 733 76473382320858 734 78495929142411 735 80564115263824 736 82698513185897 737 84881394008474 738 87113570109593 739 89416804728837 740 91772390698386 741 94181209542955 742 96666282525503 743 99207873484958 744 101806939024595 745 104487828412686 746 107229721752778 747 110033656628068 748 112925385143255 749 115882947731739 750 118907469785490 751 122026184039605 752 125215930981133 753 128477930729138 754 131840979847377 755 135280657232018 756 138798285590208 757 142424311776852 758 146132986762575 759 149925743936679 760 153834772917539 761 157832928851200 762 161921764860040 763 166135309399487 764 170444948834546 765 174852365467324 766 179393529343721 767 184038283300493 768 188788449238989 769 193682045528726 770 198687291283266 771 203806159009588 772 209078829544649 773 214471816040749 774 219987253604752 775 225667604092108 776 231477586594259 777 237419511617664 778 243538248799588 779 249796632744137 780 256197163161256 781 262787249121652 782 269527744015851 783 276421351617304 784 283518161173483 785 290776945487308 786 298200628281009 787 305842125149226 788 313658022173718 789 321651480250507 790 329878397545808 791 338293064281106 792 346898896800198 793 355754938103120 794 364813066162253 795 374076972707501 796 383609018939611 797 393358550791152 798 403329556395326 799 413587895242719 800 424080253670944 801 434810939262166 802 445849502145610 803 457139837661685 804 468686597005629 805 480563220784422 806 492710673632896 807 505133976965120 808 517910675224603 809 530978658294273 810 544343345578581 811 558086607073709 812 572143104986433 813 586518687389052 814 601299786445009 815 616417678879003 816 631878673336491 817 647774010093286 818 664031413106727 819 680657686928666 820 697749142299688 821 715229777641441 822 733106930053568 823 751482253514404 824 770275838034653 825 789495593912741 826 809248809196581 827 829451476465769 828 850112121276291 829 871343968227190 830 893058712674478 831 915265542156498 832 938083940165710 833 961421098173775 834 985286913959890 835 1009807465276019 836 1034885221584580 837 1060530844558220 838 1086877363413053 839 1113822299811433 840 1141377134663415 841 1169682220419008 842 1198629892960977 843 1228232513990759 844 1258638154959765 845 1289733719455915 846 1321532513412179 847 1354190739343334 848 1387589609080450 849 1421743443346702 850 1456817014141141 851 1492685572594248 852 1529364526903666 853 1567027675204423 854 1605544025244679 855 1644930153510345 856 1685369369870557 857 1726724145495124 858 1769012308393624 859 1812427186160883 860 1856824405634386 861 1902223138835811 862 1948827268855124 863 1996485258810454 864 2045217720002333 865 2095239651603144 866 2146392018208697 867 2198696976172267 868 2252381236209054 869 2307277916749356 870 2363410828182455 871 2421019013750863 872 2479927381775440 873 2540161517560118 874 2601973456129364 875 2665179517600283 876 2729807186800863 877 2796122178338349 878 2863931828815852 879 2933265660635963 880 3004403797774269 881 3077144182453298 882 3151518517053160 883 3227822096626318 884 3305843039986979 885 3385615387050828 886 3467450411711601 887 3551125963282961 888 3636678581866675 889 3724436363652250 890 3814166423225253 891 3905907980584188 892 4000006848189680 893 4096218921988415 894 4194586287560244 895 4295473407495459 896 4398624455065689 897 4504084586287824 898 4612237903156675 899 4722816331823192 900 4835868310606316 901 4951798614746167 902 5070326377683180 903 5191503553423944 904 5315756685075225 905 5442791545532475 906 5572663846106916 907 5705823042167831 908 5841960956059682 909 5981137322136979 910 6123825719100744 911 6269703404542405 912 6418834411263760 913 6571717707939393 914 6728015349997264 915 6887795971101674 916 7051585269680436 917 7219029435331320 918 7390202016336935 919 7565656842684233 920 7745023550223590 921 7928380945831477 922 8116312473094625 923 8308430497776096 924 8504819442613577 925 8706093916035162 926 8911848272091458 927 9122172940430652 928 9337715333599512 929 9558051021610111 930 9783276847633569 931 10014074744782228 932 10250000700408337 933 10491158415553061 934 10738266156948736 935 10990859497587398 936 11249049458919860 937 11513592540385021 938 11784003041629875 939 12060399809186886 940 12343579580311424 941 12633034486775627 942 12928891726101001 943 13231990374335595 944 13541799472626351 945 13858455142400210 946 14182841015864312 947 14514402082689487 948 14853283985872410 949 15200417237927646 950 15555221787103947 951 15917853448067190 952 16289292065577192 953 16668931515792713 954 17056938463939359 955 17454344657854211 956 17860516841053714 957 18275633266680065 958 18700780296813963 959 19135296438386456 960 19579372303245810 961 20034151711212917 962 20498943798125269 963 20973952370500886 964 21460381703550161 965 21957510381409347 966 22465556279995065 967 22985787274773191 968 23517450186475357 969 24060777907778444 970 24617105228638292 971 25185645945872057 972 25766648961140932 973 26361519456854152 974 26969436913941467 975 27590667316211387 976 28226689902618921 977 28876648494751267 978 29540827283563377 979 30220783410662936 980 30915623663230963 981 31625651654547138 982 32352506479590408 983 33095256461974482 984 33854225912277640 985 34631140131834453 986 35425027520040829 987 36236234460220475 988 37066576938031822 989 37915041911405329 990 38781999280719804 991 39669360418621519 992 40576069293271780 993 41502520878354660 994 42450726883616647 995 43419586680220557 996 44409521950586263 997 45422649941198676 998 46457823788750099 999 47515493644545381 1000 48597887763682660