0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 22 9 30 10 41 11 54 12 72 13 93 14 120 15 153 16 194 17 242 18 302 19 372 20 457 21 556 22 675 23 812 24 975 25 1162 26 1381 27 1632 28 1923 29 2254 30 2636 31 3068 32 3562 33 4119 34 4752 35 5462 36 6265 37 7162 38 8170 39 9293 40 10549 41 11942 42 13495 43 15211 44 17115 45 19214 46 21534 47 24083 48 26892 49 29970 50 33349 51 37043 52 41087 53 45495 54 50309 55 55544 56 61245 57 67431 58 74151 59 81427 60 89314 61 97836 62 107052 63 116993 64 127720 65 139268 66 151708 67 165076 68 179448 69 194868 70 211418 71 229143 72 248137 73 268450 74 290180 75 313387 76 338175 77 364610 78 392805 79 422833 80 454816 81 488835 82 525021 83 563461 84 604301 85 647631 86 693608 87 742337 88 793981 89 848654 90 906535 91 967747 92 1032476 93 1100862 94 1173105 95 1249351 96 1329819 97 1414665 98 1504122 99 1598359 100 1697625 101 1802103 102 1912059 103 2027689 104 2149274 105 2277031 106 2411252 107 2552171 108 2700106 109 2855301 110 3018093 111 3188748 112 3367623 113 3554995 114 3751251 115 3956688 116 4171708 117 4396635 118 4631892 119 4877824 120 5134878 121 5403422 122 5683930 123 5976793 124 6282511 125 6601497 126 6934286 127 7281308 128 7643128 129 8020212 130 8413147 131 8822426 132 9248673 133 9692409 134 10154282 135 10634853 136 11134805 137 11654722 138 12195330 139 12757243 140 13341223 141 13947917 142 14578127 143 15232537 144 15911988 145 16617200 146 17349052 147 18108311 148 18895888 149 19712592 150 20559389 151 21437119 152 22346793 153 23289300 154 24265698 155 25276910 156 26324054 157 27408101 158 28530209 159 29691406 160 30892899 161 32135765 162 33421264 163 34750526 164 36124869 165 37545475 166 39013719 167 40530835 168 42098267 169 43717294 170 45389424 171 47116007 172 48898603 173 50738622 174 52637697 175 54597300 176 56619119 177 58704704 178 60855815 179 63074057 180 65361272 181 67719130 182 70149547 183 72654262 184 75235270 185 77894386 186 80633682 187 83455048 188 86360633 189 89352416 190 92432616 191 95603295 192 98866772 193 102225178 194 105680920 195 109236222 196 112893581 197 116655295 198 120523969 199 124501994 200 128592057 201 132796653 202 137118564 203 141560380 204 146124982 205 150815061 206 155633605 207 160583404 208 165667552 209 170888939 210 176250781 211 181756059 212 187408105 213 193210025 214 199165252 215 205277004 216 211548841 217 217984096 218 224586435 219 231359326 220 238306563 221 245431720 222 252738732 223 260231293 224 267913469 225 275789079 226 283862327 227 292137167 228 300617938 229 309308728 230 318214013 231 327338032 232 336685389 233 346260468 234 356068039 235 366112614 236 376399114 237 386932209 238 397716975 239 408758217 240 420061188 241 431630852 242 443472608 243 455591593 244 467993368 245 480683233 246 493666916 247 506949888 248 520538055 249 534437056 250 548652975 251 563191621 252 578059275 253 593261906 254 608805986 255 624697686 256 640943650 257 657550236 258 674524293 259 691872370 260 709601496 261 727718435 262 746230424 263 765144408 264 784467847 265 804207885 266 824372194 267 844968123 268 866003565 269 887486087 270 909423800 271 931824488 272 954696483 273 978047807 274 1001887003 275 1026222325 276 1051062572 277 1076416210 278 1102292278 279 1128699490 280 1155647130 281 1183144133 282 1211200055 283 1239824082 284 1269026005 285 1298815278 286 1329201947 287 1360195723 288 1391806913 289 1424045495 290 1456922052 291 1490446825 292 1524630673 293 1559484104 294 1595018276 295 1631243953 296 1668172585 297 1705815242 298 1744183645 299 1783289153 300 1823143797 301 1863759230 302 1905147765 303 1947321378 304 1990292697 305 2034073982 306 2078678194 307 2124117899 308 2170406379 309 2217556513 310 2265581916 311 2314495796 312 2364312097 313 2415044356 314 2466706851 315 2519313473 316 2572878822 317 2627417137 318 2682943394 319 2739472157 320 2797018760 321 2855598134 322 2915225978 323 2975917560 324 3037688975 325 3100555864 326 3164534676 327 3229641445 328 3295892998 329 3363305750 330 3431896914 331 3501683298 332 3572682519 333 3644911774 334 3718389085 335 3793132044 336 3869159104 337 3946488240 338 4025138330 339 4105127790 340 4186475899 341 4269201495 342 4353324304 343 4438863593 344 4525839503 345 4614271764 346 4704180971 347 4795587273 348 4888511740 349 4982974966 350 5078998484 351 5176603341 352 5275811547 353 5376644622 354 5479125049 355 5583274822 356 5689116903 357 5796673789 358 5905968909 359 6017025257 360 6129866791 361 6244516976 362 6361000280 363 6479340688 364 6599563186 365 6721692246 366 6845753408 367 6971771673 368 7099773088 369 7229783206 370 7361828610 371 7495935392 372 7632130680 373 7770441120 374 7910894407 375 8053517737 376 8198339373 377 8345387069 378 8494689687 379 8646275526 380 8800174041 381 8956414142 382 9115025851 383 9276038669 384 9439483237 385 9605389656 386 9773789151 387 9944712462 388 10118191443 389 10294257424 390 10472942913 391 10654279860 392 10838301414 393 11025040155 394 11214529890 395 11406803853 396 11601896504 397 11799841733 398 12000674662 399 12204429870 400 12411143128 401 12620849698 402 12833586071 403 13049388164 404 13268293167 405 13490337708 406 13715559686 407 13943996404 408 14175686511 409 14410668033 410 14648980318 411 14890662141 412 15135753582 413 15384294152 414 15636324674 415 15891885413 416 16151017960 417 16413763330 418 16680163885 419 16950261400 420 17224099043 421 17501719335 422 17783166245 423 18068483115 424 18357714686 425 18650905100 426 18948099929 427 19249344126 428 19554684056 429 19864165527 430 20177835749 431 20495741331 432 20817930356 433 21144450269 434 21475350013 435 21810677881 436 22150483695 437 22494816624 438 22843727365 439 23197265966 440 23555484010 441 23918432461 442 24286163775 443 24658729827 444 25036184025 445 25418579125 446 25805969465 447 26198408745 448 26595952245 449 26998654570 450 27406571989 451 27819760066 452 28238276003 453 28662176353 454 29091519289 455 29526362340 456 29966764662 457 30412784781 458 30864482866 459 31321918436 460 31785152677 461 32254246113 462 32729260987 463 33210258814 464 33697302889 465 34190455802 466 34689781869 467 35195344733 468 35707209797 469 36225441770 470 36750107102 471 37281271617 472 37819002870 473 38363367742 474 38914434925 475 39472272397 476 40036949973 477 40608536742 478 41187103665 479 41772720974 480 42365460772 481 42965394438 482 43572595231 483 44187135719 484 44809090303 485 45438532736 486 46075538649 487 46720182948 488 47372542471 489 48032693347 490 48700713636 491 49376680648 492 50060673717 493 50752771395 494 51453054230 495 52161602050 496 52878496659 497 53603819148 498 54337652592 499 55080079369 500 55831183859 501 56591049723 502 57359762652 503 58137407605 504 58924071628 505 59719840964 506 60524804010 507 61339048386 508 62162663807 509 62995739247 510 63838365813 511 64690633848 512 65552635808 513 66424463460 514 67306210674 515 68197970579 516 69099838494 517 70011908955 518 70934278717 519 71867043739 520 72810302238 521 73764151632 522 74728691597 523 75704021016 524 76690241040 525 77687452064 526 78695756700 527 79715256852 528 80746056690 529 81788259593 530 82841971266 531 83907296640 532 84984342972 533 86073216701 534 87174026694 535 88286880966 536 89411889929 537 90549163212 538 91698812820 539 92860949983 540 94035688316 541 95223140677 542 96423422330 543 97636647758 544 98862933881 545 100102396825 546 101355155215 547 102621326806 548 103901031925 549 105194390058 550 106501523200 551 107822552544 552 109157601834 553 110506793988 554 111870254454 555 113248107936 556 114640481657 557 116047502041 558 117469298126 559 118905998106 560 120357732821 561 121824632253 562 123306829074 563 124804455095 564 126317644817 565 127846531888 566 129391252657 567 130951942661 568 132528740083 569 134121782347 570 135731209577 571 137357161048 572 138999778801 573 140659204047 574 142335580764 575 144029052053 576 145739763892 577 147467861347 578 149213492328 579 150976803908 580 152757945982 581 154557067617 582 156374320713 583 158209856362 584 160063828512 585 161936390278 586 163827697665 587 165737905832 588 167667172895 589 169615656043 590 171583515502 591 173570910602 592 175578003643 593 177604956072 594 179651932352 595 181719096068 596 183806613798 597 185914651332 598 188043377442 599 190192960053 600 192363570175 601 194555377923 602 196768556533 603 199003278331 604 201259718812 605 203538052559 606 205838457324 607 208161109957 608 210506190489 609 212873878094 610 215264355069 611 217677802911 612 220114406299 613 222574349016 614 225057818099 615 227564999710 616 230096083266 617 232651257260 618 235230713559 619 237834643069 620 240463240035 621 243116697822 622 245795213112 623 248498981717 624 251228202778 625 253983074589 626 256763798798 627 259570576180 628 262403610901 629 265263106241 630 268149268944 631 271062304781 632 274002423074 633 276969832206 634 279964744040 635 282987369547 636 286037923227 637 289116618663 638 292223672943 639 295359302335 640 298523726601 641 301717164620 642 304939838877 643 308191970923 644 311473785954 645 314785508217 646 318127365656 647 321499585265 648 324902397735 649 328336032819 650 331800723981 651 335296703795 652 338824208485 653 342383473447 654 345974737791 655 349598239697 656 353254221136 657 356942923173 658 360664590666 659 364419467515 660 368207801541 661 372029839568 662 375885832305 663 379776029551 664 383700684967 665 387660051316 666 391654385236 667 395683942493 668 399748982755 669 403849764791 670 407986551313 671 412159604120 672 416369189033 673 420615570868 674 424899018557 675 429219800064 676 433578187393 677 437974451632 678 442408867962 679 446881710622 680 451393257919 681 455943787322 682 460533580358 683 465162917649 684 469832083995 685 474541363238 686 479291043440 687 484081411690 688 488912759353 689 493785376821 690 498699558763 691 503655598888 692 508653795198 693 513694444787 694 518777848978 695 523904308253 696 529074127391 697 534287610223 698 539545064960 699 544846798891 700 550193123688 701 555584350046 702 561020793181 703 566502767291 704 572030591057 705 577604582236 706 583225063044 707 588892354787 708 594606783244 709 600368673313 710 606178354395 711 612036154981 712 617942408110 713 623897445897 714 629901605090 715 635955221416 716 642058635335 717 648212186327 718 654416218525 719 660671075138 720 666977104085 721 673334652334 722 679744071538 723 686205712510 724 692719930738 725 699287080800 726 705907522077 727 712581612985 728 719309716788 729 726092195770 730 732929417124 731 739821747063 732 746769556711 733 753773216227 734 760833100699 735 767949584306 736 775123046088 737 782353864249 738 789642421927 739 796989101311 740 804394289613 741 811858373124 742 819381743163 743 826964790070 744 834607909360 745 842311495527 746 850075948200 747 857901666088 748 865789053010 749 873738511881 750 881750450742 751 889825276761 752 897963402265 753 906165238678 754 914431202632 755 922761709842 756 931157181321 757 939618037064 758 948144702471 759 956737601968 760 965397165302 761 974123821306 762 982918004196 763 991780147246 764 1000710689087 765 1009710067527 766 1018778725721 767 1027917105928 768 1037125655890 769 1046404822396 770 1055755057767 771 1065176813355 772 1074670546110 773 1084236712014 774 1093875772650 775 1103588188650 776 1113374426266 777 1123234950860 778 1133170233343 779 1143180743814 780 1153266957999 781 1163429350693 782 1173668402414 783 1183984592779 784 1194378407134 785 1204850329864 786 1215400851239 787 1226030460525 788 1236739652831 789 1247528922370 790 1258398769173 791 1269349692392 792 1280382197015 793 1291496787185 794 1302693972917 795 1313974263350 796 1325338173547 797 1336786217682 798 1348318915949 799 1359936787547 800 1371640357809 801 1383430151120 802 1395306697912 803 1407270527733 804 1419322176244 805 1431462178194 806 1443691074418 807 1456009404966 808 1468417715964 809 1480916552677 810 1493506466591 811 1506188008271 812 1518961734556 813 1531828201348 814 1544787970894 815 1557841604506 816 1570989669844 817 1584232733653 818 1597571369047 819 1611006148290 820 1624537649941 821 1638166451792 822 1651893138014 823 1665718291886 824 1679642503168 825 1693666360761 826 1707790460054 827 1722015395515 828 1736341768265 829 1750770178460 830 1765301232866 831 1779935537398 832 1794673704556 833 1809516346008 834 1824464080027 835 1839517524091 836 1854677302321 837 1869944038012 838 1885318361158 839 1900800900914 840 1916392293236 841 1932093173130 842 1947904182525 843 1963825962450 844 1979859160766 845 1996004424503 846 2012262407593 847 2028633763109 848 2045119150998 849 2061719230483 850 2078434667652 851 2095266127789 852 2112214283197 853 2129279805313 854 2146463372650 855 2163765662839 856 2181187360662 857 2198729150023 858 2216391721981 859 2234175766739 860 2252081981678 861 2270111063392 862 2288263715577 863 2306540641230 864 2324942550539 865 2343470152863 866 2362124164860 867 2380905302395 868 2399814288640 869 2418851845910 870 2438018704002 871 2457315591810 872 2476743245666 873 2496302401120 874 2515993801135 875 2535818187913 876 2555776311090 877 2575868919582 878 2596096769780 879 2616460617323 880 2636961225385 881 2657599356375 882 2678375780346 883 2699291266470 884 2720346591692 885 2741542532130 886 2762879871580 887 2784359393085 888 2805981887440 889 2827748144659 890 2849658962480 891 2871715138002 892 2893917476040 893 2916266780687 894 2938763863915 895 2961409536910 896 2984204618797 897 3007149927900 898 3030246290562 899 3053494532330 900 3076895486775 901 3100449986696 902 3124158872942 903 3148022985663 904 3172043172980 905 3196220282409 906 3220555169531 907 3245048689187 908 3269701704397 909 3294515077480 910 3319489678944 911 3344626378529 912 3369926054349 913 3395389583703 914 3421017852219 915 3446811744838 916 3472772154804 917 3498899974698 918 3525196105427 919 3551661447279 920 3578296908912 921 3605103398332 922 3632081831980 923 3659233125632 924 3686558203614 925 3714057989467 926 3741733415418 927 3769585412967 928 3797614922201 929 3825822882559 930 3854210242146 931 3882777948390 932 3911526957357 933 3940458224586 934 3969572714247 935 3998871389897 936 4028355223895 937 4058025187922 938 4087882262525 939 4117927427558 940 4148161671826 941 4178585983447 942 4209201359497 943 4240008796391 944 4271009299530 945 4302203873732 946 4333593532719 947 4365179289730 948 4396962167007 949 4428943186169 950 4461123377959 951 4493503772538 952 4526085409203 953 4558869326600 954 4591856572706 955 4625048194799 956 4658445249441 957 4692048792631 958 4725859889626 959 4759879605146 960 4794109013194 961 4828549187283 962 4863201210257 963 4898066164436 964 4933145141540 965 4968439232753 966 5003949538780 967 5039677159666 968 5075623205120 969 5111788784253 970 5148175015738 971 5184783017733 972 5221613918042 973 5258668843925 974 5295948932260 975 5333455319539 976 5371189151865 977 5409151574867 978 5447343743965 979 5485766814038 980 5524421949824 981 5563310315505 982 5602433085213 983 5641791432531 984 5681386541000 985 5721219593641 986 5761291783463 987 5801604303038 988 5842158354841 989 5882955141016 990 5923995873715 991 5965281764613 992 6006814035521 993 6048593907817 994 6090622613029 995 6132901382181 996 6175431456651 997 6218214077265 998 6261250495155 999 6304541961044 1000 6348089735935