0 0 1 1 2 9 3 35 4 95 5 210 6 406 7 714 8 1170 9 1815 10 2695 11 3861 12 5369 13 7280 14 9660 15 12580 16 16116 17 20349 18 25365 19 31255 20 38115 21 46046 22 55154 23 65550 24 77350 25 90675 26 105651 27 122409 28 141085 29 161820 30 184760 31 210056 32 237864 33 268345 34 301665 35 337995 36 377511 37 420394 38 466830 39 517010 40 571130 41 629391 42 691999 43 759165 44 831105 45 908040 46 990196 47 1077804 48 1171100 49 1270325 50 1375725 51 1487551 52 1606059 53 1731510 54 1864170 55 2004310 56 2152206 57 2308139 58 2472395 59 2645265 60 2827045 61 3018036 62 3218544 63 3428880 64 3649360 65 3880305 66 4122041 67 4374899 68 4639215 69 4915330 70 5203590 71 5504346 72 5817954 73 6144775 74 6485175 75 6839525 76 7208201 77 7591584 78 7990060 79 8404020 80 8833860 81 9279981 82 9742789 83 10222695 84 10720115 85 11235470 86 11769186 87 12321694 88 12893430 89 13484835 90 14096355 91 14728441 92 15381549 93 16056140 94 16752680 95 17471640 96 18213496 97 18978729 98 19767825 99 20581275 100 21419575 101 22283226 102 23172734 103 24088610 104 25031370 105 26001535 106 26999631 107 28026189 108 29081745 109 30166840 110 31282020 111 32427836 112 33604844 113 34813605 114 36054685 115 37328655 116 38636091 117 39977574 118 41353690 119 42765030 120 44212190 121 45695771 122 47216379 123 48774625 124 50371125 125 52006500 126 53681376 127 55396384 128 57152160 129 58949345 130 60788585 131 62670531 132 64595839 133 66565170 134 68579190 135 70638570 136 72743986 137 74896119 138 77095655 139 79343285 140 81639705 141 83985616 142 86381724 143 88828740 144 91327380 145 93878365 146 96482421 147 99140279 148 101852675 149 104620350 150 107444050 151 110324526 152 113262534 153 116258835 154 119314195 155 122429385 156 125605181 157 128842364 158 132141720 159 135504040 160 138930120 161 142420761 162 145976769 163 149598955 164 153288135 165 157045130 166 160870766 167 164765874 168 168731290 169 172767855 170 176876415 171 181057821 172 185312929 173 189642600 174 194047700 175 198529100 176 203087676 177 207724309 178 212439885 179 217235295 180 222111435 181 227069206 182 232109514 183 237233270 184 242441390 185 247734795 186 253114411 187 258581169 188 264136005 189 269779860 190 275513680 191 281338416 192 287255024 193 293264465 194 299367705 195 305565715 196 311859471 197 318249954 198 324738150 199 331325050 200 338011650 201 344798951 202 351687959 203 358679685 204 365775145 205 372975360 206 380281356 207 387694164 208 395214820 209 402844365 210 410583845 211 418434311 212 426396819 213 434472430 214 442662210 215 450967230 216 459388566 217 467927299 218 476584515 219 485361305 220 494258765 221 503277996 222 512420104 223 521686200 224 531077400 225 540594825 226 550239601 227 560012859 228 569915735 229 579949370 230 590114910 231 600413506 232 610846314 233 621414495 234 632119215 235 642961645 236 653942961 237 665064344 238 676326980 239 687732060 240 699280780 241 710974341 242 722813949 243 734800815 244 746936155 245 759221190 246 771657146 247 784245254 248 796986750 249 809882875 250 822934875 251 836144001 252 849511509 253 863038660 254 876726720 255 890576960 256 904590656 257 918769089 258 933113545 259 947625315 260 962305695 261 977155986 262 992177494 263 1007371530 264 1022739410 265 1038282455 266 1054001991 267 1069899349 268 1085975865 269 1102232880 270 1118671740 271 1135293796 272 1152100404 273 1169092925 274 1186272725 275 1203641175 276 1221199651 277 1238949534 278 1256892210 279 1275029070 280 1293361510 281 1311890931 282 1330618739 283 1349546345 284 1368675165 285 1388006620 286 1407542136 287 1427283144 288 1447231080 289 1467387385 290 1487753505 291 1508330891 292 1529120999 293 1550125290 294 1571345230 295 1592782290 296 1614437946 297 1636313679 298 1658410975 299 1680731325 300 1703276225 301 1726047176 302 1749045684 303 1772273260 304 1795731420 305 1819421685 306 1843345581 307 1867504639 308 1891900395 309 1916534390 310 1941408170 311 1966523286 312 1991881294 313 2017483755 314 2043332235 315 2069428305 316 2095773541 317 2122369524 318 2149217840 319 2176320080 320 2203677840 321 2231292721 322 2259166329 323 2287300275 324 2315696175 325 2344355650 326 2373280326 327 2402471834 328 2431931810 329 2461661895 330 2491663735 331 2521938981 332 2552489289 333 2583316320 334 2614421740 335 2645807220 336 2677474436 337 2709425069 338 2741660805 339 2774183335 340 2806994355 341 2840095566 342 2873488674 343 2907175390 344 2941157430 345 2975436515 346 3010014371 347 3044892729 348 3080073325 349 3115557900 350 3151348200 351 3187445976 352 3223852984 353 3260570985 354 3297601745 355 3334947035 356 3372608631 357 3410588314 358 3448887870 359 3487509090 360 3526453770 361 3565723711 362 3605320719 363 3645246605 364 3685503185 365 3726092280 366 3767015716 367 3808275324 368 3849872940 369 3891810405 370 3934089565 371 3976712271 372 4019680379 373 4062995750 374 4106660250 375 4150675750 376 4195044126 377 4239767259 378 4284847035 379 4330285345 380 4376084085 381 4422245156 382 4468770464 383 4515661920 384 4562921440 385 4610550945 386 4658552361 387 4706927619 388 4755678655 389 4804807410 390 4854315830 391 4904205866 392 4954479474 393 5005138615 394 5056185255 395 5107621365 396 5159448921 397 5211669904 398 5264286300 399 5317300100 400 5370713300 401 5424527901 402 5478745909 403 5533369335 404 5588400195 405 5643840510 406 5699692306 407 5755957614 408 5812638470 409 5869736915 410 5927254995 411 5985194761 412 6043558269 413 6102347580 414 6161564760 415 6221211880 416 6281291016 417 6341804249 418 6402753665 419 6464141355 420 6525969415 421 6588239946 422 6650955054 423 6714116850 424 6777727450 425 6841788975 426 6906303551 427 6971273309 428 7036700385 429 7102586920 430 7168935060 431 7235746956 432 7303024764 433 7370770645 434 7438986765 435 7507675295 436 7576838411 437 7646478294 438 7716597130 439 7787197110 440 7858280430 441 7929849291 442 8001905899 443 8074452465 444 8147491205 445 8221024340 446 8295054096 447 8369582704 448 8444612400 449 8520145425 450 8596184025 451 8672730451 452 8749786959 453 8827355810 454 8905439270 455 8984039610 456 9063159106 457 9142800039 458 9222964695 459 9303655365 460 9384874345 461 9466623936 462 9548906444 463 9631724180 464 9715079460 465 9798974605 466 9883411941 467 9968393799 468 10053922515 469 10140000430 470 10226629890 471 10313813246 472 10401552854 473 10489851075 474 10578710275 475 10668132825 476 10758121101 477 10848677484 478 10939804360 479 11031504120 480 11123779160 481 11216631881 482 11310064689 483 11404079995 484 11498680215 485 11593867770 486 11689645086 487 11786014594 488 11882978730 489 11980539935 490 12078700655 491 12177463341 492 12276830449 493 12376804440 494 12477387780 495 12578582940 496 12680392396 497 12782818629 498 12885864125 499 12989531375 500 13093822875 501 13198741126 502 13304288634 503 13410467910 504 13517281470 505 13624731835 506 13732821531 507 13841553089 508 13950929045 509 14060951940 510 14171624320 511 14282948736 512 14394927744 513 14507563905 514 14620859785 515 14734817955 516 14849440991 517 14964731474 518 15080691990 519 15197325130 520 15314633490 521 15432619671 522 15551286279 523 15670635925 524 15790671225 525 15911394800 526 16032809276 527 16154917284 528 16277721460 529 16401224445 530 16525428885 531 16650337431 532 16775952739 533 16902277470 534 17029314290 535 17157065870 536 17285534886 537 17414724019 538 17544635955 539 17675273385 540 17806639005 541 17938735516 542 18071565624 543 18205132040 544 18339437480 545 18474484665 546 18610276321 547 18746815179 548 18884103975 549 19022145450 550 19160942350 551 19300497426 552 19440813434 553 19581893135 554 19723739295 555 19866354685 556 20009742081 557 20153904264 558 20298844020 559 20444564140 560 20591067420 561 20738356661 562 20886434669 563 21035304255 564 21184968235 565 21335429430 566 21486690666 567 21638754774 568 21791624590 569 21945302955 570 22099792715 571 22255096721 572 22411217829 573 22568158900 574 22725922800 575 22884512400 576 23043930576 577 23204180209 578 23365264185 579 23527185395 580 23689946735 581 23853551106 582 24018001414 583 24183300570 584 24349451490 585 24516457095 586 24684320311 587 24853044069 588 25022631305 589 25193084960 590 25364407980 591 25536603316 592 25709673924 593 25883622765 594 26058452805 595 26234167015 596 26410768371 597 26588259854 598 26766644450 599 26945925150 600 27126104950 601 27307186851 602 27489173859 603 27672068985 604 27855875245 605 28040595660 606 28226233256 607 28412791064 608 28600272120 609 28788679465 610 28978016145 611 29168285211 612 29359489719 613 29551632730 614 29744717310 615 29938746530 616 30133723466 617 30329651199 618 30526532815 619 30724371405 620 30923170065 621 31122931896 622 31323660004 623 31525357500 624 31728027500 625 31931673125 626 32136297501 627 32341903759 628 32548495035 629 32756074470 630 32964645210 631 33174210406 632 33384773214 633 33596336795 634 33808904315 635 34022478945 636 34237063861 637 34452662244 638 34669277280 639 34886912160 640 35105570080 641 35325254241 642 35545967849 643 35767714115 644 35990496255 645 36214317490 646 36439181046 647 36665090154 648 36892048050 649 37120057975 650 37349123175 651 37579246901 652 37810432409 653 38042682960 654 38276001820 655 38510392260 656 38745857556 657 38982400989 658 39220025845 659 39458735415 660 39698532995 661 39939421886 662 40181405394 663 40424486830 664 40668669510 665 40913956755 666 41160351891 667 41407858249 668 41656479165 669 41906217980 670 42157078040 671 42409062696 672 42662175304 673 42916419225 674 43171797825 675 43428314475 676 43685972551 677 43944775434 678 44204726510 679 44465829170 680 44728086810 681 44991502831 682 45256080639 683 45521823645 684 45788735265 685 46056818920 686 46326078036 687 46596516044 688 46868136380 689 47140942485 690 47414937805 691 47690125791 692 47966509899 693 48244093590 694 48522880330 695 48802873590 696 49084076846 697 49366493579 698 49650127275 699 49934981425 700 50221059525 701 50508365076 702 50796901584 703 51086672560 704 51377681520 705 51669931985 706 51963427481 707 52258171539 708 52554167695 709 52851419490 710 53149930470 711 53449704186 712 53750744194 713 54053054055 714 54356637335 715 54661497605 716 54967638441 717 55275063424 718 55583776140 719 55893780180 720 56205079140 721 56517676621 722 56831576229 723 57146781575 724 57463296275 725 57781123950 726 58100268226 727 58420732734 728 58742521110 729 59065636995 730 59390084035 731 59715865881 732 60042986189 733 60371448620 734 60701256840 735 61032414520 736 61364925336 737 61698792969 738 62034021105 739 62370613435 740 62708573655 741 63047905466 742 63388612574 743 63730698690 744 64074167530 745 64419022815 746 64765268271 747 65112907629 748 65461944625 749 65812383000 750 66164226500 751 66517478876 752 66872143884 753 67228225285 754 67585726845 755 67944652335 756 68305005531 757 68666790214 758 69030010170 759 69394669190 760 69760771070 761 70128319611 762 70497318619 763 70867771905 764 71239683285 765 71613056580 766 71987895616 767 72364204224 768 72741986240 769 73121245505 770 73501985865 771 73884211171 772 74267925279 773 74653132050 774 75039835350 775 75428039050 776 75817747026 777 76208963159 778 76601691335 779 76995935445 780 77391699385 781 77788987056 782 78187802364 783 78588149220 784 78990031540 785 79393453245 786 79798418261 787 80204930519 788 80612993955 789 81022612510 790 81433790130 791 81846530766 792 82260838374 793 82676716915 794 83094170355 795 83513202665 796 83933817821 797 84356019804 798 84779812600 799 85205200200 800 85632186600 801 86060775801 802 86490971809 803 86922778635 804 87356200295 805 87791240810 806 88227904206 807 88666194514 808 89106115770 809 89547672015 810 89990867295 811 90435705661 812 90882191169 813 91330327880 814 91780119860 815 92231571180 816 92684685916 817 93139468149 818 93595921965 819 94054051455 820 94513860715 821 94975353846 822 95438534954 823 95903408150 824 96369977550 825 96838247275 826 97308221451 827 97779904209 828 98253299685 829 98728412020 830 99205245360 831 99683803856 832 100164091664 833 100646112945 834 101129871865 835 101615372595 836 102102619311 837 102591616194 838 103082367430 839 103574877210 840 104069149730 841 104565189191 842 105062999799 843 105562585765 844 106063951305 845 106567100640 846 107072037996 847 107578767604 848 108087293700 849 108597620525 850 109109752325 851 109623693351 852 110139447859 853 110657020110 854 111176414370 855 111697634910 856 112220686006 857 112745571939 858 113272296995 859 113800865465 860 114331281645 861 114863549836 862 115397674344 863 115933659480 864 116471509560 865 117011228905 866 117552821841 867 118096292699 868 118641645815 869 119188885530 870 119738016190 871 120289042146 872 120841967754 873 121396797375 874 121953535375 875 122512186125 876 123072754001 877 123635243384 878 124199658660 879 124766004220 880 125334284460 881 125904503781 882 126476666589 883 127050777295 884 127626840315 885 128204860070 886 128784840986 887 129366787494 888 129950704030 889 130536595035 890 131124464955 891 131714318241 892 132306159349 893 132899992740 894 133495822880 895 134093654240 896 134693491296 897 135295338529 898 135899200425 899 136505081475 900 137112986175 901 137722919026 902 138334884534 903 138948887210 904 139564931570 905 140183022135 906 140803163431 907 141425359989 908 142049616345 909 142675937040 910 143304326620 911 143934789636 912 144567330644 913 145201954205 914 145838664885 915 146477467255 916 147118365891 917 147761365374 918 148406470290 919 149053685230 920 149703014790 921 150354463571 922 151008036179 923 151663737225 924 152321571325 925 152981543100 926 153643657176 927 154307918184 928 154974330760 929 155642899545 930 156313629185 931 156986524331 932 157661589639 933 158338829770 934 159018249390 935 159699853170 936 160383645786 937 161069631919 938 161757816255 939 162448203485 940 163140798305 941 163835605416 942 164532629524 943 165231875340 944 165933347580 945 166637050965 946 167342990221 947 168051170079 948 168761595275 949 169474270550 950 170189200650 951 170906390326 952 171625844334 953 172347567435 954 173071564395 955 173797839985 956 174526398981 957 175257246164 958 175990386320 959 176725824240 960 177463564720 961 178203612561 962 178945972569 963 179690649555 964 180437648335 965 181186973730 966 181938630566 967 182692623674 968 183448957890 969 184207638055 970 184968669015 971 185732055621 972 186497802729 973 187265915200 974 188036397900 975 188809255700 976 189584493476 977 190362116109 978 191142128485 979 191924535495 980 192709342035 981 193496553006 982 194286173314 983 195078207870 984 195872661590 985 196669539395 986 197468846211 987 198270586969 988 199074766605 989 199881390060 990 200690462280 991 201501988216 992 202315972824 993 203132421065 994 203951337905 995 204772728315 996 205596597271 997 206422949754 998 207251790750 999 208083125250 1000 208916958250