0 1 1 1 2 1 3 2 4 2 5 1 6 5 7 4 8 3 9 1 10 12 11 10 12 7 13 4 14 1 15 29 16 25 17 18 18 11 19 5 20 1 21 71 22 62 23 47 24 30 25 16 26 6 27 1 28 175 29 155 30 121 31 82 32 47 33 22 34 7 35 1 36 434 37 389 38 311 39 220 40 135 41 70 42 29 43 8 44 1 45 1082 46 979 47 799 48 584 49 378 50 212 51 100 52 37 53 9 54 1 55 2709 56 2471 57 2051 58 1541 59 1039 60 620 61 320 62 138 63 46 64 10 65 1 66 6807 67 6252 68 5264 69 4047 70 2822 71 1767 72 978 73 467 74 185 75 56 76 11 77 1 78 17157 79 15852 80 13512 81 10592 82 7597 83 4947 84 2892 85 1492 86 662 87 242 88 67 89 12 90 1 91 43359 92 40269 93 34692 94 27654 95 20314 96 13669 97 8353 98 4579 99 2211 100 915 101 310 102 79 103 13 104 1 105 109830 106 102468 107 89103 108 72068 109 54040 110 37389 111 23709 112 13651 113 7043 114 3194 115 1237 116 390 117 92 118 14 119 1 120 278769 121 261132 122 228947 123 187557 124 143183 125 101469 126 66396 127 39824 128 21677 129 10559 130 4511 131 1640 132 483 133 106 134 15 135 1 136 708840 137 666380 138 588533 139 487619 140 378169 141 273659 142 183980 143 114246 144 65017 145 33553 146 15473 147 6244 148 2137 149 590 150 121 151 16 152 1 153 1805291 154 1702621 155 1513585 156 1266764 157 996264 158 734339 159 505489 160 323419 161 191139 162 103484 163 50759 164 22214 165 8488 166 2742 167 712 168 137 169 17 170 1 171 4604363 172 4355117 173 3894437 174 3288994 175 2619198 176 1962433 177 1379267 178 905801 179 553025 180 311829 181 160984 182 75217 183 31307 184 11352 185 3470 186 850 187 154 188 18 189 1 190 11758552 191 11151296 192 10024963 193 8535865 194 6874361 195 5226559 196 3742012 197 2514674 198 1579516 199 922354 200 497271 201 245294 202 109388 203 43387 204 14960 205 4337 206 1005 207 172 208 19 209 1 210 30064037 211 28579694 212 25817687 213 22146195 214 18017587 215 13880499 216 10103978 217 6930401 218 4463519 219 2687312 220 1503935 221 776736 222 366762 223 156383 224 59214 225 19452 226 5360 227 1178 228 191 229 20 230 1 231 76949216 232 73310122 233 66518613 234 57445604 235 47169920 236 36775505 237 27172866 238 18983224 239 12501716 240 7732412 241 4470712 242 2402139 243 1190493 244 538972 245 220089 246 79689 247 24985 248 6557 249 1370 250 211 251 21 252 1 253 197144517 254 188198257 255 171456652 256 148987942 257 123373442 258 97237792 259 72827617 260 51727405 261 34753833 262 22017528 263 13101328 264 7286608 265 3764842 266 1793171 267 779536 268 305311 269 105871 270 31734 271 7947 272 1582 273 232 274 22 275 1 276 505538075 277 483489304 278 442124238 279 386372432 280 322429256 281 256663346 282 194619948 283 140325631 284 95997050 285 62140277 286 37934752 287 21750639 288 11654128 289 5798577 290 2657929 291 1111029 292 417931 293 138995 294 39893 295 9550 296 1815 297 254 298 23 299 1 300 1297420937 301 1242953360 302 1140529322 303 1001937984 304 842091592 305 676474758 306 518781308 307 379215224 308 263709125 309 174054551 310 108724340 311 64052911 312 35438502 313 18317463 314 8787999 315 3881578 316 1562084 317 565085 318 180491 319 49676 320 11387 321 2070 322 277 323 24 324 1 325 3332257159 326 3197414315 327 2943296428 328 2598186466 329 2198075078 330 1780684312 331 1379851342 332 1021380026 333 720981850 334 484347739 335 308897050 336 186465114 337 106154748 338 56745387 339 28329111 340 13120632 341 5590816 342 2168665 343 755359 344 232004 345 61318 346 13480 347 2348 348 301 349 25 350 1 351 8564507696 352 8230014542 353 7598367887 354 6737619988 355 5734854264 356 4682135974 357 3663134372 358 2742997994 359 1963000490 360 1340172088 361 870985563 362 537464001 363 313926747 364 172911783 365 89407131 366 43158981 367 19318029 368 7949755 369 2975537 370 999005 371 295415 372 75076 373 15852 374 2650 375 326 376 26 377 1 378 22026772775 379 21195475810 380 19622705989 381 17472655673 382 14956535148 383 12299440298 384 9708416998 385 7347752830 386 5325188722 387 3689810402 388 2439724602 389 1535911197 390 918147783 391 519500274 392 277148784 393 138763509 394 64835949 395 28074656 396 11168938 397 4037953 398 1308178 399 372863 400 91230 401 18527 402 2977 403 352 404 27 405 1 406 56684513664 407 54614940032 408 50692469585 409 45314276822 410 38993776855 411 32282256470 412 25692475754 413 19638360556 414 14399751464 415 10114551638 416 6794460638 417 4356319581 418 2659632507 419 1541885058 420 846005436 421 437589261 422 212356085 423 96129788 424 40306010 425 15516064 426 5423579 427 1697195 428 466768 429 110084 430 21530 431 3330 432 379 433 28 434 1 435 145957194585 436 140796447471 437 130998980450 438 117527867589 439 101633774999 440 84669068781 441 67904675782 442 52382834944 443 38827474936 444 27618953338 445 18825607255 446 12274501529 447 7639689363 448 4528022727 449 2548330971 450 1357187273 451 681239185 452 320717227 453 140782924 454 57207700 455 21328660 456 7214679 457 2182817 458 579855 459 131967 460 24887 461 3710 462 407 463 29 464 1 465 376026322977 466 363137682474 467 338630825925 468 304846346216 469 264836934514 470 221925263092 471 179264103753 472 139476625106 473 104429511754 474 75157483891 475 51924601484 476 34383478566 477 21782581112 478 13174158003 479 7587535535 480 4149168168 481 2146787600 482 1046609548 483 478401841 484 203803220 485 80327460 486 29028961 487 9510583 488 2784555 489 715179 490 157234 491 28625 492 4118 493 436 494 30 495 1 496 969233133843 497 936998383905 498 875615874165 499 790786239066 500 689974768823 501 581357232578 502 472761316169 503 370787405669 504 280236145815 505 203892643791 506 142639956686 507 95816159633 508 61700528318 509 38016251923 510 22362530735 511 12526304030 512 6661326131 513 3351081762 514 1588031685 515 705324821 516 291830981 517 111652325 518 39141282 519 12430462 520 3525001 521 876151 522 186267 523 32772 524 4555 525 466 526 31 527 1 528 2499438328614 529 2418709709439 530 2264769671211 531 2051530535838 532 1797281305953 533 1522168054478 534 1245641850663 535 984308242547 536 750486683521 537 551611262401 538 390424158626 539 265773166071 540 173750358762 541 108905152973 542 65317551153 543 37400992728 544 20391924323 545 10553830030 546 5166036427 547 2381384267 548 1028480667 549 413595627 550 153713486 551 52312190 552 16116435 553 4430185 554 1066565 555 219476 556 37357 557 5022 558 497 559 32 560 1 561 6448353232824 562 6245919325359 563 5859394042323 564 5322795273936 565 4681005127446 566 3983733978516 567 3279356831519 568 2609649371062 569 2006170042654 570 1488629460757 571 1065168630412 572 734131523826 573 486728149488 574 309956810965 575 189261166119 576 110584164174 577 61685420950 578 32760709018 579 16513219039 580 7870576540 581 3531629580 582 1484137455 583 580480021 584 209711649 585 69333809 586 20737034 587 5529959 588 1290626 589 257300 590 42410 591 5520 592 529 593 33 594 1 595 16643187462393 596 16134956891067 597 15163338970407 598 13811663907867 599 12190253073945 600 10421927883003 601 8627098330434 602 6910868002688 603 5353962190952 604 4008356871422 605 2897505456369 606 2020255137655 607 1357066125517 608 877040973599 609 544484590105 610 324129758515 611 184638369819 612 100405518977 613 51978468170 614 25534040892 615 11857862908 616 5182651429 617 2120615639 618 807213289 619 283666057 620 91170617 621 26491054 622 6858409 623 1552979 624 300208 625 47962 626 6050 627 562 628 34 629 1 630 42972978583029 631 41695563998508 632 39250565727018 633 35842460678283 634 31742839737369 635 27255545308866 636 22680537384606 637 18282279153012 638 14267017022408 639 10771195057986 640 7860948835034 641 5540695195715 642 3767634087283 643 2468634878256 644 1556394156100 645 942668554265 646 547488226361 647 304261647948 648 161404809000 649 81499795430 650 39042925649 651 17676992521 652 7530000336 653 3001783336 654 1112716154 655 380590694 656 118990121 657 33611816 658 8454296 659 1858739 660 348700 661 54045 662 6613 663 596 664 35 665 1 666 110998333702173 667 107784151417488 668 101625251433402 669 93024202234803 670 82650592650573 671 71256994547838 672 59591263516050 673 48318965557338 674 37966529042454 675 28890804044006 676 21275333632366 677 15149022980377 678 10419898035737 679 6915622148040 680 4423212998516 681 2722421178211 682 1609780058755 683 912749164332 684 495187784208 685 256413489187 686 126361850692 687 59067267077 688 26088160554 689 10837286537 690 4211424127 691 1521126352 692 506701577 693 154197824 694 42371872 695 10361527 696 2213522 697 403308 698 60692 699 7210 700 631 701 36 702 1 703 286807840238805 704 278712172554555 705 263183039358675 706 241457585640495 707 215188949695845 708 186243305405595 709 156486686236620 710 127594478962830 711 100909281621390 712 77361471660840 713 57454211821715 714 41303559452765 715 28716909076871 716 19290098304037 717 12504862168667 718 7812745681217 719 4697462174937 720 2713455359347 721 1502945628727 722 796463328657 723 402799681307 724 193840285802 725 88462713832 726 38135087882 727 15457120862 728 5858661362 729 2063035632 730 669659457 731 198476927 732 53088182 733 12629657 734 2623477 735 464597 736 67937 737 7842 738 667 739 37 740 1 741 741329519329992 742 720918900734547 743 681727546120323 744 626805372460212 745 560239248091362 746 486661946790222 747 410733207088995 748 336671481263502 749 267898703202606 750 206834161059939 751 154843909302954 752 112325657370974 753 78890668797936 754 53596247401535 755 35184493155405 756 22292648846610 757 13613883156746 758 8001113998679 759 4517676532523 760 2445795149504 761 1266741445074 762 626035413864 763 294349926962 764 131217636039 765 55239445979 766 21857691504 767 8084654874 768 2776974192 769 878852694 770 253833239 771 66127794 772 15314423 773 3095319 774 533166 775 75815 776 8510 777 704 778 38 779 1 780 1916770099155726 781 1865263793630307 782 1766268779956407 783 1627314581031402 784 1458517617645951 785 1271391096564984 786 1077579948906099 787 887708912592273 788 710495063904657 789 552215301904659 790 416549515912152 791 304756676019099 792 216095664493574 793 148381311050839 794 98568527234883 795 63278279477544 796 39210183827098 797 23419218328601 798 13461640051979 799 7433749798444 800 3935772327135 801 1993286500098 802 963140263033 803 442671921098 804 192857652660 805 79323130995 806 30656284938 807 11070822303 808 3711183198 809 1145725545 810 322645799 811 81914059 812 18478311 813 3636363 814 609649 815 84362 816 9215 817 742 818 39 819 1 820 4957474472611767 821 4827383772007893 822 4577119608497793 823 4225295606173548 824 3796984047150975 825 3320826716326812 826 2825946750974361 827 2339112444139527 828 1882520575198983 829 1472425720661529 830 1118677584532956 831 825076199053851 832 590342982765576 833 409449255377761 834 275043624607861 835 178764341692915 836 112293798476497 837 68089928208999 838 39796931646501 839 22385367028054 840 12096067180603 841 6266163676402 842 3104748757267 843 1467452200752 844 659613258774 845 280979377089 846 112965583362 847 42661316247 848 15048878352 849 4925721303 850 1484157609 851 407723746 852 100933414 853 22191157 854 4254559 855 694716 856 93615 857 9958 858 781 859 40 860 1 861 12825562618075701 862 12496714059487146 863 11863530206722827 864 10972084680790914 865 9884588752005384 866 8672366417887164 867 7408305962534601 868 6159870857720598 869 4983563676095382 870 3921408578488809 871 2999629988336184 872 2229340090333284 873 1608772772703614 874 1126454551700359 875 764688694443654 876 502823485299729 877 319937884551313 878 196761440003396 879 116810586831575 880 66844616056714 881 36811825557924 882 19473693114174 883 9875224371388 884 4789142295695 885 2215187183955 886 974235088230 887 405949991760 888 159604955658 889 58924732704 890 20313031719 891 6494956859 892 1910900710 893 512370006 894 123742767 895 26530783 896 4958528 897 789074 898 103612 899 10740 900 821 901 41 902 1 903 33190364823026781 904 32358423112277781 905 30755209338503094 906 28494908033345577 907 25732055803532487 908 22644434416100337 909 19414596487168002 910 16212628052211054 911 13182322537105806 912 10432176522258846 913 8031701072625321 914 6012666652319231 915 4374224431971681 916 3090466763469866 917 2118923106835881 918 1408685722601781 919 907229011377941 920 565419983177285 921 340619711245184 922 198081661418159 923 111034067548209 924 59894579367084 925 31033311023990 926 15412101650286 927 7318951309106 928 3314392886856 929 1426824452286 930 581818363875 931 223793841729 932 80806999979 933 27234731679 934 8510503829 935 2446080069 936 640452399 937 150977519 938 31583669 939 5757599 940 893468 941 114392 942 11562 943 862 944 42 945 1 946 85913590140255642 947 83807283214320510 948 79745010277403625 949 74010088494590244 950 66986809500973017 951 59118720288913662 952 50863352992944792 953 42649676218764264 954 34843563435480324 955 27724791553501164 956 21476914258867214 957 16189252066582949 958 11868585075057164 959 8457159750577069 960 5853386898463874 961 3932014355515874 962 2561396832605694 963 1616507265797014 964 987310769009053 965 582890824154838 966 332198482775528 967 182488264825109 968 96464767669972 969 48975221687687 970 23830258662293 971 11085933560018 972 4917085711257 973 2072831702232 974 827494472879 975 311522541668 976 110057278628 977 36280414867 978 11084666291 979 3113767220 980 796482804 981 183360259 982 37445662 983 6661847 984 1008682 985 125995 986 12425 987 904 988 43 989 1 990 222444098671805013 991 217107460519701996 992 206807172647811285 993 192247000239621309 994 174383562480944436 995 154324448366731134 996 133217153013454716 997 112143964594978326 998 92035708670639946 999 73613092725589856 1000 57359256806326006 1001 43522084748188096 1002 32140772460245501 1003 23088664960628241 1004 16123637897720936 1005 10938112363983661 1006 7202689442540641 1007 4599794884234476 1008 2846089147715721 1009 1704318414521260 1010 986543504207266 1011 551256935903525 1012 296894943158778 1013 153858146369666 1014 76572462600892 1015 36518885046712 1016 16649026521221 1017 7235593522493 1018 2988054875050 1019 1168267293196 1020 430625503484 1021 148911855957 1022 48032768309 1023 14354463916 1024 3942632764 1025 985705056 1026 221710169 1027 44222723 1028 7682132 1029 1135540 1030 138462 1031 13330 1032 947 1033 44 1034 1 1035 576082067723056380 1036 562551448624997784 1037 536416623129730965 1038 499427646873786786 1039 453968201586323862 1040 402806443572216624 1041 348822212982219384 1042 294747150060308724 1043 242949202555727804 1044 195283266649054644 1045 153017520021236744 1046 116832861948176654 1047 86882937094004674 1048 62895915568017609 1049 44297028323868964 1050 30332425348729364 1051 20179199858153084 1052 13032066208693824 1053 8162891677462404 1054 4954060242289409 1055 2909920371856523 1056 1652207118444460 1057 905545257761997 1058 478350330441649 1059 243119235354977 1060 118654440608807 1061 55486419379169 1062 24799843216532 1063 10564421217860 1064 4275425130062 1065 1637747374009 1066 591289712883 1067 200214421891 1068 63216097769 1069 18486318932 1070 4966687730 1071 1214192286 1072 266953177 1073 52031713 1074 8830139 1075 1274907 1076 151835 1077 14278 1078 991 1079 45 1080 1 1081 1492271485399305531 1082 1457942678958083133 1083 1391588545980704250 1084 1297565471350220304 1085 1181818729551382836 1086 1051272409774028736 1087 913158653601290016 1088 774374601003277586 1089 640943910594451226 1090 517636896500429336 1091 407774391812142036 1092 313211234315229976 1093 234470942149953436 1094 170987216025263006 1095 121401731342895001 1096 83870541166767751 1097 56341001973035631 1098 36774362860074836 1099 23302928980729916 1100 14322553877087076 1101 8529644228383126 1102 4916415812159455 1103 2739207763489328 1104 1473156677188957 1105 763551543804541 1106 380741210296241 1107 182291676683287 1108 83615090291068 1109 36651634689404 1110 15309326428735 1111 6073836713470 1112 2280339652826 1113 806687464234 1114 267562374676 1115 82726471667 1116 23681493892 1117 6226123024 1118 1488954453 1119 320132897 1120 61001219 1121 10118419 1122 1427690 1123 166157 1124 15270 1125 1036 1126 46 1127 1 1128 3866403582033637815 1129 3779251261713095130 1130 3610680073159276722 1131 3371545100008520604 1132 3076688409089308014 1133 2743443349354484964 1134 2389983451396376954 1135 2033730015138710104 1136 1690006205542430344 1137 1371071932257967954 1138 1085605002606564604 1139 838623706329148794 1140 631786455396441744 1141 463963973950093834 1142 331962460211056794 1143 231280849133969019 1144 156806706141725134 1145 103386227605146559 1146 66236954040429424 1147 41201066843910709 1148 24858693545773134 1149 14533060685587449 1150 8223234995075743 1151 4497565654041177 1152 2374330195934762 1153 1207929990175262 1154 591161557891427 1155 277758558447227 1156 125011630191347 1157 53759372701547 1158 22025755421022 1159 8569574117647 1160 3154375069845 1161 1093760212808 1162 355484021303 1163 107667400853 1164 30182379083 1165 7768257197 1166 1818056856 1167 382422396 1168 71272421 1169 11560431 1170 1594839 1171 181472 1172 16307 1173 1082 1174 47 1175 1 1176 10019786940381065229 1177 9798392237947926534 1178 9369887888900188206 1179 8761348110906885036 1180 8009858128900930746 1181 7158842800066141196 1182 6253998162288282006 1183 5339345071074239816 1184 4453864242344657176 1185 3629046243906533566 1186 2887526249381539316 1187 2242803930016925166 1188 1699903193525730936 1189 1256725673532329366 1190 905805551952224646 1191 636179474319983196 1192 435132780907805081 1193 289655524927226281 1194 187521319508756776 1195 117974160553026191 1196 72063176846888166 1197 42698573414276871 1198 24514653571215041 1199 13621974167862725 1200 7316274296346660 1201 3792680533705210 1202 1894558429830629 1203 910316656238933 1204 419877926650717 1205 185487431885181 1206 78280865526746 1207 31469364955688 1208 12011021936066 1209 4336056929280 1210 1474185163297 1211 469652307347 1212 139391914109 1213 38279738683 1214 9648603552 1215 2210750454 1216 455136829 1217 83000001 1218 13170585 1219 1777348 1220 197825 1221 17390 1222 1129 1223 48 1224 1 1225 25971562536676419177 1226 25408815805516084839 1227 24318948164595723054 1228 22769549028699483384 1229 20853360630784648964 1230 18679255741900868984 1231 16362202582032286064 1232 14013477460568468894 1233 11732249351783000214 1234 9599364803374762104 1235 7673771420698433444 1236 5991609666595046624 1237 4567646341678543724 1238 3398470445060191114 1239 2466748239593480414 1240 1745836958046043904 1241 1204161074013289424 1242 808923397738641579 1243 528914050948579824 1244 336357590064760424 1245 207877217268418094 1246 124743343146792629 1247 72611966158278894 1248 40955336381383249 1249 22356598801979833 1250 11795583269707237 1251 6006394061883345 1252 2946994454273052 1253 1390670384583484 1254 629886851361097 1255 273211906946593 1256 113191678300853 1257 44662068751189 1258 16727503815835 1259 5924410378621 1260 1975561983900 1261 617141581056 1262 179551999147 1263 48321035833 1264 11932068439 1265 2677614863 1266 539746984 1267 96353095 1268 14964286 1269 1976256 1270 215262 1271 18520 1272 1177 1273 49 1274 1 1275 67332153938487857964 1276 65900934268840300536 1277 63127425109911103071 1278 59180509713172970366 1279 54292307272484070586 1280 48735976154651662816 1281 42800937622213341936 1282 36768584323309515356 1283 30891227373381574036 1284 25376339331949662196 1285 20377219641286702856 1286 15990223498955098626 1287 12257823259808050526 1288 9176139352799885886 1289 6705250090747490786 1290 4780566797332830546 1291 3323788648890169826 1292 2252342997773284546 1293 1486673719243225051 1294 955174697728732151 1295 596914973633082981 1296 362533953159212746 1297 213795992115239731 1298 122301927173779251 1299 67791244156723659 1300 36365895599865205 1301 18854413356033005 1302 9433742244500948 1303 4547673763566916 1304 2108281711005993 1305 938009571081797 1306 399596289042947 1307 162570228931811 1308 62977926016365 1309 23153291015059 1310 8047461636230 1311 2632863649994 1312 806734877353 1313 230156499867 1314 60719968681 1315 14694293457 1316 3230714941 1317 637893780 1318 111516289 1319 16957979 1320 2192648 1321 233830 1322 19698 1323 1226 1324 50 1325 1