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