0 0 1 0 2 3 3 13 4 37 5 84 6 164 7 291 8 480 9 748 10 1115 11 1602 12 2233 13 3034 14 4033 15 5260 16 6747 17 8529 18 10642 19 13125 20 16019 21 19366 22 23212 23 27604 24 32591 25 38225 26 44559 27 51649 28 59553 29 68331 30 78045 31 88759 32 100540 33 113456 34 127578 35 142979 36 159733 37 177918 38 197613 39 218899 40 241860 41 266581 42 293150 43 321657 44 352194 45 384855 46 419736 47 456936 48 496555 49 538696 50 583464 51 630965 52 681309 53 734607 54 790972 55 850520 56 913368 57 979636 58 1049446 59 1122922 60 1200190 61 1281378 62 1366617 63 1456039 64 1549779 65 1647974 66 1750762 67 1858285 68 1970686 69 2088110 70 2210705 71 2338620 72 2472007 73 2611020 74 2755815 75 2906550 76 3063385 77 3226483 78 3396008 79 3572127 80 3755009 81 3944824 82 4141746 83 4345950 84 4557613 85 4776915 86 5004037 87 5239163 88 5482479 89 5734173 90 5994435 91 6263457 92 6541434 93 6828562 94 7125040 95 7431069 96 7746851 97 8072592 98 8408499 99 8754781 100 9111650 101 9479319 102 9858004 103 10247923 104 10649296 105 11062345 106 11487294 107 11924370 108 12373801 109 12835818 110 13310654 111 13798543 112 14299723 113 14814433 114 15342914 115 15885410 116 16442166 117 17013430 118 17599452 119 18200484 120 18816780 121 19448596 122 20096191 123 20759825 124 21439761 125 22136264 126 22849600 127 23580039 128 24327852 129 25093312 130 25876695 131 26678278 132 27498341 133 28337166 134 29195037 135 30072240 136 30969063 137 31885797 138 32822734 139 33780169 140 34758399 141 35757722 142 36778440 143 37820856 144 38885275 145 39972005 146 41081355 147 42213637 148 43369165 149 44548255 150 45751225 151 46978395 152 48230088 153 49506628 154 50808342 155 52135559 156 53488609 157 54867826 158 56273545 159 57706103 160 59165840 161 60653097 162 62168218 163 63711549 164 65283438 165 66884235 166 68514292 167 70173964 168 71863607 169 73583580 170 75334244 171 77115961 172 78929097 173 80774019 174 82651096 175 84560700 176 86503204 177 88478984 178 90488418 179 92531886 180 94609770 181 96722454 182 98870325 183 101053771 184 103273183 185 105528954 186 107821478 187 110151153 188 112518378 189 114923554 190 117367085 191 119849376 192 122370835 193 124931872 194 127532899 195 130174330 196 132856581 197 135580071 198 138345220 199 141152451 200 144002189 201 146894860 202 149830894 203 152810722 204 155834777 205 158903495 206 162017313 207 165176671 208 168382011 209 171633777 210 174932415 211 178278373 212 181672102 213 185114054 214 188604684 215 192144449 216 195733807 217 199373220 218 203063151 219 206804065 220 210596430 221 214440715 222 218337392 223 222286935 224 226289820 225 230346525 226 234457530 227 238623318 228 242844373 229 247121182 230 251454234 231 255844019 232 260291031 233 264795765 234 269358718 235 273980390 236 278661282 237 283401898 238 288202744 239 293064328 240 297987160 241 302971752 242 308018619 243 313128277 244 318301245 245 323538044 246 328839196 247 334205227 248 339636664 249 345134036 250 350697875 251 356328714 252 362027089 253 367793538 254 373628601 255 379532820 256 385506739 257 391550905 258 397665866 259 403852173 260 410110379 261 416441038 262 422844708 263 429321948 264 435873319 265 442499385 266 449200711 267 455977865 268 462831417 269 469761939 270 476770005 271 483856191 272 491021076 273 498265240 274 505589266 275 512993739 276 520479245 277 528046374 278 535695717 279 543427867 280 551243420 281 559142973 282 567127126 283 575196481 284 583351642 285 591593215 286 599921808 287 608338032 288 616842499 289 625435824 290 634118624 291 642891517 292 651755125 293 660710071 294 669756980 295 678896480 296 688129200 297 697455772 298 706876830 299 716393010 300 726004950 301 735713290 302 745518673 303 755421743 304 765423147 305 775523534 306 785723554 307 796023861 308 806425110 309 816927958 310 827533065 311 838241092 312 849052703 313 859968564 314 870989343 315 882115710 316 893348337 317 904687899 318 916135072 319 927690535 320 939354969 321 951129056 322 963013482 323 975008934 324 987116101 325 999335675 326 1011668349 327 1024114819 328 1036675783 329 1049351941 330 1062143995 331 1075052649 332 1088078610 333 1101222586 334 1114485288 335 1127867429 336 1141369723 337 1154992888 338 1168737643 339 1182604709 340 1196594810 341 1210708671 342 1224947020 343 1239310587 344 1253800104 345 1268416305 346 1283159926 347 1298031706 348 1313032385 349 1328162706 350 1343423414 351 1358815255 352 1374338979 353 1389995337 354 1405785082 355 1421708970 356 1437767758 357 1453962206 358 1470293076 359 1486761132 360 1503367140 361 1520111868 362 1536996087 363 1554020569 364 1571186089 365 1588493424 366 1605943352 367 1623536655 368 1641274116 369 1659156520 370 1677184655 371 1695359310 372 1713681277 373 1732151350 374 1750770325 375 1769539000 376 1788458175 377 1807528653 378 1826751238 379 1846126737 380 1865655959 381 1885339714 382 1905178816 383 1925174080 384 1945326323 385 1965636365 386 1986105027 387 2006733133 388 2027521509 389 2048470983 390 2069582385 391 2090856547 392 2112294304 393 2133896492 394 2155663950 395 2177597519 396 2199698041 397 2221966362 398 2244403329 399 2267009791 400 2289786600 401 2312734609 402 2335854674 403 2359147653 404 2382614406 405 2406255795 406 2430072684 407 2454065940 408 2478236431 409 2502585028 410 2527112604 411 2551820033 412 2576708193 413 2601777963 414 2627030224 415 2652465860 416 2678085756 417 2703890800 418 2729881882 419 2756059894 420 2782425730 421 2808980286 422 2835724461 423 2862659155 424 2889785271 425 2917103714 426 2944615390 427 2972321209 428 3000222082 429 3028318922 430 3056612645 431 3085104168 432 3113794411 433 3142684296 434 3171774747 435 3201066690 436 3230561053 437 3260258767 438 3290160764 439 3320267979 440 3350581349 441 3381101812 442 3411830310 443 3442767786 444 3473915185 445 3505273455 446 3536843545 447 3568626407 448 3600622995 449 3632834265 450 3665261175 451 3697904685 452 3730765758 453 3763845358 454 3797144452 455 3830664009 456 3864404999 457 3898368396 458 3932555175 459 3966966313 460 4001602790 461 4036465587 462 4071555688 463 4106874079 464 4142421748 465 4178199685 466 4214208882 467 4250450334 468 4286925037 469 4323633990 470 4360578194 471 4397758651 472 4435176367 473 4472832349 474 4510727606 475 4548863150 476 4587239994 477 4625859154 478 4664721648 479 4703828496 480 4743180720 481 4782779344 482 4822625395 483 4862719901 484 4903063893 485 4943658404 486 4984504468 487 5025603123 488 5066955408 489 5108562364 490 5150425035 491 5192544466 492 5234921705 493 5277557802 494 5320453809 495 5363610780 496 5407029771 497 5450711841 498 5494658050 499 5538869461 500 5583347139 501 5628092150 502 5673105564 503 5718388452 504 5763941887 505 5809766945 506 5855864703 507 5902236241 508 5948882641 509 5995804987 510 6043004365 511 6090481863 512 6138238572 513 6186275584 514 6234593994 515 6283194899 516 6332079397 517 6381248590 518 6430703581 519 6480445475 520 6530475380 521 6580794405 522 6631403662 523 6682304265 524 6733497330 525 6784983975 526 6836765320 527 6888842488 528 6941216603 529 6993888792 530 7046860184 531 7100131909 532 7153705101 533 7207580895 534 7261760428 535 7316244840 536 7371035272 537 7426132868 538 7481538774 539 7537254138 540 7593280110 541 7649617842 542 7706268489 543 7763233207 544 7820513155 545 7878109494 546 7936023386 547 7994255997 548 8052808494 549 8111682046 550 8170877825 551 8230397004 552 8290240759 553 8350410268 554 8410906711 555 8471731270 556 8532885129 557 8594369475 558 8656185496 559 8718334383 560 8780817329 561 8843635528 562 8906790178 563 8970282478 564 9034113629 565 9098284835 566 9162797301 567 9227652235 568 9292850847 569 9358394349 570 9424283955 571 9490520881 572 9557106346 573 9624041570 574 9691327776 575 9758966189 576 9826958035 577 9895304544 578 9964006947 579 10033066477 580 10102484370 581 10172261863 582 10242400196 583 10312900611 584 10383764352 585 10454992665 586 10526586798 587 10598548002 588 10670877529 589 10743576634 590 10816646574 591 10890088607 592 10963903995 593 11038094001 594 11112659890 595 11187602930 596 11262924390 597 11338625542 598 11414707660 599 11491172020 600 11568019900 601 11645252580 602 11722871343 603 11800877473 604 11879272257 605 11958056984 606 12037232944 607 12116801431 608 12196763740 609 12277121168 610 12357875015 611 12439026582 612 12520577173 613 12602528094 614 12684880653 615 12767636160 616 12850795927 617 12934361269 618 13018333502 619 13102713945 620 13187503919 621 13272704746 622 13358317752 623 13444344264 624 13530785611 625 13617643125 626 13704918139 627 13792611989 628 13880726013 629 13969261551 630 14058219945 631 14147602539 632 14237410680 633 14327645716 634 14418308998 635 14509401879 636 14600925713 637 14692881858 638 14785271673 639 14878096519 640 14971357760 641 15065056761 642 15159194890 643 15253773517 644 15348794014 645 15444257755 646 15540166116 647 15636520476 648 15733322215 649 15830572716 650 15928273364 651 16026425545 652 16125030649 653 16224090067 654 16323605192 655 16423577420 656 16524008148 657 16624898776 658 16726250706 659 16828065342 660 16930344090 661 17033088358 662 17136299557 663 17239979099 664 17344128399 665 17448748874 666 17553841942 667 17659409025 668 17765451546 669 17871970930 670 17978968605 671 18086446000 672 18194404547 673 18302845680 674 18411770835 675 18521181450 676 18631078965 677 18741464823 678 18852340468 679 18963707347 680 19075566909 681 19187920604 682 19300769886 683 19414116210 684 19527961033 685 19642305815 686 19757152017 687 19872501103 688 19988354539 689 20104713793 690 20221580335 691 20338955637 692 20456841174 693 20575238422 694 20694148860 695 20813573969 696 20933515231 697 21053974132 698 21174952159 699 21296450801 700 21418471550 701 21541015899 702 21664085344 703 21787681383 704 21911805516 705 22036459245 706 22161644074 707 22287361510 708 22413613061 709 22540400238 710 22667724554 711 22795587523 712 22923990663 713 23052935493 714 23182423534 715 23312456310 716 23443035346 717 23574162170 718 23705838312 719 23838065304 720 23970844680 721 24104177976 722 24238066731 723 24372512485 724 24507516781 725 24643081164 726 24779207180 727 24915896379 728 25053150312 729 25190970532 730 25329358595 731 25468316058 732 25607844481 733 25747945426 734 25888620457 735 26029871140 736 26171699043 737 26314105737 738 26457092794 739 26600661789 740 26744814299 741 26889551902 742 27034876180 743 27180788716 744 27327291095 745 27474384905 746 27622071735 747 27770353177 748 27919230825 749 28068706275 750 28218781125 751 28369456975 752 28520735428 753 28672618088 754 28825106562 755 28978202459 756 29131907389 757 29286222966 758 29441150805 759 29596692523 760 29752849740 761 29909624077 762 30067017158 763 30225030609 764 30383666058 765 30542925135 766 30702809472 767 30863320704 768 31024460467 769 31186230400 770 31348632144 771 31511667341 772 31675337637 773 31839644679 774 32004590116 775 32170175600 776 32336402784 777 32503273324 778 32670788878 779 32838951106 780 33007761670 781 33177222234 782 33347334465 783 33518100031 784 33689520603 785 33861597854 786 34034333458 787 34207729093 788 34381786438 789 34556507174 790 34731892985 791 34907945556 792 35084666575 793 35262057732 794 35440120719 795 35618857230 796 35798268961 797 35978357611 798 36159124880 799 36340572471 800 36522702089 801 36705515440 802 36889014234 803 37073200182 804 37258074997 805 37443640395 806 37629898093 807 37816849811 808 38004497271 809 38192842197 810 38381886315 811 38571631353 812 38762079042 813 38953231114 814 39145089304 815 39337655349 816 39530930987 817 39724917960 818 39919618011 819 40115032885 820 40311164330 821 40508014095 822 40705583932 823 40903875595 824 41102890840 825 41302631425 826 41503099110 827 41704295658 828 41906222833 829 42108882402 830 42312276134 831 42516405799 832 42721273171 833 42926880025 834 43133228138 835 43340319290 836 43548155262 837 43756737838 838 43966068804 839 44176149948 840 44386983060 841 44598569932 842 44810912359 843 45024012137 844 45237871065 845 45452490944 846 45667873576 847 45884020767 848 46100934324 849 46318616056 850 46537067775 851 46756291294 852 46976288429 853 47197060998 854 47418610821 855 47640939720 856 47864049519 857 48087942045 858 48312619126 859 48538082593 860 48764334279 861 48991376018 862 49219209648 863 49447837008 864 49677259939 865 49907480285 866 50138499891 867 50370320605 868 50602944277 869 50836372759 870 51070607905 871 51305651571 872 51541505616 873 51778171900 874 52015652286 875 52253948639 876 52493062825 877 52732996714 878 52973752177 879 53215331087 880 53457735320 881 53700966753 882 53945027266 883 54189918741 884 54435643062 885 54682202115 886 54929597788 887 55177831972 888 55426906559 889 55676823444 890 55927584524 891 56179191697 892 56431646865 893 56684951931 894 56939108800 895 57194119380 896 57449985580 897 57706709312 898 57964292490 899 58222737030 900 58482044850 901 58742217870 902 59003258013 903 59265167203 904 59527947367 905 59791600434 906 60056128334 907 60321533001 908 60587816370 909 60854980378 910 61123026965 911 61391958072 912 61661775643 913 61932481624 914 62204077963 915 62476566610 916 62749949517 917 63024228639 918 63299405932 919 63575483355 920 63852462869 921 64130346436 922 64409136022 923 64688833594 924 64969441121 925 65250960575 926 65533393929 927 65816743159 928 66101010243 929 66386197161 930 66672305895 931 66959338429 932 67247296750 933 67536182846 934 67825998708 935 68116746329 936 68408427703 937 68701044828 938 68994599703 939 69289094329 940 69584530710 941 69880910851 942 70178236760 943 70476510447 944 70775733924 945 71075909205 946 71377038306 947 71679123246 948 71982166045 949 72286168726 950 72591133314 951 72897061835 952 73203956319 953 73511818797 954 73820651302 955 74130455870 956 74441234538 957 74752989346 958 75065722336 959 75379435552 960 75694131040 961 76009810848 962 76326477027 963 76644131629 964 76962776709 965 77282414324 966 77603046532 967 77924675395 968 78247302976 969 78570931340 970 78895562555 971 79221198690 972 79547841817 973 79875494010 974 80204157345 975 80533833900 976 80864525755 977 81196234993 978 81528963698 979 81862713957 980 82197487859 981 82533287494 982 82870114956 983 83207972340 984 83546861743 985 83886785265 986 84227745007 987 84569743073 988 84912781569 989 85256862603 990 85601988285 991 85948160727 992 86295382044 993 86643654352 994 86992979770 995 87343360419 996 87694798421 997 88047295902 998 88400854989 999 88755477811 1000 89111166500