0 1 1 14 2 76 3 218 4 472 5 870 6 1444 7 2226 8 3248 9 4542 10 6140 11 8074 12 10376 13 13078 14 16212 15 19810 16 23904 17 28526 18 33708 19 39482 20 45880 21 52934 22 60676 23 69138 24 78352 25 88350 26 99164 27 110826 28 123368 29 136822 30 151220 31 166594 32 182976 33 200398 34 218892 35 238490 36 259224 37 281126 38 304228 39 328562 40 354160 41 381054 42 409276 43 438858 44 469832 45 502230 46 536084 47 571426 48 608288 49 646702 50 686700 51 728314 52 771576 53 816518 54 863172 55 911570 56 961744 57 1013726 58 1067548 59 1123242 60 1180840 61 1240374 62 1301876 63 1365378 64 1430912 65 1498510 66 1568204 67 1640026 68 1714008 69 1790182 70 1868580 71 1949234 72 2032176 73 2117438 74 2205052 75 2295050 76 2387464 77 2482326 78 2579668 79 2679522 80 2781920 81 2886894 82 2994476 83 3104698 84 3217592 85 3333190 86 3451524 87 3572626 88 3696528 89 3823262 90 3952860 91 4085354 92 4220776 93 4359158 94 4500532 95 4644930 96 4792384 97 4942926 98 5096588 99 5253402 100 5413400 101 5576614 102 5743076 103 5912818 104 6085872 105 6262270 106 6442044 107 6625226 108 6811848 109 7001942 110 7195540 111 7392674 112 7593376 113 7797678 114 8005612 115 8217210 116 8432504 117 8651526 118 8874308 119 9100882 120 9331280 121 9565534 122 9803676 123 10045738 124 10291752 125 10541750 126 10795764 127 11053826 128 11315968 129 11582222 130 11852620 131 12127194 132 12405976 133 12688998 134 12976292 135 13267890 136 13563824 137 13864126 138 14168828 139 14477962 140 14791560 141 15109654 142 15432276 143 15759458 144 16091232 145 16427630 146 16768684 147 17114426 148 17464888 149 17820102 150 18180100 151 18544914 152 18914576 153 19289118 154 19668572 155 20052970 156 20442344 157 20836726 158 21236148 159 21640642 160 22050240 161 22464974 162 22884876 163 23309978 164 23740312 165 24175910 166 24616804 167 25063026 168 25514608 169 25971582 170 26433980 171 26901834 172 27375176 173 27854038 174 28338452 175 28828450 176 29324064 177 29825326 178 30332268 179 30844922 180 31363320 181 31887494 182 32417476 183 32953298 184 33494992 185 34042590 186 34596124 187 35155626 188 35721128 189 36292662 190 36870260 191 37453954 192 38043776 193 38639758 194 39241932 195 39850330 196 40464984 197 41085926 198 41713188 199 42346802 200 42986800 201 43633214 202 44286076 203 44945418 204 45611272 205 46283670 206 46962644 207 47648226 208 48340448 209 49039342 210 49744940 211 50457274 212 51176376 213 51902278 214 52635012 215 53374610 216 54121104 217 54874526 218 55634908 219 56402282 220 57176680 221 57958134 222 58746676 223 59542338 224 60345152 225 61155150 226 61972364 227 62796826 228 63628568 229 64467622 230 65314020 231 66167794 232 67028976 233 67897598 234 68773692 235 69657290 236 70548424 237 71447126 238 72353428 239 73267362 240 74188960 241 75118254 242 76055276 243 77000058 244 77952632 245 78913030 246 79881284 247 80857426 248 81841488 249 82833502 250 83833500 251 84841514 252 85857576 253 86881718 254 87913972 255 88954370 256 90002944 257 91059726 258 92124748 259 93198042 260 94279640 261 95369574 262 96467876 263 97574578 264 98689712 265 99813310 266 100945404 267 102086026 268 103235208 269 104392982 270 105559380 271 106734434 272 107918176 273 109110638 274 110311852 275 111521850 276 112740664 277 113968326 278 115204868 279 116450322 280 117704720 281 118968094 282 120240476 283 121521898 284 122812392 285 124111990 286 125420724 287 126738626 288 128065728 289 129402062 290 130747660 291 132102554 292 133466776 293 134840358 294 136223332 295 137615730 296 139017584 297 140428926 298 141849788 299 143280202 300 144720200 301 146169814 302 147629076 303 149098018 304 150576672 305 152065070 306 153563244 307 155071226 308 156589048 309 158116742 310 159654340 311 161201874 312 162759376 313 164326878 314 165904412 315 167492010 316 169089704 317 170697526 318 172315508 319 173943682 320 175582080 321 177230734 322 178889676 323 180558938 324 182238552 325 183928550 326 185628964 327 187339826 328 189061168 329 190793022 330 192535420 331 194288394 332 196051976 333 197826198 334 199611092 335 201406690 336 203213024 337 205030126 338 206858028 339 208696762 340 210546360 341 212406854 342 214278276 343 216160658 344 218054032 345 219958430 346 221873884 347 223800426 348 225738088 349 227686902 350 229646900 351 231618114 352 233600576 353 235594318 354 237599372 355 239615770 356 241643544 357 243682726 358 245733348 359 247795442 360 249869040 361 251954174 362 254050876 363 256159178 364 258279112 365 260410710 366 262554004 367 264709026 368 266875808 369 269054382 370 271244780 371 273447034 372 275661176 373 277887238 374 280125252 375 282375250 376 284637264 377 286911326 378 289197468 379 291495722 380 293806120 381 296128694 382 298463476 383 300810498 384 303169792 385 305541390 386 307925324 387 310321626 388 312730328 389 315151462 390 317585060 391 320031154 392 322489776 393 324960958 394 327444732 395 329941130 396 332450184 397 334971926 398 337506388 399 340053602 400 342613600 401 345186414 402 347772076 403 350370618 404 352982072 405 355606470 406 358243844 407 360894226 408 363557648 409 366234142 410 368923740 411 371626474 412 374342376 413 377071478 414 379813812 415 382569410 416 385338304 417 388120526 418 390916108 419 393725082 420 396547480 421 399383334 422 402232676 423 405095538 424 407971952 425 410861950 426 413765564 427 416682826 428 419613768 429 422558422 430 425516820 431 428488994 432 431474976 433 434474798 434 437488492 435 440516090 436 443557624 437 446613126 438 449682628 439 452766162 440 455863760 441 458975454 442 462101276 443 465241258 444 468395432 445 471563830 446 474746484 447 477943426 448 481154688 449 484380302 450 487620300 451 490874714 452 494143576 453 497426918 454 500724772 455 504037170 456 507364144 457 510705726 458 514061948 459 517432842 460 520818440 461 524218774 462 527633876 463 531063778 464 534508512 465 537968110 466 541442604 467 544932026 468 548436408 469 551955782 470 555490180 471 559039634 472 562604176 473 566183838 474 569778652 475 573388650 476 577013864 477 580654326 478 584310068 479 587981122 480 591667520 481 595369294 482 599086476 483 602819098 484 606567192 485 610330790 486 614109924 487 617904626 488 621714928 489 625540862 490 629382460 491 633239754 492 637112776 493 641001558 494 644906132 495 648826530 496 652762784 497 656714926 498 660682988 499 664667002 500 668667000 501 672683014 502 676715076 503 680763218 504 684827472 505 688907870 506 693004444 507 697117226 508 701246248 509 705391542 510 709553140 511 713731074 512 717925376 513 722136078 514 726363212 515 730606810 516 734866904 517 739143526 518 743436708 519 747746482 520 752072880 521 756415934 522 760775676 523 765152138 524 769545352 525 773955350 526 778382164 527 782825826 528 787286368 529 791763822 530 796258220 531 800769594 532 805297976 533 809843398 534 814405892 535 818985490 536 823582224 537 828196126 538 832827228 539 837475562 540 842141160 541 846824054 542 851524276 543 856241858 544 860976832 545 865729230 546 870499084 547 875286426 548 880091288 549 884913702 550 889753700 551 894611314 552 899486576 553 904379518 554 909290172 555 914218570 556 919164744 557 924128726 558 929110548 559 934110242 560 939127840 561 944163374 562 949216876 563 954288378 564 959377912 565 964485510 566 969611204 567 974755026 568 979917008 569 985097182 570 990295580 571 995512234 572 1000747176 573 1006000438 574 1011272052 575 1016562050 576 1021870464 577 1027197326 578 1032542668 579 1037906522 580 1043288920 581 1048689894 582 1054109476 583 1059547698 584 1065004592 585 1070480190 586 1075974524 587 1081487626 588 1087019528 589 1092570262 590 1098139860 591 1103728354 592 1109335776 593 1114962158 594 1120607532 595 1126271930 596 1131955384 597 1137657926 598 1143379588 599 1149120402 600 1154880400 601 1160659614 602 1166458076 603 1172275818 604 1178112872 605 1183969270 606 1189845044 607 1195740226 608 1201654848 609 1207588942 610 1213542540 611 1219515674 612 1225508376 613 1231520678 614 1237552612 615 1243604210 616 1249675504 617 1255766526 618 1261877308 619 1268007882 620 1274158280 621 1280328534 622 1286518676 623 1292728738 624 1298958752 625 1305208750 626 1311478764 627 1317768826 628 1324078968 629 1330409222 630 1336759620 631 1343130194 632 1349520976 633 1355931998 634 1362363292 635 1368814890 636 1375286824 637 1381779126 638 1388291828 639 1394824962 640 1401378560 641 1407952654 642 1414547276 643 1421162458 644 1427798232 645 1434454630 646 1441131684 647 1447829426 648 1454547888 649 1461287102 650 1468047100 651 1474827914 652 1481629576 653 1488452118 654 1495295572 655 1502159970 656 1509045344 657 1515951726 658 1522879148 659 1529827642 660 1536797240 661 1543787974 662 1550799876 663 1557832978 664 1564887312 665 1571962910 666 1579059804 667 1586178026 668 1593317608 669 1600478582 670 1607660980 671 1614864834 672 1622090176 673 1629337038 674 1636605452 675 1643895450 676 1651207064 677 1658540326 678 1665895268 679 1673271922 680 1680670320 681 1688090494 682 1695532476 683 1702996298 684 1710481992 685 1717989590 686 1725519124 687 1733070626 688 1740644128 689 1748239662 690 1755857260 691 1763496954 692 1771158776 693 1778842758 694 1786548932 695 1794277330 696 1802027984 697 1809800926 698 1817596188 699 1825413802 700 1833253800 701 1841116214 702 1849001076 703 1856908418 704 1864838272 705 1872790670 706 1880765644 707 1888763226 708 1896783448 709 1904826342 710 1912891940 711 1920980274 712 1929091376 713 1937225278 714 1945382012 715 1953561610 716 1961764104 717 1969989526 718 1978237908 719 1986509282 720 1994803680 721 2003121134 722 2011461676 723 2019825338 724 2028212152 725 2036622150 726 2045055364 727 2053511826 728 2061991568 729 2070494622 730 2079021020 731 2087570794 732 2096143976 733 2104740598 734 2113360692 735 2122004290 736 2130671424 737 2139362126 738 2148076428 739 2156814362 740 2165575960 741 2174361254 742 2183170276 743 2192003058 744 2200859632 745 2209740030 746 2218644284 747 2227572426 748 2236524488 749 2245500502 750 2254500500 751 2263524514 752 2272572576 753 2281644718 754 2290740972 755 2299861370 756 2309005944 757 2318174726 758 2327367748 759 2336585042 760 2345826640 761 2355092574 762 2364382876 763 2373697578 764 2383036712 765 2392400310 766 2401788404 767 2411201026 768 2420638208 769 2430099982 770 2439586380 771 2449097434 772 2458633176 773 2468193638 774 2477778852 775 2487388850 776 2497023664 777 2506683326 778 2516367868 779 2526077322 780 2535811720 781 2545571094 782 2555355476 783 2565164898 784 2574999392 785 2584858990 786 2594743724 787 2604653626 788 2614588728 789 2624549062 790 2634534660 791 2644545554 792 2654581776 793 2664643358 794 2674730332 795 2684842730 796 2694980584 797 2705143926 798 2715332788 799 2725547202 800 2735787200 801 2746052814 802 2756344076 803 2766661018 804 2777003672 805 2787372070 806 2797766244 807 2808186226 808 2818632048 809 2829103742 810 2839601340 811 2850124874 812 2860674376 813 2871249878 814 2881851412 815 2892479010 816 2903132704 817 2913812526 818 2924518508 819 2935250682 820 2946009080 821 2956793734 822 2967604676 823 2978441938 824 2989305552 825 3000195550 826 3011111964 827 3022054826 828 3033024168 829 3044020022 830 3055042420 831 3066091394 832 3077166976 833 3088269198 834 3099398092 835 3110553690 836 3121736024 837 3132945126 838 3144181028 839 3155443762 840 3166733360 841 3178049854 842 3189393276 843 3200763658 844 3212161032 845 3223585430 846 3235036884 847 3246515426 848 3258021088 849 3269553902 850 3281113900 851 3292701114 852 3304315576 853 3315957318 854 3327626372 855 3339322770 856 3351046544 857 3362797726 858 3374576348 859 3386382442 860 3398216040 861 3410077174 862 3421965876 863 3433882178 864 3445826112 865 3457797710 866 3469797004 867 3481824026 868 3493878808 869 3505961382 870 3518071780 871 3530210034 872 3542376176 873 3554570238 874 3566792252 875 3579042250 876 3591320264 877 3603626326 878 3615960468 879 3628322722 880 3640713120 881 3653131694 882 3665578476 883 3678053498 884 3690556792 885 3703088390 886 3715648324 887 3728236626 888 3740853328 889 3753498462 890 3766172060 891 3778874154 892 3791604776 893 3804363958 894 3817151732 895 3829968130 896 3842813184 897 3855686926 898 3868589388 899 3881520602 900 3894480600 901 3907469414 902 3920487076 903 3933533618 904 3946609072 905 3959713470 906 3972846844 907 3986009226 908 3999200648 909 4012421142 910 4025670740 911 4038949474 912 4052257376 913 4065594478 914 4078960812 915 4092356410 916 4105781304 917 4119235526 918 4132719108 919 4146232082 920 4159774480 921 4173346334 922 4186947676 923 4200578538 924 4214238952 925 4227928950 926 4241648564 927 4255397826 928 4269176768 929 4282985422 930 4296823820 931 4310691994 932 4324589976 933 4338517798 934 4352475492 935 4366463090 936 4380480624 937 4394528126 938 4408605628 939 4422713162 940 4436850760 941 4451018454 942 4465216276 943 4479444258 944 4493702432 945 4507990830 946 4522309484 947 4536658426 948 4551037688 949 4565447302 950 4579887300 951 4594357714 952 4608858576 953 4623389918 954 4637951772 955 4652544170 956 4667167144 957 4681820726 958 4696504948 959 4711219842 960 4725965440 961 4740741774 962 4755548876 963 4770386778 964 4785255512 965 4800155110 966 4815085604 967 4830047026 968 4845039408 969 4860062782 970 4875117180 971 4890202634 972 4905319176 973 4920466838 974 4935645652 975 4950855650 976 4966096864 977 4981369326 978 4996673068 979 5012008122 980 5027374520 981 5042772294 982 5058201476 983 5073662098 984 5089154192 985 5104677790 986 5120232924 987 5135819626 988 5151437928 989 5167087862 990 5182769460 991 5198482754 992 5214227776 993 5230004558 994 5245813132 995 5261653530 996 5277525784 997 5293429926 998 5309365988 999 5325334002 1000 5341334000