1 1 2 2 3 4 4 7 5 12 6 18 7 28 8 39 9 55 10 74 11 100 12 127 13 167 14 208 15 261 16 322 17 399 18 477 19 581 20 686 21 820 22 967 23 1142 24 1318 25 1545 26 1778 27 2053 28 2347 29 2697 30 3048 31 3486 32 3925 33 4441 34 4986 35 5610 36 6250 37 7024 38 7799 39 8680 40 9604 41 10673 42 11743 43 13008 44 14274 45 15718 46 17239 47 18937 48 20636 49 22623 50 24621 51 26872 52 29203 53 31812 54 34422 55 37411 56 40432 57 43814 58 47303 59 51144 60 54986 61 59401 62 63817 63 68673 64 73692 65 79227 66 84808 67 91088 68 97369 69 104277 70 111363 71 119150 72 126938 73 135687 74 144437 75 153963 76 163777 77 174475 78 185210 79 197109 80 209009 81 222039 82 235363 83 249758 84 264154 85 280139 86 296207 87 313542 88 331230 89 350373 90 369517 91 390637 92 411808 93 434680 94 457993 95 483006 96 508129 97 535678 98 563228 99 592818 100 622969 101 655479 102 687990 103 723384 104 758779 105 796794 106 835638 107 877093 108 918549 109 963664 110 1008780 111 1057084 112 1106165 113 1158689 114 1211214 115 1268010 116 1324987 117 1385808 118 1447569 119 1513173 120 1578865 121 1650083 122 1721328 123 1796990 124 1873724 125 1955317 126 2037143 127 2125184 128 2213226 129 2306803 130 2401648 131 2502327 132 2603007 133 2711263 134 2819634 135 2934287 136 3050736 137 3174104 138 3297473 139 3429456 140 3561440 141 3701613 142 3843487 143 3993150 144 4142880 145 4303119 146 4463714 147 4633060 148 4804540 149 4985549 150 5166559 151 5359758 152 5552958 153 5756867 154 5963123 155 6180303 156 6397927 157 6629811 158 6861696 159 7105482 160 7351880 161 7611747 162 7871800 163 8147872 164 8423945 165 8714416 166 9008479 167 9316939 168 9625400 169 9953054 170 10280749 171 10625077 172 10972910 173 11338081 174 11703253 175 12089609 176 12476832 177 12883259 178 13293530 179 13722946 180 14152363 181 14607517 182 15062672 183 15539273 184 16020292 185 16524194 186 17028876 187 17561294 188 18093816 189 18651354 190 19214186 191 19802936 192 20391687 193 21013006 194 21634326 195 22283197 196 22938585 197 23623860 198 24309136 199 25030376 200 25751617 201 26506303 202 27267272 203 28060753 204 28854595 205 29690142 206 30526764 207 31398782 208 32277902 209 33195098 210 34112425 211 35077170 212 36041916 213 37048120 214 38062114 215 39117565 216 40174287 217 41284099 218 42394360 219 43549738 220 44713868 221 45927676 222 47141602 223 48413366 224 49685131 225 51009859 226 52345861 227 53734389 228 55122918 229 56578087 230 58033257 231 59546945 232 61072020 233 62657927 234 64243835 235 65902557 236 67562983 237 69289016 238 71026951 239 72831165 240 74635380 241 76524473 242 78413567 243 80374054 244 82347865 245 84397341 246 86449444 247 88591612 248 90733925 249 92957842 250 95196157 251 97518316 252 99840476 253 102266037 254 104691800 255 107205606 256 109737786 257 112363543 258 114989301 259 117725979 260 120463442 261 123304023 262 126162308 263 129121274 264 132080241 265 135165339 266 138253052 267 141449953 268 144666000 269 147996703 270 151327407 271 154796769 272 158266132 273 161858924 274 165473904 275 169212254 276 172953852 277 176848634 278 180743417 279 184770185 280 188820282 281 193014508 282 197208735 283 201568156 284 205927578 285 210436666 286 214974314 287 219662073 288 224350912 289 229225552 290 234100270 291 239139092 292 244205466 293 249441189 294 254676913 295 260112785 296 265552504 297 271173243 298 276824408 299 282656584 300 288488976 301 294548695 302 300609690 303 306863886 304 313150595 305 319641274 306 326136374 307 332870871 308 339605369 309 346558610 310 353547248 311 360757946 312 367968645 313 375446810 314 382924976 315 390635028 316 398390240 317 406389241 318 414388243 319 422672494 320 430957122 321 439506636 322 448097608 323 456950196 324 465802966 325 474973934 326 484150710 327 493603560 328 503101528 329 512889978 330 522680137 331 532815580 332 542951024 333 553394931 334 563887935 335 574689401 336 585497153 337 596683400 338 607869648 339 619383825 340 630950529 341 642867950 342 654785836 343 667104940 344 679426042 345 692112326 346 704862550 347 717977947 348 731093345 349 744652106 350 758210868 351 772165998 352 786183164 353 800607196 354 815031229 355 829927301 356 844831166 357 860164450 358 875565813 359 891396594 360 907227376 361 923587903 362 939948535 363 956764323 364 973651874 365 991018654 366 1008394189 367 1026321995 368 1044249802 369 1062681572 370 1081190092 371 1100212064 372 1119236656 373 1138870430 374 1158504205 375 1178671195 376 1198929592 377 1219745538 378 1240561875 379 1262026676 380 1283491478 381 1305554952 382 1327706470 383 1350446740 384 1373187011 385 1396636643 386 1420100628 387 1444185934 388 1468366101 389 1493195142 390 1518024184 391 1543614804 392 1569205677 393 1595484857 394 1621864719 395 1648929858 396 1676006902 397 1703907802 398 1731808703 399 1760430846 400 1789164878 401 1818665557 402 1848166237 403 1878536264 404 1908906770 405 1940070760 406 1971364229 407 2003455071 408 2035546714 409 2068590540 410 2101634367 411 2135528160 412 2169545324 413 2204434509 414 2239327546 415 2275224678 416 2311136211 417 2347965379 418 2384926533 419 2422805937 420 2460685342 421 2499680143 422 2538674945 423 2578634494 424 2618735933 425 2659843587 426 2700967536 427 2743247360 428 2785531610 429 2828871314 430 2872362147 431 2916925790 432 2961489434 433 3007314380 434 3053139327 435 3100078993 436 3147196644 437 3195469676 438 3243742988 439 3293341032 440 3342939077 441 3393769553 442 3444776381 443 3496997914 444 3549219448 445 3602884256 446 3656568213 447 3711523936 448 3766660671 449 3823127153 450 3879593636 451 3937598728 452 3995604916 453 4054999635 454 4114587556 455 4175564007 456 4236567793 457 4299220135 458 4361872478 459 4425979992 460 4490294037 461 4556143049 462 4621992062 463 4689579252 464 4757166443 465 4826339602 466 4895753312 467 4966752931 468 5037752551 469 5110631518 470 5183516776 471 5258085793 472 5332886697 473 5409413645 474 5485941885 475 5564439952 476 5642963369 477 5723297578 478 5803878201 479 5886263040 480 5968647880 481 6053193773 482 6137740481 483 6224176284 484 6310879184 485 6399543840 486 6488236051 487 6579164821 488 6670093592 489 6763071850 490 6856326183 491 6951667316 492 7047008450 493 7144767855 494 7242527688 495 7342430843 496 7442659111 497 7545111357 498 7647571401 499 7752563830 500 7857556260 501 7964901108 502 8072554419 503 8182529891 504 8292505364 505 8405225855 506 8517978862 507 8633159301 508 8748668318 509 8866691144 510 8984713971 511 9105630106 512 9226555001 513 9350105653 514 9474004413 515 9600528932 516 9727088851 517 9856733311 518 9986379496 519 10118771936 520 10251529550 521 10387164075 522 10522798601 523 10661660158 524 10800521716 525 10942342243 526 11084597723 527 11229812171 528 11375027135 529 11523716180 530 11672405401 531 11824221199 532 11976447284 533 12131880381 534 12287314588 535 12446375120 536 12605477113 537 12767909820 538 12930771946 539 13096964777 540 13263170330 541 13433320735 542 13603471141 543 13777090911 544 13951165838 545 14128833996 546 14306547275 547 14488342775 548 14670138276 549 14855672130 550 15041687019 551 15231490787 552 15421295010 553 15615475221 554 15809667342 555 16007754247 556 16206394193 557 16409060910 558 16611727628 559 16818953626 560 17026180930 561 17237663502 562 17449681365 563 17665893456 564 17882105548 565 18103209613 566 18324366208 567 18549882226 568 18775974106 569 19006575085 570 19237176065 571 19472931202 572 19708686340 573 19949132837 574 20190168087 575 20435905542 576 20681700201 577 20932963270 578 21184226340 579 21440364674 580 21697124330 581 21958979893 582 22220849862 583 22488407532 584 22755967838 585 23028763878 586 23302277587 587 23581027021 588 23859776456 589 24144631871 590 24429487829 591 24719845287 592 25010888023 593 25307551559 594 25604215096 595 25907223497 596 26210314204 597 26519237090 598 26828881219 599 27144359495 600 27459837772 601 27782163812 602 28104489853 603 28432892999 604 28762057130 605 29097475460 606 29432968029 607 29775508283 608 30118048538 609 30467079911 610 30816922597 611 31173331648 612 31529742438 613 31893688518 614 32257634599 615 32628315179 616 32999908098 617 33378474978 618 33757041859 619 34143434007 620 34529826156 621 34923505845 622 35318064929 623 35719834713 624 36121623651 625 36531771634 626 36942001443 627 37359709419 628 37778338622 629 38204677880 630 38631017990 631 39066140261 632 39501262533 633 39944383817 634 40388469849 635 40840554884 636 41292727966 637 41754150075 638 42215595342 639 42685328874 640 43156076416 641 43635461514 642 44114846613 643 44603836685 644 45092826758 645 45590690887 646 46089705370 647 46597573944 648 47105442519 649 47623546759 650 48141654867 651 48669036847 652 49197552096 653 49735520198 654 50273488301 655 50822064640 656 51370741664 657 51929207199 658 52488836880 659 53058280075 660 53627723271 661 54208571963 662 54789420656 663 55380404794 664 55972605992 665 56575251108 666 57178030237 667 57792525131 668 58407020551 669 59032317440 670 59658886096 671 60296370895 672 60933860136 673 61583832951 674 62233805767 675 62894964832 676 63557574827 677 64231701333 678 64905827840 679 65592857060 680 66279913840 681 66979005425 682 67679485541 683 68391888107 684 69104290674 685 69830411358 686 70556655416 687 71295248168 688 72035296092 689 72788030361 690 73540767280 691 74307834860 692 75074902441 693 75855085422 694 76636827940 695 77431685857 696 78226675763 697 79036749692 698 79846824768 699 80670458607 700 81495678356 701 82335015772 702 83174353189 703 84029307343 704 84884262376 705 85753646460 706 86624831198 707 87510439970 708 88396081263 709 89298279084 710 90200476906 711 91117720487 712 92036702019 713 92971016846 714 93905332287 715 94856821200 716 95808468372 717 96775946328 718 97745228501 719 98730341457 720 99715454414 721 100718895503 722 101722371997 723 102742209899 724 103763936897 725 104802479686 726 105841183297 727 106898669288 728 107956155280 729 109031046479 730 110107911489 731 111202312649 732 112296715152 733 113411019302 734 114525323453 735 115657555412 736 116792047024 737 117944970845 738 119097900973 739 120271405133 740 121444909294 741 122637607015 742 123832451314 743 125046359091 744 126260266869 745 127495950921 746 128731815988 747 129987314831 748 131245052005 749 132522963719 750 133800916899 751 135101550176 752 136402183454 753 137723632739 754 139047404186 755 140391995693 756 141736780405 757 143105408894 758 144474037384 759 145864130677 760 147256657159 761 148671441250 762 150086225342 763 151525586722 764 152964993228 765 154427140007 766 155892024335 767 157379648935 768 158867277417 769 160380887711 770 161894498006 771 163431830952 772 164971789658 773 166535833673 774 168099877689 775 169690743783 776 171281827728 777 172897740725 778 174516439625 779 176159967568 780 177803496685 781 179475577817 782 181147666763 783 182845348649 784 184545889095 785 186272757863 786 187999858521 787 189756197333 788 191512536146 789 193295940101 790 195082303025 791 196895974898 792 198709699306 793 200554309244 794 202398923638 795 204271438934 796 206147285784 797 208051754780 798 209956223777 799 211892568937 800 213828915873 801 215795010325 802 217764320840 803 219763132036 804 221761952008 805 223794358084 806 225827081638 807 227890180348 808 229956609764 809 232054203181 810 234151796599 811 236284296452 812 238416796306 813 240581444276 814 242749561611 815 244949779487 816 247150273441 817 249387282344 818 251624292617 819 253894346718 820 256168081492 821 258475986240 822 260783890989 823 263129427889 824 265474964790 825 267855390887 826 270239859150 827 272659282253 828 275078705357 829 277537789032 830 279996872708 831 282492162000 832 284991346077 833 287527364341 834 290063450284 835 292640392171 836 295217642524 837 297832783364 838 300451974576 839 303109045194 840 305766115813 841 308466609615 842 311167103768 843 313906592724 844 316650275909 845 319433918646 846 322217894618 847 325046189654 848 327874566643 849 330744051347 850 333617895475 851 336533193810 852 339448493095 853 342410431656 854 345372370218 855 348376664317 856 351385841852 857 354438359102 858 357490876353 859 360591438788 860 363692001224 861 366837475244 862 369987713901 863 373182516203 864 376377318506 865 379622660156 866 382868366983 867 386159898758 868 389456307504 869 392799732947 870 396143170316 871 399538969092 872 402934774189 873 406378852329 874 409827996859 875 413325416998 876 416823305953 877 420375859356 878 423928412760 879 427530564210 880 431137951386 881 434796568222 882 438455185059 883 442170155020 884 445885124982 885 449652325092 886 453425371403 887 457250639249 888 461075907096 889 464960279657 890 468844740270 891 472783295131 892 476727514187 893 480726688969 894 484725865554 895 488785830046 896 492846223960 897 496963172398 898 501085961019 899 505265216124 900 509444472018 901 513688029581 902 517931589831 903 522233169741 904 526540904359 905 530908033707 906 535275618215 907 539708851646 908 544142085078 909 548636294964 910 553136791575 911 557698849352 912 562260907130 913 566891905719 914 571522918730 915 576216584085 916 580917221196 917 585681965824 918 590446811142 919 595282501356 920 600118191571 921 605020212752 922 609928968433 923 614903573128 924 619878185651 925 624927236528 926 629976792314 927 635093935292 928 640218066924 929 645411372154 930 650604677385 931 655874894439 932 661145221851 933 666486548885 934 671835086620 935 677254623976 936 682674712833 937 688174934726 938 693675156620 939 699248372185 940 704829065918 941 710484861298 942 716140656679 943 721878731137 944 727616806840 945 733431409552 946 739254439942 947 745154014788 948 751053589635 949 757039417791 950 763025254737 951 769090180725 952 775163105717 953 781316484399 954 787469863082 955 793711860319 956 799954446312 957 806279417147 958 812612690463 959 819028348620 960 825444130156 961 831953335983 962 838462542249 963 845056304207 964 851658657153 965 858347445905 966 865036855982 967 871821685939 968 878606515897 969 885480028210 970 892362398928 971 899334083197 972 906305767467 973 913377275403 974 920448915333 975 927611484035 976 934783888846 977 942049271976 978 949314655107 979 956682469354 980 964050302771 981 971514265095 982 978987725403 983 986556526846 984 994125328290 985 1001801387294 986 1009478131579 987 1017252639732 988 1025037078353 989 1032921432277 990 1040805787642 991 1048800917153 992 1056796046665 993 1064893628862 994 1073001346505 995 1081211666108 996 1089422706957 997 1097748875709 998 1106075044462 999 1114506205646 1000 1122947860109