0 1 1 1 2 1 3 1 4 2 5 1 6 1 7 3 8 4 9 2 10 1 11 4 12 8 13 8 14 3 15 1 16 5 17 13 18 19 19 15 20 5 21 1 22 6 23 19 24 36 25 42 26 28 27 8 28 1 29 7 30 26 31 60 32 91 33 89 34 51 35 13 36 1 37 8 38 34 39 92 40 170 41 216 42 182 43 92 44 21 45 1 46 9 47 43 48 133 49 288 50 446 51 489 52 363 53 164 54 34 55 1 56 10 57 53 58 184 59 455 60 826 61 1105 62 1068 63 709 64 290 65 55 66 1 67 11 68 64 69 246 70 682 71 1414 72 2219 73 2619 74 2266 75 1362 76 509 77 89 78 1 79 12 80 76 81 320 82 981 83 2280 84 4088 85 5664 86 5990 87 4696 88 2580 89 888 90 144 91 1 92 13 93 89 94 407 95 1365 96 3507 97 7050 98 11166 99 13873 100 13305 101 9542 102 4830 103 1541 104 233 105 1 106 14 107 103 108 508 109 1848 110 5192 111 11538 112 20496 113 29127 114 32842 115 28837 116 19068 117 8951 118 2662 119 377 120 1 121 15 122 118 123 624 124 2445 125 7447 126 18095 127 35541 128 56673 129 73135 130 75552 131 61210 132 37561 133 16443 134 4580 135 610 136 1 137 16 138 134 139 756 140 3172 141 10400 142 27390 143 58828 144 103752 145 150304 146 177814 147 169604 148 127608 149 73072 150 29974 151 7852 152 987 153 1 154 17 155 151 156 905 157 4046 158 14196 159 40235 160 93665 161 180675 162 289597 163 384791 164 420553 165 372764 166 261890 167 140607 168 54269 169 13419 170 1597 171 1 172 18 173 169 174 1072 175 5085 176 18998 177 57603 178 144300 179 301730 180 529100 181 778140 182 955648 183 971131 184 804258 185 530105 186 267948 187 97662 188 22868 189 2584 190 1 191 19 192 188 193 1258 194 6308 195 24988 196 80647 197 216099 198 486265 199 924495 200 1487915 201 2023385 202 2311570 203 2195942 204 1707127 205 1059943 206 506217 207 174799 208 38871 209 4181 210 1 211 20 212 208 213 1464 214 7735 215 32368 216 110720 217 315744 218 759967 219 1555060 220 2714140 221 4040400 222 5113095 223 5463160 224 4874200 225 3571328 226 2096265 227 948964 228 311332 229 65920 230 6765 231 1 232 21 233 229 234 1691 235 9387 236 41361 237 149396 238 451452 239 1156358 240 2531126 241 4755465 242 7679035 243 10641410 244 12599640 245 12648930 246 10641470 247 7374720 248 4105172 249 1766513 250 552051 251 111556 252 10946 253 1 254 22 255 251 256 1940 257 11286 258 52212 259 198492 260 633216 261 1718530 262 4003228 263 8046558 264 13989560 265 21034585 266 27281450 267 30361665 268 28753560 269 22890390 270 15051220 271 7967950 272 3267528 273 974939 274 188422 275 17711 276 1 277 23 278 274 279 2212 280 13455 281 65189 282 260091 283 873069 284 2501142 285 6173210 286 13206144 287 24567244 288 39779610 289 55995070 290 68284525 291 71714865 292 64292880 293 48583080 294 30393890 295 15340650 296 6008980 297 1715412 298 317689 299 28657 300 1 301 24 302 298 303 2508 304 15918 305 80584 306 336566 307 1185372 308 3572703 309 9307568 310 21097884 311 41776616 312 72393412 313 109764240 314 145314180 315 167280840 316 166369410 317 141629520 318 101867360 319 60785760 320 29317580 321 10991920 322 3008040 323 534768 324 46368 325 1 326 25 327 323 328 2829 329 18700 330 98714 331 430605 332 1587127 333 5018166 334 13753340 335 32906594 336 69047710 337 127376172 338 206724896 339 294858030 340 368590090 341 401934775 342 379713795 343 307789760 344 211236200 345 120497230 346 55650150 347 20008940 348 5258220 349 898825 350 75025 351 1 352 26 353 349 354 3176 355 21827 356 119922 357 545237 358 2098316 359 6941859 360 19956878 361 50232637 362 111261872 363 217521766 364 375877684 365 573976338 366 773212360 367 915839045 368 948929410 369 853872965 370 660655480 371 433600790 372 236933140 373 104976670 374 36259080 375 9165085 376 1508618 377 121393 378 1 379 27 380 376 381 3550 382 25326 383 144578 384 683859 385 2742267 386 9470780 387 28485864 388 75207681 389 175247849 390 361690232 391 662447160 392 1077230194 393 1553913594 394 1983909435 395 2233358545 396 2204737150 397 1894242240 398 1402046030 399 881770130 400 462407040 401 196885900 402 65433105 403 15931923 404 2528836 405 196418 406 1 407 28 408 404 409 3952 410 29225 411 173080 412 850264 413 3546048 414 12758284 415 40054960 416 110635404 417 270412408 418 587170718 419 1135399264 420 1957199120 421 3007021472 422 4111799367 423 4990480340 424 5353934740 425 5047908800 426 4150161235 427 2944471640 428 1777777960 429 896226080 430 367295675 431 117624108 432 27625844 433 4233872 434 317811 435 1 436 29 437 433 438 4383 439 33553 440 205855 441 1048670 442 4540890 443 16988191 444 55555511 445 160161144 446 409533676 447 932790807 448 1897817831 449 3454288616 450 5626667752 451 8196051033 452 10656193301 453 12328324515 454 12635202085 455 11402807185 456 8988875115 457 6124295630 458 3555774170 459 1725928795 460 681805683 461 210683057 462 47791639 463 7080519 464 514229 465 1 466 30 467 463 468 4844 469 38340 470 243360 471 1283750 472 5762640 473 22379345 474 76089750 475 228474939 476 609749780 477 1452959887 478 3101021046 479 5939277165 480 10216355632 481 15779917905 482 21859265806 483 27096317183 484 29954006940 485 29391944010 486 25439591100 487 19263331980 488 12624541440 489 7059480925 490 3303960558 491 1259784415 492 376098804 493 82498002 494 11828620 495 832040 496 1 497 31 498 494 499 5336 500 43617 501 286083 502 1560663 503 7252245 504 29190655 505 103009985 506 321552880 507 893780230 508 2222870811 509 4963514609 510 9973089018 511 18053450628 512 29450562153 513 43265851463 514 57151634022 515 67706517424 516 71674275465 517 67466737195 518 56105730265 519 40876748535 520 25808317995 521 13919215653 522 6289673768 523 2317688902 524 669279863 525 142118261 526 19741179 527 1346269 528 1 529 32 530 526 531 5860 532 49416 533 334544 534 1885086 535 9056268 536 37726650 537 137963280 538 446942210 539 1291422860 540 3345125980 541 7796135200 542 16389563514 543 31127560692 544 53443289946 545 82932769248 546 116197403390 547 146717417252 548 166477110072 549 169095019600 550 152964411470 551 122422069900 552 85948398510 553 52352075088 554 27268370346 555 11911323228 556 4246753180 557 1187496928 558 244357442 559 32916068 560 2178309 561 1 562 33 563 559 564 6417 565 55770 566 389296 567 2263247 568 11227437 569 48343581 570 182942175 571 614096145 572 1841375055 573 4958101720 574 12035041410 575 26408569525 576 52480638815 577 94543939656 578 154429509822 579 228580734791 580 306180672105 581 370346161346 582 403278647096 583 393733706535 584 342853218565 585 264476198675 586 179177222133 587 105428763429 588 53098909227 589 22447750176 590 7751939010 591 2101134233 592 419391771 593 54835556 594 3524578 595 1 596 34 597 593 598 7008 599 62713 600 450926 601 2701959 602 13825228 603 61456104 604 240342024 605 834764970 606 2593434480 607 7246418985 608 18284565990 609 41788736915 610 86685343540 611 163414141985 612 280101010170 613 436453534559 614 617694176144 615 792724236841 616 920342225694 617 963489463703 618 905681944700 619 760293828710 620 566075490708 621 370554384072 622 210879747744 623 102815029749 624 42111012414 625 14099826423 626 3708022932 627 718584769 628 91276202 629 5702887 630 1 631 35 632 628 633 7634 634 70280 635 520056 636 3208655 637 16916483 638 77544579 639 313025565 640 1123450575 641 3611141625 642 10453949610 643 27372360030 644 65031404625 645 140509121865 646 276508055050 647 495995790970 648 811098484385 649 1208577220525 650 1638999147776 651 2019247134640 652 2254177850743 653 2272450055499 654 2059709479945 655 1669222537983 656 1201106073455 657 760611353949 658 419123540922 659 198024951390 660 78658589013 661 25559788365 662 6527741934 663 1229252742 664 151814645 665 9227465 666 1 667 36 668 664 669 8296 670 78507 671 597344 672 3791424 673 20576064 674 97163021 675 404395372 676 1497932244 677 4974934224 678 14899856205 679 40419744120 680 99650183640 681 223825092480 682 458805913830 683 859189189560 684 1470508417340 685 2299776715080 686 3284029902860 687 4275940458560 688 5066149222224 689 5446970131936 690 5295648999147 691 4634613962628 692 3630622440148 693 2527792918112 694 1550289278943 695 828028240056 696 379498570152 697 146329389792 698 46187356722 699 11465017608 700 2099652156 701 252318312 702 14930352 703 1 704 37 705 701 706 8995 707 87431 708 683485 709 4459048 710 24887544 711 120947740 712 518474876 713 1979872195 714 6785892033 715 20998241004 716 58930741950 717 150523877370 718 350847636150 719 747662410935 720 1458504225255 721 2606205661950 722 4266280923390 723 6394905102325 724 8768547581945 725 10981088828560 726 12532366488800 727 12996796981826 728 12202713017274 729 10324945882721 730 7827637896243 731 5279188270510 732 3138928872948 733 1626650351130 734 723852911334 735 271175335527 736 83212162695 737 20092411698 738 3581223210 739 419063309 740 24157817 741 1 742 38 743 739 744 9732 745 97090 746 779212 747 5221040 748 29943936 749 149626708 750 659998680 751 2595510092 752 9170159600 753 29282065281 754 84903917178 755 224354475525 756 541791257640 757 1198160230725 758 2429991728670 759 4523515801035 760 7731675774900 761 12131694443055 762 17463229399350 763 23033666313365 764 27789395775920 765 30595312692850 766 30646480131036 767 27823307899142 768 22787197741592 769 16737448606901 770 10945910061570 771 6315868503021 772 3178531502520 773 1374526817013 774 500716888014 775 149491931115 776 35138652516 777 6099938675 778 695539438 779 39088169 780 1 781 39 782 778 783 10508 784 107523 785 885297 786 6087683 787 35848461 788 184029692 789 834512932 790 3376456512 791 12284144568 792 40432097076 793 120971874492 794 330256633707 795 825076475115 796 1890475365735 797 3978999595545 798 7701169940640 799 13713695801190 800 22469575879905 801 33861204765795 802 46891800815040 803 59591609671230 804 69365797297330 805 73774159312686 806 71466585012004 807 62813218658008 808 49849592231214 809 35510996564714 810 22540966835101 811 12633328878489 812 6179708670663 813 2599096616361 814 921384154656 815 267842746326 816 61331002889 817 10376701323 818 1153690916 819 63245986 820 1 821 40 822 818 823 11324 824 118770 825 1002552 826 7070070 827 42715356 828 225099193 829 1048486560 830 4360596152 831 16320599760 832 55311751736 833 170574131168 834 480510573480 835 1240237026000 836 2939906316375 837 6411266218920 838 12878329766910 839 23844857470500 840 40706787482130 841 64062456420600 842 92884700023890 843 123946639885620 844 151991073281925 845 170929352385936 846 175836057017540 847 164926283801048 848 140486118788364 849 108147786537520 850 74789412006716 851 46120205775160 852 25128906052173 853 11957336789544 854 4895007588030 855 1689943788996 856 478665680330 857 106846356728 858 17630330914 859 1912476340 860 102334155 861 1 862 41 863 859 864 12181 865 130872 866 1131830 867 8180145 868 50670723 869 273902232 870 1309434214 871 5593112404 872 21515708844 873 75008808008 874 238170027472 875 691516801724 876 1841719473972 877 4510399976082 878 10176249010410 879 21180071351565 880 40702186832955 881 72252814893270 882 118482939703920 883 179416732324395 884 250692544675305 885 322829513982585 886 382512035339091 887 416131206700806 888 414536500131274 889 376878987601416 890 311447123983892 891 232786790775450 892 156420614346590 893 93790078662434 894 49719571720206 895 23032053048237 896 9184047993387 897 3089993623982 898 853354783384 899 185807690531 900 29919508577 901 3168501411 902 165580141 903 1 904 42 905 901 906 13080 907 143871 908 1274026 909 9430745 910 59853420 911 331643025 912 1626051802 913 7127645811 914 28157307808 915 100885113004 916 329499435240 917 984998580932 918 2703810406864 919 6832630023534 920 15926886012492 921 34296226678350 922 68293524403440 923 125833331493135 924 214580612067690 925 338606459510445 926 494171733420300 927 666406758681780 928 829288189207296 929 950634315321822 930 1001597059218016 931 967251544750230 932 853252395386356 933 684720033547706 934 497355191659560 935 325000105015740 936 189629856157800 937 97880530820616 938 44173437831168 939 17169049205399 940 5633292196362 941 1517828154245 942 322573555836 943 50718340902 944 5246557892 945 267914296 946 1 947 43 948 944 949 14022 950 157810 951 1430078 952 10835643 953 70415995 954 399676590 955 2008365550 956 9027599845 957 36594387833 958 134635533216 959 451900257088 960 1389506824180 961 3926979015268 962 10227957232122 963 24601235509998 964 54733512666924 965 112766000092200 966 215306927248140 967 381116130393780 968 625439886471405 969 951261132634665 970 1339995224426475 971 1746387492564381 972 2102752018511703 973 2334743409878929 974 2384979810669052 975 2235040440267860 976 1914851416535478 977 1493522349191158 978 1055142087450750 979 671050575520130 980 381300465640850 981 191773540371990 982 84374540084804 983 31986389395148 984 10241113974589 985 2693756493465 986 559099587269 987 85884407371 988 8682973599 989 433494437 990 1 991 44 992 988 993 15008 994 172733 995 1600968 996 12409592 997 82525664 998 479523330 999 2467895560 1000 11367608420 1001 47248039480 1002 178357566860 1003 614693098112 1004 1942292194272 1005 5645985274688 1006 15139934828322 1007 37533003148984 1008 86167378200456 1009 183426398771616 1010 362369154018690 1011 664716582045360 1012 1132389348358320 1013 1791281631173760 1014 2629862816571585 1015 3580554450411156 1016 4515546269757864 1017 5266783617597928 1018 5670357535869803 1019 5621617310154928 1020 5117143401553568 1021 4261626161112992 1022 3233384470189614 1023 2223547854630440 1024 1377351146176720 1025 762703862170640 1026 374028611277410 1027 160534367311120 1028 59396552575136 1029 18568162664416 1030 4770684234979 1031 967557550476 1032 145285721872 1033 14363025928 1034 701408733 1035 1 1036 45 1037 1033 1038 16039 1039 188685 1040 1787723 1041 14168370 1042 96365334 1043 572884637 1044 3017834885 1045 14235180570 1046 60624013450 1047 234633206185 1048 829645052805 1049 2691620825600 1050 8040177726048 1051 22175426927190 1052 56599916992574 1053 133928338581562 1054 294195012482070 1055 600529065457230 1056 1139851736156250 1057 2012412857651820 1058 3304787109925860 1059 5046584334216750 1060 7161678399617406 1061 9436095944595495 1062 11528717379920173 1063 13039893171979434 1064 13626718255903660 1065 13123740522377548 1066 11613810002934420 1067 9409862047838084 1068 6950454674011212 1069 4656041088257910 1070 2811105583867490 1071 1518032939088900 1072 726336518960520 1073 304305459971060 1074 109951104634700 1075 33579960873984 1076 8431998278920 1077 1671942859617 1078 245533155171 1079 23747408260 1080 1134903170 1081 1 1082 46 1083 1079 1084 17116 1085 205712 1086 1991416 1087 16128826 1088 112134672 1089 681659563 1090 3673245186 1091 17732538785 1092 77327089580 1093 306624828055 1094 1111526298470 1095 3699623445265 1096 11346491649760 1097 32157896847510 1098 84421329194452 1099 205668190402458 1100 465656354212616 1101 980891456139756 1102 1923807200385096 1103 3514633747826760 1104 5981916549623040 1105 9483760792500930 1106 13999544365007916 1107 19227637160784486 1108 24545367774926824 1109 29084156821657471 1110 31933395045481022 1111 32420816314151011 1112 30359167835466896 1113 26140815452326072 1114 20621942882962288 1115 14839880232458736 1116 9690694526755840 1117 5706489669133110 1118 3007073320220060 1119 1404670590208990 1120 574790931916880 1121 202927618083820 1122 60580121817320 1123 14874625373516 1124 2885033565264 1125 414566285303 1126 39245337358 1127 1836311903 1128 1 1129 47 1130 1126 1131 18240 1132 223861 1133 2213167 1134 18308927 1135 130051221 1136 807962605 1137 4451270083 1138 21978668608 1139 98077463250 1140 398187098205 1141 1478775139975 1142 5045782949920 1143 15875760147830 1144 46196009322870 1145 124619403768010 1146 312264946524100 1147 727924461607648 1148 1580476148933934 1149 3198893669006922 1150 6038970013669086 1151 10636402033606050 1152 17478090199775790 1153 26788092267434706 1154 38273765860009152 1155 50934683335328716 1156 63065620541179790 1157 72546269247058666 1158 77394104531611467 1159 76406702405521567 1160 69623723810170516 1161 58376568338222780 1162 44871685163259108 1163 31481029433225788 1164 20053225284146860 1165 11524668573220660 1166 5929776849517950 1167 2705798041086390 1168 1082024009971760 1169 373458844535840 1170 109034708064820 1171 26191657217700 1172 4971542710184 1173 699344777832 1174 64829057521 1175 2971215073 1176 1 1177 48 1178 1174 1179 19412 1180 243180 1181 2454144 1182 20727806 1183 150351564 1184 954142652 1185 5371367360 1186 27111598254 1187 123729377044 1188 513997100240 1189 1954289327760 1190 6831182917950 1191 22033069396220 1192 65771392915965 1193 182161904740640 1194 469042247139620 1195 1124610737326200 1196 2514068800944040 1197 5245026172153472 1198 10218755138815764 1199 18599179247660232 1200 31629125981208600 1201 50248099016833536 1202 74545618919944788 1203 103207993560345784 1204 133227941037292992 1205 160157257563165280 1206 179024530600327604 1207 185734201982614056 1208 178451242529843094 1209 158359459983860192 1210 129389068953807960 1211 96974657479447184 1212 66374134949831384 1213 41268588384123360 1214 23160935091871720 1215 11642648210824400 1216 5192492641267140 1217 2030273786424480 1218 685421170684480 1219 195806487099840 1220 46037825301400 1221 8555921053280 1222 1178740120656 1223 107045609952 1224 4807526976 1225 1 1226 49 1227 1223 1228 20633 1229 263718 1230 2715564 1231 23405811 1232 173292537 1233 1122803143 1234 6455561233 1235 33290928219 1236 155292245381 1237 659705145892 1238 2566363891250 1239 9183659343915 1240 30343027454145 1241 92850245262105 1242 263809057804435 1243 697400161203130 1244 1718272388233830 1245 3950944484794340 1246 8487019434705160 1247 17044257459903170 1248 32016828055482918 1249 56267275242537918 1250 92513627031648186 1251 142271808136554114 1252 204541704747725278 1253 274709700457647928 1254 344319881935786988 1255 402247408704672674 1256 437305001830000326 1257 441579549044068617 1258 413217404919224853 1259 357372252747838668 1260 284740294771477924 1261 208220477592537676 1262 139123752767180532 1263 84482748760141940 1264 46328251875916780 1265 22764917701609490 1266 9928564468778010 1267 3797718967080720 1268 1254686502320160 1269 350879020466060 1270 80785403572380 1271 14706203884120 1272 1985130508440 1273 176682194449 1274 7778742049 1275 1 1276 50 1277 1273 1278 21904 1279 285525 1280 2998694 1281 26364555 1282 199152492 1283 1316823486 1284 7728715940 1285 40700632104 1286 193954540960 1287 842108989527 1288 3349798414186 1289 12264020335405 1290 41480976125820 1291 130024455634200 1292 378692372462760 1293 1026980611923530 1294 2597834454177600 1295 6138259120167790 1296 13562574656825700 1297 28045345695552370 1298 54306111687539560 1299 98502858436836600 1300 167380081521846336 1301 266414561149410900 1302 397061611901112928 1303 553797024125317994 1304 722237575953780700 1305 879795231677752654 1306 999709668097838280 1307 1057909081474396547 1308 1040531155945907526 1309 949040900196906615 1310 800472007503176784 1311 622349841317823560 1312 444318887839165392 1313 289980636477153856 1314 172079589020182080 1315 92254104669397990 1316 44336130381211900 1317 18918776077125870 1318 7082679255825360 1319 2290986693470700 1320 627470911138280 1321 141529432757900 1322 25247255445840 1323 3340552823545 1324 291506546450 1325 12586269025