0 1 1 5 2 14 3 30 4 55 5 91 6 140 7 204 8 285 9 385 10 506 11 651 12 823 13 1024 14 1256 15 1521 16 1821 17 2158 18 2534 19 2952 20 3415 21 3925 22 4485 23 5098 24 5766 25 6491 26 7275 27 8120 28 9028 29 10002 30 11046 31 12162 32 13351 33 14616 34 15960 35 17385 36 18893 37 20486 38 22167 39 23939 40 25805 41 27768 42 29829 43 31989 44 34251 45 36618 46 39092 47 41675 48 44370 49 47180 50 50106 51 53150 52 56315 53 59602 54 63012 55 66548 56 70213 57 74010 58 77943 59 82016 60 86231 61 90589 62 95093 63 99746 64 104549 65 109503 66 114611 67 119877 68 125304 69 130894 70 136649 71 142570 72 148658 73 154916 74 161347 75 167952 76 174733 77 181695 78 188842 79 196175 80 203696 81 211408 82 219312 83 227409 84 235702 85 244194 86 252887 87 261784 88 270889 89 280204 90 289730 91 299470 92 309427 93 319602 94 329996 95 340613 96 351458 97 362533 98 373839 99 385379 100 397155 101 409168 102 421421 103 433917 104 446657 105 459643 106 472880 107 486371 108 500115 109 514113 110 528369 111 542885 112 557662 113 572703 114 588012 115 603592 116 619446 117 635578 118 651990 119 668682 120 685656 121 702916 122 720464 123 738301 124 756431 125 774859 126 793586 127 812612 128 831940 129 851572 130 871508 131 891750 132 912302 133 933167 134 954348 135 975850 136 997676 137 1019825 138 1042298 139 1065099 140 1088230 141 1111691 142 1135484 143 1159614 144 1184085 145 1208899 146 1234059 147 1259567 148 1285423 149 1311629 150 1338189 151 1365105 152 1392378 153 1420012 154 1448013 155 1476383 156 1505122 157 1534233 158 1563718 159 1593577 160 1623812 161 1654427 162 1685425 163 1716808 164 1748579 165 1780741 166 1813294 167 1846239 168 1879580 169 1913319 170 1947456 171 1981994 172 2016939 173 2052295 174 2088063 175 2124245 176 2160844 177 2197861 178 2235298 179 2273159 180 2311446 181 2350160 182 2389305 183 2428886 184 2468904 185 2509358 186 2550250 187 2591583 188 2633358 189 2675577 190 2718245 191 2761366 192 2804942 193 2848976 194 2893471 195 2938427 196 2983844 197 3029725 198 3076073 199 3122889 200 3170176 201 3217940 202 3266184 203 3314908 204 3364114 205 3413805 206 3463982 207 3514646 208 3565800 209 3617448 210 3669593 211 3722239 212 3775391 213 3829050 214 3883215 215 3937888 216 3993072 217 4048768 218 4104977 219 4161703 220 4218951 221 4276723 222 4335021 223 4393848 224 4453204 225 4513089 226 4573506 227 4634458 228 4695947 229 4757976 230 4820550 231 4883673 232 4947346 233 5011571 234 5076351 235 5141687 236 5207580 237 5274033 238 5341050 239 5408634 240 5476787 241 5545512 242 5614811 243 5684684 244 5755133 245 5826161 246 5897769 247 5969959 248 6042736 249 6116105 250 6190068 251 6264626 252 6339781 253 6415534 254 6491886 255 6568840 256 6646399 257 6724565 258 6803341 259 6882731 260 6962738 261 7043363 262 7124607 263 7206472 264 7288960 265 7372073 266 7455815 267 7540191 268 7625204 269 7710856 270 7797150 271 7884088 272 7971670 273 8059897 274 8148771 275 8238294 276 8328469 277 8419301 278 8510794 279 8602949 280 8695767 281 8789250 282 8883399 283 8978215 284 9073700 285 9169857 286 9266690 287 9364203 288 9462400 289 9561284 290 9660856 291 9761117 292 9862069 293 9963714 294 10066054 295 10169092 296 10272832 297 10377277 298 10482429 299 10588291 300 10694865 301 10802151 302 10910150 303 11018864 304 11128296 305 11238450 306 11349330 307 11460939 308 11573279 309 11686352 310 11800160 311 11914704 312 12029985 313 12146005 314 12262767 315 12380275 316 12498532 317 12617540 318 12737301 319 12857817 320 12979090 321 13101122 322 13223915 323 13347472 324 13471797 325 13596894 326 13722766 327 13849415 328 13976843 329 14105051 330 14234040 331 14363812 332 14494369 333 14625714 334 14757851 335 14890783 336 15024512 337 15159040 338 15294369 339 15430500 340 15567433 341 15705170 342 15843715 343 15983072 344 16123245 345 16264237 346 16406050 347 16548686 348 16692147 349 16836435 350 16981551 351 17127496 352 17274274 353 17421890 354 17570347 355 17719647 356 17869792 357 18020784 358 18172624 359 18325313 360 18478853 361 18633246 362 18788495 363 18944605 364 19101580 365 19259422 366 19418133 367 19577715 368 19738169 369 19899495 370 20061695 371 20224773 372 20388732 373 20553574 374 20719302 375 20885919 376 21053427 377 21221828 378 21391124 379 21561316 380 21732406 381 21904399 382 22077300 383 22251111 384 22425833 385 22601469 386 22778022 387 22955493 388 23133883 389 23313194 390 23493428 391 23674588 392 23856678 393 24039701 394 24223658 395 24408550 396 24594380 397 24781150 398 24968860 399 25157513 400 25347114 401 25537666 402 25729171 403 25921632 404 26115052 405 26309432 406 26504773 407 26701078 408 26898349 409 27096588 410 27295800 411 27495989 412 27697156 413 27899302 414 28102430 415 28306543 416 28511641 417 28717724 418 28924796 419 29132861 420 29341922 421 29551983 422 29763047 423 29975115 424 30188188 425 30402269 426 30617360 427 30833460 428 31050571 429 31268699 430 31487847 431 31708016 432 31929209 433 32151429 434 32374677 435 32598954 436 32824263 437 33050607 438 33277988 439 33506410 440 33735878 441 33966394 442 34197959 443 34430576 444 34664248 445 34898975 446 35134757 447 35371598 448 35609502 449 35848470 450 36088504 451 36329608 452 36571784 453 36815033 454 37059358 455 37304761 456 37551242 457 37798804 458 38047453 459 38297192 460 38548021 461 38799942 462 39052959 463 39307074 464 39562288 465 39818604 466 40076025 467 40334553 468 40594191 469 40854943 470 41116811 471 41379795 472 41643897 473 41909121 474 42175468 475 42442939 476 42711539 477 42981272 478 43252139 479 43524142 480 43797285 481 44071570 482 44346997 483 44623568 484 44901286 485 45180152 486 45460169 487 45741342 488 46023673 489 46307162 490 46591811 491 46877624 492 47164603 493 47452748 494 47742062 495 48032550 496 48324215 497 48617060 498 48911089 499 49206304 500 49502705 501 49800294 502 50099075 503 50399049 504 50700216 505 51002580 506 51306145 507 51610912 508 51916883 509 52224062 510 52532451 511 52842050 512 53152861 513 53464888 514 53778133 515 54092598 516 54408287 517 54725203 518 55043347 519 55362721 520 55683329 521 56005173 522 56328253 523 56652572 524 56978135 525 57304944 526 57633000 527 57962306 528 58292865 529 58624678 530 58957747 531 59292076 532 59627667 533 59964521 534 60302642 535 60642034 536 60982698 537 61324635 538 61667848 539 62012340 540 62358112 541 62705166 542 63053506 543 63403134 544 63754051 545 64106260 546 64459764 547 64814564 548 65170661 549 65528058 550 65886758 551 66246763 552 66608077 553 66970705 554 67334649 555 67699910 556 68066491 557 68434395 558 68803623 559 69174176 560 69546057 561 69919269 562 70293814 563 70669695 564 71046915 565 71425475 566 71805376 567 72186621 568 72569213 569 72953153 570 73338443 571 73725087 572 74113088 573 74502448 574 74893170 575 75285257 576 75678710 577 76073530 578 76469720 579 76867283 580 77266221 581 77666537 582 78068234 583 78471314 584 78875779 585 79281632 586 79688876 587 80097512 588 80507541 589 80918967 590 81331794 591 81746024 592 82161659 593 82578701 594 82997152 595 83417014 596 83838290 597 84260983 598 84685094 599 85110625 600 85537580 601 85965961 602 86395769 603 86827006 604 87259674 605 87693775 606 88129311 607 88566285 608 89004701 609 89444562 610 89885871 611 90328631 612 90772844 613 91218512 614 91665637 615 92114221 616 92564266 617 93015774 618 93468749 619 93923195 620 94379113 621 94836504 622 95295370 623 95755713 624 96217535 625 96680838 626 97145624 627 97611896 628 98079658 629 98548914 630 99019666 631 99491915 632 99965663 633 100440912 634 100917664 635 101395921 636 101875685 637 102356959 638 102839747 639 103324052 640 103809876 641 104297221 642 104786089 643 105276482 644 105768402 645 106261851 646 106756832 647 107253349 648 107751405 649 108251002 650 108752142 651 109254827 652 109759059 653 110264840 654 110772172 655 111281057 656 111791498 657 112303499 658 112817062 659 113332187 660 113848876 661 114367132 662 114886957 663 115408353 664 115931322 665 116455867 666 116981992 667 117509701 668 118038997 669 118569881 670 119102354 671 119636419 672 120172079 673 120709336 674 121248192 675 121788650 676 122330714 677 122874386 678 123419667 679 123966559 680 124515063 681 125065180 682 125616913 683 126170265 684 126725239 685 127281839 686 127840069 687 128399931 688 128961425 689 129524553 690 130089318 691 130655721 692 131223763 693 131793447 694 132364777 695 132937757 696 133512390 697 134088678 698 134666622 699 135246223 700 135827484 701 136410408 702 136994996 703 137581250 704 138169175 705 138758776 706 139350055 707 139943013 708 140537652 709 141133973 710 141731977 711 142331667 712 142933046 713 143536116 714 144140880 715 144747342 716 145355504 717 145965366 718 146576930 719 147190199 720 147805174 721 148421856 722 149040249 723 149660358 724 150282186 725 150905735 726 151531008 727 152158007 728 152786733 729 153417189 730 154049378 731 154683301 732 155318960 733 155956360 734 156595505 735 157236395 736 157879030 737 158523413 738 159169546 739 159817430 740 160467068 741 161118464 742 161771621 743 162426542 744 163083231 745 163741690 746 164401918 747 165063916 748 165727688 749 166393236 750 167060561 751 167729667 752 168400559 753 169073239 754 169747708 755 170423969 756 171102024 757 171781873 758 172463518 759 173146963 760 173832211 761 174519265 762 175208130 763 175898810 764 176591305 765 177285615 766 177981743 767 178679691 768 179379459 769 180081049 770 180784466 771 181489714 772 182196795 773 182905712 774 183616467 775 184329059 776 185043489 777 185759761 778 186477877 779 187197838 780 187919648 781 188643313 782 189368836 783 190096218 784 190825462 785 191556570 786 192289542 787 193024380 788 193761088 789 194499669 790 195240125 791 195982459 792 196726675 793 197472774 794 198220756 795 198970624 796 199722380 797 200476024 798 201231559 799 201988991 800 202748324 801 203509559 802 204272698 803 205037744 804 205804697 805 206573558 806 207344331 807 208117018 808 208891620 809 209668141 810 210446586 811 211226957 812 212009254 813 212793479 814 213579635 815 214367723 816 215157745 817 215949706 818 216743610 819 217539459 820 218337256 821 219137005 822 219938707 823 220742361 824 221547969 825 222355534 826 223165057 827 223976541 828 224789992 829 225605413 830 226422804 831 227242167 832 228063505 833 228886818 834 229712106 835 230539372 836 231368620 837 232199853 838 233033075 839 233868291 840 234705503 841 235544711 842 236385917 843 237229124 844 238074333 845 238921545 846 239770764 847 240621995 848 241475240 849 242330501 850 243187782 851 244047084 852 244908406 853 245771750 854 246637119 855 247504515 856 248373941 857 249245402 858 250118902 859 250994442 860 251872024 861 252751651 862 253633323 863 254517040 864 255402805 865 256290622 866 257180494 867 258072423 868 258966412 869 259862464 870 260760580 871 261660762 872 262563013 873 263467334 874 264373727 875 265282197 876 266192749 877 267105385 878 268020106 879 268936915 880 269855814 881 270776803 882 271699884 883 272625060 884 273552333 885 274481706 886 275413183 887 276346767 888 277282459 889 278220260 890 279160172 891 280102196 892 281046333 893 281992587 894 282940963 895 283891464 896 284844092 897 285798850 898 286755741 899 287714766 900 288675926 901 289639223 902 290604659 903 291572237 904 292541962 905 293513838 906 294487866 907 295464047 908 296442384 909 297422879 910 298405532 911 299390344 912 300377318 913 301366458 914 302357768 915 303351252 916 304346913 917 305344752 918 306344770 919 307346969 920 308351350 921 309357914 922 310366664 923 311377604 924 312390737 925 313406065 926 314423591 927 315443318 928 316465247 929 317489379 930 318515716 931 319544261 932 320575018 933 321607991 934 322643183 935 323680596 936 324720232 937 325762094 938 326806184 939 327852502 940 328901049 941 329951828 942 331004843 943 332060097 944 333117592 945 334177330 946 335239313 947 336303543 948 337370022 949 338438751 950 339509732 951 340582969 952 341658466 953 342736226 954 343816251 955 344898543 956 345983104 957 347069936 958 348159041 959 349250421 960 350344079 961 351440019 962 352538244 963 353638756 964 354741557 965 355846649 966 356954034 967 358063713 968 359175687 969 360289959 970 361406533 971 362525413 972 363646602 973 364770102 974 365895915 975 367024043 976 368154488 977 369287251 978 370422332 979 371559734 980 372699462 981 373841519 982 374985907 983 376132628 984 377281684 985 378433077 986 379586809 987 380742882 988 381901298 989 383062060 990 384225173 991 385390641 992 386558466 993 387728650 994 388901195 995 390076103 996 391253375 997 392433012 998 393615017 999 394799393 1000 395986142