1 0 2 2 3 11 4 36 5 89 6 183 7 335 8 565 9 894 10 1347 11 1952 12 2738 13 3738 14 4988 15 6525 16 8390 17 10627 18 13281 19 16401 20 20039 21 24248 22 29085 23 34610 24 40884 25 47972 26 55942 27 64863 28 74808 29 85853 30 98075 31 111555 32 126377 33 142626 34 160391 35 179764 36 200838 37 223710 38 248480 39 275249 40 304122 41 335207 42 368613 43 404453 44 442843 45 483900 46 527745 47 574502 48 624296 49 677256 50 733514 51 793203 52 856460 53 923425 54 994239 55 1069047 56 1147997 57 1231238 58 1318923 59 1411208 60 1508250 61 1610210 62 1717252 63 1829541 64 1947246 65 2070539 66 2199593 67 2334585 68 2475695 69 2623104 70 2776997 71 2937562 72 3104988 73 3279468 74 3461198 75 3650375 76 3847200 77 4051877 78 4264611 79 4485611 80 4715089 81 4953258 82 5200335 83 5456540 84 5722094 85 5997222 86 6282152 87 6577113 88 6882338 89 7198063 90 7524525 91 7861965 92 8210627 93 8570756 94 8942601 95 9326414 96 9722448 97 10130960 98 10552210 99 10986459 100 11433972 101 11895017 102 12369863 103 12858783 104 13362053 105 13879950 106 14412755 107 14960752 108 15524226 109 16103466 110 16698764 111 17310413 112 17938710 113 18583955 114 19246449 115 19926497 116 20624407 117 21340488 118 22075053 119 22828418 120 23600900 121 24392820 122 25204502 123 26036271 124 26888456 125 27761389 126 28655403 127 29570835 128 30508025 129 31467314 130 32449047 131 33453572 132 34481238 133 35532398 134 36607408 135 37706625 136 38830410 137 39979127 138 41153141 139 42352821 140 43578539 141 44830668 142 46109585 143 47415670 144 48749304 145 50110872 146 51500762 147 52919363 148 54367068 149 55844273 150 57351375 151 58888775 152 60456877 153 62056086 154 63686811 155 65349464 156 67044458 157 68772210 158 70533140 159 72327669 160 74156222 161 76019227 162 77917113 163 79850313 164 81819263 165 83824400 166 85866165 167 87945002 168 90061356 169 92215676 170 94408414 171 96640023 172 98910960 173 101221685 174 103572659 175 105964347 176 108397217 177 110871738 178 113388383 179 115947628 180 118549950 181 121195830 182 123885752 183 126620201 184 129399666 185 132224639 186 135095613 187 138013085 188 140977555 189 143989524 190 147049497 191 150157982 192 153315488 193 156522528 194 159779618 195 163087275 196 166446020 197 169856377 198 173318871 199 176834031 200 180402389 201 184024478 202 187700835 203 191432000 204 195218514 205 199060922 206 202959772 207 206915613 208 210928998 209 215000483 210 219130625 211 223319985 212 227569127 213 231878616 214 236249021 215 240680914 216 245174868 217 249731460 218 254351270 219 259034879 220 263782872 221 268595837 222 273474363 223 278419043 224 283430473 225 288509250 226 293655975 227 298871252 228 304155686 229 309509886 230 314934464 231 320430033 232 325997210 233 331636615 234 337348869 235 343134597 236 348994427 237 354928988 238 360938913 239 367024838 240 373187400 241 379427240 242 385745002 243 392141331 244 398616876 245 405172289 246 411808223 247 418525335 248 425324285 249 432205734 250 439170347 251 446218792 252 453351738 253 460569858 254 467873828 255 475264325 256 482742030 257 490307627 258 497961801 259 505705241 260 513538639 261 521462688 262 529478085 263 537585530 264 545785724 265 554079372 266 562467182 267 570949863 268 579528128 269 588202693 270 596974275 271 605843595 272 614811377 273 623878346 274 633045231 275 642312764 276 651681678 277 661152710 278 670726600 279 680404089 280 690185922 281 700072847 282 710065613 283 720164973 284 730371683 285 740686500 286 751110185 287 761643502 288 772287216 289 783042096 290 793908914 291 804888443 292 815981460 293 827188745 294 838511079 295 849949247 296 861504037 297 873176238 298 884966643 299 896876048 300 908905250 301 921055050 302 933326252 303 945719661 304 958236086 305 970876339 306 983641233 307 996531585 308 1009548215 309 1022691944 310 1035963597 311 1049364002 312 1062893988 313 1076554388 314 1090346038 315 1104269775 316 1118326440 317 1132516877 318 1146841931 319 1161302451 320 1175899289 321 1190633298 322 1205505335 323 1220516260 324 1235666934 325 1250958222 326 1266390992 327 1281966113 328 1297684458 329 1313546903 330 1329554325 331 1345707605 332 1362007627 333 1378455276 334 1395051441 335 1411797014 336 1428692888 337 1445739960 338 1462939130 339 1480291299 340 1497797372 341 1515458257 342 1533274863 343 1551248103 344 1569378893 345 1587668150 346 1606116795 347 1624725752 348 1643495946 349 1662428306 350 1681523764 351 1700783253 352 1720207710 353 1739798075 354 1759555289 355 1779480297 356 1799574047 357 1819837488 358 1840271573 359 1860877258 360 1881655500 361 1902607260 362 1923733502 363 1945035191 364 1966513296 365 1988168789 366 2010002643 367 2032015835 368 2054209345 369 2076584154 370 2099141247 371 2121881612 372 2144806238 373 2167916118 374 2191212248 375 2214695625 376 2238367250 377 2262228127 378 2286279261 379 2310521661 380 2334956339 381 2359584308 382 2384406585 383 2409424190 384 2434638144 385 2460049472 386 2485659202 387 2511468363 388 2537477988 389 2563689113 390 2590102775 391 2616720015 392 2643541877 393 2670569406 394 2697803651 395 2725245664 396 2752896498 397 2780757210 398 2808828860 399 2837112509 400 2865609222 401 2894320067 402 2923246113 403 2952388433 404 2981748103 405 3011326200 406 3041123805 407 3071142002 408 3101381876 409 3131844516 410 3162531014 411 3193442463 412 3224579960 413 3255944605 414 3287537499 415 3319359747 416 3351412457 417 3383696738 418 3416213703 419 3448964468 420 3481950150 421 3515171870 422 3548630752 423 3582327921 424 3616264506 425 3650441639 426 3684860453 427 3719522085 428 3754427675 429 3789578364 430 3824975297 431 3860619622 432 3896512488 433 3932655048 434 3969048458 435 4005693875 436 4042592460 437 4079745377 438 4117153791 439 4154818871 440 4192741789 441 4230923718 442 4269365835 443 4308069320 444 4347035354 445 4386265122 446 4425759812 447 4465520613 448 4505548718 449 4545845323 450 4586411625 451 4627248825 452 4668358127 453 4709740736 454 4751397861 455 4793330714 456 4835540508 457 4878028460 458 4920795790 459 4963843719 460 5007173472 461 5050786277 462 5094683363 463 5138865963 464 5183335313 465 5228092650 466 5273139215 467 5318476252 468 5364105006 469 5410026726 470 5456242664 471 5502754073 472 5549562210 473 5596668335 474 5644073709 475 5691779597 476 5739787267 477 5788097988 478 5836713033 479 5885633678 480 5934861200 481 5984396880 482 6034242002 483 6084397851 484 6134865716 485 6185646889 486 6236742663 487 6288154335 488 6339883205 489 6391930574 490 6444297747 491 6496986032 492 6549996738 493 6603331178 494 6656990668 495 6710976525 496 6765290070 497 6819932627 498 6874905521 499 6930210081 500 6985847639 501 7041819528 502 7098127085 503 7154771650 504 7211754564 505 7269077172 506 7326740822 507 7384746863 508 7443096648 509 7501791533 510 7560832875 511 7620222035 512 7679960377 513 7740049266 514 7800490071 515 7861284164 516 7922432918 517 7983937710 518 8045799920 519 8108020929 520 8170602122 521 8233544887 522 8296850613 523 8360520693 524 8424556523 525 8488959500 526 8553731025 527 8618872502 528 8684385336 529 8750270936 530 8816530714 531 8883166083 532 8950178460 533 9017569265 534 9085339919 535 9153491847 536 9222026477 537 9290945238 538 9360249563 539 9429940888 540 9500020650 541 9570490290 542 9641351252 543 9712604981 544 9784252926 545 9856296539 546 9928737273 547 10001576585 548 10074815935 549 10148456784 550 10222500597 551 10296948842 552 10371802988 553 10447064508 554 10522734878 555 10598815575 556 10675308080 557 10752213877 558 10829534451 559 10907271291 560 10985425889 561 11063999738 562 11142994335 563 11222411180 564 11302251774 565 11382517622 566 11463210232 567 11544331113 568 11625881778 569 11707863743 570 11790278525 571 11873127645 572 11956412627 573 12040134996 574 12124296281 575 12208898014 576 12293941728 577 12379428960 578 12465361250 579 12551740139 580 12638567172 581 12725843897 582 12813571863 583 12901752623 584 12990387733 585 13079478750 586 13169027235 587 13259034752 588 13349502866 589 13440433146 590 13531827164 591 13623686493 592 13716012710 593 13808807395 594 13902072129 595 13995808497 596 14090018087 597 14184702488 598 14279863293 599 14375502098 600 14471620500 601 14568220100 602 14665302502 603 14762869311 604 14860922136 605 14959462589 606 15058492283 607 15158012835 608 15258025865 609 15358532994 610 15459535847 611 15561036052 612 15663035238 613 15765535038 614 15868537088 615 15972043025 616 16076054490 617 16180573127 618 16285600581 619 16391138501 620 16497188539 621 16603752348 622 16710831585 623 16818427910 624 16926542984 625 17035178472 626 17144336042 627 17254017363 628 17364224108 629 17474957953 630 17586220575 631 17698013655 632 17810338877 633 17923197926 634 18036592491 635 18150524264 636 18264994938 637 18380006210 638 18495559780 639 18611657349 640 18728300622 641 18845491307 642 18963231113 643 19081521753 644 19200364943 645 19319762400 646 19439715845 647 19560227002 648 19681297596 649 19802929356 650 19925124014 651 20047883303 652 20171208960 653 20295102725 654 20419566339 655 20544601547 656 20670210097 657 20796393738 658 20923154223 659 21050493308 660 21178412750 661 21306914310 662 21435999752 663 21565670841 664 21695929346 665 21826777039 666 21958215693 667 22090247085 668 22222872995 669 22356095204 670 22489915497 671 22624335662 672 22759357488 673 22894982768 674 23031213298 675 23168050875 676 23305497300 677 23443554377 678 23582223911 679 23721507711 680 23861407589 681 24001925358 682 24143062835 683 24284821840 684 24427204194 685 24570211722 686 24713846252 687 24858109613 688 25003003638 689 25148530163 690 25294691025 691 25441488065 692 25588923127 693 25736998056 694 25885714701 695 26035074914 696 26185080548 697 26335733460 698 26487035510 699 26638988559 700 26791594472 701 26944855117 702 27098772363 703 27253348083 704 27408584153 705 27564482450 706 27721044855 707 27878273252 708 28036169526 709 28194735566 710 28353973264 711 28513884513 712 28674471210 713 28835735255 714 28997678549 715 29160302997 716 29323610507 717 29487602988 718 29652282353 719 29817650518 720 29983709400 721 30150460920 722 30317907002 723 30486049571 724 30654890556 725 30824431889 726 30994675503 727 31165623335 728 31337277325 729 31509639414 730 31682711547 731 31856495672 732 32030993738 733 32206207698 734 32382139508 735 32558791125 736 32736164510 737 32914261627 738 33093084441 739 33272634921 740 33452915039 741 33633926768 742 33815672085 743 33998152970 744 34181371404 745 34365329372 746 34550028862 747 34735471863 748 34921660368 749 35108596373 750 35296281875 751 35484718875 752 35673909377 753 35863855386 754 36054558911 755 36246021964 756 36438246558 757 36631234710 758 36824988440 759 37019509769 760 37214800722 761 37410863327 762 37607699613 763 37805311613 764 38003701363 765 38202870900 766 38402822265 767 38603557502 768 38805078656 769 39007387776 770 39210486914 771 39414378123 772 39619063460 773 39824544985 774 40030824759 775 40237904847 776 40445787317 777 40654474238 778 40863967683 779 41074269728 780 41285382450 781 41497307930 782 41710048252 783 41923605501 784 42137981766 785 42353179139 786 42569199713 787 42786045585 788 43003718855 789 43222221624 790 43441555997 791 43661724082 792 43882727988 793 44104569828 794 44327251718 795 44550775775 796 44775144120 797 45000358877 798 45226422171 799 45453336131 800 45681102889 801 45909724578 802 46139203335 803 46369541300 804 46600740614 805 46832803422 806 47065731872 807 47299528113 808 47534194298 809 47769732583 810 48006145125 811 48243434085 812 48481601627 813 48720649916 814 48960581121 815 49201397414 816 49443100968 817 49685693960 818 49929178570 819 50173556979 820 50418831372 821 50665003937 822 50912076863 823 51160052343 824 51408932573 825 51658719750 826 51909416075 827 52161023752 828 52413544986 829 52666981986 830 52921336964 831 53176612133 832 53432809710 833 53689931915 834 53947980969 835 54206959097 836 54466868527 837 54727711488 838 54989490213 839 55252206938 840 55515863900 841 55780463340 842 56046007502 843 56312498631 844 56579938976 845 56848330789 846 57117676323 847 57387977835 848 57659237585 849 57931457834 850 58204640847 851 58478788892 852 58753904238 853 59029989158 854 59307045928 855 59585076825 856 59864084130 857 60144070127 858 60425037101 859 60706987341 860 60989923139 861 61273846788 862 61558760585 863 61844666830 864 62131567824 865 62419465872 866 62708363282 867 62998262363 868 63289165428 869 63581074793 870 63873992775 871 64167921695 872 64462863877 873 64758821646 874 65055797331 875 65353793264 876 65652811778 877 65952855210 878 66253925900 879 66556026189 880 66859158422 881 67163324947 882 67468528113 883 67774770273 884 68082053783 885 68390381000 886 68699754285 887 69010176002 888 69321648516 889 69634174196 890 69947755414 891 70262394543 892 70578093960 893 70894856045 894 71212683179 895 71531577747 896 71851542137 897 72172578738 898 72494689943 899 72817878148 900 73142145750 901 73467495150 902 73793928752 903 74121448961 904 74450058186 905 74779758839 906 75110553333 907 75442444085 908 75775433515 909 76109524044 910 76444718097 911 76781018102 912 77118426488 913 77456945688 914 77796578138 915 78137326275 916 78479192540 917 78822179377 918 79166289231 919 79511524551 920 79857887789 921 80205381398 922 80554007835 923 80903769560 924 81254669034 925 81606708722 926 81959891092 927 82314218613 928 82669693758 929 83026319003 930 83384096825 931 83743029705 932 84103120127 933 84464370576 934 84826783541 935 85190361514 936 85555106988 937 85921022460 938 86288110430 939 86656373399 940 87025813872 941 87396434357 942 87768237363 943 88141225403 944 88515400993 945 88890766650 946 89267324895 947 89645078252 948 90024029246 949 90404180406 950 90785534264 951 91168093353 952 91551860210 953 91936837375 954 92323027389 955 92710432797 956 93099056147 957 93488899988 958 93879966873 959 94272259358 960 94665780000 961 95060531360 962 95456516002 963 95853736491 964 96252195396 965 96651895289 966 97052838743 967 97455028335 968 97858466645 969 98263156254 970 98669099747 971 99076299712 972 99484758738 973 99894479418 974 100305464348 975 100717716125 976 101131237350 977 101546030627 978 101962098561 979 102379443761 980 102798068839 981 103217976408 982 103639169085 983 104061649490 984 104485420244 985 104910483972 986 105336843302 987 105764500863 988 106193459288 989 106623721213 990 107055289275 991 107488166115 992 107922354377 993 108357856706 994 108794675751 995 109232814164 996 109672274598 997 110113059710 998 110555172160 999 110998614609 1000 111443389722