0 1 1 2 2 5 3 11 4 23 5 43 6 74 7 124 8 197 9 296 10 434 11 627 12 875 13 1188 14 1600 15 2128 16 2755 17 3522 18 4511 19 5661 20 6983 21 8637 22 10610 23 12781 24 15343 25 18497 26 21937 27 25751 28 30416 29 35702 30 41266 31 47772 32 55531 33 63578 34 72405 35 83101 36 94662 37 106544 38 120507 39 136663 40 152742 41 170490 42 191873 43 213877 44 236363 45 263126 46 292952 47 321797 48 354244 49 392890 50 430779 51 469933 52 517136 53 567365 54 615314 55 670669 56 735163 57 795773 58 859980 59 937959 60 1016672 61 1092097 62 1181661 63 1282415 64 1374180 65 1474882 66 1596818 67 1713269 68 1827278 69 1966078 70 2114862 71 2248300 72 2400902 73 2582499 74 2747111 75 2914518 76 3121615 77 3330931 78 3519564 79 3744351 80 4002986 81 4227852 82 4468270 83 4766567 84 5049133 85 5310710 86 5633614 87 5987000 88 6287001 89 6626114 90 7041358 91 7410163 92 7768148 93 8220974 94 8685651 95 9080131 96 9551055 97 10109706 98 10579173 99 11064456 100 11684052 101 12274452 102 12789314 103 13433565 104 14159844 105 14748179 106 15400812 107 16226744 108 16955653 109 17625698 110 18493149 111 19406270 112 20138514 113 21009437 114 22079932 115 22960743 116 23832152 117 24979193 118 26091927 119 27003430 120 28155760 121 29502343 122 30553333 123 31685958 124 33171193 125 34490766 126 35630906 127 37139553 128 38782004 129 40032204 130 41501422 131 43378807 132 44910978 133 46346518 134 48294885 135 50238792 136 51733886 137 53632021 138 55942003 139 57698739 140 59516392 141 61989522 142 64227836 143 66035408 144 68471312 145 71231881 146 73241780 147 75550040 148 78623776 149 81143838 150 83357688 151 86451931 152 89653770 153 91972084 154 94902527 155 98629311 156 101425865 157 104168849 158 108043194 159 111652510 160 114368491 161 118075278 162 122469447 163 125561652 164 128987056 165 133748178 166 137718094 167 140960278 168 145614167 169 150642814 170 154090976 171 158382935 172 164101027 173 168391568 174 172330977 175 178104314 176 183690768 177 187607957 178 192980458 179 199666435 180 204271134 181 209121426 182 216164539 183 222205366 184 226763913 185 233453939 186 241043229 187 246016875 188 252032269 189 260443061 190 266837556 191 272271504 192 280520004 193 288873772 194 294352179 195 301824996 196 311615179 197 318305703 198 324908774 199 334928071 200 343856708 201 350064856 202 359318360 203 370385741 204 377401811 205 385521569 206 397452908 207 406759127 208 414011400 209 425377905 210 437500805 211 444992761 212 455024309 213 468889617 214 478427464 215 487122134 216 500900533 217 513767600 218 522018803 219 534396943 220 550054963 221 559795587 222 570403871 223 586801430 224 600072227 225 609496388 226 624672556 227 641800678 228 651887847 229 664940453 230 684005910 231 697393945 232 708523953 233 726914622 234 745040439 235 755814849 236 771890210 237 793449450 238 806816929 239 820285780 240 842195419 241 860777431 242 872770906 243 892472680 244 916090753 245 929535982 246 946052652 247 971583648 248 990125040 249 1004039580 250 1027939795 251 1052943721 252 1066850443 253 1087179010 254 1116141031 255 1134323671 256 1151000295 257 1179542017 258 1205121275 259 1220153075 260 1245090227 261 1276933778 262 1294749120 263 1315129208 264 1348507429 265 1373867724 266 1390932194 267 1421250487 268 1455068754 269 1472906481 270 1497995648 271 1536033073 272 1560580697 273 1580781168 274 1617114295 275 1651755248 276 1670410805 277 1701251111 278 1743294503 279 1766823464 280 1791401215 281 1834088992 282 1868357336 283 1888979026 284 1926596024 285 1971485011 286 1994321830 287 2024597064 288 2073519875 289 2106424017 290 2130439143 291 2175718327 292 2221890925 293 2244939049 294 2282267041 295 2336696984 296 2367707890 297 2396738333 298 2450231664 299 2495974276 300 2520649131 301 2566371519 302 2624893790 303 2654166980 304 2689939223 305 2751648645 306 2795421277 307 2823539566 308 2878863353 309 2939451136 310 2967936914 311 3012208754 312 3081382132 313 3122169617 314 3155826151 315 3221598364 316 3281896716 317 3311282167 318 3365790801 319 3440780848 320 3478414793 321 3519853423 322 3596282980 323 3654028869 324 3686581350 325 3752935060 326 3831219451 327 3866583212 328 3918081421 329 4004465910 330 4057955489 331 4096345076 332 4175782164 333 4254250548 334 4289267438 335 4353061527 336 4447570765 337 4496106038 338 4543225334 339 4636268339 340 4711743700 341 4749177592 342 4827370617 343 4926989731 344 4971209586 345 5030002551 346 5136100463 347 5205947207 348 5249151235 349 5343479017 350 5444255587 351 5486222966 352 5559561539 353 5676784163 354 5739510624 355 5792175781 356 5903602076 357 6001248699 358 6044237187 359 6134834528 360 6259716334 361 6315469849 362 6381381877 363 6509640201 364 6600310991 365 6648458812 366 6758664456 367 6886367854 368 6937172720 369 7020016891 370 7163196878 371 7244284518 372 7302243107 373 7433608586 374 7558554308 375 7608146512 376 7711395919 377 7865666035 378 7936502958 379 8009103440 380 8161811477 381 8278642812 382 8332023189 383 8458774110 384 8618422511 385 8680718853 386 8772682922 387 8945001542 388 9049619399 389 9112567443 390 9265117889 391 9423137894 392 9480949922 393 9596708969 394 9784573311 395 9875088561 396 9953710326 397 10132885338 398 10282107223 399 10341325473 400 10484884653 401 10681781368 402 10759207912 403 10859528189 404 11063975156 405 11198383773 406 11266076400 407 11440646878 408 11638080475 409 11706527583 410 11834195216 411 12059801568 412 12175795738 413 12259591363 414 12466856821 415 12655568744 416 12721757525 417 12881893906 418 13121484712 419 13218889540 420 13326420993 421 13565654063 422 13737257751 423 13809671695 424 14006584309 425 14250202257 426 14332767905 427 14471227268 428 14738509051 429 14887125300 430 14975168784 431 15211631319 432 15447720553 433 15522804225 434 15698703795 435 15986406425 436 16110065767 437 16223318230 438 16499514023 439 16716862593 440 16794416351 441 17013378687 442 17310203663 443 17411730482 444 17559316443 445 17871818976 446 18061642814 447 18153087431 448 18419213822 449 18711214263 450 18798221063 451 18988407259 452 19329415702 453 19487230351 454 19604456095 455 19919155071 456 20191883483 457 20275722143 458 20515724204 459 20872817642 460 20999796980 461 21154304720 462 21514998646 463 21756100840 464 21850405338 465 22145899857 466 22502790034 467 22606205652 468 22808476791 469 23207548158 470 23409199121 471 23528542418 472 23882494044 473 24221186233 474 24313535160 475 24572745041 476 24996969889 477 25157811382 478 25316558654 479 25727648897 480 26031554453 481 26128783819 482 26452469267 483 26883410931 484 27009557913 485 27220955421 486 27682184193 487 27939231858 488 28058949669 489 28451964494 490 28867934403 491 28972513955 492 29248185162 493 29745942541 494 29951210105 495 30111164394 496 30573899551 497 30953473000 498 31054677000 499 31404379255 500 31918411728 501 32075823235 502 32292652567 503 32819234320 504 33145143331 505 33263908539 506 33694718407 507 34199713071 508 34322197646 509 34610602591 510 35187548829 511 35450138030 512 35608124734 513 36122610143 514 36591846333 515 36699520174 516 37071952949 517 37677665724 518 37877418466 519 38095344775 520 38689335468 521 39099402973 522 39216701903 523 39682826389 524 40288660361 525 40437162058 526 40733565180 527 41394321715 528 41729553625 529 41882556411 530 42447578867 531 43021288357 532 43139909729 533 43530570473 534 44235758462 535 44491747844 536 44705976804 537 45368059960 538 45879228744 539 45995857161 540 46493476680 541 47211611830 542 47397156579 543 47695850057 544 48443711786 545 48869325762 546 49014887099 547 49627757209 548 50321148314 549 50457768848 550 50860866035 551 51672168205 552 52001306033 553 52206862318 554 52936131394 555 53566680682 556 53685335648 557 54209169520 558 55050270358 559 55287214377 560 55581649978 561 56418293405 562 56954318669 563 57091052497 564 57747462687 565 58575637831 566 58740496666 567 59148929851 568 60071461773 569 60493764292 570 60685885938 571 61479643847 572 62248753956 573 62374714650 574 62917909947 575 63891394970 576 64197746063 577 64480782138 578 65405984580 579 66074466308 580 66202691663 581 66896584767 582 67873976710 583 68081095954 584 68486513269 585 69523508195 586 70062044913 587 70236704799 588 71090287604 589 72017475893 590 72159352627 591 72713406652 592 73826995337 593 74224625132 594 74488894460 595 75500280473 596 76324845630 597 76447338558 598 77170782465 599 78310565716 600 78578270129 601 78971238870 602 80123703434 603 80804388435 604 80958947750 605 81865577541 606 82970021829 607 83140531208 608 83695277223 609 84954538130 610 85469256138 611 85707671496 612 86800491733 613 87805755611 614 87928605272 615 88671678307 616 89985188900 617 90336490720 618 90706817028 619 91973203381 620 92824411201 621 92958413045 622 93909071844 623 95208861660 624 95425570040 625 95969259238 626 97377173485 627 98038624648 628 98245039969 629 99411983245 630 100622804866 631 100756345757 632 101507060044 633 103003228671 634 103466054105 635 103803260407 636 105179172126 637 106231155490 638 106347262887 639 107330574592 640 108841941243 641 109127908208 642 109647426554 643 111203981105 644 112045337498 645 112215371851 646 113446414443 647 114887015513 648 115046793222 649 115791087112 650 117475892921 651 118083127413 652 118377094079 653 119855043176 654 121139145959 655 121244208414 656 122246326262 657 123982901975 658 124367145511 659 124848412538 660 126550227471 661 127607658948 662 127739683524 663 129021974807 664 130714961497 665 130922662471 666 131644504818 667 133520457118 668 134309776380 669 134551564290 670 136120780325 671 137668464711 672 137774672020 673 138779203801 674 140751318344 675 141269063919 676 141697632729 677 143537631929 678 144849542057 679 144945830962 680 146263599134 681 148228958483 682 148513209817 683 149194867675 684 151260528835 685 152273974950 686 152456845619 687 154103132396 688 155944848516 689 156070918655 690 157058931580 691 159272950153 692 159965640302 693 160327501877 694 162294646016 695 163900660377 696 163968698033 697 165303154913 698 167557309137 699 167954245746 700 168576770234 701 170826333508 702 172109609538 703 172230242255 704 173935881622 705 176099819085 706 176272147415 707 177222296793 708 179680013279 709 180595045977 710 180877646654 711 182956741411 712 184896458739 713 184950361093 714 186279629953 715 188834574202 716 189388116489 717 189932079399 718 192355009711 719 193956487451 720 194016382832 721 195760074679 722 198270871981 723 198524530742 724 199413375101 725 202111466876 726 203301629587 727 203495114409 728 205666690326 729 207978241384 730 208040211474 731 209339345398 732 212201849715 733 212963676623 734 213410158520 735 215990910630 736 217960348356 737 217967409217 738 219724217786 739 222601744321 740 222981193443 741 223783769864 742 226713322792 743 228235886174 744 228334577572 745 230574827815 746 233293302307 747 233395034449 748 234636175074 749 237807071671 750 238836248589 751 239168085206 752 241885914276 753 244272888983 754 244243146216 755 245984446233 756 249242739447 757 249802143519 758 250492857813 759 253638975555 760 255554428807 761 255558529671 762 257839294374 763 260995112442 764 261179030837 765 262331771611 766 265805339950 767 267167572686 768 267370862633 769 270199733662 770 273051829320 771 273011220943 772 274704724035 773 278351044524 774 279154199055 775 279708021200 776 283049539805 777 285419976092 778 285337470871 779 287626244453 780 291243597636 781 291563763109 782 292595809074 783 296359257093 784 298125744620 785 298191624880 786 301100206320 787 304461039552 788 304447124782 789 306057067915 790 310091063629 791 311210903582 792 311604870327 793 315114185858 794 318001357791 795 317850080316 796 320110006230 797 324205517923 798 324728027484 799 325606241645 800 329639288154 801 331885147405 802 331811834002 803 334763550045 804 338670736563 805 338734213290 806 340221777484 807 344634785403 808 346152427704 809 346367459493 810 350010474611 811 353473555085 812 353283340963 813 355473252301 814 360054859650 815 360857714126 816 361549552347 817 365824138172 818 368626399838 819 368421464488 820 371374578707 821 375857772004 822 376063624503 823 377387677154 824 382162168608 825 384165468974 826 384188492185 827 387924679758 828 392017810625 829 391832586992 830 393907217207 831 398973208159 832 400145676545 833 400620979919 834 405101129910 835 408536337872 836 408219172798 837 411126862464 838 416206046800 839 416634097144 840 417752381564 841 422861536947 842 425443149985 843 425269517181 844 429052069732 845 433821832185 846 433701476442 847 435611931390 848 441150153013 849 442791581581 850 443024737178 851 447666567683 852 451808037759 853 451412428517 854 454222864585 855 459907000092 856 460651737782 857 461522566968 858 466929990772 859 470184922999 860 469821113094 861 473597132818 862 479080102652 863 479101877700 864 480796466616 865 486783726855 866 489001754523 867 488974219053 868 493726084579 869 498640906077 870 498217557438 871 500874135611 872 507160057571 873 508329824062 874 508914209238 875 514573832585 876 518596510833 877 518063054075 878 521773736181 879 527994324651 880 528253642853 881 529679202550 882 536080856291 883 538989034954 884 538692196841 885 543494957385 886 549240874079 887 548859688702 888 551301543122 889 558173080642 890 559888606479 891 560152802980 892 566008977337 893 570889908347 894 570224444026 895 573805229029 896 580773999000 897 581384278544 898 582488115173 899 589257814225 900 592972645889 901 592410998563 902 597198356153 903 603820728779 904 603572600359 905 605735521240 906 613162852440 907 615555093258 908 615473571254 909 621461329727 910 627283460546 911 626543762129 912 629924597403 913 637636985601 914 638728642909 915 639461038558 916 646540683473 917 651178090144 918 650372672543 919 655071504327 920 662600599678 921 662598446211 922 664416339910 923 672355593458 924 675562845054 925 675121659424 926 681167124203 927 688002046215 928 687268790418 929 690374681156 930 698810025914 931 700528684371 932 700845888623 933 708165821387 934 713837110379 935 712829122721 936 717359750009 937 725808616489 938 726187345026 939 727594402868 940 735987477042 941 740151800546 942 739352310406 943 745373204512 944 753277413028 945 752656420676 946 755408417395 947 764529283940 948 767033172248 949 766900870301 950 774380287804 951 781187749926 952 780042160841 953 784318656163 954 793681610106 955 794596939190 956 795530538990 957 804305137164 958 809568136743 959 808431022052 960 814337202544 961 823348703603 962 822972325029 963 825289113681 964 835040917751 965 838497425306 966 837894670958 967 845442213357 968 853474537485 969 852283418503 970 856214195443 971 866465735954 972 868092036783 973 868496238811 974 877566177871 975 884064184886 976 882633680096 977 888327590652 978 898463194545 979 898490469335 980 900290753802 981 910601669512 982 915183070281 983 914106633146 984 921621100758 985 930948823766 986 929834121746 987 933322982255 988 944417096653 989 946944276440 990 946773861754 991 956039659104 992 963898451791 993 962246624725 994 967623681698 995 978877162917 996 979492525910 997 980698317323 998 991479442619 999 997357858498 1000 995826901943