1 1 2 0 3 0 4 1 5 1 6 1 7 1 8 1 9 2 10 2 11 3 12 3 13 4 14 4 15 5 16 6 17 7 18 8 19 10 20 11 21 13 22 15 23 17 24 19 25 23 26 25 27 29 28 33 29 38 30 42 31 49 32 54 33 62 34 69 35 78 36 87 37 99 38 109 39 123 40 137 41 154 42 170 43 191 44 211 45 236 46 261 47 290 48 320 49 357 50 392 51 435 52 479 53 530 54 582 55 644 56 706 57 779 58 854 59 940 60 1029 61 1133 62 1237 63 1358 64 1485 65 1627 66 1775 67 1944 68 2118 69 2316 70 2523 71 2754 72 2996 73 3269 74 3552 75 3869 76 4204 77 4573 78 4962 79 5395 80 5848 81 6351 82 6881 83 7463 84 8079 85 8758 86 9471 87 10255 88 11086 89 11993 90 12952 91 14003 92 15111 93 16322 94 17605 95 18999 96 20477 97 22086 98 23785 99 25633 100 27593 101 29714 102 31962 103 34399 104 36978 105 39769 106 42729 107 45921 108 49308 109 52965 110 56835 111 61009 112 65437 113 70199 114 75249 115 80683 116 86440 117 92627 118 99189 119 106227 120 113692 121 121702 122 130184 123 139278 124 148922 125 159241 126 170180 127 181888 128 194289 129 207552 130 221608 131 236619 132 252526 133 269515 134 287502 135 306699 136 327037 137 348716 138 371675 139 396150 140 422054 141 449651 142 478866 143 509959 144 542873 145 577898 146 614948 147 654354 148 696051 149 740361 150 787232 151 837036 152 889693 153 945617 154 1004750 155 1067505 156 1133849 157 1204244 158 1278628 159 1357521 160 1440890 161 1529256 162 1622610 163 1721542 164 1826021 165 1936696 166 2053571 167 2177308 168 2307951 169 2446239 170 2592185 171 2746615 172 2909592 173 3081956 174 3263817 175 3456113 176 3658940 177 3873330 178 4099436 179 4338331 180 4590229 181 4856317 182 5136796 183 5432982 184 5745159 185 6074685 186 6421923 187 6788381 188 7174430 189 7581727 190 8010737 191 8463199 192 8939685 193 9442112 194 9971071 195 10528671 196 11115641 197 11734188 198 12385176 199 13071046 200 13792710 201 14552842 202 15352519 203 16194570 204 17080259 205 18012685 206 18993194 207 20025189 208 21110241 209 22251951 210 23452116 211 24714699 212 26041633 213 27437247 214 28903761 215 30445778 216 32065831 217 33768957 218 35557883 219 37438125 220 39412784 221 41487734 222 43666467 223 45955421 224 48358383 225 50882369 226 53531643 227 56313711 228 59233362 229 62298792 230 65515181 231 68891481 232 72433500 233 76150815 234 80049901 235 84141218 236 88431800 237 92933035 238 97652758 239 102603197 240 107793052 241 113235651 242 118940435 243 124921926 244 131190611 245 137762073 246 144647911 247 151865110 248 159426279 249 167349891 250 175649872 251 184346103 252 193453950 253 202995040 254 212986065 255 223450542 256 234406882 257 245880383 258 257891290 259 270467131 260 283629902 261 297409498 262 311830090 263 326923894 264 342717448 265 359245738 266 376537582 267 394630974 268 413557531 269 433358189 270 454067562 271 475730111 272 498383425 273 522075729 274 546848162 275 572752722 276 599834396 277 628149584 278 657747101 279 688688116 280 721025967 281 754826606 282 790148236 283 827062379 284 865632188 285 905935134 286 948040102 287 992030661 288 1037981896 289 1085984341 290 1136119383 291 1188485082 292 1243170099 293 1300280181 294 1359911822 295 1422179532 296 1487187884 297 1555060789 298 1625911996 299 1699875166 300 1777073956 301 1857652988 302 1941746165 303 2029509934 304 2121089802 305 2216654456 306 2316361883 307 2420394528 308 2528923403 309 2642145720 310 2760247060 311 2883440087 312 3011926114 313 3145934973 314 3285684419 315 3431422781 316 3583386168 317 3741842254 318 3907046889 319 4079289245 320 4258845917 321 4446029148 322 4641138521 323 4844510575 324 5056469681 325 5277379132 326 5507589387 327 5747492554 328 5997467916 329 6257937926 330 6529312847 331 6812048539 332 7106588026 333 7413423023 334 7733032557 335 8065946266 336 8412681942 337 8773810739 338 9149891444 339 9541539876 340 9949359774 341 10374014192 342 10816155183 343 11276497462 344 11755744356 345 12254666001 346 12774021710 347 13314640459 348 13877341772 349 14463018698 350 15072554654 351 15706911541 352 16367042448 353 17053982332 354 17768759117 355 18512487234 356 19286274203 357 20091319711 358 20928817778 359 21800058796 360 22706329706 361 23649019261 362 24629513252 363 25649306029 364 26709890698 365 27812873884 366 28959863850 367 30152588906 368 31392779994 369 32682295886 370 34023000330 371 35416891081 372 36865974449 373 38372398402 374 39938321134 375 41566051729 376 43257912650 377 45016384571 378 46843966101 379 48743323277 380 50717142524 381 52768288478 382 54899650318 383 57114304422 384 59415357404 385 61806113891 386 64289912331 387 66870301984 388 69550871328 389 72335430385 390 75227835511 391 78232177671 392 81352599037 393 84593491380 394 87959304655 395 91454751486 396 95084611587 397 98853942723 398 102767876363 399 106831839888 400 111051343231 401 115432207911 402 119980349069 403 124702011962 404 129603544150 405 134691644263 406 139973124554 407 145455167366 408 151145082384 409 157050571335 410 163179474590 411 169540049607 412 176140706679 413 182990295971 414 190097837499 415 197472817484 416 205124906561 417 213064271081 418 221301279655 419 229846824234 420 238712019957 421 247908536647 422 257448285866 423 267343769100 424 277607751819 425 288253622447 426 299295059271 427 310746401127 428 322622300156 429 334938110741 430 347709528222 431 360952990190 432 374685306897 433 388924075612 434 403687295759 435 418993803525 436 434862871516 437 451314656967 438 468369792497 439 486049849050 440 504376909719 441 523374054992 442 543064919784 443 563474194186 444 584627170348 445 606550259541 446 629270520915 447 652816203236 448 677216255165 449 702500884169 450 728701055795 451 755849071139 452 783978046001 453 813122515495 454 843317893323 455 874601095760 456 907009988647 457 940584031846 458 975363704698 459 1011391180618 460 1048709730580 461 1087364419388 462 1127401495807 463 1168869112010 464 1211816690004 465 1256295674143 466 1302358874109 467 1350061241763 468 1399459199271 469 1450611441677 470 1503578239570 471 1558422278515 472 1615207935865 473 1674002147368 474 1734873667977 475 1797893967428 476 1863136463297 477 1930677456980 478 2000595339166 479 2072971556450 480 2147889798987 481 2225436999444 482 2305702490847 483 2388779050541 484 2474762027857 485 2563750422125 486 2655845991448 487 2751154367007 488 2849784129415 489 2951847972577 490 3057461747787 491 3166745666147 492 3279823321660 493 3396822934172 494 3517876337897 495 3643120279375 496 3772695371092 497 3906747432275 498 4045426420281 499 4188887816995 500 4337291522656 501 4490803303126 502 4649593646446 503 4813839258517 504 4983721895307 505 5159429909320 506 5341157042098 507 5529104038264 508 5723477397839 509 5924491044269 510 6132365051009 511 6347327366913 512 6569612499818 513 6799463316726 514 7037129684864 515 7282870332693 516 7536951463223 517 7799648678920 518 8071245549764 519 8352035621402 520 8642320937474 521 8942414115944 522 9252636842247 523 9573322017719 524 9904812204230 525 10247461864725 526 10601635760009 527 10967711265975 528 11346076739279 529 11737133915164 530 12141296222210 531 12558991283090 532 12990659178139 533 13436755032113 534 13897747245592 535 14374120172516 536 14866372297713 537 15375019028409 538 15900590818626 539 16443636057697 540 17004719160642 541 17584423558575 542 18183349732987 543 18802118333563 544 19441368156382 545 20101759370476 546 20783971461713 547 21488706574098 548 22216687394865 549 22968660637402 550 23745394868613 551 24547684114817 552 25376345653457 553 26232223747916 554 27116187378960 555 28029134137874 556 28971987898091 557 29945702846298 558 30951261118969 559 31989676979000 560 33061994389849 561 34169291368823 562 35312677500527 563 36493298446276 564 37712333422356 565 38970999872956 566 40270550885979 567 41612280063646 568 42997518876617 569 44427641710278 570 45904063185555 571 47428243390332 572 49001685136842 573 50625939414093 574 52302602584468 575 54033322034869 576 55819793342000 577 57663766131814 578 59567041183118 579 61531476535007 580 63558984530374 581 65651538147717 582 67811168017442 583 70039968989637 584 72340097090182 585 74713776366152 586 77163295785537 587 79691016336655 588 82299367905405 589 84990856640962 590 87768061777248 591 90633643311140 592 93590338771135 593 96640971182739 594 99788445822585 595 103035758485593 596 106385992188595 597 109842325788047 598 113408030638421 599 117086479535720 600 120881143370063 601 124795600410801 602 128833532917286 603 132998736819269 604 137295118290824 605 141726703799531 606 146297636688179 607 151012187611417 608 155874751086200 609 160889856373221 610 166062164003602 611 171396477079683 612 176897737824374 613 182571039321251 614 188421622048109 615 194454886119289 616 200676387811137 617 207091852279705 618 213707170130107 619 220528410633645 620 227561818299419 621 234813826658337 622 242291054848045 623 250000321938116 624 257948643583132 625 266143246914776 626 274591567222591 627 283301263487342 628 292280215100655 629 301536538013343 630 311078581555258 631 320914945229443 632 331054475588835 633 341506283755829 634 352279742371683 635 363384503816763 636 374830497297909 637 386627947802923 638 398787373283832 639 411319604433908 640 424235781983329 641 437547377274256 642 451266189741982 643 465404368327572 644 479974409100475 645 494989177603318 646 510461906638458 647 526406219523145 648 542836128117750 649 559766057035105 650 577210841868322 651 595185754459666 652 613706501352134 653 632789250096691 654 652450628015484 655 672707749598545 656 693578215535398 657 715080141314865 658 737232156556223 659 760053434795483 660 783563693209899 661 807783223647954 662 832732892707361 663 858434174134792 664 884909149292170 665 912180540911268 666 940271714054554 667 969206711291428 668 999010254113215 669 1029707779668222 670 1061325442674357 671 1093890153704747 672 1127429581712475 673 1161972193941230 674 1197547259027385 675 1234184888687974 676 1271916041449375 677 1310772566108086 678 1350787206215301 679 1391993645397815 680 1434426512564520 681 1478121429254133 682 1523115015624407 683 1569444939830750 684 1617149924938969 685 1666269800432445 686 1716845510022812 687 1768919165471322 688 1822534055366070 689 1877734701268681 690 1934566867617077 691 1993077620311821 692 2053315337722243 693 2115329771915859 694 2179172060852152 695 2244894792277864 696 2312552017283024 697 2382199316990853 698 2453893817464824 699 2527694259421080 700 2603661014582025 701 2681856158444992 702 2762343488280083 703 2845188599104653 704 2930458903321762 705 3018223710150947 706 3108554247023457 707 3201523742519629 708 3297207449738486 709 3395682732911460 710 3497029092758057 711 3601328257057403 712 3708664208122390 713 3819123277394754 714 3932794175285384 715 4049768089989427 716 4170138719717103 717 4294002376039943 718 4421458018670868 719 4552607363430627 720 4687554919851045 721 4826408103985587 722 4969277278881803 723 5116275872585538 724 5267520421665072 725 5423130694519980 726 5583229738269394 727 5747944007624691 728 5917403415206598 729 6091741466370498 730 6271095313169129 731 6455605895273653 732 6645417997929645 733 6840680399268788 734 7041545932353864 735 7248171639318539 736 7460718837751163 737 7679353281837219 738 7904245233478147 739 8135569630778334 740 8373506164022115 741 8618239451994093 742 8869959123109780 743 9128859999786252 744 9395142185170401 745 9669011255949356 746 9950678354842146 747 10240360392401333 748 10538280145607995 749 10844666468926377 750 11159754399508385 751 11483785377952322 752 11817007360322994 753 12159675049231915 754 12512050013073987 755 12874400927747993 756 13247003703679690 757 13630141738697459 758 14024106053104981 759 14429195554411017 760 14845717180912962 761 15273986178661385 762 15714326254205292 763 16167069864386103 764 16632558378565866 765 17111142382035299 766 17603181848267229 767 18109046456396390 768 18629115774232098 769 19163779590490528 770 19713438108964928 771 20278502296400520 772 20859394088446725 773 21456546753715684 774 22070405112356809 775 22701425917083763 776 23350078084850983 777 24016843095851767 778 24702215239026898 779 25406702029679079 780 26130824469763898 781 26875117485019999 782 27640130200626413 783 28426426398986511 784 29234584811593918 785 30065199598227995 786 30918880656117089 787 31796254121582197 788 32697962697192490 789 33624666177143306 790 34577041793385425 791 35555784765634541 792 36561608667708951 793 37595246003357685 794 38657448593643090 795 39748988180049059 796 40870656834040501 797 42023267588501040 798 43207654870883526 799 44424675164345597 800 45675207465478785 801 46960153976797549 802 48280440590363275 803 49637017612860252 804 51030860276722865 805 52462969499365695 806 53934372422991193 807 55446123209857679 808 56999303612283834 809 58595023805393516 810 60234422989159061 811 61918670260428286 812 63648965248389399 813 65426539028016553 814 67252654790717052 815 69128608800878357 816 71055731103796180 817 73035386527391355 818 75068975429053344 819 77157934744961580 820 79303738777871118 821 81507900295995844 822 83771971364140958 823 86097544494527421 824 88486253523183928 825 90939774815477348 826 93459828190113184 827 96048178181653095 828 98706635014865219 829 101437055926956441 830 104241346194519741 831 107121460518634346 832 110079404107113243 833 113117234125116032 834 116237060835839374 835 119441049119777384 836 122731419676475341 837 126110450616023235 838 129580478724998386 839 133143901133266181 840 136803176647697208 841 140560827497868802 842 144419440740621250 843 148381670088750237 844 152450237389998480 845 156627934542294661 846 160917625051291272 847 165322246036277803 848 169844809869825530 849 174488406279031979 850 179256204071424020 851 184151453335655592 852 189177487258362555 853 194337724429042870 854 199635670752013411 855 205074921860786131 856 210659165129900493 857 216392182203555192 858 222277851112694268 859 228320148923324267 860 234523153963663208 861 240891048598197985 862 247428121570399288 863 254138770908022297 864 261027506387532412 865 268098952576867954 866 275357851427164004 867 282809065459888030 868 290457580492183630 869 298308508974724471 870 306367092857716538 871 314638707086606004 872 323128862615200877 873 331843210067109664 874 340787542903262568 875 349967801256402590 876 359390075261050420 877 369060609069217997 878 378985804350301054 879 389172224497008697 880 399626598303540010 881 410355824370159966 882 421366974968871877 883 432667300656005782 884 444264234334025907 885 456165396082384932 886 468378597425078501 887 480911846389476387 888 493773351990150525 889 506971529526404813 890 520515005292359505 891 534412622124887153 892 548673444350979293 893 563306763597252956 894 578322103986651170 895 593729228221802448 896 609538143042559623 897 625759105596562988 898 642402629170283483 899 659479489859632605 900 677000732588279723 901 694977678092362787 902 713421929239347632 903 732345378342079936 904 751760213792707130 905 771678927720818112 906 792114322958185898 907 813079521057085092 908 834587969601119450 909 856653450601099736 910 879290088168618553 911 902512357306429399 912 926335091962771185 913 950773494234648323 914 975843142820479507 915 1001560002656117591 916 1027940433784911331 917 1055001201445895783 918 1082759485381856479 919 1111232890400743887 920 1140439456141930199 921 1170397668133474469 922 1201126468038455038 923 1232645265230377379 924 1264973947543100224 925 1298132893388448844 926 1332142983032944591 927 1367025611283442101 928 1402802699315711116 929 1439496707953641816 930 1477130650076561860 931 1515728104519525678 932 1555313229085997732 933 1595910775098665383 934 1637546101046179838 935 1680245187813764160 936 1724034652994708516 937 1768941766832206520 938 1814994467226172378 939 1862221376419890497 940 1910651816734971985 941 1960315828036327737 942 2011244184230334913 943 2063468411544051111 944 2117020805821626157 945 2171934451656043440 946 2228243240521333487 947 2285981890795203206 948 2345185966767078738 949 2405891899592633982 950 2468137007217823923 951 2531959516308974818 952 2597398583135735733 953 2664494316520603046 954 2733287799726498023 955 2803821114472557038 956 2876137363872317180 957 2950280697565532874 958 3026296335756051586 959 3104230595509833873 960 3184130915944663459 961 3266045885747814315 962 3350025269570243445 963 3436120036820628385 964 3524382389320107159 965 3614865791430022636 966 3707624999026720298 967 3802716091023989313 968 3900196499728133161 969 4000125043819734614 970 4102561960153047812 971 4207568938262603260 972 4315209153674781169 973 4425547304008815151 974 4538649643869419631 975 4654584022615829784 976 4773419920908592795 977 4895228490221448098 978 5020082591119679930 979 5148056834594171314 980 5279227622150013609 981 5413673189046600981 982 5551473646279953563 983 5692711025814251411 984 5837469324546086395 985 5985834551617861846 986 6137894774453893496 987 6293740168251192662 988 6453463064182610630 989 6617158001162437539 990 6784921776317143477 991 6956853499128862500 992 7133054644276384594 993 7313629108265263023 994 7498683264747644446 995 7688326023750139608 996 7882668889587039780 997 8081826022803365457 998 8285914300798651016 999 8495053382608960236 1000 8709365772365013652