0 1 1 3 2 8 3 17 4 33 5 58 6 97 7 153 8 233 9 342 10 489 11 681 12 930 13 1245 14 1641 15 2130 16 2730 17 3456 18 4330 19 5370 20 6602 21 8048 22 9738 23 11698 24 13963 25 16563 26 19538 27 22923 28 26763 29 31098 30 35979 31 41451 32 47571 33 54390 34 61971 35 70371 36 79660 37 89901 38 101171 39 113540 40 127092 41 141904 42 158068 43 175668 44 194804 45 215568 46 238068 47 262404 48 288693 49 317043 50 347580 51 380421 52 415701 53 453546 54 494101 55 537501 56 583901 57 633446 58 686301 59 742621 60 802582 61 866349 62 934109 63 1006038 64 1082334 65 1163184 66 1248798 67 1339374 68 1435134 69 1536288 70 1643070 71 1755702 72 1874431 73 1999491 74 2131142 75 2269631 76 2415231 77 2568202 78 2728831 79 2897391 80 3074183 81 3259494 82 3453639 83 3656919 84 3869664 85 4092189 86 4324839 87 4567944 88 4821864 89 5086944 90 5363560 91 5652072 92 5952872 93 6266336 94 6592872 95 6932872 96 7286761 97 7654947 98 8037872 99 8435961 100 8849673 101 9279450 102 9725769 103 10189089 104 10669905 105 11168694 106 11685969 107 12222225 108 12777994 109 13353789 110 13950161 111 14567642 112 15206802 113 15868192 114 16552402 115 17260002 116 17991602 117 18747792 118 19529202 119 20336442 120 21170163 121 22030995 122 22919610 123 23836659 124 24782835 125 25758810 126 26765299 127 27802995 128 28872635 129 29974934 130 31110651 131 32280523 132 33485332 133 34725837 134 36002843 135 37317132 136 38669532 137 40060848 138 41491932 139 42963612 140 44476764 141 46032240 142 47630940 143 49273740 144 50961565 145 52695315 146 54475940 147 56304365 148 58181565 149 60108490 150 62086141 151 64115493 152 66197573 153 68333382 154 70523973 155 72770373 156 75073662 157 77434893 158 79855173 159 82335582 160 84877254 161 87481296 162 90148870 163 92881110 164 95679206 165 98544320 166 101477670 167 104480446 168 107553895 169 110699235 170 113917742 171 117210663 172 120579303 173 124024938 174 127548903 175 131152503 176 134837103 177 138604038 178 142454703 179 146390463 180 150412744 181 154522941 182 158722511 183 163012880 184 167395536 185 171871936 186 176443600 187 181112016 188 185878736 189 190745280 190 195713232 191 200784144 192 205959633 193 211241283 194 216630744 195 222129633 196 227739633 197 233462394 198 239299633 199 245253033 200 251324345 201 257515286 202 263827641 203 270263161 204 276823666 205 283510941 206 290326841 207 297273186 208 304351866 209 311564736 210 318913722 211 326400714 212 334027674 213 341796528 214 349709274 215 357767874 216 365974363 217 374330739 218 382839074 219 391501403 220 400319835 221 409296442 222 418433371 223 427732731 224 437196707 225 446827446 226 456627171 227 466598067 228 476742396 229 487062381 230 497560323 231 508238484 232 519099204 233 530144784 234 541377604 235 552800004 236 564414404 237 576223184 238 588228804 239 600433684 240 612840325 241 625451187 242 638268812 243 651295701 244 664534437 245 677987562 246 691657701 247 705547437 248 719659437 249 733996326 250 748560813 251 763355565 252 778383334 253 793646829 254 809148845 255 824892134 256 840879534 257 857113840 258 873597934 259 890334654 260 907326926 261 924577632 262 942089742 263 959866182 264 977909967 265 996224067 266 1014811542 267 1033675407 268 1052818767 269 1072244682 270 1091956303 271 1111956735 272 1132249175 273 1152836774 274 1173722775 275 1194910375 276 1216402864 277 1238203485 278 1260315575 279 1282742424 280 1305487416 281 1328553888 282 1351945272 283 1375664952 284 1399716408 285 1424103072 286 1448828472 287 1473896088 288 1499309497 289 1525072227 290 1551187904 291 1577660105 292 1604492505 293 1631688730 294 1659252505 295 1687187505 296 1715497505 297 1744186230 298 1773257505 299 1802715105 300 1832562906 301 1862804733 302 1893444513 303 1924486122 304 1955933538 305 1987790688 306 2020061602 307 2052750258 308 2085860738 309 2119397072 310 2153363394 311 2187763786 312 2222602435 313 2257883475 314 2293611146 315 2329789635 316 2366423235 317 2403516186 318 2441072835 319 2479097475 320 2517594507 321 2556568278 322 2596023243 323 2635963803 324 2676394468 325 2717319693 326 2758744043 327 2800672028 328 2843108268 329 2886057328 330 2929523884 331 2973512556 332 3018028076 333 3063075120 334 3108658476 335 3154782876 336 3201453165 337 3248674131 338 3296450676 339 3344787645 340 3393689997 341 3443162634 342 3493210573 343 3543838773 344 3595052309 345 3646856198 346 3699255573 347 3752255509 348 3805861198 349 3860077773 350 3914910485 351 3970364526 352 4026445206 353 4083157776 354 4140507606 355 4198500006 356 4257140406 357 4316434176 358 4376386806 359 4437003726 360 4498290487 361 4560252579 362 4622895614 363 4686225143 364 4750246839 365 4814966314 366 4880389303 367 4946521479 368 5013368639 369 5080936518 370 5149230975 371 5218257807 372 5288022936 373 5358532221 374 5429791647 375 5501807136 376 5574584736 377 5648130432 378 5722450336 379 5797550496 380 5873437088 381 5950116224 382 6027594144 383 6105877024 384 6184971169 385 6264882819 386 6345618344 387 6427184049 388 6509586369 389 6592831674 390 6676926465 391 6761877177 392 6847690377 393 6934372566 394 7021930377 395 7110370377 396 7199699266 397 7289923677 398 7381050377 399 7473086066 400 7566037578 401 7659911680 402 7754715274 403 7850455194 404 7947138410 405 8044771824 406 8143362474 407 8242917330 408 8343443499 409 8444948019 410 8547438066 411 8650920747 412 8755403307 413 8860892922 414 8967396907 415 9074922507 416 9183477107 417 9293068022 418 9403702707 419 9515388547 420 9628133068 421 9741943725 422 9856828115 423 9972793764 424 10089848340 425 10207999440 426 10327254804 427 10447622100 428 10569109140 429 10691723664 430 10815473556 431 10940366628 432 11066410837 433 11193614067 434 11321984348 435 11451529637 436 11582258037 437 11714177578 438 11847296437 439 11981622717 440 12117164669 441 12253930470 442 12391928445 443 12531166845 444 12671654070 445 12813398445 446 12956408445 447 13100692470 448 13246259070 449 13393116720 450 13541274046 451 13690739598 452 13841522078 453 13993630112 454 14147072478 455 14301857878 456 14457995167 457 14615493123 458 14774360678 459 14934606687 460 15096240159 461 15259270026 462 15423705375 463 15589555215 464 15756828711 465 15925534950 466 16095683175 467 16267282551 468 16440342400 469 16614871965 470 16790880647 471 16968377768 472 17147372808 473 17327875168 474 17509894408 475 17693440008 476 17878521608 477 18065148768 478 18253331208 479 18443078568 480 18634400649 481 18827307171 482 19021808016 483 19217912985 484 19415632041 485 19614975066 486 19815952105 487 20018573121 488 20222848241 489 20428787510 490 20636401137 491 20845699249 492 21056692138 493 21269390013 494 21483803249 495 21699942138 496 21917817138 497 22137438624 498 22358817138 499 22581963138 500 22806887250 501 23033600016 502 23262112146 503 23492434266 504 23724577171 505 23958551571 506 24194368346 507 24432038291 508 24671572371 509 24912981466 510 25156276627 511 25401468819 512 25648569179 513 25897588758 514 26148538779 515 26401430379 516 26656274868 517 26913083469 518 27171867579 519 27432638508 520 27695407740 521 27960186672 522 28226986876 523 28495819836 524 28766697212 525 29039630576 526 29314631676 527 29591712172 528 29870883901 529 30152158611 530 30435548228 531 30721064589 532 31008719709 533 31298525514 534 31590494109 535 31884637509 536 32180967909 537 32479497414 538 32780238309 539 33083202789 540 33388403230 541 33695851917 542 34005561317 543 34317543806 544 34631811942 545 34948378192 546 35267255206 547 35588455542 548 35911991942 549 36237877056 550 36566123718 551 36896744670 552 37229752839 553 37565161059 554 37902982350 555 38243229639 556 38585916039 557 38931054570 558 39278658439 559 39628740759 560 39981314831 561 40336393862 562 40693991247 563 41054120287 564 41416794472 565 41782027197 566 42149832047 567 42520222512 568 42893212272 569 43268814912 570 43647044208 571 44027913840 572 44411437680 573 44797629504 574 45186503280 575 45578072880 576 45972352369 577 46369355715 578 46769097080 579 47171590529 580 47576850321 581 47984890618 582 48395725777 583 48809370057 584 49225837913 585 49645143702 586 50067301977 587 50492327193 588 50920234002 589 51351036957 590 51784750809 591 52221390210 592 52660970010 593 53103504960 594 53549010010 595 53997500010 596 54448990010 597 54903494960 598 55361030010 599 55821610210 600 56285250811 601 56751966963 602 57221774018 603 57694687227 604 58170722043 605 58649893818 606 59132218107 607 59617710363 608 60106386243 609 60598261302 610 61093351299 611 61591671891 612 62093238940 613 62598068205 614 63106175651 615 63617577140 616 64132288740 617 64650326416 618 65171706340 619 65696444580 620 66224557412 621 66756061008 622 67290971748 623 67829305908 624 68371079973 625 68916310323 626 69465013548 627 70017206133 628 70572904773 629 71132126058 630 71694886789 631 72261203661 632 72831093581 633 73404573350 634 73981659981 635 74562370381 636 75146721670 637 75734730861 638 76326415181 639 76921791750 640 77520877902 641 78123690864 642 78730248078 643 79340566878 644 79954664814 645 80572559328 646 81194268078 647 81819808614 648 82449198703 649 83082456003 650 83719598390 651 84360643631 652 85005609711 653 85654514506 654 86307376111 655 86964212511 656 87625041911 657 88289882406 658 88958752311 659 89631669831 660 90308653392 661 90989721309 662 91674892119 663 92364184248 664 93057616344 665 93755206944 666 94456974808 667 95162938584 668 95873117144 669 96587529248 670 97306193880 671 98029129912 672 98756356441 673 99487892451 674 100223757152 675 100963969641 676 101708549241 677 102457515162 678 103210886841 679 103968683601 680 104730924993 681 105497630454 682 106268819649 683 107044512129 684 107824727674 685 108609485949 686 109398806849 687 110192710154 688 110991215874 689 111794343904 690 112602114370 691 113414547282 692 114231662882 693 115053481296 694 115880022882 695 116711307882 696 117547356771 697 118388189907 698 119233827882 699 120084291171 700 120939600483 701 121799776410 702 122664839779 703 123534811299 704 124409711915 705 125289562454 706 126174383979 707 127064197435 708 127959024004 709 128858884749 710 129763800971 711 130673793852 712 131588884812 713 132509095152 714 133434446412 715 134364960012 716 135300657612 717 136241560752 718 137187691212 719 138139070652 720 139095720973 721 140057663955 722 141024921620 723 141997515869 724 142975468845 725 143958802570 726 144947539309 727 145941701205 728 146941310645 729 147946389894 730 148956961461 731 149973047733 732 150994671342 733 152021854797 734 153054620853 735 154092992142 736 155136991542 737 156186641808 738 157241965942 739 158302986822 740 159369727574 741 160442211200 742 161520460950 743 162604499950 744 163694351575 745 164790039075 746 165891585950 747 166999015575 748 168112351575 749 169231617450 750 170356836951 751 171488033703 752 172625231583 753 173768454342 754 174917725983 755 176073070383 756 177234511672 757 178402073853 758 179575781183 759 180755657792 760 181941728064 761 183134016256 762 184332546880 763 185537344320 764 186748433216 765 187965838080 766 189189583680 767 190419694656 768 191656195905 769 192899112195 770 194148468552 771 195404289873 772 196666601313 773 197935427898 774 199210794913 775 200492727513 776 201781251113 777 203076390998 778 204378172713 779 205686621673 780 207001763554 781 208323623901 782 209652228521 783 210987603090 784 212329773546 785 213678765696 786 215034605610 787 216397319226 788 217766932746 789 219143472240 790 220526964042 791 221917434354 792 223314909643 793 224719416243 794 226130980754 795 227549629643 796 228975389643 797 230408287354 798 231848349643 799 233295603243 800 234750075155 801 236211792246 802 237680781651 803 239157070371 804 240640685676 805 242131654701 806 243630004851 807 245135763396 808 246648957876 809 248169615696 810 249697764532 811 251233431924 812 252776645684 813 254327433488 814 255885823284 815 257451842884 816 259025520373 817 260606883699 818 262195961084 819 263792780613 820 265397370645 821 267009759402 822 268629975381 823 270258046941 824 271894002717 825 273537871206 826 275189681181 827 276849461277 828 278517240406 829 280193047341 830 281876911133 831 283568860694 832 285268925214 833 286977133744 834 288693515614 835 290418100014 836 292150916414 837 293891994144 838 295641362814 839 297399051894 840 299165091135 841 300939510147 842 302722338822 843 304513606911 844 306313344447 845 308121581322 846 309938347711 847 311763673647 848 313597589447 849 315440125286 850 317291311623 851 319151178775 852 321019757344 853 322897077789 854 324783170855 855 326678067144 856 328581797544 857 330494392800 858 332415883944 859 334346301864 860 336285677736 861 338234042592 862 340191427752 863 342157864392 864 344133383977 865 346118017827 866 348111797552 867 350114754617 868 352126920777 869 354148327642 870 356179007113 871 358218990945 872 360268311185 873 362326999734 874 364395088785 875 366472610385 876 368559596874 877 370656080445 878 372762093585 879 374877668634 880 377002838226 881 379137634848 882 381282091282 883 383436240162 884 385600114418 885 387773746832 886 389957170482 887 392150418298 888 394353523507 889 396566519187 890 398789438714 891 401022315315 892 403265182515 893 405518073690 894 407781022515 895 410054062515 896 412337227515 897 414630551190 898 416934067515 899 419247810315 900 421571813716 901 423906111693 902 426250738523 903 428605728332 904 430971115548 905 433346934448 906 435733219612 907 438130005468 908 440537326748 909 442955218032 910 445383714204 911 447822849996 912 450272660445 913 452733180435 914 455204445156 915 457686489645 916 460179349245 917 462683059146 918 465197654845 919 467723171685 920 470259645317 921 472807111238 922 475365605253 923 477935163013 924 480515820478 925 483107613453 926 485710578053 927 488324750238 928 490950166278 929 493586862288 930 496234874694 931 498894239766 932 501564994086 933 504247174080 934 506940816486 935 509645957886 936 512362635175 937 515090885091 938 517830744686 939 520582250855 940 523345440807 941 526120351594 942 528907020583 943 531705484983 944 534515782319 945 537337949958 946 540172025583 947 543018046719 948 545876051208 949 548746076733 950 551628161295 951 554522342736 952 557428659216 953 560347148736 954 563277849616 955 566220800016 956 569176038416 957 572143603136 958 575123532816 959 578115865936 960 581120641297 961 584137897539 962 587167673624 963 590210008353 964 593264940849 965 596332510074 966 599412755313 967 602505715689 968 605611430649 969 608729939478 970 611861281785 971 615005497017 972 618162624946 973 621332705181 974 624515777657 975 627711882146 976 630921058746 977 634143347392 978 637378788346 979 640627421706 980 643889287898 981 647164427184 982 650452880154 983 653754687234 984 657069889179 985 660398526579 986 663740640354 987 667096271259 988 670465460379 989 673848248634 990 677244677275 991 680654787387 992 684078620387 993 687516217526 994 690967620387 995 694432870387 996 697912009276 997 701405078637 998 704912120387 999 708433176276 1000 711968288388