0 0 1 4 2 34 3 113 4 268 5 524 6 905 7 1437 8 2145 9 3054 10 4189 11 5575 12 7238 13 9203 14 11494 15 14137 16 17157 17 20580 18 24429 19 28731 20 33510 21 38792 22 44602 23 50965 24 57906 25 65450 26 73622 27 82448 28 91952 29 102160 30 113097 31 124788 32 137258 33 150533 34 164636 35 179594 36 195432 37 212175 38 229847 39 248475 40 268083 41 288696 42 310339 43 333038 44 356818 45 381704 46 407720 47 434893 48 463247 49 492807 50 523599 51 555647 52 588977 53 623615 54 659584 55 696910 56 735619 57 775735 58 817283 59 860290 60 904779 61 950776 62 998306 63 1047394 64 1098066 65 1150347 66 1204260 67 1259833 68 1317090 69 1376055 70 1436755 71 1499214 72 1563458 73 1629511 74 1697398 75 1767146 76 1838778 77 1912321 78 1987799 79 2065237 80 2144661 81 2226095 82 2309565 83 2395096 84 2482713 85 2572441 86 2664305 87 2758331 88 2854543 89 2952967 90 3053628 91 3156551 92 3261761 93 3369283 94 3479142 95 3591364 96 3705973 97 3822996 98 3942456 99 4064379 100 4188790 101 4315715 102 4445178 103 4577204 104 4711819 105 4849048 106 4988916 107 5131448 108 5276669 109 5424605 110 5575280 111 5728719 112 5884949 113 6043993 114 6205877 115 6370626 116 6538266 117 6708821 118 6882316 119 7058778 120 7238229 121 7420697 122 7606206 123 7794781 124 7986448 125 8181231 126 8379155 127 8580247 128 8784530 129 8992030 130 9202772 131 9416782 132 9634083 133 9854703 134 10078665 135 10305995 136 10536717 137 10770858 138 11008442 139 11249495 140 11494040 141 11742105 142 11993713 143 12248890 144 12507661 145 12770051 146 13036085 147 13305788 148 13579187 149 13856304 150 14137167 151 14421799 152 14710227 153 15002475 154 15298568 155 15598531 156 15902390 157 16210170 158 16521895 159 16837592 160 17157285 161 17480999 162 17808759 163 18140591 164 18476519 165 18816569 166 19160766 167 19509135 168 19861702 169 20218490 170 20579526 171 20944835 172 21314441 173 21688370 174 22066647 175 22449298 176 22836346 177 23227818 178 23623738 179 24024132 180 24429024 181 24838441 182 25252407 183 25670946 184 26094085 185 26521849 186 26954262 187 27391349 188 27833137 189 28279649 190 28730912 191 29186950 192 29647788 193 30113452 194 30583966 195 31059356 196 31539647 197 32024864 198 32515032 199 33010176 200 33510322 201 34015494 202 34525718 203 35041019 204 35561421 205 36086951 206 36617633 207 37153493 208 37694554 209 38240844 210 38792386 211 39349206 212 39911329 213 40478780 214 41051585 215 41629768 216 42213354 217 42802369 218 43396838 219 43996786 220 44602238 221 45213219 222 45829755 223 46451870 224 47079589 225 47712938 226 48351943 227 48996627 228 49647016 229 50303135 230 50965010 231 51632666 232 52306127 233 52985419 234 53670567 235 54361596 236 55058531 237 55761397 238 56470220 239 57185025 240 57905836 241 58632679 242 59365579 243 60104561 244 60849651 245 61600872 246 62358252 247 63121814 248 63891583 249 64667586 250 65449847 251 66238391 252 67033243 253 67834429 254 68641973 255 69455901 256 70276238 257 71103009 258 71936239 259 72775953 260 73622177 261 74474935 262 75334252 263 76200155 264 77072667 265 77951815 266 78837623 267 79730116 268 80629319 269 81535258 270 82447958 271 83367443 272 84293740 273 85226872 274 86166866 275 87113746 276 88067538 277 89028266 278 89995956 279 90970634 280 91952323 281 92941049 282 93936837 283 94939713 284 95949702 285 96966828 286 97991117 287 99022594 288 100061284 289 101107213 290 102160404 291 103220885 292 104288678 293 105363811 294 106446307 295 107536193 296 108633493 297 109738232 298 110850435 299 111970128 300 113097336 301 114232083 302 115374395 303 116524298 304 117681816 305 118846974 306 120019797 307 121200311 308 122388541 309 123584512 310 124788249 311 125999777 312 127219121 313 128446307 314 129681359 315 130924303 316 132175164 317 133433966 318 134700736 319 135975498 320 137258277 321 138549099 322 139847989 323 141154971 324 142470071 325 143793314 326 145124725 327 146464329 328 147812152 329 149168219 330 150532554 331 151905182 332 153286130 333 154675422 334 156073083 335 157479139 336 158893613 337 160316533 338 161747922 339 163187806 340 164636210 341 166093159 342 167558679 343 169032794 344 170515529 345 172006910 346 173506962 347 175015710 348 176533179 349 178059394 350 179594380 351 181138163 352 182690767 353 184252218 354 185822541 355 187401761 356 188989903 357 190586993 358 192193055 359 193808114 360 195432196 361 197065326 362 198707528 363 200358829 364 202019253 365 203688825 366 205367571 367 207055515 368 208752683 369 210459099 370 212174790 371 213899780 372 215634094 373 217377758 374 219130796 375 220893233 376 222665096 377 224446408 378 226237196 379 228037483 380 229847296 381 231666659 382 233495598 383 235334138 384 237182303 385 239040120 386 240907612 387 242784806 388 244671726 389 246568398 390 248474846 391 250391096 392 252317173 393 254253102 394 256198908 395 258154617 396 260120253 397 262095841 398 264081407 399 266076976 400 268082573 401 270098223 402 272123951 403 274159783 404 276205743 405 278261857 406 280328149 407 282404646 408 284491371 409 286588351 410 288695610 411 290813173 412 292941066 413 295079313 414 297227941 415 299386973 416 301556436 417 303736353 418 305926751 419 308127655 420 310339089 421 312561079 422 314793649 423 317036826 424 319290634 425 321555098 426 323830244 427 326116096 428 328412680 429 330720020 430 333038143 431 335367072 432 337706834 433 340057454 434 342418955 435 344791365 436 347174707 437 349569006 438 351974289 439 354390580 440 356817905 441 359256288 442 361705754 443 364166329 444 366638038 445 369120905 446 371614957 447 374120218 448 376636713 449 379164468 450 381703507 451 384253857 452 386815540 453 389388584 454 391973014 455 394568853 456 397176128 457 399794863 458 402425084 459 405066816 460 407720083 461 410384912 462 413061327 463 415749353 464 418449016 465 421160340 466 423883351 467 426618074 468 429364534 469 432122756 470 434892765 471 437674587 472 440468246 473 443273768 474 446091178 475 448920500 476 451761761 477 454614985 478 457480197 479 460357422 480 463246686 481 466148014 482 469061431 483 471986962 484 474924631 485 477874465 486 480836489 487 483810727 488 486797204 489 489795947 490 492806979 491 495830326 492 498866014 493 501914066 494 504974510 495 508047368 496 511132668 497 514230433 498 517340690 499 520463462 500 523598776 501 526746656 502 529907127 503 533080215 504 536265945 505 539464342 506 542675431 507 545899237 508 549135785 509 552385101 510 555647209 511 558922135 512 562209904 513 565510541 514 568824071 515 572150519 516 575489911 517 578842271 518 582207624 519 585585997 520 588977413 521 592381898 522 595799478 523 599230177 524 602674020 525 606131033 526 609601240 527 613084667 528 616581340 529 620091282 530 623614519 531 627151077 532 630700981 533 634264255 534 637840924 535 641431015 536 645034551 537 648651559 538 652282063 539 655926089 540 659583661 541 663254805 542 666939545 543 670637907 544 674349917 545 678075599 546 681814978 547 685568079 548 689334929 549 693115551 550 696909970 551 700718213 552 704540304 553 708376268 554 712226131 555 716089917 556 719967652 557 723859361 558 727765068 559 731684800 560 735618581 561 739566436 562 743528390 563 747504470 564 751494699 565 755499103 566 759517706 567 763550535 568 767597615 569 771658969 570 775734624 571 779824605 572 783928937 573 788047644 574 792180753 575 796328288 576 800490274 577 804666737 578 808857701 579 813063192 580 817283234 581 821517854 582 825767076 583 830030925 584 834309427 585 838602606 586 842910487 587 847233097 588 851570459 589 855922600 590 860289543 591 864671315 592 869067941 593 873479445 594 877905853 595 882347189 596 886803480 597 891274749 598 895761023 599 900262326 600 904778684 601 909310122 602 913856664 603 918418336 604 922995163 605 927587170 606 932194383 607 936816826 608 941454525 609 946107504 610 950775789 611 955459406 612 960158378 613 964872731 614 969602491 615 974347683 616 979108331 617 983884461 618 988676097 619 993483266 620 998305992 621 1003144300 622 1007998216 623 1012867764 624 1017752970 625 1022653859 626 1027570455 627 1032502785 628 1037450873 629 1042414744 630 1047394424 631 1052389938 632 1057401310 633 1062428566 634 1067471731 635 1072530831 636 1077605889 637 1082696932 638 1087803985 639 1092927072 640 1098066219 641 1103221452 642 1108392794 643 1113580271 644 1118783909 645 1124003732 646 1129239766 647 1134492035 648 1139760566 649 1145045382 650 1150346510 651 1155663974 652 1160997799 653 1166348011 654 1171714635 655 1177097695 656 1182497217 657 1187913227 658 1193345748 659 1198794807 660 1204260429 661 1209742638 662 1215241460 663 1220756919 664 1226289042 665 1231837853 666 1237403377 667 1242985639 668 1248584665 669 1254200480 670 1259833108 671 1265482576 672 1271148907 673 1276832128 674 1282532263 675 1288249338 676 1293983377 677 1299734405 678 1305502449 679 1311287533 680 1317089682 681 1322908921 682 1328745275 683 1334598770 684 1340469431 685 1346357282 686 1352262350 687 1358184658 688 1364124233 689 1370081099 690 1376055281 691 1382046805 692 1388055696 693 1394081979 694 1400125678 695 1406186820 696 1412265429 697 1418361530 698 1424475149 699 1430606311 700 1436755040 701 1442921362 702 1449105303 703 1455306886 704 1461526138 705 1467763083 706 1474017747 707 1480290155 708 1486580331 709 1492888301 710 1499214091 711 1505557725 712 1511919228 713 1518298625 714 1524695943 715 1531111205 716 1537544437 717 1543995664 718 1550464911 719 1556952203 720 1563457566 721 1569981025 722 1576522604 723 1583082329 724 1589660225 725 1596256317 726 1602870631 727 1609503190 728 1616154022 729 1622823149 730 1629510599 731 1636216396 732 1642940564 733 1649683130 734 1656444118 735 1663223553 736 1670021461 737 1676837867 738 1683672796 739 1690526272 740 1697398322 741 1704288970 742 1711198241 743 1718126161 744 1725072754 745 1732038046 746 1739022062 747 1746024827 748 1753046366 749 1760086705 750 1767145868 751 1774223880 752 1781320767 753 1788436554 754 1795571266 755 1802724928 756 1809897565 757 1817089203 758 1824299866 759 1831529580 760 1838778369 761 1846046259 762 1853333276 763 1860639443 764 1867964787 765 1875309332 766 1882673104 767 1890056127 768 1897458427 769 1904880029 770 1912320959 771 1919781240 772 1927260899 773 1934759960 774 1942278449 775 1949816390 776 1957373810 777 1964950732 778 1972547183 779 1980163187 780 1987798769 781 1995453955 782 2003128770 783 2010823238 784 2018537385 785 2026271236 786 2034024817 787 2041798152 788 2049591266 789 2057404185 790 2065236934 791 2073089537 792 2080962021 793 2088854409 794 2096766728 795 2104699003 796 2112651258 797 2120623518 798 2128615809 799 2136628157 800 2144660585 801 2152713119 802 2160785785 803 2168878607 804 2176991611 805 2185124822 806 2193278264 807 2201451964 808 2209645945 809 2217860234 810 2226094855 811 2234349834 812 2242625195 813 2250920964 814 2259237167 815 2267573827 816 2275930970 817 2284308622 818 2292706807 819 2301125550 820 2309564878 821 2318024814 822 2326505384 823 2335006613 824 2343528527 825 2352071150 826 2360634507 827 2369218624 828 2377823526 829 2386449238 830 2395095785 831 2403763192 832 2412451484 833 2421160687 834 2429890825 835 2438641924 836 2447414009 837 2456207105 838 2465021237 839 2473856430 840 2482712710 841 2491590101 842 2500488628 843 2509408318 844 2518349194 845 2527311282 846 2536294608 847 2545299196 848 2554325071 849 2563372259 850 2572440785 851 2581530673 852 2590641949 853 2599774639 854 2608928766 855 2618104357 856 2627301437 857 2636520030 858 2645760162 859 2655021858 860 2664305142 861 2673610041 862 2682936580 863 2692284782 864 2701654675 865 2711046282 866 2720459628 867 2729894740 868 2739351642 869 2748830359 870 2758330916 871 2767853339 872 2777397653 873 2786963882 874 2796552052 875 2806162188 876 2815794315 877 2825448459 878 2835124644 879 2844822895 880 2854543238 881 2864285698 882 2874050300 883 2883837069 884 2893646031 885 2903477209 886 2913330630 887 2923206319 888 2933104300 889 2943024600 890 2952967242 891 2962932252 892 2972919656 893 2982929478 894 2992961744 895 3003016478 896 3013093706 897 3023193453 898 3033315744 899 3043460605 900 3053628059 901 3063818133 902 3074030852 903 3084266241 904 3094524324 905 3104805127 906 3115108676 907 3125434994 908 3135784108 909 3146156043 910 3156550823 911 3166968475 912 3177409022 913 3187872490 914 3198358904 915 3208868289 916 3219400672 917 3229956075 918 3240534526 919 3251136048 920 3261760667 921 3272408408 922 3283079297 923 3293773358 924 3304490616 925 3315231098 926 3325994826 927 3336781828 928 3347592128 929 3358425751 930 3369282723 931 3380163068 932 3391066811 933 3401993978 934 3412944594 935 3423918684 936 3434916273 937 3445937387 938 3456982049 939 3468050287 940 3479142123 941 3490257585 942 3501396697 943 3512559483 944 3523745970 945 3534956182 946 3546190145 947 3557447883 948 3568729422 949 3580034786 950 3591364002 951 3602717094 952 3614094087 953 3625495006 954 3636919877 955 3648368724 956 3659841573 957 3671338449 958 3682859378 959 3694404383 960 3705973491 961 3717566726 962 3729184113 963 3740825679 964 3752491447 965 3764181443 966 3775895692 967 3787634220 968 3799397050 969 3811184210 970 3822995723 971 3834831614 972 3846691910 973 3858576634 974 3870485813 975 3882419471 976 3894377634 977 3906360326 978 3918367572 979 3930399399 980 3942455830 981 3954536892 982 3966642609 983 3978773006 984 3990928109 985 4003107942 986 4015312531 987 4027541901 988 4039796077 989 4052075084 990 4064378947 991 4076707692 992 4089061343 993 4101439926 994 4113843466 995 4126271987 996 4138725516 997 4151204077 998 4163707696 999 4176236396 1000 4188790205