0 1 1 0 2 1 3 1 4 2 5 1 6 3 7 2 8 4 9 4 10 6 11 6 12 9 13 9 14 12 15 14 16 17 17 18 18 25 19 26 20 32 21 38 22 43 23 49 24 62 25 65 26 78 27 92 28 103 29 114 30 142 31 151 32 175 33 203 34 229 35 252 36 302 37 323 38 378 39 422 40 477 41 524 42 619 43 661 44 758 45 847 46 958 47 1038 48 1204 49 1297 50 1485 51 1626 52 1829 53 1989 54 2285 55 2459 56 2770 57 3035 58 3411 59 3694 60 4177 61 4511 62 5063 63 5519 64 6143 65 6672 66 7479 67 8068 68 8986 69 9789 70 10855 71 11741 72 13049 73 14133 74 15632 75 16994 76 18691 77 20268 78 22386 79 24216 80 26638 81 28894 82 31688 83 34311 84 37664 85 40764 86 44595 87 48339 88 52754 89 57094 90 62421 91 67438 92 73495 93 79572 94 86546 95 93584 96 101802 97 109955 98 119450 99 129097 100 140011 101 151133 102 163924 103 176842 104 191557 105 206717 106 223543 107 241004 108 260713 109 280868 110 303452 111 326925 112 352809 113 379828 114 409827 115 440945 116 475330 117 511315 118 550723 119 592026 120 637476 121 684807 122 736835 123 791430 124 850970 125 913353 126 981662 127 1053120 128 1131243 129 1213108 130 1302234 131 1395873 132 1497785 133 1604587 134 1720778 135 1842786 136 1975324 137 2114316 138 2265224 139 2423658 140 2595602 141 2775610 142 2971036 143 3176075 144 3398178 145 3631039 146 3883323 147 4147640 148 4434004 149 4733743 150 5058109 151 5398481 152 5766416 153 6151241 154 6567814 155 7003717 156 7474829 157 7968241 158 8501009 159 9058209 160 9660555 161 10290597 162 10969362 163 11681336 164 12448350 165 13249593 166 14114983 167 15019836 168 15993905 169 17013504 170 18110789 171 19258062 172 20494146 173 21785664 174 23173881 175 24627827 176 26189827 177 27821541 178 29576949 179 31412214 180 33380300 181 35441586 182 37651990 183 39962197 184 42442638 185 45035050 186 47811755 187 50719909 188 53832421 189 57086078 190 60571723 191 64218621 192 68115832 193 72197860 194 76558988 195 81120168 196 85998485 197 91100475 198 96544471 199 102248643 200 108331527 201 114696424 202 121488885 203 128597949 204 136169293 205 144102558 206 152549969 207 161391629 208 170809819 209 180670327 210 191153218 211 202143669 212 213823631 213 226052957 214 239056492 215 252676131 216 267134096 217 282291827 218 298375231 219 315222803 220 333105277 221 351841807 222 371700074 223 392523552 224 414585303 225 437701349 226 462199656 227 487873555 228 515045921 229 543542473 230 573691284 231 605288835 232 638725739 233 673772731 234 710816968 235 749667732 236 790721748 237 833751143 238 879224928 239 926894807 240 977216974 241 1029999948 242 1085704321 243 1144095118 244 1205725626 245 1270333509 246 1338467950 247 1409923560 248 1485252392 249 1564218416 250 1647469737 251 1734743516 252 1826682327 253 1923093896 254 2024635284 255 2131065075 256 2243163970 257 2360666207 258 2484335753 259 2613998922 260 2750436384 261 2893434376 262 3043903650 263 3201597973 264 3367436030 265 3541276317 266 3724050622 267 3915573938 268 4116937309 269 4327937178 270 4549656270 271 4782014556 272 5026136539 273 5281886981 274 5550579666 275 5832049285 276 6127623845 277 6437299326 278 6762422362 279 7102948497 280 7460446726 281 7834869915 282 8227795157 283 8639326873 284 9071122865 285 9523251250 286 9997624209 287 10494280876 288 11015187476 289 11560589886 290 12132516451 291 12731182307 292 13358933445 293 14015976992 294 14704719707 295 15425591798 296 16181133248 297 16971744733 298 17800311377 299 18667246582 300 19575543647 301 20525899129 302 21521453830 303 22562852030 304 23653702773 305 24794683531 306 25989546745 307 27239252998 308 28547779744 309 29916131074 310 31348762636 311 32846700401 312 34414670807 313 36054033480 314 37769797672 315 39563339746 316 41440318735 317 43402190437 318 45454891198 319 47600268830 320 49844678345 321 52190053822 322 54643457377 323 57206913405 324 59887967007 325 62689074937 326 65618305853 327 68678211555 328 71877756927 329 75219684940 330 78713543882 331 82362549467 332 86176970930 333 90160209640 334 94323589741 335 98670725443 336 103213769142 337 107956936989 338 112913216449 339 118087102841 340 123492902691 341 129135472443 342 135030104130 343 141182266065 344 147608539638 345 154314750856 346 161318974418 347 168627520565 348 176259826542 349 184222999578 350 192537910283 351 201212290561 352 210268846283 353 219715890117 354 229577957145 355 239864183364 356 250601083345 357 261798581007 358 273485328162 359 285672149993 360 298389945602 361 311650649129 362 325487533227 363 339913565832 364 354964734220 365 370655222009 366 387023807430 367 404085886824 368 421883363311 369 440433089103 370 459780143391 371 479942973767 372 500970237139 373 522881882979 374 545730422466 375 569537750341 376 594360265006 377 620221911861 378 647183529785 379 675271073598 380 704550074765 381 735049139577 382 766838380854 383 799949105380 384 834457147343 385 870396080075 386 907847763885 387 946849167364 388 987487617710 389 1029803820045 390 1073891932038 391 1119795774695 392 1167616833851 393 1217403248197 394 1269263340208 395 1323249941694 396 1379480030224 397 1438010142522 398 1498966260610 399 1562410827612 400 1628477948620 401 1697236123902 402 1768829990940 403 1843332975169 404 1920900884963 405 2001614483968 406 2085639558152 407 2173064744974 408 2264068675528 409 2358746225101 410 2457289787764 411 2559803943726 412 2666492826597 413 2777470999551 414 2892958759906 415 3013078655956 416 3138067709295 417 3268060436088 418 3403308481336 419 3543959506265 420 3690284492005 421 3842441279866 422 4000721264481 423 4165297872741 424 4336480354545 425 4514458114897 426 4699564558739 427 4892002240641 428 5092129265123 429 5300167963522 430 5516497874612 431 5741362441799 432 5975170103484 433 6218180554867 434 6470833144121 435 6733412577346 436 7006384352148 437 7290058836011 438 7584937289712 439 7891351751849 440 8209840384804 441 8540765967045 442 8884699288884 443 9242036001306 444 9613389835902 445 9999183352769 446 10400075932669 447 10816529232734 448 11249241684632 449 11698715710754 450 12165702777539 451 12650740035296 452 13154633541985 453 13677968661587 454 14221600324400 455 14786165215106 456 15372582275538 457 15981530766364 458 16613997237452 459 17270722269350 460 17952750689280 461 18660886333309 462 19396252680516 463 20159708378016 464 20952458383091 465 21775435711895 466 22629918776876 467 23516919590107 468 24437810782372 469 25393672920611 470 26385978565483 471 27415901636862 472 28485002992370 473 29594553344780 474 30746230124324 475 31941390458582 476 33181832317924 477 34469026433412 478 35804880803919 479 37190987278976 480 38629393544045 481 40121798186657 482 41670396983547 483 43277030295670 484 44944027169842 485 46673375221476 486 48467575546281 487 50328750214773 488 52259578407122 489 54262354569245 490 56339923801591 491 58494763563466 492 60729925297561 493 63048051748838 494 65452413909614 495 67945867281870 496 70531884304061 497 73213542500908 498 75994567699336 499 78878245064832 500 81868563880005 501 84969068446469 502 88183996943662 503 91517168281152 504 94973126120047 505 98555943090750 506 102270486369961 507 106121147284802 508 110113095621518 509 114251055858572 510 118540571678067 511 122986683315270 512 127595324364363 513 132371921275947 514 137322782073283 515 142453742625724 516 147771560406482 517 153282458303807 518 158993670969225 519 164911894689930 520 171044818481210 521 177399634469809 522 183984582188521 523 190807331716941 524 197876697948142 525 205200923891350 526 212789384416148 527 220650930122705 528 228795597919284 529 237232822666678 530 245973343740992 531 255027295277006 532 264406097269977 533 274120618941285 534 284183087345576 535 294605090706542 536 305399703596208 537 316579359940324 538 328157969589905 539 340148863270590 540 352566924450907 541 365426358741853 542 378743081282019 543 392532328688141 544 406811029238971 545 421595503538259 546 436903863946515 547 452753503661870 548 469163779924193 549 486153330271059 550 503742753342631 551 521952003633413 552 540803106218612 553 560317321572188 554 580518186626486 555 601428472587320 556 623073219650497 557 645476792712902 558 668665962030701 559 692666686172638 560 717507559417202 561 743216361280491 562 769823523126155 563 797358756455149 564 825854575435403 565 855342627027374 566 885857635284390 567 917433454540353 568 950107032716659 569 983914554155801 570 1018895490523418 571 1055088380196371 572 1092535358615950 573 1131277626667975 574 1171360022567966 575 1212826567526645 576 1255725136599038 577 1300102606360426 578 1346010072928093 579 1393497627319418 580 1442619637369100 581 1493429593218788 582 1545985532688996 583 1600344410771165 584 1656568141795143 585 1714717555176246 586 1774858529617968 587 1837056002505111 588 1901380266947811 589 1967900449460299 590 2036691523312241 591 2107827285930739 592 2181387502374156 593 2257450916729884 594 2336102610746779 595 2417426405503162 596 2501513007953927 597 2588451863387205 598 2678339472984449 599 2771271240921792 600 2867350064877614 601 2966677472725951 602 3069363142261637 603 3175515374926714 604 3285250830292523 605 3398684982518229 606 3515942180184556 607 3637145301809637 608 3762426840503443 609 3891917813305830 610 4025759139882925 611 4164090464796836 612 4307061941619851 613 4454822146297448 614 4607531015183164 615 4765346910542322 616 4928439911356495 617 5096978753067950 618 5271144601739730 619 5451116950156469 620 5637088712827445 621 5829251129802017 622 6027809327221226 623 6232967006405509 624 6444942583795782 625 6663952717300653 626 6890229911292772 627 7124004934723737 628 7365524965096784 629 7615035722828135 630 7872800324832397 631 8139080071748449 632 8414154971734942 633 8698303251189058 634 8991822533969612 635 9295008988462327 636 9608179323955885 637 9931648441857566 638 10265753281383418 639 10610829027149479 640 10967233761587249 641 11335324172011650 642 11715481188788304 643 12108083996913323 644 12513537732754617 645 12932245889065056 646 13364638936768083 647 13811146136428264 648 14272225289705791 649 14748332643480126 650 15239954959397814 651 15747577566295730 652 16271717589169755 653 16812891213265559 654 17371648207620153 655 17948537118788877 656 18544142323806022 657 19159047186295701 658 19793872408304971 659 20449238245944582 660 21125804420349951 661 21824229946831593 662 22545215882013447 663 23289462864858083 664 24057715383267084 665 24850718207673418 666 25669262376132441 667 26514139054080636 668 27386188631611865 669 28286252002276488 670 29215221448544277 671 30173990564873512 672 31163507196299566 673 32184720437404942 674 33238636959486312 675 34326265244151408 676 35448673920261300 677 36606934424282923 678 37802181595446770 679 39035553164016072 680 40308254136886360 681 41621493105237634 682 42976548980084392 683 44374705457942338 684 45817320333929082 685 47305756501749590 686 48841455303543544 687 50425864132255114 688 52060512460292422 689 53746937231007815 690 55486761833568554 691 57281617669179727 692 59133227632566745 693 61043323859541535 694 63013734167518977 695 65046297395468962 696 67142953130501489 697 69305652880012441 698 71536454576263000 699 73837429650256892 700 76210760998939496 701 78658647128937391 702 81183403813943383 703 83787363775364411 704 86472983525408394 705 89242738567491580 706 92099233998321337 707 95045096530285620 708 98083089247286871 709 101215998640624317 710 104446755006564322 711 107778314614109792 712 111213784467175639 713 114756300711638323 714 118409157886421470 715 122175682231708560 716 126059366909895166 717 130063740012552753 718 134192504575426787 719 138449402395946515 720 142838359233201583 721 147363342879340178 722 152028514784108528 723 156838082502015776 724 161796456674609158 725 166908098749730584 726 172177683502693265 727 177609940842998775 728 183209825198412062 729 188982351132310437 730 194932768671610347 731 201066393662904299 732 207388789432145847 733 213905590587621967 734 220622691857227971 735 227546065545533058 736 234681956945293378 737 242036695826936449 738 249616898648488886 739 257429273250166753 740 265480828888582068 741 273778673820012266 742 282330232640339682 743 291143037326772708 744 300224952105404018 745 309583957290915925 746 319228382109455253 747 329166681299679041 748 339407676082586505 749 349960323198508667 750 360833964189357701 751 372038086869991069 752 383582583251493567 753 395477503053642044 754 407733320414510748 755 420360679389246482 756 433370669756746481 757 446774564487537118 758 460584104354973979 759 474811227187614304 760 489468362528418931 761 504568151507618023 762 520123751469311106 763 536148547652670665 764 552656467078430675 765 569661681492715877 766 587178931965669848 767 605223221889483960 768 623810152586591699 769 642955607358874289 770 662676096822081367 771 682988433889416163 772 703910091140345556 773 725458864460738288 774 747653242243801249 775 770512060205259491 776 794054880662643168 777 818301637609668673 778 843273029162846335 779 868990150192617337 780 895474898163898091 781 922749596083478012 782 950837408775165620 783 979761955904064954 784 1009547742809174376 785 1040219759698424689 786 1071803926686454844 787 1104326683540015483 788 1137815445598387520 789 1172298182684673969 790 1207803891184859463 791 1244362157691910963 792 1282003647140418964 793 1320759656200568610 794 1360662612386086965 795 1401745616750474416 796 1444042960827307036 797 1487589652129725750 798 1532421948535246995 799 1578576873458758640 800 1626092762023973620 801 1675008764473394219 802 1725365411961699096 803 1777204101331689937 804 1830567680130673674 805 1885499920613479453 806 1942046116614284542 807 2000252545687217310 808 2060167087964607407 809 2121838666986710286 810 2185317889945921269 811 2250656477542838068 812 2317907916853879828 813 2387126878300834095 814 2458369892635360884 815 2531694744963006084 816 2607161175237848212 817 2684830260764637543 818 2764765129624658525 819 2847030329846012780 820 2931692570306725558 821 3018820063426439357 822 3108483292338213858 823 3200754342043238726 824 3295707679962218102 825 3393419473118949343 826 3493968398696629809 827 3597434932495325865 828 3703902188775302092 829 3813455196028311169 830 3926181751311568931 831 4042171681143800924 832 4161517729877729819 833 4284314787985379794 834 4410660812745589657 835 4540656044175747870 836 4674403940770960485 837 4812010379491977556 838 4953584629439850689 839 5099238515535798476 840 5249087429058254612 841 5403249477380006305 842 5561846510848867778 843 5725003255829683603 844 5892848383994429188 845 6065513604815996900 846 6243134775684541972 847 6425850980287032667 848 6613805656466691791 849 6807145655810140838 850 7006022419864319228 851 7210590994175142003 852 7421011250639970937 853 7637446886162606497 854 7860066664014724418 855 8089043393020880330 856 8324555223055561730 857 8566784572906497530 858 8815919477735809075 859 9072152500641486613 860 9335682101361890805 861 9606711525875638526 862 9885450236678880989 863 10172112744777798450 864 10466920098509117103 865 10770098697963720000 866 11081881807218845104 867 11402508345025570367 868 11732224466507750528 869 12071282288723650510 870 12419941539278499408 871 12778468262099474806 872 13147136492792342591 873 13526226937930635185 874 13916028728780309961 875 14316838028162555047 876 14728959859292863515 877 15152706690968593672 878 15588400296920612979 879 16036370311148202670 880 16496956176746244442 881 16970505618960930364 882 17457376679786512572 883 17957936167007441390 884 18472561722945113904 885 19001640240805893965 886 19545570034588069755 887 20104759163106944881 888 20679627697225958726 889 21270606016136817802 890 21878137115360774358 891 22502674865321501525 892 23144686434345916752 893 23804650443252516862 894 24483059498958427355 895 25180418318581519050 896 25897246308700247893 897 26634075647741186768 898 27391453996178672629 899 28169942461277106768 900 28970118433285900515 901 29792573515030381495 902 30637916412571549786 903 31506770816655068207 904 32399778441163923910 905 33317596773616796265 906 34260902256798638928 907 35230387999124376712 908 36226767018801328407 909 37250769899694351821 910 38303148205195953461 911 39384671985212109803 912 40496133352689397518 913 41638343945095546364 914 42812138574567568983 915 44018372627695162708 916 45257925906244846618 917 46531699861252572580 918 47840621619573153127 919 49185641164499298852 920 50567735448220261838 921 51987905502158021299 922 53447180767681904083 923 54946616019105873205 924 56487295904070073920 925 58070331807310566453 926 59696866491790462080 927 61368070882147048068 928 63085148951264338812 929 64849334295116445066 930 66661895259617970161 931 68524131445644678720 932 70437378952348746530 933 72403006791910429479 934 74422422412753154238 935 76497067879899836510 936 78628425668362908804 937 80818014765850149407 938 83067396603677596089 939 85378171054756729669 940 87751982680520259319 941 90190516468083566748 942 92695504386057681980 943 95268721030672875462 944 97911990339088858242 945 100627181120892970929 946 103416214128929628166 947 106281057298886763393 948 109223733167454795565 949 112246314009765657918 950 115350929445197007250 951 118539761440358221225 952 121815052317753903328 953 125179099436252586088 954 128634263594513598689 955 132182963594365565719 956 135827684856994965657 957 139570973839609605301 958 143415447108257069610 959 147363785392352801509 960 151418743102201949344 961 155583142253196942714 962 159859882233399469315 963 164251933559050306490 964 168762348152871095355 965 173394252703719202983 966 178150859448319341643 967 183035459380805523371 968 188051433319894704722 969 193202244932874501134 970 198491452382262385034 971 203922700906900190478 972 209499735032918977230 973 215226390990325402367 974 221106609256385668634 975 227144426761838629322 976 233343990080536252314 977 239709547152433474134 978 246245461111693885800 979 252956201821404443334 980 259846360079995206578 981 266920638926071621124 982 274183868575891178246 983 281640997190513658042 984 289297106525659743574 985 297157402496697812318 986 305227231265421882740 987 313512069546445308870 988 322017541506737285335 989 330749408488770943689 990 339713586716323883941 991 348916136784347597443 992 358363281862245645030 993 368061396904293095152 994 378017027767080607654 995 388236879777162019206 996 398727837744750085819 997 409496954283104696099 998 420551470394359261289 999 431898803475251477037 1000 443546568920648780086