0 2 1 12 2 52 3 140 4 294 5 532 6 872 7 1332 8 1930 9 2684 10 3612 11 4732 12 6062 13 7620 14 9424 15 11492 16 13842 17 16492 18 19460 19 22764 20 26422 21 30452 22 34872 23 39700 24 44954 25 50652 26 56812 27 63452 28 70590 29 78244 30 86432 31 95172 32 104482 33 114380 34 124884 35 136012 36 147782 37 160212 38 173320 39 187124 40 201642 41 216892 42 232892 43 249660 44 267214 45 285572 46 304752 47 324772 48 345650 49 367404 50 390052 51 413612 52 438102 53 463540 54 489944 55 517332 56 545722 57 575132 58 605580 59 637084 60 669662 61 703332 62 738112 63 774020 64 811074 65 849292 66 888692 67 929292 68 971110 69 1014164 70 1058472 71 1104052 72 1150922 73 1199100 74 1248604 75 1299452 76 1351662 77 1405252 78 1460240 79 1516644 80 1574482 81 1633772 82 1694532 83 1756780 84 1820534 85 1885812 86 1952632 87 2021012 88 2090970 89 2162524 90 2235692 91 2310492 92 2386942 93 2465060 94 2544864 95 2626372 96 2709602 97 2794572 98 2881300 99 2969804 100 3060102 101 3152212 102 3246152 103 3341940 104 3439594 105 3539132 106 3640572 107 3743932 108 3849230 109 3956484 110 4065712 111 4176932 112 4290162 113 4405420 114 4522724 115 4642092 116 4763542 117 4887092 118 5012760 119 5140564 120 5270522 121 5402652 122 5536972 123 5673500 124 5812254 125 5953252 126 6096512 127 6242052 128 6389890 129 6540044 130 6692532 131 6847372 132 7004582 133 7164180 134 7326184 135 7490612 136 7657482 137 7826812 138 7998620 139 8172924 140 8349742 141 8529092 142 8710992 143 8895460 144 9082514 145 9272172 146 9464452 147 9659372 148 9856950 149 10057204 150 10260152 151 10465812 152 10674202 153 10885340 154 11099244 155 11315932 156 11535422 157 11757732 158 11982880 159 12210884 160 12441762 161 12675532 162 12912212 163 13151820 164 13394374 165 13639892 166 13888392 167 14139892 168 14394410 169 14651964 170 14912572 171 15176252 172 15443022 173 15712900 174 15985904 175 16262052 176 16541362 177 16823852 178 17109540 179 17398444 180 17690582 181 17985972 182 18284632 183 18586580 184 18891834 185 19200412 186 19512332 187 19827612 188 20146270 189 20468324 190 20793792 191 21122692 192 21455042 193 21790860 194 22130164 195 22472972 196 22819302 197 23169172 198 23522600 199 23879604 200 24240202 201 24604412 202 24972252 203 25343740 204 25718894 205 26097732 206 26480272 207 26866532 208 27256530 209 27650284 210 28047812 211 28449132 212 28854262 213 29263220 214 29676024 215 30092692 216 30513242 217 30937692 218 31366060 219 31798364 220 32234622 221 32674852 222 33119072 223 33567300 224 34019554 225 34475852 226 34936212 227 35400652 228 35869190 229 36341844 230 36818632 231 37299572 232 37784682 233 38273980 234 38767484 235 39265212 236 39767182 237 40273412 238 40783920 239 41298724 240 41817842 241 42341292 242 42869092 243 43401260 244 43937814 245 44478772 246 45024152 247 45573972 248 46128250 249 46687004 250 47250252 251 47818012 252 48390302 253 48967140 254 49548544 255 50134532 256 50725122 257 51320332 258 51920180 259 52524684 260 53133862 261 53747732 262 54366312 263 54989620 264 55617674 265 56250492 266 56888092 267 57530492 268 58177710 269 58829764 270 59486672 271 60148452 272 60815122 273 61486700 274 62163204 275 62844652 276 63531062 277 64222452 278 64918840 279 65620244 280 66326682 281 67038172 282 67754732 283 68476380 284 69203134 285 69935012 286 70672032 287 71414212 288 72161570 289 72914124 290 73671892 291 74434892 292 75203142 293 75976660 294 76755464 295 77539572 296 78329002 297 79123772 298 79923900 299 80729404 300 81540302 301 82356612 302 83178352 303 84005540 304 84838194 305 85676332 306 86519972 307 87369132 308 88223830 309 89084084 310 89949912 311 90821332 312 91698362 313 92581020 314 93469324 315 94363292 316 95262942 317 96168292 318 97079360 319 97996164 320 98918722 321 99847052 322 100781172 323 101721100 324 102666854 325 103618452 326 104575912 327 105539252 328 106508490 329 107483644 330 108464732 331 109451772 332 110444782 333 111443780 334 112448784 335 113459812 336 114476882 337 115500012 338 116529220 339 117564524 340 118605942 341 119653492 342 120707192 343 121767060 344 122833114 345 123905372 346 124983852 347 126068572 348 127159550 349 128256804 350 129360352 351 130470212 352 131586402 353 132708940 354 133837844 355 134973132 356 136114822 357 137262932 358 138417480 359 139578484 360 140745962 361 141919932 362 143100412 363 144287420 364 145480974 365 146681092 366 147887792 367 149101092 368 150321010 369 151547564 370 152780772 371 154020652 372 155267222 373 156520500 374 157780504 375 159047252 376 160320762 377 161601052 378 162888140 379 164182044 380 165482782 381 166790372 382 168104832 383 169426180 384 170754434 385 172089612 386 173431732 387 174780812 388 176136870 389 177499924 390 178869992 391 180247092 392 181631242 393 183022460 394 184420764 395 185826172 396 187238702 397 188658372 398 190085200 399 191519204 400 192960402 401 194408812 402 195864452 403 197327340 404 198797494 405 200274932 406 201759672 407 203251732 408 204751130 409 206257884 410 207772012 411 209293532 412 210822462 413 212358820 414 213902624 415 215453892 416 217012642 417 218578892 418 220152660 419 221733964 420 223322822 421 224919252 422 226523272 423 228134900 424 229754154 425 231381052 426 233015612 427 234657852 428 236307790 429 237965444 430 239630832 431 241303972 432 242984882 433 244673580 434 246370084 435 248074412 436 249786582 437 251506612 438 253234520 439 254970324 440 256714042 441 258465692 442 260225292 443 261992860 444 263768414 445 265551972 446 267343552 447 269143172 448 270950850 449 272766604 450 274590452 451 276422412 452 278262502 453 280110740 454 281967144 455 283831732 456 285704522 457 287585532 458 289474780 459 291372284 460 293278062 461 295192132 462 297114512 463 299045220 464 300984274 465 302931692 466 304887492 467 306851692 468 308824310 469 310805364 470 312794872 471 314792852 472 316799322 473 318814300 474 320837804 475 322869852 476 324910462 477 326959652 478 329017440 479 331083844 480 333158882 481 335242572 482 337334932 483 339435980 484 341545734 485 343664212 486 345791432 487 347927412 488 350072170 489 352225724 490 354388092 491 356559292 492 358739342 493 360928260 494 363126064 495 365332772 496 367548402 497 369772972 498 372006500 499 374249004 500 376500502 501 378761012 502 381030552 503 383309140 504 385596794 505 387893532 506 390199372 507 392514332 508 394838430 509 397171684 510 399514112 511 401865732 512 404226562 513 406596620 514 408975924 515 411364492 516 413762342 517 416169492 518 418585960 519 421011764 520 423446922 521 425891452 522 428345372 523 430808700 524 433281454 525 435763652 526 438255312 527 440756452 528 443267090 529 445787244 530 448316932 531 450856172 532 453404982 533 455963380 534 458531384 535 461109012 536 463696282 537 466293212 538 468899820 539 471516124 540 474142142 541 476777892 542 479423392 543 482078660 544 484743714 545 487418572 546 490103252 547 492797772 548 495502150 549 498216404 550 500940552 551 503674612 552 506418602 553 509172540 554 511936444 555 514710332 556 517494222 557 520288132 558 523092080 559 525906084 560 528730162 561 531564332 562 534408612 563 537263020 564 540127574 565 543002292 566 545887192 567 548782292 568 551687610 569 554603164 570 557528972 571 560465052 572 563411422 573 566368100 574 569335104 575 572312452 576 575300162 577 578298252 578 581306740 579 584325644 580 587354982 581 590394772 582 593445032 583 596505780 584 599577034 585 602658812 586 605751132 587 608854012 588 611967470 589 615091524 590 618226192 591 621371492 592 624527442 593 627694060 594 630871364 595 634059372 596 637258102 597 640467572 598 643687800 599 646918804 600 650160602 601 653413212 602 656676652 603 659950940 604 663236094 605 666532132 606 669839072 607 673156932 608 676485730 609 679825484 610 683176212 611 686537932 612 689910662 613 693294420 614 696689224 615 700095092 616 703512042 617 706940092 618 710379260 619 713829564 620 717291022 621 720763652 622 724247472 623 727742500 624 731248754 625 734766252 626 738295012 627 741835052 628 745386390 629 748949044 630 752523032 631 756108372 632 759705082 633 763313180 634 766932684 635 770563612 636 774205982 637 777859812 638 781525120 639 785201924 640 788890242 641 792590092 642 796301492 643 800024460 644 803759014 645 807505172 646 811262952 647 815032372 648 818813450 649 822606204 650 826410652 651 830226812 652 834054702 653 837894340 654 841745744 655 845608932 656 849483922 657 853370732 658 857269380 659 861179884 660 865102262 661 869036532 662 872982712 663 876940820 664 880910874 665 884892892 666 888886892 667 892892892 668 896910910 669 900940964 670 904983072 671 909037252 672 913103522 673 917181900 674 921272404 675 925375052 676 929489862 677 933616852 678 937756040 679 941907444 680 946071082 681 950246972 682 954435132 683 958635580 684 962848334 685 967073412 686 971310832 687 975560612 688 979822770 689 984097324 690 988384292 691 992683692 692 996995542 693 1001319860 694 1005656664 695 1010005972 696 1014367802 697 1018742172 698 1023129100 699 1027528604 700 1031940702 701 1036365412 702 1040802752 703 1045252740 704 1049715394 705 1054190732 706 1058678772 707 1063179532 708 1067693030 709 1072219284 710 1076758312 711 1081310132 712 1085874762 713 1090452220 714 1095042524 715 1099645692 716 1104261742 717 1108890692 718 1113532560 719 1118187364 720 1122855122 721 1127535852 722 1132229572 723 1136936300 724 1141656054 725 1146388852 726 1151134712 727 1155893652 728 1160665690 729 1165450844 730 1170249132 731 1175060572 732 1179885182 733 1184722980 734 1189573984 735 1194438212 736 1199315682 737 1204206412 738 1209110420 739 1214027724 740 1218958342 741 1223902292 742 1228859592 743 1233830260 744 1238814314 745 1243811772 746 1248822652 747 1253846972 748 1258884750 749 1263936004 750 1269000752 751 1274079012 752 1279170802 753 1284276140 754 1289395044 755 1294527532 756 1299673622 757 1304833332 758 1310006680 759 1315193684 760 1320394362 761 1325608732 762 1330836812 763 1336078620 764 1341334174 765 1346603492 766 1351886592 767 1357183492 768 1362494210 769 1367818764 770 1373157172 771 1378509452 772 1383875622 773 1389255700 774 1394649704 775 1400057652 776 1405479562 777 1410915452 778 1416365340 779 1421829244 780 1427307182 781 1432799172 782 1438305232 783 1443825380 784 1449359634 785 1454908012 786 1460470532 787 1466047212 788 1471638070 789 1477243124 790 1482862392 791 1488495892 792 1494143642 793 1499805660 794 1505481964 795 1511172572 796 1516877502 797 1522596772 798 1528330400 799 1534078404 800 1539840802 801 1545617612 802 1551408852 803 1557214540 804 1563034694 805 1568869332 806 1574718472 807 1580582132 808 1586460330 809 1592353084 810 1598260412 811 1604182332 812 1610118862 813 1616070020 814 1622035824 815 1628016292 816 1634011442 817 1640021292 818 1646045860 819 1652085164 820 1658139222 821 1664208052 822 1670291672 823 1676390100 824 1682503354 825 1688631452 826 1694774412 827 1700932252 828 1707104990 829 1713292644 830 1719495232 831 1725712772 832 1731945282 833 1738192780 834 1744455284 835 1750732812 836 1757025382 837 1763333012 838 1769655720 839 1775993524 840 1782346442 841 1788714492 842 1795097692 843 1801496060 844 1807909614 845 1814338372 846 1820782352 847 1827241572 848 1833716050 849 1840205804 850 1846710852 851 1853231212 852 1859766902 853 1866317940 854 1872884344 855 1879466132 856 1886063322 857 1892675932 858 1899303980 859 1905947484 860 1912606462 861 1919280932 862 1925970912 863 1932676420 864 1939397474 865 1946134092 866 1952886292 867 1959654092 868 1966437510 869 1973236564 870 1980051272 871 1986881652 872 1993727722 873 2000589500 874 2007467004 875 2014360252 876 2021269262 877 2028194052 878 2035134640 879 2042091044 880 2049063282 881 2056051372 882 2063055332 883 2070075180 884 2077110934 885 2084162612 886 2091230232 887 2098313812 888 2105413370 889 2112528924 890 2119660492 891 2126808092 892 2133971742 893 2141151460 894 2148347264 895 2155559172 896 2162787202 897 2170031372 898 2177291700 899 2184568204 900 2191860902 901 2199169812 902 2206494952 903 2213836340 904 2221193994 905 2228567932 906 2235958172 907 2243364732 908 2250787630 909 2258226884 910 2265682512 911 2273154532 912 2280642962 913 2288147820 914 2295669124 915 2303206892 916 2310761142 917 2318331892 918 2325919160 919 2333522964 920 2341143322 921 2348780252 922 2356433772 923 2364103900 924 2371790654 925 2379494052 926 2387214112 927 2394950852 928 2402704290 929 2410474444 930 2418261332 931 2426064972 932 2433885382 933 2441722580 934 2449576584 935 2457447412 936 2465335082 937 2473239612 938 2481161020 939 2489099324 940 2497054542 941 2505026692 942 2513015792 943 2521021860 944 2529044914 945 2537084972 946 2545142052 947 2553216172 948 2561307350 949 2569415604 950 2577540952 951 2585683412 952 2593843002 953 2602019740 954 2610213644 955 2618424732 956 2626653022 957 2634898532 958 2643161280 959 2651441284 960 2659738562 961 2668053132 962 2676385012 963 2684734220 964 2693100774 965 2701484692 966 2709885992 967 2718304692 968 2726740810 969 2735194364 970 2743665372 971 2752153852 972 2760659822 973 2769183300 974 2777724304 975 2786282852 976 2794858962 977 2803452652 978 2812063940 979 2820692844 980 2829339382 981 2838003572 982 2846685432 983 2855384980 984 2864102234 985 2872837212 986 2881589932 987 2890360412 988 2899148670 989 2907954724 990 2916778592 991 2925620292 992 2934479842 993 2943357260 994 2952252564 995 2961165772 996 2970096902 997 2979045972 998 2988013000 999 2996998004 1000 3006001002