0 0 1 1 2 3 3 8 4 16 5 32 6 55 7 94 8 147 9 227 10 332 11 480 12 668 13 920 14 1232 15 1635 16 2124 17 2738 18 3470 19 4368 20 5424 21 6695 22 8172 23 9922 24 11934 25 14287 26 16968 27 20068 28 23572 29 27584 30 32087 31 37199 32 42901 33 49325 34 56450 35 64424 36 73223 37 83012 38 93764 39 105661 40 118674 41 133003 42 148616 43 165732 44 184316 45 204607 46 226567 47 250456 48 276232 49 304177 50 334246 51 366743 52 401620 53 439204 54 479443 55 522689 56 568886 57 618411 58 671204 59 727668 60 787739 61 851847 62 919924 63 992427 64 1069284 65 1150981 66 1237441 67 1329180 68 1426116 69 1528795 70 1637131 71 1751701 72 1872414 73 1999879 74 2134000 75 2275419 76 2424035 77 2580524 78 2744779 79 2917511 80 3098608 81 3288816 82 3488018 83 3696996 84 3915627 85 4144731 86 4384179 87 4634829 88 4896546 89 5170227 90 5455731 91 5753995 92 6064872 93 6389339 94 6727243 95 7079603 96 7446259 97 7828273 98 8225478 99 8638979 100 9068603 101 9515499 102 9979487 103 10461761 104 10962134 105 11481846 106 12020703 107 12579992 108 13159511 109 13760595 110 14383035 111 15028214 112 15695916 113 16387573 114 17102961 115 17843563 116 18609147 117 19401247 118 20219623 119 21065861 120 21939713 121 22842818 122 23774920 123 24737711 124 25730927 125 26756315 126 27813602 127 28904591 128 30029000 129 31188688 130 32383365 131 33614947 132 34883135 133 36189903 134 37534943 135 38920288 136 40345621 137 41813035 138 43322203 139 44875279 140 46471927 141 48114362 142 49802239 143 51537835 144 53320795 145 55153460 146 57035465 147 58969215 148 60954335 149 62993295 150 65085710 151 67234116 152 69438118 153 71700318 154 74020311 155 76400767 156 78841270 157 81344559 158 83910207 159 86541022 160 89236567 161 91999720 162 94830033 163 97730455 164 100700527 165 103743270 166 106858214 167 110048453 168 113313505 169 116656538 170 120077059 171 123578310 172 127159787 173 130824807 174 134572854 175 138407322 176 142327683 177 146337408 178 150435957 179 154626879 180 158909622 181 163287814 182 167760891 183 172332560 184 177002245 185 181773734 186 186646438 187 191624227 188 196706499 189 201897206 190 207195734 191 212606118 192 218127731 193 223764692 194 229516361 195 235386942 196 241375782 197 247487171 198 253720442 199 260079972 200 266565081 201 273180233 202 279924735 203 286803139 204 293814738 205 300964174 206 308250726 207 315679126 208 323248639 209 330964088 210 338824724 211 346835462 212 354995539 213 363309962 214 371777954 215 380404616 216 389189156 217 398136770 218 407246651 219 416524090 220 425968266 221 435584566 222 445372154 223 455336514 224 465476795 225 475798579 226 486301000 227 496989739 228 507863914 229 518929306 230 530185018 231 541636931 232 553284133 233 565132606 234 577181422 235 589436666 236 601897394 237 614569794 238 627452906 239 640553022 240 653869166 241 667407735 242 681167737 243 695155674 244 709370538 245 723818938 246 738499849 247 753419988 248 768578313 249 783981649 250 799628938 251 815527114 252 831675102 253 848079946 254 864740554 255 881664081 256 898849418 257 916303832 258 934026196 259 952023890 260 970295770 261 988849329 262 1007683406 263 1026805608 264 1046214756 265 1065918573 266 1085915862 267 1106214462 268 1126813158 269 1147719906 270 1168933473 271 1190461933 272 1212304035 273 1234467971 274 1256952472 275 1279765850 276 1302906817 277 1326383806 278 1350195510 279 1374350483 280 1398847400 281 1423694937 282 1448891750 283 1474446638 284 1500358238 285 1526635473 286 1553276961 287 1580291750 288 1607678438 289 1635446199 290 1663593612 291 1692129977 292 1721053854 293 1750374670 294 1780090965 295 1810212295 296 1840737180 297 1871675305 298 1903025170 299 1934796590 300 1966988045 301 1999609481 302 2032659358 303 2066147753 304 2100073106 305 2134445627 306 2169263735 307 2204537774 308 2240266142 309 2276459317 310 2313115677 311 2350245835 312 2387848148 313 2425933365 314 2464499822 315 2503558405 316 2543107429 317 2583157918 318 2623708165 319 2664769333 320 2706339694 321 2748430550 322 2791040152 323 2834179942 324 2877848149 325 2922056357 326 2966802773 327 3012099123 328 3057943592 329 3104348049 330 3151310657 331 3198843429 332 3246944506 333 3295626045 334 3344886165 335 3394737169 336 3445177153 337 3496218567 338 3547859484 339 3600112501 340 3652975669 341 3706461733 342 3760568721 343 3815309527 344 3870682156 345 3926699652 346 3983359997 347 4040676386 348 4098646777 349 4157284517 350 4216587541 351 4276569348 352 4337227850 353 4398576699 354 4460613783 355 4523352909 356 4586791941 357 4650944841 358 4715809449 359 4781399883 360 4847713959 361 4914765952 362 4982553654 363 5051091497 364 5120377249 365 5190425501 366 5261233996 367 5332817485 368 5405173686 369 5478317510 370 5552246651 371 5626976181 372 5702503769 373 5778844649 374 5855996465 375 5933974614 376 6012776715 377 6092418329 378 6172897049 379 6254228601 380 6336410553 381 6419458796 382 6503370873 383 6588162841 384 6673832217 385 6760395226 386 6847849359 387 6936211009 388 7025477641 389 7115665817 390 7206772976 391 7298815850 392 7391791852 393 7485717884 394 7580591333 395 7676429273 396 7773229064 397 7871007953 398 7969763273 399 8069512444 400 8170252773 401 8272001854 402 8374756967 403 8478535881 404 8583335849 405 8689174816 406 8796050008 407 8903979547 408 9012960631 409 9123011560 410 9234129505 411 9346332944 412 9459619021 413 9574006393 414 9689492176 415 9806095208 416 9923812577 417 10042663302 418 10162644443 419 10283775201 420 10406052608 421 10529496048 422 10654102525 423 10779891606 424 10906860267 425 11035028260 426 11164392532 427 11294973021 428 11426766645 429 11559793528 430 11694050560 431 11829558052 432 11966312865 433 12104335498 434 12243622783 435 12384195408 436 12526050176 437 12669207965 438 12813665548 439 12959443994 440 13106540047 441 13254974967 442 13404745469 443 13555873005 444 13708354260 445 13862210880 446 14017439520 447 14174062020 448 14332075005 449 14491500510 450 14652335130 451 14814601096 452 14978294973 453 15143439188 454 15310030276 455 15478090862 456 15647617450 457 15818632864 458 15991133577 459 16165142612 460 16340656412 461 16517698200 462 16696264388 463 16876378400 464 17058036617 465 17241262665 466 17426052894 467 17612431133 468 17800393700 469 17989964628 470 18181140204 471 18373944665 472 18568374267 473 18764453452 474 18962178444 475 19161573892 476 19362635988 477 19565389588 478 19769830852 479 19975984844 480 20183847692 481 20393444669 482 20604771871 483 20817854780 484 21032689460 485 21249301604 486 21467687243 487 21687872282 488 21909852719 489 22133654671 490 22359274104 491 22586737348 492 22816040336 493 23047209612 494 23280241076 495 23515161487 496 23751966712 497 23990683726 498 24231308362 499 24473867812 500 24718357876 501 24964805963 502 25213207840 503 25463591134 504 25715951578 505 25970317019 506 26226683156 507 26485078056 508 26745497384 509 27007969428 510 27272489819 511 27539087067 512 27807756769 513 28078527657 514 28351395294 515 28626388636 516 28903503211 517 29182768200 518 29464179096 519 29747765305 520 30033522286 521 30321479671 522 30611632884 523 30904011784 524 31198611760 525 31495462899 526 31794560555 527 32095935044 528 32399581684 529 32705531021 530 33013778338 531 33324354411 532 33637254488 533 33952509576 534 34270114887 535 34590101661 536 34912465074 537 35237236599 538 35564411376 539 35894021112 540 36226060911 541 36560562715 542 36897521592 543 37236969719 544 37578902128 545 37923351233 546 38270312029 547 38619817168 548 38971861608 549 39326478239 550 39683661983 551 40043445969 552 40405825082 553 40770832691 554 41138463644 555 41508751551 556 41881691223 557 42257316512 558 42635622191 559 43016642355 560 43400371740 561 43786844684 562 44176055886 563 44568039928 564 44962791471 565 45360345343 566 45760696167 567 46163879017 568 46569888478 569 46978759871 570 47390487743 571 47805107663 572 48222614140 573 48643042991 574 49066388687 575 49492687295 576 49921933247 577 50354162861 578 50789370530 579 51227592823 580 51668824095 581 52113101167 582 52560418355 583 53010812733 584 53464278578 585 53920853218 586 54380530891 587 54843349180 588 55309302283 589 55778428039 590 56250720607 591 56726218082 592 57204914584 593 57686848465 594 58172013805 595 58660449215 596 59152148735 597 59647151235 598 60145450715 599 60647086305 600 61152051965 601 61660387086 602 62172085588 603 62687187123 604 63205685571 605 63727620847 606 64252986790 607 64781823579 608 65314125012 609 65849931532 610 66389236897 611 66932081815 612 67478460003 613 68028412435 614 68581932787 615 69139062300 616 69699794609 617 70264171223 618 70832185735 619 71403879923 620 71979247339 621 72558330030 622 73141121507 623 73727664087 624 74317951239 625 74912025552 626 75509880453 627 76111558803 628 76717053987 629 77326409139 630 77939617602 631 78556722784 632 79177717986 633 79802646890 634 80431502755 635 81064329539 636 81701120458 637 82341919747 638 82986720579 639 83635567466 640 84288453539 641 84945423588 642 85606470701 643 86271639947 644 86940924371 645 87614369322 646 88291967802 647 88973765441 648 89659755197 649 90349982982 650 91044441711 651 91743177578 652 92446183455 653 93153505819 654 93865137498 655 94581125254 656 95301461871 657 96026194396 658 96755315569 659 97488872723 660 98226858554 661 98969320682 662 99716251759 663 100467699692 664 101223657089 665 101984172146 666 102749237426 667 103518901415 668 104293156631 669 105072051850 670 105855579546 671 106643788786 672 107436671999 673 108234278544 674 109036600805 675 109843688434 676 110655533770 677 111472186759 678 112293639694 679 113119942816 680 113951088373 681 114787126901 682 115628050603 683 116473910311 684 117324698182 685 118180465346 686 119041203914 687 119906965314 688 120777741611 689 121653584532 690 122534486096 691 123420498330 692 124311613207 693 125207883054 694 126109299798 695 127015916068 696 127927723744 697 128844775758 698 129767063943 699 130694641534 700 131627500318 701 132565693834 702 133509213822 703 134458114126 704 135412386439 705 136372084911 706 137337201188 707 138307789727 708 139283842126 709 140265413150 710 141252494350 711 142245140799 712 143243344001 713 144247159338 714 145256578266 715 146271656478 716 147292385382 717 148318820982 718 149350954638 719 150388842666 720 151432476378 721 152481912403 722 153537142005 723 154598222126 724 155665143982 725 156737964830 726 157816675837 727 158901334576 728 159991932165 729 161088526493 730 162191108630 731 163299736782 732 164414401970 733 165535162718 734 166662009998 735 167795002653 736 168934131606 737 170079456020 738 171230966768 739 172388723334 740 173552716542 741 174723006197 742 175899583074 743 177082507300 744 178271769600 745 179467430425 746 180669480450 747 181877980450 748 183092921050 749 184314363350 750 185542297925 751 186776786201 752 188017818703 753 189265457183 754 190519692116 755 191780585582 756 193048128005 757 194322381794 758 195603337322 759 196891057327 760 198185532132 761 199486824805 762 200794925618 763 202109897970 764 203431732082 765 204760491685 766 206096166949 767 207438821938 768 208788446770 769 210145105843 770 211508789224 771 212879561645 772 214257413122 773 215642408722 774 217034538409 775 218433867587 776 219840386168 777 221254159893 778 222675178622 779 224103508434 780 225539139137 781 226982137149 782 228432492226 783 229890271125 784 231355463550 785 232828136599 786 234308279923 787 235795960962 788 237291169314 789 238793972761 790 240304360849 791 241822401703 792 243348084816 793 244881478657 794 246422572666 795 247971435657 796 249528057017 797 251092505906 798 252664771657 799 254244923777 800 255832951546 801 257428924818 802 259032832820 803 260644745754 804 262264652793 805 263892624489 806 265528649961 807 267172800111 808 268825064004 809 270485512893 810 272154135789 811 273831004297 812 275516107374 813 277209516977 814 278911222009 815 280621294781 816 282339724141 817 284066582755 818 285801859416 819 287545627145 820 289297874681 821 291058675401 822 292828017989 823 294605976179 824 296392538600 825 298187779344 826 299991686985 827 301804335974 828 303625714829 829 305455898361 830 307294875033 831 309142720016 832 310999421718 833 312865055671 834 314739610227 835 316623161281 836 318515697129 837 320417294029 838 322327940221 839 324247712327 840 326176598531 841 328114675820 842 330061932322 843 332018445389 844 333984203093 845 335959283153 846 337943673584 847 339937452473 848 341940607778 849 343953217954 850 345975270903 851 348006845449 852 350047929437 853 352098602061 854 354158851109 855 356228756146 856 358308304903 857 360397577317 858 362496561061 859 364605336445 860 366723891085 861 368852305664 862 370990567741 863 373138758373 864 375296865061 865 377464969238 866 379643058347 867 381831214197 868 384029424173 869 386237770461 870 388456240388 871 390684916518 872 392923786120 873 395172932136 874 397432341777 875 399702098365 876 401982189052 877 404272697541 878 406573610925 879 408885013288 880 411206891665 881 413539330522 882 415882316835 883 418235935453 884 420600173293 885 422975115588 886 425360749196 887 427757159735 888 430164334003 889 432582358004 890 435011218477 891 437451001812 892 439901694689 893 442363383885 894 444836056020 895 447319798260 896 449814597165 897 452320540290 898 454837614135 899 457365906645 900 459905404260 901 462456195316 902 465018266193 903 467591705618 904 470176499911 905 472772738192 906 475380406720 907 477999595009 908 480630289257 909 483272579372 910 485926451492 911 488591995920 912 491269198733 913 493958150630 914 496658837627 915 499371350820 916 502095676164 917 504831905153 918 507580023680 919 510340123638 920 513112190859 921 515896317635 922 518692489737 923 521500799857 924 524321233704 925 527153884372 926 529998737508 927 532855886608 928 535725317257 929 538607123354 930 541501290422 931 544407912764 932 547326975841 933 550258574360 934 553202693720 935 556159429034 936 559128765638 937 562110799052 938 565105514549 939 568113008056 940 571133264784 941 574166381068 942 577212342056 943 580271244492 944 583343073461 945 586427926117 946 589525787482 947 592636755121 948 595760813992 949 598898062072 950 602048484256 951 605212178933 952 608389130935 953 611579439064 954 614783088088 955 618000177224 956 621230691176 957 624474729576 958 627732277064 959 631003433688 960 634288184024 961 637586628537 962 640898751739 963 644224654512 964 647564321304 965 650917853416 966 654285235231 967 657666568470 968 661061837451 969 664471144315 970 667894473316 971 671331927016 972 674783489604 973 678249264064 974 681729234520 975 685223504379 976 688732057700 977 692254998314 978 695792310214 979 699344097656 980 702910344568 981 706491155631 982 710086514708 983 713696526906 984 717321176022 985 720960567591 986 724614685344 987 728283635244 988 731967400956 989 735666088872 990 739379682591 991 743108288935 992 746851891437 993 750610597349 994 754384390138 995 758173377488 996 761977542799 997 765796994188 998 769631714988 999 773481813749 1000 777347273738