0 1 1 0 2 1 3 1 4 1 5 1 6 1 7 3 8 2 9 1 10 3 11 6 12 6 13 3 14 1 15 6 16 15 17 15 18 10 19 4 20 1 21 15 22 36 23 40 24 29 25 15 26 5 27 1 28 36 29 91 30 105 31 84 32 49 33 21 34 6 35 1 36 91 37 232 38 280 39 238 40 154 41 76 42 28 43 7 44 1 45 232 46 603 47 750 48 672 49 468 50 258 51 111 52 36 53 8 54 1 55 603 56 1585 57 2025 58 1890 59 1398 60 837 61 405 62 155 63 45 64 9 65 1 66 1585 67 4213 68 5500 69 5313 70 4125 71 2640 72 1397 73 605 74 209 75 55 76 10 77 1 78 4213 79 11298 80 15026 81 14938 82 12078 83 8162 84 4642 85 2211 86 869 87 274 88 66 89 11 90 1 91 11298 92 30537 93 41262 94 42042 95 35178 96 24882 97 15015 98 7722 99 3354 100 1209 101 351 102 78 103 12 104 1 105 30537 106 83097 107 113841 108 118482 109 102102 110 75075 111 47619 112 26091 113 12285 114 4914 115 1638 116 441 117 91 118 13 119 1 120 83097 121 227475 122 315420 123 334425 124 295659 125 224796 126 148785 127 85995 128 43290 129 18837 130 6993 131 2170 132 545 133 105 134 14 135 1 136 227475 137 625992 138 877320 139 945504 140 854880 141 669240 142 459576 143 278070 144 148122 145 69120 146 28000 147 9708 148 2820 149 664 150 120 151 15 152 1 153 625992 154 1730787 155 2448816 156 2677704 157 2469624 158 1983696 159 1406886 160 885768 161 495312 162 245242 163 106828 164 40528 165 13192 166 3604 167 799 168 136 169 16 170 1 171 1730787 172 4805595 173 6857307 174 7596144 175 7131024 176 5860206 177 4276350 178 2787966 179 1626322 180 847382 181 392598 182 160548 183 57324 184 17595 185 4539 186 951 187 153 188 17 189 1 190 4805595 191 13393689 192 19259046 193 21584475 194 20587374 195 17267580 196 12924522 197 8690638 198 5261670 199 2866302 200 1400528 201 610470 202 235467 203 79458 204 23085 205 5643 206 1121 207 171 208 18 209 1 210 13393689 211 37458330 212 54237210 213 61430895 214 59439429 215 50779476 216 38882740 217 26876830 218 16818610 219 9528500 220 4877300 221 2246465 222 925395 223 338010 224 108186 225 29849 226 6935 227 1310 228 190 229 19 230 1 231 37458330 232 105089229 233 153126435 234 175107534 235 171649800 236 149101645 237 116539046 238 82578180 239 53223940 240 31224410 241 16652265 242 8049160 243 3509870 244 1371591 245 476045 246 144970 247 38094 248 8435 249 1519 250 210 251 20 252 1 253 105089229 254 295673994 255 433323198 256 499883769 257 495858979 258 437290491 259 348218871 260 252341166 261 167026530 262 101100615 263 55925835 264 28211295 265 12930621 266 5357506 267 1992606 268 659109 269 191499 270 48048 271 10164 272 1749 273 231 274 21 275 1 276 295673994 277 834086421 278 1228880961 279 1429065946 280 1433033239 281 1281368341 282 1037850528 283 767586567 284 520468311 285 324052980 286 185237745 287 97067751 288 46499422 289 20280733 290 8009221 291 2843214 292 898656 293 249711 294 59961 295 12144 296 2001 297 253 298 22 299 1 300 834086421 301 2358641376 302 3492033328 303 4090980146 304 4143467526 305 3752252108 306 3086805436 307 2325905406 308 1612107858 309 1029759036 310 606358476 311 328804918 312 163847906 313 74789376 314 31133168 315 11751091 316 3991581 317 1208328 318 321816 319 74106 320 14398 321 2276 322 276 323 23 324 1 325 2358641376 326 6684761125 327 9941654850 328 11726481000 329 11986699780 330 10982525070 331 9164962950 332 7024818700 333 4967772300 334 3248225370 335 1964922430 336 1099011300 337 567442200 338 269770450 339 117673635 340 46875840 341 16951000 342 5521725 343 1604250 344 410320 345 90780 346 16950 347 2575 348 300 349 24 350 1 351 6684761125 352 18985057351 353 28352896975 354 33654835630 355 34695705850 356 32134187800 357 27172306720 358 21157553950 359 15240816370 360 10180920100 361 6312159100 362 3631375930 363 1936223950 364 954886285 365 434319925 366 181500475 367 69348565 368 24076975 369 7536295 370 2105350 371 518050 372 110305 373 19825 374 2899 375 325 376 25 377 1 378 18985057351 379 54022715451 380 80992789956 381 96703438455 382 100484729280 383 94002200370 384 80464048470 385 63570677040 386 46579290420 387 31733895570 388 20124455130 389 11879758980 390 6522486165 391 3325430160 392 1570706685 393 685168965 394 274926015 395 100961835 396 33718620 397 10159695 398 2733705 399 648180 400 133029 401 23049 402 3249 403 351 404 26 405 1 406 54022715451 407 154000562758 408 231718943862 409 278180957691 410 291190368105 411 274950978120 412 238036925880 413 190614015930 414 141883863030 415 98437641120 416 63738109680 417 38526700275 418 21727675305 419 11418623010 420 5581305810 421 2530801665 422 1061056815 423 409606470 424 144840150 425 46612020 426 13541580 427 3514914 428 804258 429 159327 430 26649 431 3626 432 378 433 27 434 1 435 154000562758 436 439742222071 437 663900464311 438 801090269658 439 844322303916 440 804178272105 441 703601919930 442 570534804840 443 430935520080 444 304059613830 445 200702451075 446 123992485260 447 71672998590 448 38727604125 449 19530730485 450 9173164290 451 4001464950 452 1615503435 453 601058640 454 204993750 455 63668514 456 17860752 457 4478499 458 990234 459 189602 460 30653 461 4031 462 406 463 28 464 1 465 439742222071 466 1257643249140 467 1904732956040 468 2309313037885 469 2449590845679 470 2352102495951 471 2078314996875 472 1705072244850 473 1305529938750 474 935697584985 475 628754550165 476 396367934925 477 234393087975 478 129931333200 479 67431498900 480 32705359725 481 14790132675 482 6218027025 483 2421555825 484 869720904 485 286523016 486 86007765 487 23329485 488 5658335 489 1210489 490 224286 491 35090 492 4465 493 435 494 29 495 1 496 1257643249140 497 3602118427251 498 5471689243065 499 6663636839604 500 7111006379515 501 6880008338505 502 6135489737676 503 5088917180475 504 3946299768585 505 2869982073900 506 1960820070075 507 1259515573065 508 760692356100 509 431755920075 510 230068191825 511 114926991300 512 53713519425 513 23429715525 514 9509303754 515 3577799745 516 1242251685 517 395860266 518 114995585 519 30198309 520 7093110 521 1469865 522 263841 523 39990 524 4929 525 465 526 30 527 1 528 3602118427251 529 10331450919456 530 15737444509920 531 19246332462184 532 20654651557624 533 20126504455696 534 18104415256656 535 15170706686736 536 11905199022960 537 8777101912560 538 6090317717040 539 3981027999240 540 2451963849240 541 1422516468000 542 776751103200 543 398708702550 544 192070226250 545 86652538704 546 36516819024 547 14329355184 548 5215911696 549 1753107536 550 541054160 551 152287004 552 38761284 553 8826816 554 1773696 555 308760 556 45384 557 5424 558 496 559 31 560 1 561 10331450919456 562 29671013856627 563 45315227891560 564 55638428529728 565 60027488475504 566 58885571269976 567 53401626399088 568 45180320966352 569 35853007622256 570 26772618652560 571 18848447628840 572 12523309565520 573 7855508316480 574 4651231420440 575 2597976273750 576 1367530032000 577 677431467504 578 315239583978 579 137498712912 580 56062085904 581 21298374416 582 7510073392 583 2446448700 584 732102448 585 199875104 586 49361796 587 10909272 588 2127840 589 359568 590 51304 591 5951 592 528 593 32 594 1 595 29671013856627 596 85317692667643 597 130624670277915 598 160981144896792 599 174551488275208 600 172314686144568 601 157467518635416 602 134434954987696 603 107805947241168 604 81474073903656 605 58144375846920 606 39227265510840 607 25030049302440 608 15104716010670 609 8616737726190 610 4642937773254 611 2360201083482 612 1130169764394 613 508800382794 614 214859173232 615 84870533712 616 31254896508 617 10688624540 618 3378426252 619 981339348 620 260146172 621 62398908 622 13396680 623 2538712 624 416823 625 57783 626 6511 627 561 628 33 629 1 630 85317692667643 631 245613376802185 632 376923507842350 633 466157303449915 634 507847319316568 635 504333693055192 636 464217159767680 637 399708420864280 638 323714976132520 639 247424396991744 640 178845715261416 641 122401690660200 642 79362030823950 643 48751503039300 644 28364391510114 645 15619876582926 646 8133308621130 647 3999171230670 648 1853829320420 649 808530089738 650 330984603452 651 126814054760 652 45321947300 653 15048390140 654 4619911772 655 1303884428 656 335941760 657 78334300 658 16352215 659 3013318 660 481117 661 64855 662 7105 663 595 664 34 665 1 666 245613376802185 667 707854577312178 668 1088694188094450 669 1350928130608833 670 1478338315821675 671 1476398172139440 672 1368259273687152 673 1187640556764480 674 970847793988544 675 749985088385680 676 548671802913360 677 380609436745566 678 250515224523450 679 156477925373364 680 92735771132340 681 52117576714170 682 27752356434726 683 13986309172220 684 6661530640828 685 2993344013610 686 1266328747950 687 503120605512 688 187184392200 689 64990249212 690 20972186340 691 6259737960 692 1718160488 693 430628275 694 97699833 695 19846650 696 3559290 697 553077 698 72555 699 7734 700 630 701 35 702 1 703 707854577312178 704 2042162142208813 705 3147476896015461 706 3917960634524958 707 4305664618569948 708 4322995761648267 709 4032298002591072 710 3526747624440176 711 2908473439138704 712 2269504685287584 713 1679266328044606 714 1179796464182376 715 787602586642380 716 499728921029154 717 301331273219874 718 172605704281236 719 93856242321116 720 48400196247774 721 23641183826658 722 10921203402388 723 4762793367072 724 1956633745662 725 755295246924 726 273146827752 727 92222173512 728 28950084788 729 8408526723 730 2246488596 731 548174758 732 121105773 733 23959017 734 4184922 735 633366 736 80919 737 8399 738 666 739 36 740 1 741 2042162142208813 742 5897493615536452 743 9107599672749232 744 11371102149110367 745 12546621014743173 746 12660958382809287 747 11882041388679515 748 10467519066169952 749 8704725748866464 750 6857244452470894 751 5128567477514566 752 3646665378869362 753 2467127971853910 754 1588662780891408 755 973665898530264 756 567793219822226 757 314862142850126 758 165897622395548 759 82962583476820 760 39325180596118 761 17640630515122 762 7474722359658 763 2985075820338 764 1120664248188 765 394319086052 766 129580785023 767 39605100107 768 11203190077 769 2915769127 770 693239548 771 149249712 772 28777305 773 4899207 774 722684 775 89984 776 9101 777 703 778 37 779 1 780 5897493615536452 781 17047255430494497 782 26376195437396051 783 33025322836602772 784 36578681546662827 785 37089620786231975 786 35010518837658754 787 31054286203715931 788 26029489267507310 789 20690537678851924 790 15632477308854822 791 11242360828237838 792 7702456131614680 793 5029456651275582 794 3130121899243898 795 1856321261202616 796 1048552985067900 797 563722348722494 798 288185386468486 799 139928394588060 800 64440533470898 801 28100428695118 802 11580462428184 803 4500059154578 804 1644564119263 805 563504971182 806 180389075207 807 53724059311 808 14812198752 809 3758258387 810 871266565 811 182926224 812 34399196 813 5711875 814 821769 815 99788 816 9841 817 741 818 38 819 1 820 17047255430494497 821 49320944483427000 822 76448773704493320 823 95980199820661650 824 106693625169497574 825 108678821170553556 826 103154425827606660 827 92094294308881995 828 77774313150075165 829 62352504255214056 830 47565375815944584 831 34577294268707340 832 23974273611128100 833 15862034682134160 834 10015899811722096 835 6034996145514414 836 3468596594993010 837 1900460720258880 838 991836129779040 839 492554314527444 840 232469356754076 841 104121424594200 842 44180950277880 843 17725085702025 844 6708128245023 845 2388458165652 846 797618105700 847 248925333270 848 72294516450 849 19441723704 850 4812451176 851 1088591985 852 223037295 853 40932840 854 6633432 855 931398 856 110370 857 10620 858 780 859 39 860 1 861 49320944483427000 862 142816973618414817 863 221749918008581970 864 279122598694652544 865 311352646160712780 866 318526872167657790 867 303927541307042211 868 273023033286563820 869 232221111714171216 870 187692193221233805 871 144495174339865980 872 106116943695780024 873 74413602561969600 874 49852208104984356 875 31912930639370670 876 19519492552229520 877 11404053460766304 878 6360893445030930 879 3384851164565364 880 1716859801060560 881 829145095875720 882 380771731626156 883 166027460574105 884 68614164224928 885 26821672112700 886 9894204516375 887 3435001604622 888 1118837955420 889 340661573424 890 96548691330 891 25342766865 892 6124080456 893 1352562120 894 270603567 895 48497670 896 7675200 897 1052388 898 121770 899 11439 900 820 901 40 902 1 903 142816973618414817 904 413887836110423787 905 643689490321649331 906 812225162863947294 907 909002117023023114 908 933807059635412781 909 895477446761263821 910 809171686307777247 911 692936338221968841 912 564408479275271001 913 438304311256879809 914 325025720597615604 915 230382754362733980 916 156178741306324626 917 101284631296584546 918 62836476652366494 919 37284439458026754 920 21149798070362598 921 11462604410656854 922 5930856061501644 923 2926776628562436 924 1375944288075981 925 615413356425189 926 261463296911733 927 105330040854003 928 40150878233697 929 14448044076417 930 4894501133466 931 1556048220174 932 462553031619 933 128015538651 934 32819409441 935 7747246143 936 1671663357 937 326776437 938 57225258 939 8849358 940 1185597 941 134029 942 12299 943 861 944 41 945 1 946 413887836110423787 947 1200394300050487935 948 1869802489296020412 949 2364916770208619739 950 2655034339522383189 951 2738286623419699716 952 2638456192704453849 953 2397585471291009909 954 2066516503805017089 955 1695649128754119651 956 1327738511129766414 957 993712786217229393 958 711587216266674210 959 487846126965643152 960 320299849255275666 961 201405547406977794 962 121270714180755846 963 69896841939046206 964 38543258542521096 965 20320237100720934 966 10233576978140061 967 4918134273063606 968 2252820941412903 969 982206694190925 970 406944215999433 971 159928963164117 972 59493423443580 973 20898593430057 974 6913102385259 975 2146616790444 976 623387979711 977 168582194235 978 42238318941 979 9745685937 980 2055665052 981 392851053 982 67260213 983 10168984 984 1331925 985 147189 986 13201 987 903 988 42 989 1 990 1200394300050487935 991 3484084625456932134 992 5435113559555128086 993 6889753599027023340 994 7758237733150702644 995 8031777155646536754 996 7774328287415163474 997 7102558167800480847 998 6159751103850146649 999 5089904143688903154 1000 4017100426101115458 1001 3033038513613670017 1002 2193146129449546755 1003 1519733192487593028 1004 1009551523627896612 1005 642976110843009306 1006 392573103526779846 1007 229710814662323148 1008 128760337582288236 1009 69097072621382091 1010 35471948351924601 1011 17404532192616570 1012 8153161908667434 1013 3641971851603261 1014 1549079873354475 1015 626366602607130 1016 240320980037754 1017 87305119258896 1018 29958312605760 1019 9683107155414 1020 2938586964390 1021 834208492887 1022 220566199113 1023 54039669930 1024 12194202042 1025 2515776318 1026 470280250 1027 78761122 1028 11648098 1029 1492315 1030 161293 1031 14146 1032 946 1033 43 1034 1 1035 3484084625456932134 1036 10119592485062548155 1037 15808951784039083560 1038 20083104891732854070 1039 22679768487824262738 1040 23564343176212402872 1041 22908663610862181075 1042 21036637559065790970 1043 18352213415339530650 1044 15266755673640165261 1045 12140043083403688629 1046 9243285069164332230 1047 6745917835550809800 1048 4722430845565036395 1049 3172260826958498946 1050 2045100737997685764 1051 1265260029032112300 1052 751044255771391230 1053 427568224865993475 1054 233329358555594928 1055 121973553165923262 1056 61029642453208605 1057 29199665952887265 1058 13344213633625170 1059 5817418327564866 1060 2415767455999359 1061 953992701903780 1062 357584411902410 1063 126946539020070 1064 42580006725564 1065 13455902612691 1066 3993361656390 1067 1108814361930 1068 286800071085 1069 68749648290 1070 15180258610 1071 3064817690 1072 560689470 1073 91901535 1074 13301706 1075 1667754 1076 176385 1077 15135 1078 990 1079 44 1080 1 1081 10119592485062548155 1082 29412628894558563849 1083 46011649160834485785 1084 58571825163596200368 1085 66327216555769519680 1086 69152775274898846685 1087 67509644346140374917 1088 62297514585267502695 1089 54655606648045486881 1090 45759012172383384540 1091 36650083826208186120 1092 28129245988118830659 1093 20711633750280178425 1094 14640609508074345141 1095 9939792410521221105 1096 6482621593988297010 1097 4061405022801189294 1098 2443872509669497005 1099 1411941839192979633 1100 782871136587511665 1101 416332554174726795 1102 212202861572019132 1103 103573522039721040 1104 48361297914077301 1105 21577399417189395 1106 9187178485468005 1107 3727344569805549 1108 1438523652826260 1109 527110957648044 1110 182982448358325 1111 60029270994645 1112 18558078631011 1113 5388976089405 1114 1464364081305 1115 370729977985 1116 86994724590 1117 18805765770 1118 3717408695 1119 665892711 1120 106870995 1121 15145845 1122 1859274 1123 192510 1124 16169 1125 1035 1126 45 1127 1 1128 29412628894558563849 1129 85543870540455597789 1130 133996103218989250002 1131 170910690880200205833 1132 194051816994264566733 1133 202989636176808741282 1134 198959934206306724297 1135 184462765579453364493 1136 162712133405696374116 1137 137064702646637057541 1138 110538341986710401319 1139 85490963564607195204 1140 63481489246473354225 1141 45292035668875744671 1142 31063023512583863256 1143 20483819027310707409 1144 12987899126458983309 1145 7917219371663665932 1146 4638685485449988303 1147 2611145529955218093 1148 1411406552334257592 1149 732108937786466967 1150 364137681525817473 1151 173512219370987736 1152 79125875816734701 1153 34491922472462949 1154 14353046708099814 1155 5692979180279853 1156 2148617058832629 1157 770122677001014 1158 261569797983981 1159 83976325715061 1160 25411418801721 1161 7224070148695 1162 1922088783880 1163 476530468345 1164 109517899055 1165 23189067176 1166 4490172401 1167 787909551 1168 123876114 1169 17197629 1170 2067953 1171 209714 1172 17249 1173 1081 1174 46 1175 1 1176 85543870540455597789 1177 248952602654003411640 1178 390450664639645053624 1179 498958611093454022568 1180 567952144051273513848 1181 596001387377380032312 1182 586412335962568830072 1183 546134833191456462906 1184 484239601631786796150 1185 410315178039043832976 1186 333094008197954654064 1187 259510794797790950748 1188 194264488479956294100 1189 139836548427932962152 1190 96838878208770315336 1191 64534741666353553974 1192 41388937525433356650 1193 25543803983572637544 1194 15167050387068872328 1195 8661237567739463988 1196 4754661020075942652 1197 2507653171646542032 1198 1269758838683272176 1199 616775776713539910 1200 287130017660185386 1201 127970844997297464 1202 54537948360842616 1203 22194642947212296 1204 8611718916113496 1205 3180309533817624 1206 1115668800700056 1207 370957542500763 1208 116611814665477 1209 34557577734296 1210 9622689400920 1211 2508137151280 1212 609237434576 1213 137197138632 1214 28467149128 1215 5401958066 1216 928983294 1217 143141696 1218 19475296 1219 2294916 1220 228044 1221 18376 1222 1128 1223 47 1224 1 1225 248952602654003411640 1226 724947137834104063053 1227 1138361878387102487832 1228 1457361419784372590040 1229 1662912142522107568728 1230 1750365867391222376232 1231 1728548556531405325290 1232 1616786770785812089128 1233 1440689612862287092032 1234 1227648787868785283190 1235 1002919981034789437788 1236 786869291475701898912 1237 593611831705680207000 1238 430939915116659571588 1239 301210168303056831462 1240 202762557400557225960 1241 131467483175359548168 1242 82099791896074866522 1243 49372091938380973860 1244 28582948974884278968 1245 15923551759461948672 1246 8532073030405756860 1247 4394187787043354118 1248 2173664633056997472 1249 1031876639371022760 1250 469638811018325466 1251 204703436305352376 1252 85344310224168408 1253 33986671397143416 1254 12907697250631176 1255 4666935877018443 1256 1603238157866296 1257 522126934900536 1258 160792081800693 1259 46688404286496 1260 12740063986776 1261 3254571724488 1262 774901722336 1263 171066245826 1264 34798090488 1265 6474083056 1266 1091600286 1267 164911908 1268 21998256 1269 2541336 1270 247548 1271 19551 1272 1176 1273 48 1274 1