0 0 1 0 2 0 3 0 4 1 5 0 6 0 7 0 8 0 9 1 10 1 11 1 12 1 13 1 14 1 15 2 16 2 17 3 18 3 19 4 20 4 21 5 22 6 23 7 24 8 25 10 26 11 27 13 28 15 29 17 30 20 31 23 32 26 33 30 34 35 35 39 36 45 37 51 38 58 39 66 40 75 41 84 42 96 43 108 44 122 45 137 46 155 47 173 48 195 49 219 50 245 51 274 52 307 53 342 54 383 55 427 56 475 57 529 58 589 59 654 60 727 61 807 62 894 63 991 64 1098 65 1214 66 1343 67 1485 68 1638 69 1809 70 1995 71 2198 72 2422 73 2667 74 2933 75 3226 76 3545 77 3893 78 4274 79 4691 80 5142 81 5637 82 6175 83 6760 84 7399 85 8095 86 8848 87 9671 88 10564 89 11533 90 12587 91 13732 92 14971 93 16319 94 17780 95 19361 96 21077 97 22936 98 24945 99 27125 100 29482 101 32029 102 34787 103 37768 104 40986 105 44466 106 48224 107 52278 108 56658 109 61384 110 66476 111 71972 112 77897 113 84277 114 91158 115 98567 116 106541 117 115130 118 124373 119 134313 120 145011 121 156513 122 168874 123 182165 124 196447 125 211782 126 228259 127 245949 128 264933 129 285313 130 307179 131 330626 132 355781 133 382749 134 411652 135 442633 136 475828 137 511378 138 549461 139 590237 140 633880 141 680599 142 730591 143 784064 144 841272 145 902445 146 967842 147 1037759 148 1112481 149 1192315 150 1277614 151 1368721 152 1466006 153 1569888 154 1680783 155 1799129 156 1925430 157 2060180 158 2203908 159 2357211 160 2520680 161 2694948 162 2880725 163 3078717 164 3289682 165 3514458 166 3753890 167 4008881 168 4280426 169 4569534 170 4877275 171 5204831 172 5553400 173 5924258 174 6318802 175 6738455 176 7184732 177 7659286 178 8163805 179 8700089 180 9270083 181 9875795 182 10519350 183 11203052 184 11929273 185 12700526 186 13519528 187 14389084 188 15312163 189 16291970 190 17331809 191 18435191 192 19605881 193 20847785 194 22165035 195 23562062 196 25043464 197 26614111 198 28279205 199 30044164 200 31914704 201 33896943 202 35997242 203 38222325 204 40579364 205 43075828 206 45719608 207 48519112 208 51483099 209 54620828 210 57942134 211 61457292 212 65177139 213 69113190 214 73277470 215 77682660 216 82342221 217 87270220 218 92481484 219 97991738 220 103817411 221 109975830 222 116485340 223 123365130 224 130635419 225 138317596 226 146434045 227 155008341 228 164065407 229 173631333 230 183733577 231 194401160 232 205664458 233 217555439 234 230107861 235 243357060 236 257340222 237 272096583 238 287667226 239 304095367 240 321426570 241 339708560 242 358991520 243 379328330 244 400774387 245 423387908 246 447230228 247 472365586 248 498861487 249 526789006 250 556222583 251 587240428 252 619924844 253 654362035 254 690642546 255 728861603 256 769118966 257 811519370 258 856172940 259 903195023 260 952706690 261 1004835194 262 1059713815 263 1117482411 264 1178287930 265 1242284252 266 1309632836 267 1380503243 268 1455073038 269 1533528470 270 1616065069 271 1702887579 272 1794210710 273 1890259790 274 1991270754 275 2097490933 276 2209179842 277 2326609156 278 2450063631 279 2579841941 280 2716256720 281 2859635588 282 3010322074 283 3168675721 284 3335073228 285 3509909452 286 3693597635 287 3886570617 288 4089282002 289 4302206434 290 4525840960 291 4760706342 292 5007347419 293 5266334630 294 5538265480 295 5823764992 296 6123487448 297 6438117981 298 6768373199 299 7115003086 300 7478792800 301 7860563461 302 8261174254 303 8681524453 304 9122554383 305 9585247750 306 10070633947 307 10579789183 308 11113839113 309 11673961401 310 12261387075 311 12877403494 312 13523357195 313 14200655529 314 14910769968 315 15655239279 316 16435671512 317 17253747646 318 18111225193 319 19009940511 320 19951812872 321 20938848555 322 21973143503 323 23056887922 324 24192370836 325 25381983201 326 26628223078 327 27933700717 328 29301142203 329 30733395234 330 32233434815 331 33804367533 332 35449437975 333 37172035171 334 38975697494 335 40864119859 336 42841160985 337 44910849016 338 47077389601 339 49345174049 340 51718785765 341 54203009367 342 56802839784 343 59523489693 344 62370399699 345 65349248556 346 68465961717 347 71726722715 348 75137984659 349 78706480008 350 82439233289 351 86343574085 352 90427148110 353 94697931535 354 99164245519 355 103834768846 356 108718554010 357 113825043502 358 119164084210 359 124745945444 360 130581337186 361 136681426538 362 143057857840 363 149722773234 364 156688831269 365 163969229475 366 171577727460 367 179528667985 368 187837002281 369 196518315956 370 205588852841 371 215065543435 372 224966033889 373 235308713060 374 246112744331 375 257398098133 376 269185582566 377 281496879015 378 294354578637 379 307782216952 380 321804313695 381 336446413811 382 351735126416 383 367698169495 384 384364415807 385 401763936826 386 419928052847 387 438889384367 388 458681901656 389 479340980831 390 500903461387 391 523407702118 392 546893643787 393 571402873645 394 596978688306 395 623666163895 396 651512228340 397 680565732039 398 710877526395 399 742500544708 400 775489881599 401 809902880929 402 845799226260 403 883241030147 404 922292932418 405 963022201379 406 1005498834141 407 1049795666440 408 1095988485889 409 1144156144539 410 1194380681618 411 1246747450255 412 1301345243654 413 1358266432323 414 1417607105707 415 1479467213616 416 1543950719637 417 1611165759341 418 1681224798826 419 1754244806035 420 1830347427512 421 1909659166045 422 1992311571905 423 2078441440342 424 2168191010427 425 2261708178519 426 2359146718924 427 2460666506277 428 2566433753904 429 2676621260090 430 2791408656820 431 2910982675832 432 3035537423392 433 3165274658458 434 3300404089440 435 3441143680766 436 3587719963839 437 3740368367912 438 3899333562139 439 4064869802877 440 4237241302622 441 4416722611507 442 4603599005061 443 4798166895510 444 5000734257062 445 5211621058699 446 5431159722652 447 5659695598277 448 5897587445073 449 6145207943404 450 6402944222497 451 6671198399293 452 6950388147221 453 7240947284393 454 7543326374413 455 7857993359660 456 8185434216453 457 8526153624571 458 8880675672378 459 9249544586121 460 9633325475942 461 10032605120728 462 10447992779719 463 10880121023533 464 11329646607382 465 11797251374101 466 12283643179621 467 12789556864150 468 13315755256814 469 13863030205727 470 14432203658020 471 15024128777161 472 15639691089103 473 16279809683090 474 16945438453843 475 17637567376505 476 18357223841451 477 19105474034821 478 19883424356459 479 20692222903060 480 21533061002207 481 22407174788824 482 23315846852709 483 24260407942771 484 25242238719035 485 26262771582367 486 27323492567365 487 28425943288782 488 29571722973245 489 30762490560884 490 31999966867255 491 33285936838771 492 34622251885437 493 36010832281555 494 37453669668671 495 38952829644248 496 40510454426823 497 42128765632810 498 43810067148659 499 45556748088462 500 47371285873990 501 49256249420539 502 51214302418130 503 53248206747161 504 55360826011071 505 57555129175671 506 59834194356040 507 62201212732726 508 64659492587337 509 67212463499744 510 69863680688522 511 72616829484726 512 75475729982682 513 78444341849535 514 81526769283261 515 84727266164905 516 88050241386663 517 91500264345005 518 95082070647193 519 98800568012110 520 102660842354769 521 106668164105266 522 110827994742217 523 115145993530782 524 119628024517798 525 124280163764057 526 129108706804132 527 134120176388113 528 139321330485729 529 144719170542927 530 150320950048008 531 156134183387878 532 162166654984073 533 168426428769064 534 174921857982680 535 181661595278960 536 188654603206837 537 195910165043948 538 203437895974865 539 211247754679636 540 219350055312162 541 227755479860401 542 236475090956792 543 245520345119255 544 254903106414700 545 264635660617112 546 274730729840844 547 285201487641209 548 296061574658540 549 307325114786206 550 319006731855591 551 331121566918225 552 343685296105271 553 356714149059011 554 370224928019904 555 384235027550215 556 398762454890082 557 413825851033200 558 429444512504423 559 445638413835885 560 462428230833413 561 479835364616719 562 497881966430488 563 516590963323843 564 535986084681862 565 556091889608242 566 576933795261783 567 598538106130891 568 620932044247707 569 644143780449349 570 668202466672058 571 693138269282181 572 718982403556374 573 745767169299402 574 773525987604871 575 802293438877925 576 832105302110161 577 862998595414099 578 895011617943456 579 928183993191055 580 962556713674800 581 998172187145244 582 1035074284308235 583 1073308388077149 584 1112921444495013 585 1153962015323125 586 1196480332314460 587 1240528353319459 588 1286159820224742 589 1333430318746464 590 1382397340234623 591 1433120345492907 592 1485660830639221 593 1540082395173473 594 1596450812260381 595 1654834101257816 596 1715302602667302 597 1777929055518175 598 1842788677222342 599 1909959246086073 600 1979521186495728 601 2051557656820822 602 2126154640231191 603 2203401038451989 604 2283388768505771 605 2366212862651045 606 2451971571547617 607 2540766470704610 608 2632702570434602 609 2727888429350523 610 2826436271469834 611 2928462107163775 612 3034085857995328 613 3143431485520632 614 3256627124305824 615 3373805219212292 616 3495102667035319 617 3620660962763534 618 3750626350522920 619 3885149979300724 620 4024388063734493 621 4168502050041238 622 4317658787193323 623 4472030703646247 624 4631795989704537 625 4797138785646179 626 4968249375931479 627 5145324389594848 628 5328567006955912 629 5518187172996911 630 5714401817519941 631 5917435082237210 632 6127518555163758 633 6344891512443767 634 6569801167780530 635 6802502929865525 636 7043260667956052 637 7292346985790030 638 7550043504262304 639 7816641153030594 640 8092440471261905 641 8377751917973742 642 8672896192159014 643 8978204562930422 644 9294019210169797 645 9620693575895776 646 9958592726611935 647 10308093727154513 648 10669586026280767 649 11043471854287535 650 11430166633217271 651 11830099399921852 652 12243713242303928 653 12671465749334919 654 13113829475150883 655 13571292417580593 656 14044358511749397 657 14533548139093737 658 15039398652179551 659 15562464916014590 660 16103319866228358 661 16662555084554335 662 17240781392354721 663 17838629462604833 664 18456750450815631 665 19095816645690715 666 19756522139981573 667 20439583522067148 668 21145740589116028 669 21875757082344179 670 22630421444948563 671 23410547603640643 672 24216975774346629 673 25050573292714925 674 25912235470424317 675 26802886477920778 676 27723480254287855 677 28675001445319342 678 29658466370489969 679 30674924019597576 680 31725457080229258 681 32811182996819829 682 33933255062151168 683 35092863542536343 684 36291236837534759 685 37529642675130763 686 38809389343717562 687 40131826961817636 688 41498348786564681 689 42910392562393222 690 44369441910962148 691 45877027763436728 692 47434729836688460 693 49044178154543505 694 50707054615311371 695 52425094607277645 696 54200088673404803 697 56033884226588923 698 57928387317292551 699 59885564454919044 700 61907444484405439 701 63996120520000480 702 66153751937725421 703 68382566428136634 704 70684862111513296 705 73063009717114459 706 75519454828277852 707 78056720195653271 708 80677408120376223 709 83384202909118717 710 86179873403496868 711 89067275585814878 712 92049355263261873 713 95129150833244582 714 98309796132023114 715 101594523368964184 716 104986666149313824 717 108489662587861199 718 112107058516024493 719 115842510785496190 720 119699790671044660 721 123682787375237067 722 127795511638476156 723 132042099457194111 724 136426815913221265 725 140954059118001321 726 145628364274763066 727 150454407861941005 728 155437011941820672 729 160581148597806534 730 165891944503906495 731 171374685630736797 732 177034822091758480 733 182877973133668624 734 188909932275603590 735 195136672601208866 736 201564352207855271 737 208199319818041460 738 215048120557412638 739 222117501904060014 740 229414419814559078 741 236946045031582792 742 244719769578172432 743 252743213444578900 744 261024231472949591 745 269570920445401200 746 278391626381882304 747 287494952053577982 748 296889764717895554 749 306585204081964852 750 316590690500927198 751 326915933417591786 752 337570940050967157 753 348566024340510216 754 359911816153255172 755 371619270761955592 756 383699678601697536 757 396164675312779986 758 409026252078675078 759 422296766267192152 760 435988952383333145 761 450115933343386226 762 464691232079104900 763 479728783481212098 764 495242946692569400 765 511248517760646994 766 527760742659348482 767 544795330691389824 768 562368468281725763 769 580496833172958902 770 599197609034865120 771 618488500499457812 772 638387748633481750 773 658914146861484742 774 680087057351894516 775 701926427879032440 776 724452809175308891 777 747687372787118278 778 771651929448496014 779 796368947987967164 780 821861574783291806 781 848153653779393408 782 875269747086183500 783 903235156172277016 784 932075943671208837 785 961818955818259042 786 992491845535277109 787 1024123096181551725 788 1056742045990345192 789 1090378913209993457 790 1125064821969179067 791 1160831828887630798 792 1197712950452788850 793 1235742191183736545 794 1274954572605419251 795 1315386163055468972 796 1357074108346768831 797 1400056663310691369 798 1444373224245259780 799 1490064362293349901 800 1537171857777942056 801 1585738735520762260 802 1635809301171579444 803 1687429178577416654 804 1740645348220277172 805 1795506186752984686 806 1852061507664827306 807 1910362603108056396 808 1970462286917368161 809 2032414938856686353 810 2096276550126955498 811 2162104770169809237 812 2229958954804276575 813 2299900215733117502 814 2371991471456612079 815 2446297499634049103 816 2522884990932623915 817 2601822604404774450 818 2683181024437539903 819 2767033019317024443 820 2853453501452469754 821 2942519589307129907 822 3034310671082682943 823 3128908470205446544 824 3226397112665492144 825 3326863196259350184 826 3430395861788644702 827 3537086866269971756 828 3647030658211000716 829 3760324455009539132 830 3877068322535444648 831 3997365256954999870 832 4121321268859254439 833 4249045469761162195 834 4380650161026142812 835 4516250925302731521 836 4655966720523489109 837 4799919976546226060 838 4948236694507788741 839 5101046548966354779 840 5258482992908165109 841 5420683365696978764 842 5587789004048441147 843 5759945356111650077 844 5937302098742731798 845 6120013258059373715 846 6308237333365470273 847 6502137424537752292 848 6701881362970652460 849 6907641846175990992 850 7119596576136989746 851 7337928401520761434 852 7562825463853889636 853 7794481347768869078 854 8033095235434080004 855 8278872065280602262 856 8532022695142566136 857 8792764069932929598 858 9061319393977384312 859 9337918308132733752 860 9622797071821597204 861 9916198750116296336 862 10218373406008693788 863 10529578298008606492 864 10850078083214620820 865 11180145026005352664 866 11520059212505406398 867 11870108770981715516 868 12230590098330493146 869 12601808092821606794 870 12984076393268876724 871 13377717624799689016 872 13783063651404304444 873 14200455835447213606 874 14630245304328144732 875 15072793224487764628 876 15528471082955383302 877 15997660976641624434 878 16480755909586936860 879 16978160098379412162 880 17490289285961463079 881 18017571064053333381 882 18560445204424352130 883 19119363999249410567 884 19694792610797085035 885 20287209430699169014 886 20897106449058443435 887 21524989633661031185 888 22171379319563456911 889 22836810609332130312 890 23521833784223112559 891 24227014726594263651 892 24952935353850041994 893 25700194064230040871 894 26469406194757080399 895 27261204491669479666 896 28076239593673656742 897 28915180528358481326 898 29778715222122295036 899 30667551023975789846 900 31582415243589814298 901 32524055703967393932 902 33493241309132337618 903 34490762627233338680 904 35517432489473469189 905 36574086605288932337 906 37661584194208178332 907 38780808634834313899 908 39932668131408651573 909 41118096398421238380 910 42338053363746941217 911 43593525890801588889 912 44885528520221484677 913 46215104231583328200 914 47583325225698577187 915 48991293728025997545 916 50440142813760925266 917 51931037255177906725 918 53465174391814085205 919 55043785024096596352 920 56668134331036628370 921 58339522812624555800 922 60059287257577660924 923 61828801737112694620 924 63649478625428410114 925 65522769647601625472 926 67450166955622538336 927 69433204233309124372 928 71473457830860294465 929 73572547929831177278 930 75732139739329343535 931 77953944724252147893 932 80239721866410696346 933 82591278959402851183 934 85010473938120666407 935 87499216243804753276 936 90059468225576539632 937 92693246579404115983 938 95402623825486377421 939 98189729825060309152 940 101056753337662889175 941 104005943619910133997 942 107039612066877765436 943 110160133897196647527 944 113369949883009368618 945 116671568125958270798 946 120067565880406086318 947 123560591425125903654 948 127153365984723251416 949 130848685702086284364 950 134649423663198145142 951 138558531975673933926 952 142579043902420435083 953 146714076051857555610 954 150966830626171251002 955 155340597729106159956 956 159838757734849875024 957 164464783719594259868 958 169222243957400608608 959 174114804482042248792 960 179146231716534563513 961 184320395172106937080 962 189641270218421269418 963 195112940926881198878 964 200739602988924071374 965 206525566711241430702 966 212475260089916649366 967 218593231965519844902 968 224884155261257828955 969 231352830306323279298 970 238004188246642768256 971 244843294545285016762 972 251875352574841069994 973 259105707304147750160 974 266539849081791901778 975 274183417518887474418 976 282042205473681664569 977 290122163140617250840 978 298429402246537321142 979 306970200356787607040 980 315751005294047674866 981 324778439672786154756 982 334059305552309412826 983 343600589211454609318 984 353409466048047244155 985 363493305606323131792 986 373859676735602174274 987 384516352883576093980 988 395471317527658169308 989 406732769747936749176 990 418309129945355201730 991 430209045708833306550 992 442441397835145607177 993 455015306505459676992 994 467940137622536544524 995 481225509312703323676 996 494881298596802568392 997 508917648234429625772 998 523344973745884892218 999 538173970616369908920 1000 553415621687071024373