0 1 1 1 2 0 3 1 4 1 5 1 6 1 7 1 8 2 9 2 10 3 11 3 12 3 13 4 14 4 15 5 16 6 17 6 18 7 19 8 20 10 21 11 22 11 23 13 24 15 25 17 26 18 27 20 28 23 29 25 30 29 31 32 32 34 33 39 34 42 35 47 36 52 37 56 38 62 39 68 40 77 41 83 42 89 43 99 44 108 45 119 46 129 47 139 48 154 49 167 50 183 51 199 52 214 53 234 54 253 55 276 56 299 57 322 58 350 59 378 60 413 61 445 62 476 63 518 64 559 65 604 66 650 67 698 68 755 69 812 70 877 71 942 72 1010 73 1089 74 1167 75 1257 76 1349 77 1443 78 1551 79 1662 80 1787 81 1913 82 2042 83 2191 84 2345 85 2512 86 2683 87 2865 88 3068 89 3275 90 3504 91 3740 92 3985 93 4259 94 4540 95 4846 96 5167 97 5500 98 5864 99 6246 100 6661 101 7087 102 7533 103 8024 104 8534 105 9082 106 9652 107 10251 108 10904 109 11581 110 12308 111 13068 112 13864 113 14723 114 15619 115 16579 116 17582 117 18634 118 19763 119 20944 120 22211 121 23527 122 24903 123 26388 124 27938 125 29583 126 31305 127 33114 128 35047 129 37067 130 39213 131 41456 132 43811 133 46320 134 48939 135 51722 136 54635 137 57684 138 60927 139 64322 140 67919 141 71677 142 75611 143 79793 144 84171 145 88790 146 93620 147 98692 148 104062 149 109673 150 115601 151 121800 152 128293 153 135162 154 142340 155 149908 156 157832 157 166125 158 174874 159 184034 160 193683 161 203760 162 214310 163 225442 164 237079 165 249315 166 262106 167 275498 168 289605 169 304343 170 319828 171 336021 172 352959 173 370770 174 389384 175 408927 176 429353 177 450714 178 473148 179 496593 180 521199 181 546888 182 573733 183 601932 184 631383 185 662236 186 694465 187 728151 188 763475 189 800358 190 838986 191 879314 192 921448 193 965591 194 1011659 195 1059889 196 1110232 197 1162787 198 1217814 199 1275243 200 1335318 201 1397988 202 1463389 203 1531833 204 1603240 205 1677864 206 1755696 207 1836926 208 1921856 209 2010408 210 2102931 211 2199403 212 2300017 213 2405159 214 2514753 215 2629189 216 2748492 217 2872861 218 3002727 219 3138090 220 3279364 221 3426543 222 3579935 223 3740055 224 3906864 225 4080851 226 4262081 227 4450907 228 4647899 229 4853038 230 5066912 231 5289640 232 5521601 233 5763447 234 6015237 235 6277639 236 6550803 237 6835197 238 7131563 239 7440029 240 7761381 241 8095759 242 8443746 243 8806287 244 9183488 245 9576214 246 9984790 247 10409895 248 10852526 249 11312914 250 11792094 251 12290441 252 12808776 253 13348248 254 13909172 255 14492802 256 15099602 257 15730492 258 16386863 259 17069173 260 17778816 261 18516374 262 19282980 263 20080275 264 20908830 265 21770209 266 22665225 267 23595284 268 24562172 269 25566619 270 26610568 271 27694978 272 28821443 273 29992117 274 31207924 275 32471105 276 33782910 277 35145163 278 36560350 279 38029768 280 39555952 281 41140327 282 42785197 283 44493494 284 46266690 285 48107765 286 50018571 287 52001804 288 54060827 289 56197457 290 58415214 291 60716395 292 63104098 293 65582222 294 68153110 295 70820841 296 73588159 297 76458753 298 79437145 299 82526244 300 85730824 301 89054068 302 92500386 303 96075214 304 99781918 305 103625969 306 107611457 307 111743555 308 116028397 309 120470181 310 125075355 311 129848740 312 134796451 313 139925616 314 145241292 315 150751105 316 156460779 317 162377400 318 168509396 319 174862907 320 181446694 321 188267576 322 195333965 323 202655729 324 210240167 325 218097379 326 226235644 327 234664967 328 243396602 329 252439251 330 261804929 331 271503381 332 281546201 333 291946638 334 302715066 335 313865440 336 325409433 337 337360514 338 349734076 339 362542713 340 375802521 341 389527111 342 403732551 343 418436826 344 433654607 345 449404685 346 465703348 347 482569359 348 500023542 349 518083250 350 536770453 351 556104452 352 576107024 353 596802347 354 618211141 355 640358927 356 663268352 357 686964928 358 711476741 359 736828319 360 763049368 361 790166279 362 818208962 363 847210376 364 877199081 365 908209427 366 940272899 367 973424354 368 1007701700 369 1043138739 370 1079775514 371 1117648806 372 1156799291 373 1197270944 374 1239103452 375 1282343523 376 1327034146 377 1373222507 378 1420959884 379 1470292923 380 1521275586 381 1573958145 382 1628395693 383 1684647806 384 1742768986 385 1802821627 386 1864864768 387 1928962739 388 1995184162 389 2063592722 390 2134261234 391 2207258447 392 2282658856 393 2360542241 394 2440982995 395 2524065433 396 2609869909 397 2698482717 398 2789996223 399 2884497679 400 2982084447 401 3082849742 402 3186894257 403 3294325047 404 3405243279 405 3519761754 406 3637989315 407 3760042665 408 3886045478 409 4016115463 410 4150383319 411 4288975746 412 4432027670 413 4579682020 414 4732076070 415 4889360884 416 5051683429 417 5219200074 418 5392075981 419 5570470764 420 5754559039 421 5944510888 422 6140507508 423 6342740249 424 6551393743 425 6766669348 426 6988765115 427 7217890532 428 7454265810 429 7698105392 430 7949641975 431 8209104695 432 8476735712 433 8752789018 434 9037513027 435 9331176590 436 9634044677 437 9946396599 438 10268525708 439 10600719703 440 10943288112 441 11296537284 442 11660789888 443 12036384183 444 12423652631 445 12822951550 446 13234635427 447 13659076864 448 14096664674 449 14547782875 450 15012842697 451 15492253118 452 15986443092 453 16495860672 454 17020949235 455 17562182021 456 18120031148 457 18694990307 458 19287574968 459 19898297417 460 20527701529 461 21176330870 462 21844754730 463 22533566081 464 23243354518 465 23974745531 466 24728365929 467 25504870520 468 26304940448 469 27129254705 470 27978532412 471 28853495411 472 29754895946 473 30683516242 474 31640138529 475 32625588599 476 33640696434 477 34686326556 478 35763376957 479 36872747575 480 38015386328 481 39192246512 482 40404321287 483 41652641997 484 42938241913 485 44262207914 486 45625636642 487 47029667762 488 48475482753 489 49964269025 490 51497273230 491 53075753877 492 54701018164 493 56374420045 494 58097322478 495 59871154750 496 61697360287 497 63577436857 498 65512936265 499 67505422230 500 69556530909 501 71667917148 502 73841297365 503 76078448508 504 78381162686 505 80751312168 506 83190794016 507 85701574248 508 88285684781 509 90945178427 510 93682198752 511 96498917641 512 99397583923 513 102380522222 514 105450082871 515 108608716857 516 111858910226 517 115203234198 518 118644346001 519 122184936274 520 125827805270 521 129575795247 522 133431846945 523 137398996631 524 141480319492 525 145679014544 526 149998331882 527 154441630918 528 159012378186 529 163714087907 530 168550413092 531 173525067344 532 178641885446 533 183904823539 534 189317896804 535 194885273655 536 200611193599 537 206500033268 538 212556305665 539 218784594709 540 225189654744 541 231776322402 542 238549590508 543 245514606409 544 252676598065 545 260040984371 546 267613284339 547 275399189778 548 283404564592 549 291635371145 550 300097784667 551 308798095740 552 317742789948 553 326938546271 554 336392159931 555 346110664856 556 356101227309 557 366371232444 558 376928285764 559 387780127994 560 398934764431 561 410400355387 562 422185308370 563 434298278569 564 446748077807 565 459543813052 566 472694773495 567 486210526050 568 500100912771 569 514375960031 570 529046026972 571 544121679944 572 559613796712 573 575533567626 574 591892395915 575 608702056312 576 625974563492 577 643722280305 578 661957922786 579 680694455707 580 699945255180 581 719723973209 582 740044658079 583 760921753441 584 782369986789 585 804404548739 586 827040948338 587 850295137991 588 874183514354 589 898722801782 590 923930244247 591 949823450800 592 976420526089 593 1003740076014 594 1031801086129 595 1060623120920 596 1090226161974 597 1120630749679 598 1151857988110 599 1183929417721 600 1216867226055 601 1250694075416 602 1285433259732 603 1321108708694 604 1357744846107 605 1395366821396 606 1434000332271 607 1473671781703 608 1514408284609 609 1556237526505 610 1599188004825 611 1643288839859 612 1688569945549 613 1735062035938 614 1782796477964 615 1831805549089 616 1882122233012 617 1933780404709 618 1986814843234 619 2041261071058 620 2097155626477 621 2154535853828 622 2213440100608 623 2273907729936 624 2335978950175 625 2399695106185 626 2465098463669 627 2532232414809 628 2601141487110 629 2671871173614 630 2744468244636 631 2818980510865 632 2895457046569 633 2973948206529 634 3054505441994 635 3137181633254 636 3222030842584 637 3309108547962 638 3398471668319 639 3490178371833 640 3584288419700 641 3680862912817 642 3779964549409 643 3881657642608 644 3986007917679 645 4093082888268 646 4202951588050 647 4315684840018 648 4431355279422 649 4550037143547 650 4671806674223 651 4796741833520 652 4924922586657 653 5056430935726 654 5191350702299 655 5329767947561 656 5471770676492 657 5617449144399 658 5766895892524 659 5920205522250 660 6077475140252 661 6238804046466 662 6404294070898 663 6574049611297 664 6748177385460 665 6926786917263 666 7109990217479 667 7297902126774 668 7490640361249 669 7688325267131 670 7891080330417 671 8099031839686 672 8312309258049 673 8531045272813 674 8755375542950 675 8985439243113 676 9221378703136 677 9463339810730 678 9711472076304 679 9965928360789 680 10226865452515 681 10494443700002 682 10768827442117 683 11050185077568 684 11338688779939 685 11634515114841 686 11937844665658 687 12248862486045 688 12567758169466 689 12894725568751 690 13229963457047 691 13573675121959 692 13926068855662 693 14287358044496 694 14657760869743 695 15037501013251 696 15426807238559 697 15825913908682 698 16235061096666 699 16654494278360 700 17084465068482 701 17525230796092 702 17977055072217 703 18440207896123 704 18914965335739 705 19401610329669 706 19900432243332 707 20411727467737 708 20935799543443 709 21472958835417 710 22023523392232 711 22587818481983 712 23166177226363 713 23758940752525 714 24366457863846 715 24989085943126 716 25627190476390 717 26281145740294 718 26951334968533 719 27638150016896 720 28341992324183 721 29063272417918 722 29802410666623 723 30559837462086 724 31335992858661 725 32131327619006 726 32946302717149 727 33781390118499 728 34637072988780 729 35513845347888 730 36412213174609 731 37332693890708 732 38275817206615 733 39242125353125 734 40232172736030 735 41246527118163 736 42285769077592 737 43350492924517 738 44441306974779 739 45558833186377 740 46703708418935 741 47876583894701 742 49078126182947 743 50309017500120 744 51569955341501 745 52861653832347 746 54184843192654 747 55540270783143 748 56928701426898 749 58350917065865 750 59807718211931 751 61299923378036 752 62828370212364 753 64393915876261 754 65997436690896 755 67639829691608 756 69322012057253 757 71044922320497 758 72809520805758 759 74616789284722 760 76467732614985 761 78363378182520 762 80304777225586 763 82293005295222 764 84329161916049 765 86414372368995 766 88549787127675 767 90736583269553 768 92975964997121 769 95269163317959 770 97617437961451 771 100022076810434 772 102484397409654 773 105005747567992 774 107587505063704 775 110231079677355 776 112937912635124 777 115709478248199 778 118547284578471 779 121452873169231 780 124427821221020 781 127473741041803 782 130592281839266 783 133785130455878 784 137054011098342 785 140400687704169 786 143826963426908 787 147334682527730 788 150925731201782 789 154602037374698 790 158365573224772 791 162218354681791 792 166162443482828 793 170199948089859 794 174333023536914 795 178563874141593 796 182894753011994 797 187327964282622 798 191865864158630 799 196510860788478 800 201265417172185 801 206132050728122 802 211113335708986 803 216211904354815 804 221430446818980 805 226771714302965 806 232238518690535 807 237833735141620 808 243560303353317 809 249421227592976 810 255419580080440 811 261558500637681 812 267841199509993 813 274270958798199 814 280851132552517 815 287585150414828 816 294476517341751 817 301528816644470 818 308745711606135 819 316130945672986 820 323688346337373 821 331421824967268 822 339335380132099 823 347433099355768 824 355719159409774 825 364197830541070 826 372873476387179 827 381750557557519 828 390833633592178 829 400127363389538 830 409636509774951 831 419365939513647 832 429320627174680 833 439505657339885 834 449926225186869 835 460587641382181 836 471495332229460 837 482654843882928 838 494071844791497 839 505752126448689 840 517701608666731 841 529926339866761 842 542432501689143 843 555226411695310 844 568314524258179 845 581703436307066 846 595399887817553 847 609410766750892 848 623743112063401 849 638404114859140 850 653401124568182 851 668741649618150 852 684433362820264 853 700484104704605 854 716901884926913 855 733694888949343 856 750871478902956 857 768440199465857 858 786409781597282 859 804789144176802 860 823587401220372 861 842813863034607 862 862478042606623 863 882589659729246 864 903158642937517 865 924195137328917 866 945709506041659 867 967712337175683 868 990214448330897 869 1013226888947225 870 1036760948786142 871 1060828159675581 872 1085440303063203 873 1110609415091791 874 1136347789296798 875 1162667985793757 876 1189582833405351 877 1217105437863458 878 1245249187470243 879 1274027756235129 880 1303455113769341 881 1333545527876082 882 1364313573534130 883 1395774139097930 884 1427942429913047 885 1460833979111044 886 1494464650661516 887 1528850649123470 888 1564008526526062 889 1599955186546650 890 1636707896235744 891 1674284289583444 892 1712702378116663 893 1751980558567210 894 1792137617681745 895 1833192744888859 896 1875165536475895 897 1918076007177534 898 1961944598647845 899 2006792184958365 900 2052640086338346 901 2099510074016217 902 2147424382914818 903 2196405721005417 904 2246477275499690 905 2297662727848752 906 2349986259382753 907 2403472565057573 908 2458146863816306 909 2514034905711236 910 2571162988156612 911 2629557962388533 912 2689247248496020 913 2750258846873614 914 2812621346315244 915 2876363941681057 916 2941516441248005 917 3008109283156217 918 3076173548122286 919 3145740968528796 920 3216843947619395 921 3289515567957543 922 3363789609380763 923 3439700563026524 924 3517283641583371 925 3596574800188668 926 3677610746111194 927 3760428958313205 928 3845067702894009 929 3931566044737042 930 4019963870272803 931 4110301898370922 932 4202621701741147 933 4296965724063881 934 4393377293042335 935 4491900645178189 936 4592580938130909 937 4695464274071079 938 4800597718656416 939 4908029315697332 940 5017808114039528 941 5129984181605427 942 5244608630993051 943 5361733640319242 944 5481412469654878 945 5603699490407941 946 5728650201142276 947 5856321255503090 948 5986770485246103 949 6120056918675228 950 6256240812680310 951 6395383670519291 952 6537548272300589 953 6682798700475699 954 6831200360499138 955 6982820015655319 956 7137725807068391 957 7295987287088626 958 7457675447396759 959 7622862742093574 960 7791623125647034 961 7964032075344562 962 8140166627890455 963 8320105410374672 964 8503928665940681 965 8691718295277676 966 8883557881858468 967 9079532731811684 968 9279729908094671 969 9484238259248430 970 9693148464584433 971 9906553062396265 972 10124546493619820 973 10347225139503186 974 10574687353677903 975 10807033511450540 976 11044366041266307 977 11286789472536344 978 11534410477238393 979 11787337905518146 980 12045682839448139 981 12309558628262122 982 12579080940680857 983 12854367810716350 984 13135539677254783 985 13422719442752709 986 13716032512620743 987 14015606852410605 988 14321573038197110 989 14634064300714569 990 14953216589460769 991 15279168616432008 992 15612061918751589 993 15952040914273639 994 16299252950525899 995 16653848374686164 996 17015980582303987 997 17385806085800817 998 17763484575790614 999 18149178975399315 1000 18543055516528074