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