0 1 1 2 2 3 3 3 4 5 5 9 6 4 7 7 8 14 9 27 10 5 11 9 12 19 13 40 14 80 15 6 16 11 17 24 18 53 19 114 20 234 21 7 22 13 23 29 24 66 25 148 26 323 27 677 28 8 29 15 30 34 31 79 32 182 33 412 34 910 35 1941 36 9 37 17 38 39 39 92 40 216 41 501 42 1143 43 2551 44 5523 45 10 46 19 47 44 48 105 49 250 50 590 51 1376 52 3161 53 7120 54 15615 55 11 56 21 57 49 58 118 59 284 60 679 61 1609 62 3771 63 8717 64 19796 65 43906 66 12 67 23 68 54 69 131 70 318 71 768 72 1842 73 4381 74 10314 75 23977 76 54852 77 122868 78 13 79 25 80 59 81 144 82 352 83 857 84 2075 85 4991 86 11911 87 28158 88 65798 89 151525 90 342409 91 14 92 27 93 64 94 157 95 386 96 946 97 2308 98 5601 99 13508 100 32339 101 76744 102 180182 103 417434 104 950727 105 15 106 29 107 69 108 170 109 420 110 1035 111 2541 112 6211 113 15105 114 36520 115 87690 116 208839 117 492459 118 1147145 119 2631165 120 16 121 31 122 74 123 183 124 454 125 1124 126 2774 127 6821 128 16702 129 40701 130 98636 131 237496 132 567484 133 1343563 134 3145394 135 7260579 136 17 137 33 138 79 139 196 140 488 141 1213 142 3007 143 7431 144 18299 145 44882 146 109582 147 266153 148 642509 149 1539981 150 3659623 151 8606848 152 19982612 153 18 154 35 155 84 156 209 157 522 158 1302 159 3240 160 8041 161 19896 162 49063 163 120528 164 294810 165 717534 166 1736399 167 4173852 168 9953117 169 23507190 170 54865566 171 19 172 37 173 89 174 222 175 556 176 1391 177 3473 178 8651 179 21493 180 53244 181 131474 182 323467 183 792559 184 1932817 185 4688081 186 11299386 187 27031768 188 64093031 189 150316973 190 20 191 39 192 94 193 235 194 590 195 1480 196 3706 197 9261 198 23090 199 57425 200 142420 201 352124 202 867584 203 2129235 204 5202310 205 12645655 206 30556346 207 73320496 208 174474790 209 411015705 210 21 211 41 212 99 213 248 214 624 215 1569 216 3939 217 9871 218 24687 219 61606 220 153366 221 380781 222 942609 223 2325653 224 5716539 225 13991924 226 34080924 227 82547961 228 198632607 229 474261691 230 1121818311 231 22 232 43 233 104 234 261 235 658 236 1658 237 4172 238 10481 239 26284 240 65787 241 164312 242 409438 243 1017634 244 2522071 245 6230768 246 15338193 247 37605502 248 91775426 249 222790424 250 537507677 251 1287398452 252 3056773383 253 23 254 45 255 109 256 274 257 692 258 1747 259 4405 260 11091 261 27881 262 69968 263 175258 264 438095 265 1092659 266 2718489 267 6744997 268 16684462 269 41130080 270 101002891 271 246948241 272 600753663 273 1452978593 274 3490267820 275 8316416134 276 24 277 47 278 114 279 287 280 726 281 1836 282 4638 283 11701 284 29478 285 74149 286 186204 287 466752 288 1167684 289 2914907 290 7259226 291 18030731 292 44654658 293 110230356 294 271106058 295 663999649 296 1618558734 297 3923762257 298 9451319304 299 22593883752 300 25 301 49 302 119 303 300 304 760 305 1925 306 4871 307 12311 308 31075 309 78330 310 197150 311 495409 312 1242709 313 3111325 314 7773455 315 19377000 316 48179236 317 119457821 318 295263875 319 727245635 320 1784138875 321 4357256694 322 10586222474 323 25565098825 324 61301547025 325 26 326 51 327 124 328 313 329 794 330 2014 331 5104 332 12921 333 32672 334 82511 335 208096 336 524066 337 1317734 338 3307743 339 8287684 340 20723269 341 51703814 342 128685286 343 319421692 344 790491621 345 1949719016 346 4790751131 347 11721125644 348 28536313898 349 69080289074 350 166118284299 351 27 352 53 353 129 354 326 355 828 356 2103 357 5337 358 13531 359 34269 360 86692 361 219042 362 552723 363 1392759 364 3504161 365 8801913 366 22069538 367 55228392 368 137912751 369 343579509 370 853737607 371 2115299157 372 5224245568 373 12856028814 374 31507528971 375 76859031123 376 186483295373 377 449639574897 378 28 379 55 380 134 381 339 382 862 383 2192 384 5570 385 14141 386 35866 387 90873 388 229988 389 581380 390 1467784 391 3700579 392 9316142 393 23415807 394 58752970 395 147140216 396 367737326 397 916983593 398 2280879298 399 5657740005 400 13990931984 401 34478744044 402 84637773172 403 206848306447 404 502955866070 405 1215751720491 406 29 407 57 408 139 409 352 410 896 411 2281 412 5803 413 14751 414 37463 415 95054 416 240934 417 610037 418 1542809 419 3896997 420 9830371 421 24762076 422 62277548 423 156367681 424 391895143 425 980229579 426 2446459439 427 6091234442 428 15125835154 429 37449959117 430 92416515221 431 227213317521 432 556272157243 433 1355335582936 434 3283883157848 435 30 436 59 437 144 438 365 439 930 440 2370 441 6036 442 15361 443 39060 444 99235 445 251880 446 638694 447 1617834 448 4093415 449 10344600 450 26108345 451 65802126 452 165595146 453 416052960 454 1043475565 455 2612039580 456 6524728879 457 16260738324 458 40421174190 459 100195257270 460 247578328595 461 609588448416 462 1494919445381 463 3649318454010 464 8861749186770 465 31 466 61 467 149 468 378 469 964 470 2459 471 6269 472 15971 473 40657 474 103416 475 262826 476 667351 477 1692859 478 4289833 479 10858829 480 27454614 481 69326704 482 174822611 483 440210777 484 1106721551 485 2777619721 486 6958223316 487 17395641494 488 43392389263 489 107973999319 490 267943339669 491 662904739589 492 1634503307826 493 4014753750172 494 9818471212811 495 23892651132341 496 32 497 63 498 154 499 391 500 998 501 2548 502 6502 503 16581 504 42254 505 107597 506 273772 507 696008 508 1767884 509 4486251 510 11373058 511 28800883 512 72851282 513 184050076 514 464368594 515 1169967537 516 2943199862 517 7391717753 518 18530544664 519 46363604336 520 115752741368 521 288308350743 522 716221030762 523 1774087170271 524 4380189046334 525 10775193238852 526 26397381914302 527 64364212966173 528 33 529 65 530 159 531 404 532 1032 533 2637 534 6735 535 17191 536 43851 537 111778 538 284718 539 724665 540 1842909 541 4682669 542 11887287 543 30147152 544 76375860 545 193277541 546 488526411 547 1233213523 548 3108780003 549 7825212190 550 19665447834 551 49334819409 552 123531483417 553 308673361817 554 769537321935 555 1913671032716 556 4745624342496 557 11731915264893 558 28902112696263 559 70921683286015 560 173252727304059 561 34 562 67 563 164 564 417 565 1066 566 2726 567 6968 568 17801 569 45448 570 115959 571 295664 572 753322 573 1917934 574 4879087 575 12401516 576 31493421 577 79900438 578 202505006 579 512684228 580 1296459509 581 3274360144 582 8258706627 583 20800351004 584 52306034482 585 131310225466 586 329038372891 587 822853613108 588 2053254895161 589 5111059638658 590 12688637290934 591 31406843478224 592 77479153605857 593 190420407481624 594 466004178803727 595 35 596 69 597 169 598 430 599 1100 600 2815 601 7201 602 18411 603 47045 604 120140 605 306610 606 781979 607 1992959 608 5075505 609 12915745 610 32839690 611 83425016 612 211732471 613 536842045 614 1359705495 615 3439940285 616 8692201064 617 21935254174 618 55277249555 619 139088967515 620 349403383965 621 876169904281 622 2192838757606 623 5476494934820 624 13645359316975 625 33911574260185 626 84036623925699 627 207588087659189 628 510949749016580 629 1252537699142410 630 36 631 71 632 174 633 443 634 1134 635 2904 636 7434 637 19021 638 48642 639 124321 640 317556 641 810636 642 2067984 643 5271923 644 13429974 645 34185959 646 86949594 647 220959936 648 560999862 649 1422951481 650 3605520426 651 9125695501 652 23070157344 653 58248464628 654 146867709564 655 369768395039 656 929486195454 657 2332422620051 658 5841930230982 659 14602081343016 660 36416305042146 661 90594094245541 662 224755767836754 663 555895319229433 664 1370206729603404 665 3364332378871644 666 37 667 73 668 179 669 456 670 1168 671 2993 672 7667 673 19631 674 50239 675 128502 676 328502 677 839293 678 2143009 679 5468341 680 13944203 681 35532228 682 90474172 683 230187401 684 585157679 685 1486197467 686 3771100567 687 9559189938 688 24205060514 689 61219679701 690 154646451613 691 390133406113 692 982802486627 693 2472006482496 694 6207365527144 695 15558803369057 696 38921035824107 697 97151564565383 698 241923448014319 699 600840889442286 700 1487875760064398 701 3672393900041773 702 9030851928181657 703 38 704 75 705 184 706 469 707 1202 708 3082 709 7900 710 20241 711 51836 712 132683 713 339448 714 867950 715 2218034 716 5664759 717 14458432 718 36878497 719 93998750 720 239414866 721 609315496 722 1549443453 723 3936680708 724 9992684375 725 25339963684 726 64190894774 727 162425193662 728 410498417187 729 1036118777800 730 2611590344941 731 6572800823306 732 16515525395098 733 41425766606068 734 103709034885225 735 259091128191884 736 645786459655139 737 1605544790525392 738 3980455421211902 739 9837367461231050 740 24226677417552591 741 39 742 77 743 189 744 482 745 1236 746 3171 747 8133 748 20851 749 53433 750 136864 751 350394 752 896607 753 2293059 754 5861177 755 14972661 756 38224766 757 97523328 758 248642331 759 633473313 760 1612689439 761 4102260849 762 10426178812 763 26474866854 764 67162109847 765 170203935711 766 430863428261 767 1089435068973 768 2751174207386 769 6938236119468 770 17472247421139 771 43930497388029 772 110266505205067 773 276258808369449 774 690732029867992 775 1723213820986386 776 4288516942382031 777 10643882994280443 778 26338162495530641 779 64954149869404773 780 40 781 79 782 194 783 495 784 1270 785 3260 786 8366 787 21461 788 55030 789 141045 790 361340 791 925264 792 2368084 793 6057595 794 15486890 795 39571035 796 101047906 797 257869796 798 657631130 799 1675935425 800 4267840990 801 10859673249 802 27609770024 803 70133324920 804 177982677760 805 451228439335 806 1142751360146 807 2890758069831 808 7303671415630 809 18428969447180 810 46435228169990 811 116823975524909 812 293426488547014 813 735677600080845 814 1840882851447380 815 4596578463552160 816 11450398527329836 817 28449647573508691 818 70482089570289530 819 174052226813568435 820 41 821 81 822 199 823 508 824 1304 825 3349 826 8599 827 22071 828 56627 829 145226 830 372286 831 953921 832 2443109 833 6254013 834 16001119 835 40917304 836 104572484 837 267097261 838 681788947 839 1739181411 840 4433421131 841 11293167686 842 28744673194 843 73104539993 844 185761419809 845 471593450409 846 1196067651319 847 3030341932276 848 7669106711792 849 19385691473221 850 48939958951951 851 123381445844751 852 310594168724579 853 780623170293698 854 1958551881908374 855 4904639984722289 856 12256914060379229 857 30561132651486741 858 76010029271174287 859 188524560838244656 860 466146924895091996 861 42 862 83 863 204 864 521 865 1338 866 3438 867 8832 868 22681 869 58224 870 149407 871 383232 872 982578 873 2518134 874 6450431 875 16515348 876 42263573 877 108097062 878 276324726 879 705946764 880 1802427397 881 4599001272 882 11726662123 883 29879576364 884 76075755066 885 193540161858 886 491958461483 887 1249383942492 888 3169925794721 889 8034542007954 890 20342413499262 891 51444689733912 892 129938916164593 893 327761848902144 894 825568740506551 895 2076220912369368 896 5212701505892418 897 13063429593428622 898 32672617729464791 899 81537968972059044 900 202996894862920877 901 504035987268235902 902 1247805276220175238 903 43 904 85 905 209 906 534 907 1372 908 3527 909 9065 910 23291 911 59821 912 153588 913 394178 914 1011235 915 2593159 916 6646849 917 17029577 918 43609842 919 111621640 920 285552191 921 730104581 922 1865673383 923 4764581413 924 12160156560 925 31014479534 926 79046970139 927 201318903907 928 512323472557 929 1302700233665 930 3309509657166 931 8399977304116 932 21299135525303 933 53949420515873 934 136496386484435 935 344929529079709 936 870514310719404 937 2193889942830362 938 5520763027062547 939 13869945126478015 940 34784102807442841 941 87065908672943801 942 217469228887597098 943 541925049641379808 944 1347000129314930735 945 3338574694487045309 946 44 947 87 948 214 949 547 950 1406 951 3616 952 9298 953 23901 954 61418 955 157769 956 405124 957 1039892 958 2668184 959 6843267 960 17543806 961 44956111 962 115146218 963 294779656 964 754262398 965 1928919369 966 4930161554 967 12593650997 968 32149382704 969 82018185212 970 209097645956 971 532688483631 972 1356016524838 973 3449093519611 974 8765412600278 975 22255857551344 976 56454151297834 977 143053856804277 978 362097209257274 979 915459880932257 980 2311558973291356 981 5828824548232676 982 14676460659527408 983 36895587885420891 984 92593848373828558 985 231941562912273319 986 579814112014523714 987 1446194982409686232 988 3598270191398167894 989 8928419451057327777 990 45 991 89 992 219 993 560 994 1440 995 3705 996 9531 997 24511 998 63015 999 161950 1000 416070 1001 1068549 1002 2743209 1003 7039685 1004 18058035 1005 46302380 1006 118670796 1007 304007121 1008 778420215 1009 1992165355 1010 5095741695 1011 13027145434 1012 33284285874 1013 84989400285 1014 216876388005 1015 553053494705 1016 1409332816011 1017 3588677382056 1018 9130847896440 1019 23212579577385 1020 58958882079795 1021 149611327124119 1022 379264889434839 1023 960405451145110 1024 2429228003752350 1025 6136886069402805 1026 15482976192576801 1027 39007072963398941 1028 98121788074713315 1029 246413896936949540 1030 617703174387667620 1031 1545389835504441729 1032 3857965688309290479 1033 9608311088695940035 1034 23866879799412427695 1035 46 1036 91 1037 224 1038 573 1039 1474 1040 3794 1041 9764 1042 25121 1043 64612 1044 166131 1045 427016 1046 1097206 1047 2818234 1048 7236103 1049 18572264 1050 47648649 1051 122195374 1052 313234586 1053 802578032 1054 2055411341 1055 5261321836 1056 13460639871 1057 34419189044 1058 87960615358 1059 224655130054 1060 573418505779 1061 1462649107184 1062 3728261244501 1063 9496283192602 1064 24169301603426 1065 61463612861756 1066 156168797443961 1067 396432569612404 1068 1005351021357963 1069 2546897034213344 1070 6444947590572934 1071 16289491725626194 1072 41118558041376991 1073 103649727775598072 1074 260886230961625761 1075 655592236760811526 1076 1644584688599197226 1077 4117661185220413064 1078 10288202726334552293 1079 25646859215417141884 1080 63772307725546057239 1081 47 1082 93 1083 229 1084 586 1085 1508 1086 3883 1087 9997 1088 25731 1089 66209 1090 170312 1091 437962 1092 1125863 1093 2893259 1094 7432521 1095 19086493 1096 48994918 1097 125719952 1098 322462051 1099 826735849 1100 2118657327 1101 5426901977 1102 13894134308 1103 35554092214 1104 90931830431 1105 232433872103 1106 593783516853 1107 1515965398357 1108 3867845106946 1109 9861718488764 1110 25126023629467 1111 63968343643717 1112 162726267763803 1113 413600249789969 1114 1050296591570816 1115 2664566064674338 1116 6753009111743063 1117 17096007258675587 1118 43230043119355041 1119 109177667476482829 1120 275358564986301982 1121 693481299133955432 1122 1743779541693952723 1123 4377356682131535649 1124 10968094363973164551 1125 27426838631421856073 1126 68432354335921587548 1127 170330110571596560142 1128 48 1129 95 1130 234 1131 599 1132 1542 1133 3972 1134 10230 1135 26341 1136 67806 1137 174493 1138 448908 1139 1154520 1140 2968284 1141 7628939 1142 19600722 1143 50341187 1144 129244530 1145 331689516 1146 850893666 1147 2181903313 1148 5592482118 1149 14327628745 1150 36688995384 1151 93903045504 1152 240212614152 1153 614148527927 1154 1569281689530 1155 4007428969391 1156 10227153784926 1157 26082745655508 1158 66473074425678 1159 169283738083645 1160 430767929967534 1161 1095242161783669 1162 2782235095135332 1163 7061070632913192 1164 17902522791724980 1165 45341528197333091 1166 114705607177367586 1167 289830899010978203 1168 731370361507099338 1169 1842974394788708220 1170 4637052179042658234 1171 11647986001611776809 1172 29206818047426570262 1173 73092400946297117857 1174 182530270986718436880 1175 454758137793989969616 1176 49 1177 97 1178 239 1179 612 1180 1576 1181 4061 1182 10463 1183 26951 1184 69403 1185 178674 1186 459854 1187 1183177 1188 3043309 1189 7825357 1190 20114951 1191 51687456 1192 132769108 1193 340916981 1194 875051483 1195 2245149299 1196 5758062259 1197 14761123182 1198 37823898554 1199 96874260577 1200 247991356201 1201 634513539001 1202 1622597980703 1203 4147012831836 1204 10592589081088 1205 27039467681549 1206 68977805207639 1207 175841208403487 1208 447935610145099 1209 1140187731996522 1210 2899904125596326 1211 7369132154083321 1212 18709038324774373 1213 47453013275311141 1214 120233546878252343 1215 304303233035654424 1216 769259423880243244 1217 1942169247883463717 1218 4896747675953780819 1219 12327877639250389067 1220 30986797463431284451 1221 77752447556672648166 1222 194730431401840313618 1223 486698572428980069521 1224 1213684577030241571873 1225 50 1226 99 1227 244 1228 625 1229 1610 1230 4150 1231 10696 1232 27561 1233 71000 1234 182855 1235 470800 1236 1211834 1237 3118334 1238 8021775 1239 20629180 1240 53033725 1241 136293686 1242 350144446 1243 899209300 1244 2308395285 1245 5923642400 1246 15194617619 1247 38958801724 1248 99845475650 1249 255770098250 1250 654878550075 1251 1675914271876 1252 4286596694281 1253 10958024377250 1254 27996189707590 1255 71482535989600 1256 182398678723329 1257 465103290322664 1258 1185133302209375 1259 3017573156057320 1260 7677193675253450 1261 19515553857823766 1262 49564498353289191 1263 125761486579137100 1264 318775567060330645 1265 807148486253387150 1266 2041364100978219214 1267 5156443172864903404 1268 13007769276889001325 1269 32766776879435998640 1270 82412494167048178475 1271 206930591816962190356 1272 518639007063970169426 1273 1297305720520089994850 1274 3237976302151593069075