0 1 1 3 2 48 3 199 4 543 5 1191 6 2278 7 3963 8 6429 9 9883 10 14556 11 20703 12 28603 13 38559 14 50898 15 65971 16 84153 17 105843 18 131464 19 161463 20 196311 21 236503 22 282558 23 335019 24 394453 25 461451 26 536628 27 620623 28 714099 29 817743 30 932266 31 1058403 32 1196913 33 1348579 34 1514208 35 1694631 36 1890703 37 2103303 38 2333334 39 2581723 40 2849421 41 3137403 42 3446668 43 3778239 44 4133163 45 4512511 46 4917378 47 5348883 48 5808169 49 6296403 50 6814776 51 7364503 52 7946823 53 8562999 54 9214318 55 9902091 56 10627653 57 11392363 58 12197604 59 13044783 60 13935331 61 14870703 62 15852378 63 16881859 64 17960673 65 19090371 66 20272528 67 21508743 68 22800639 69 24149863 70 25558086 71 27027003 72 28558333 73 30153819 74 31815228 75 33544351 76 35343003 77 37213023 78 39156274 79 41174643 80 43270041 81 45444403 82 47699688 83 50037879 84 52460983 85 54971031 86 57570078 87 60260203 88 63043509 89 65922123 90 68898196 91 71973903 92 75151443 93 78433039 94 81820938 95 85317411 96 88924753 97 92645283 98 96481344 99 100435303 100 104509551 101 108706503 102 113028598 103 117478299 104 122058093 105 126770491 106 131618028 107 136603263 108 141728779 109 146997183 110 152411106 111 157973203 112 163686153 113 169552659 114 175575448 115 181757271 116 188100903 117 194609143 118 201284814 119 208130763 120 215149861 121 222345003 122 229719108 123 237275119 124 245016003 125 252944751 126 261064378 127 269377923 128 277888449 129 286599043 130 295512816 131 304632903 132 313962463 133 323504679 134 333262758 135 343239931 136 353439453 137 363864603 138 374518684 139 385405023 140 396526971 141 407887903 142 419491218 143 431340339 144 443438713 145 455789811 146 468397128 147 481264183 148 494394519 149 507791703 150 521459326 151 535401003 152 549620373 153 564121099 154 578906868 155 593981391 156 609348403 157 625011663 158 640974954 159 657242083 160 673816881 161 690703203 162 707904928 163 725425959 164 743270223 165 761441671 166 779944278 167 798782043 168 817958989 169 837479163 170 857346636 171 877565503 172 898139883 173 919073919 174 940371778 175 962037651 176 984075753 177 1006490323 178 1029285624 179 1052465943 180 1076035591 181 1099998903 182 1124360238 183 1149123979 184 1174294533 185 1199876331 186 1225873828 187 1252291503 188 1279133859 189 1306405423 190 1334110746 191 1362254403 192 1390840993 193 1419875139 194 1449361488 195 1479304711 196 1509709503 197 1540580583 198 1571922694 199 1603740603 200 1636039101 201 1668823003 202 1702097148 203 1735866399 204 1770135643 205 1804909791 206 1840193778 207 1875992563 208 1912311129 209 1949154483 210 1986527656 211 2024435703 212 2062883703 213 2101876759 214 2141419998 215 2181518571 216 2222177653 217 2263402443 218 2305198164 219 2347570063 220 2390523411 221 2434063503 222 2478195658 223 2522925219 224 2568257553 225 2614198051 226 2660752128 227 2707925223 228 2755722799 229 2804150343 230 2853213366 231 2902917403 232 2953268013 233 3004270779 234 3055931308 235 3108255231 236 3161248203 237 3214915903 238 3269264034 239 3324298323 240 3380024521 241 3436448403 242 3493575768 243 3551412439 244 3609964263 245 3669237111 246 3729236878 247 3789969483 248 3851440869 249 3913657003 250 3976623876 251 4040347503 252 4104833923 253 4170089199 254 4236119418 255 4302930691 256 4370529153 257 4438920963 258 4508112304 259 4578109383 260 4648918431 261 4720545703 262 4792997478 263 4866280059 264 4940399773 265 5015362971 266 5091176028 267 5167845343 268 5245377339 269 5323778463 270 5403055186 271 5483214003 272 5564261433 273 5646204019 274 5729048328 275 5812800951 276 5897468503 277 5983057623 278 6069574974 279 6157027243 280 6245421141 281 6334763403 282 6425060788 283 6516320079 284 6608548083 285 6701751631 286 6795937578 287 6891112803 288 6987284209 289 7084458723 290 7182643296 291 7281844903 292 7382070543 293 7483327239 294 7585622038 295 7688962011 296 7793354253 297 7898805883 298 8005324044 299 8112915903 300 8221588651 301 8331349503 302 8442205698 303 8554164499 304 8667233193 305 8781419091 306 8896729528 307 9013171863 308 9130753479 309 9249481783 310 9369364206 311 9490408203 312 9612621253 313 9736010859 314 9860584548 315 9986349871 316 10113314403 317 10241485743 318 10370871514 319 10501479363 320 10633316961 321 10766392003 322 10900712208 323 11036285319 324 11173119103 325 11311221351 326 11450599878 327 11591262523 328 11733217149 329 11876471643 330 12021033916 331 12166911903 332 12314113563 333 12462646879 334 12612519858 335 12763740531 336 12916316953 337 13070257203 338 13225569384 339 13382261623 340 13540342071 341 13699818903 342 13860700318 343 14022994539 344 14186709813 345 14351854411 346 14518436628 347 14686464783 348 14855947219 349 15026892303 350 15199308426 351 15373204003 352 15548587473 353 15725467299 354 15903851968 355 16083749991 356 16265169903 357 16448120263 358 16632609654 359 16818646683 360 17006239981 361 17195398203 362 17386130028 363 17578444159 364 17772349323 365 17967854271 366 18164967778 367 18363698643 368 18564055689 369 18766047763 370 18969683736 371 19174972503 372 19381922983 373 19590544119 374 19800844878 375 20012834251 376 20226521253 377 20441914923 378 20659024324 379 20877858543 380 21098426691 381 21320737903 382 21544801338 383 21770626179 384 21998221633 385 22227596931 386 22458761328 387 22691724103 388 22926494559 389 23163082023 390 23401495846 391 23641745403 392 23883840093 393 24127789339 394 24373602588 395 24621289311 396 24870859003 397 25122321183 398 25375685394 399 25630961203 400 25888158201 401 26147286003 402 26408354248 403 26671372599 404 26936350743 405 27203298391 406 27472225278 407 27743141163 408 28016055829 409 28290979083 410 28567920756 411 28846890703 412 29127898803 413 29410954959 414 29696069098 415 29983251171 416 30272511153 417 30563859043 418 30857304864 419 31152858663 420 31450530511 421 31750330503 422 32052268758 423 32356355419 424 32662600653 425 32971014651 426 33281607628 427 33594389823 428 33909371499 429 34226562943 430 34545974466 431 34867616403 432 35191499113 433 35517632979 434 35846028408 435 36176695831 436 36509645703 437 36844888503 438 37182434734 439 37522294923 440 37864479621 441 38208999403 442 38555864868 443 38905086639 444 39256675363 445 39610641711 446 39966996378 447 40325750083 448 40686913569 449 41050497603 450 41416512976 451 41784970503 452 42155881023 453 42529255399 454 42905104518 455 43283439291 456 43664270653 457 44047609563 458 44433467004 459 44821853983 460 45212781531 461 45606260703 462 46002302578 463 46400918259 464 46802118873 465 47205915571 466 47612319528 467 48021341943 468 48432994039 469 48847287063 470 49264232286 471 49683841003 472 50106124533 473 50531094219 474 50958761428 475 51389137551 476 51822234003 477 52258062223 478 52696633674 479 53137959843 480 53582052241 481 54028922403 482 54478581888 483 54931042279 484 55386315183 485 55844412231 486 56305345078 487 56769125403 488 57235764909 489 57705275323 490 58177668396 491 58652955903 492 59131149643 493 59612261439 494 60096303138 495 60583286611 496 61073223753 497 61566126483 498 62062006744 499 62560876503 500 63062747751 501 63567632503 502 64075542798 503 64586490699 504 65100488293 505 65617547691 506 66137681028 507 66660900463 508 67187218179 509 67716646383 510 68249197306 511 68784883203 512 69323716353 513 69865709059 514 70410873648 515 70959222471 516 71510767903 517 72065522343 518 72623498214 519 73184707963 520 73749164061 521 74316879003 522 74887865308 523 75462135519 524 76039702203 525 76620577951 526 77204775378 527 77792307123 528 78383185849 529 78977424243 530 79575035016 531 80176030903 532 80780424663 533 81388229079 534 81999456958 535 82614121131 536 83232234453 537 83853809803 538 84478860084 539 85107398223 540 85739437171 541 86374989903 542 87014069418 543 87656688739 544 88302860913 545 88952599011 546 89605916128 547 90262825383 548 90923339919 549 91587472903 550 92255237526 551 92926647003 552 93601714573 553 94280453499 554 94962877068 555 95648998591 556 96338831403 557 97032388863 558 97729684354 559 98430731283 560 99135543081 561 99844133203 562 100556515128 563 101272702359 564 101992708423 565 102716546871 566 103444231278 567 104175775243 568 104911192389 569 105650496363 570 106393700836 571 107140819503 572 107891866083 573 108646854319 574 109405797978 575 110168710851 576 110935606753 577 111706499523 578 112481403024 579 113260331143 580 114043297791 581 114830316903 582 115621402438 583 116416568379 584 117215828733 585 118019197531 586 118826688828 587 119638316703 588 120454095259 589 121274038623 590 122098160946 591 122926476403 592 123758999193 593 124595743539 594 125436723688 595 126281953911 596 127131448503 597 127985221783 598 128843288094 599 129705661803 600 130572357301 601 131443389003 602 132318771348 603 133198518799 604 134082645843 605 134971166991 606 135864096778 607 136761449763 608 137663240529 609 138569483683 610 139480193856 611 140395385703 612 141315073903 613 142239273159 614 143167998198 615 144101263771 616 145039084653 617 145981475643 618 146928451564 619 147880027263 620 148836217611 621 149797037503 622 150762501858 623 151732625619 624 152707423753 625 153686911251 626 154671103128 627 155660014423 628 156653660199 629 157652055543 630 158655215566 631 159663155403 632 160675890213 633 161693435179 634 162715805508 635 163743016431 636 164775083203 637 165812021103 638 166853845434 639 167900571523 640 168952214721 641 170008790403 642 171070313968 643 172136800839 644 173208266463 645 174284726311 646 175366195878 647 176452690683 648 177544226269 649 178640818203 650 179742482076 651 180849233503 652 181961088123 653 183078061599 654 184200169618 655 185327427891 656 186459852153 657 187597458163 658 188740261704 659 189888278583 660 191041524631 661 192200015703 662 193363767678 663 194532796459 664 195707117973 665 196886748171 666 198071703028 667 199261998543 668 200457650739 669 201658675663 670 202865089386 671 204076908003 672 205294147633 673 206516824419 674 207744954528 675 208978554151 676 210217639503 677 211462226823 678 212712332374 679 213967972443 680 215229163341 681 216495921403 682 217768262988 683 219046204479 684 220329762283 685 221618952831 686 222913792578 687 224214298003 688 225520485609 689 226832371923 690 228149973496 691 229473306903 692 230802388743 693 232137235639 694 233477864238 695 234824291211 696 236176533253 697 237534607083 698 238898529444 699 240268317103 700 241643986851 701 243025555503 702 244413039898 703 245806456899 704 247205823393 705 248611156291 706 250022472528 707 251439789063 708 252863122879 709 254292490983 710 255727910406 711 257169398203 712 258616971453 713 260070647259 714 261530442748 715 262996375071 716 264468461403 717 265946718943 718 267431164914 719 268921816563 720 270418691161 721 271921806003 722 273431178408 723 274946825719 724 276468765303 725 277997014551 726 279531590878 727 281072511723 728 282619794549 729 284173456843 730 285733516116 731 287299989903 732 288872895763 733 290452251279 734 292038074058 735 293630381731 736 295229191953 737 296834522403 738 298446390784 739 300064814823 740 301689812271 741 303321400903 742 304959598518 743 306604422939 744 308255892013 745 309914023611 746 311578835628 747 313250345983 748 314928572619 749 316613533503 750 318305246626 751 320003730003 752 321709001673 753 323421079699 754 325139982168 755 326865727191 756 328598332903 757 330337817463 758 332084199054 759 333837495883 760 335597726181 761 337364908203 762 339139060228 763 340920200559 764 342708347523 765 344503519471 766 346305734778 767 348115011843 768 349931369089 769 351754824963 770 353585397936 771 355423106503 772 357267969183 773 359120004519 774 360979231078 775 362845667451 776 364719332253 777 366600244123 778 368488421724 779 370383883743 780 372286648891 781 374196735903 782 376114163538 783 378038950579 784 379971115833 785 381910678131 786 383857656328 787 385812069303 788 387773935959 789 389743275223 790 391720106046 791 393704447403 792 395696318293 793 397695737739 794 399702724788 795 401717298511 796 403739478003 797 405769282383 798 407806730794 799 409851842403 800 411904636401 801 413965132003 802 416033348448 803 418109304999 804 420193020943 805 422284515591 806 424383808278 807 426490918363 808 428605865229 809 430728668283 810 432859346956 811 434997920703 812 437144409003 813 439298831359 814 441461207298 815 443631556371 816 445809898153 817 447996252243 818 450190638264 819 452393075863 820 454603584711 821 456822184503 822 459048894958 823 461283735819 824 463526726853 825 465777887851 826 468037238628 827 470304799023 828 472580588899 829 474864628143 830 477156936666 831 479457534403 832 481766441313 833 484083677379 834 486409262608 835 488743217031 836 491085560703 837 493436313703 838 495795496134 839 498163128123 840 500539229821 841 502923821403 842 505316923068 843 507718555039 844 510128737563 845 512547490911 846 514974835378 847 517410791283 848 519855378969 849 522308618803 850 524770531176 851 527241136503 852 529720455223 853 532208507799 854 534705314718 855 537210896491 856 539725273653 857 542248466763 858 544780496404 859 547321383183 860 549871147731 861 552429810703 862 554997392778 863 557573914659 864 560159397073 865 562753860771 866 565357326528 867 567969815143 868 570591347439 869 573221944263 870 575861626486 871 578510415003 872 581168330733 873 583835394619 874 586511627628 875 589197050751 876 591891685003 877 594595551423 878 597308671074 879 600031065043 880 602762754441 881 605503760403 882 608254104088 883 611013806679 884 613782889383 885 616561373431 886 619349280078 887 622146630603 888 624953446309 889 627769748523 890 630595558596 891 633430897903 892 636275787843 893 639130249839 894 641994305338 895 644867975811 896 647751282753 897 650644247683 898 653546892144 899 656459237703 900 659381305951 901 662313118503 902 665254696998 903 668206063099 904 671167238493 905 674138244891 906 677119104028 907 680109837663 908 683110467579 909 686121015583 910 689141503506 911 692171953203 912 695212386553 913 698262825459 914 701323291848 915 704393807671 916 707474394903 917 710565075543 918 713665871614 919 716776805163 920 719897898261 921 723029173003 922 726170651508 923 729322355919 924 732484308403 925 735656531151 926 738839046378 927 742031876323 928 745235043249 929 748448569443 930 751672477216 931 754906788903 932 758151526863 933 761406713479 934 764672371158 935 767948522331 936 771235189453 937 774532395003 938 777840161484 939 781158511423 940 784487467371 941 787827051903 942 791177287618 943 794538197139 944 797909803113 945 801292128211 946 804685195128 947 808089026583 948 811503645319 949 814929074103 950 818365335726 951 821812453003 952 825270448773 953 828739345899 954 832219167268 955 835709935791 956 839211674403 957 842724406063 958 846248153754 959 849782940483 960 853328789281 961 856885723203 962 860453765328 963 864032938759 964 867623266623 965 871224772071 966 874837478278 967 878461408443 968 882096585789 969 885743033563 970 889400775036 971 893069833503 972 896750232283 973 900441994719 974 904145144178 975 907859704051 976 911585697753 977 915323148723 978 919072080424 979 922832516343 980 926604479991 981 930387994903 982 934183084638 983 937989772779 984 941808082933 985 945638038731 986 949479663828 987 953332981903 988 957198016659 989 961074791823 990 964963331146 991 968863658403 992 972775797393 993 976699771939 994 980635605888 995 984583323111 996 988542947503 997 992514502983 998 996498013494 999 1000493503003 1000 1004500995501