0 1 1 0 2 1 3 1 4 1 5 1 6 0 7 2 8 2 9 1 10 1 11 2 12 4 13 3 14 1 15 0 16 3 17 6 18 7 19 4 20 1 21 1 22 3 23 9 24 13 25 11 26 5 27 1 28 0 29 4 30 12 31 22 32 24 33 16 34 6 35 1 36 1 37 4 38 16 39 34 40 46 41 40 42 22 43 7 44 1 45 0 46 5 47 20 48 50 49 80 50 86 51 62 52 29 53 8 54 1 55 1 56 5 57 25 58 70 59 130 60 166 61 148 62 91 63 37 64 9 65 1 66 0 67 6 68 30 69 95 70 200 71 296 72 314 73 239 74 128 75 46 76 10 77 1 78 1 79 6 80 36 81 125 82 295 83 496 84 610 85 553 86 367 87 174 88 56 89 11 90 1 91 0 92 7 93 42 94 161 95 420 96 791 97 1106 98 1163 99 920 100 541 101 230 102 67 103 12 104 1 105 1 106 7 107 49 108 203 109 581 110 1211 111 1897 112 2269 113 2083 114 1461 115 771 116 297 117 79 118 13 119 1 120 0 121 8 122 56 123 252 124 784 125 1792 126 3108 127 4166 128 4352 129 3544 130 2232 131 1068 132 376 133 92 134 14 135 1 136 1 137 8 138 64 139 308 140 1036 141 2576 142 4900 143 7274 144 8518 145 7896 146 5776 147 3300 148 1444 149 468 150 106 151 15 152 1 153 0 154 9 155 72 156 372 157 1344 158 3612 159 7476 160 12174 161 15792 162 16414 163 13672 164 9076 165 4744 166 1912 167 574 168 121 169 16 170 1 171 1 172 9 173 81 174 444 175 1716 176 4956 177 11088 178 19650 179 27966 180 32206 181 30086 182 22748 183 13820 184 6656 185 2486 186 695 187 137 188 17 189 1 190 0 191 10 192 90 193 525 194 2160 195 6672 196 16044 197 30738 198 47616 199 60172 200 62292 201 52834 202 36568 203 20476 204 9142 205 3181 206 832 207 154 208 18 209 1 210 1 211 10 212 100 213 615 214 2685 215 8832 216 22716 217 46782 218 78354 219 107788 220 122464 221 115126 222 89402 223 57044 224 29618 225 12323 226 4013 227 986 228 172 229 19 230 1 231 0 232 11 233 110 234 715 235 3300 236 11517 237 31548 238 69498 239 125136 240 186142 241 230252 242 237590 243 204528 244 146446 245 86662 246 41941 247 16336 248 4999 249 1158 250 191 251 20 252 1 253 1 254 11 255 121 256 825 257 4015 258 14817 259 43065 260 101046 261 194634 262 311278 263 416394 264 467842 265 442118 266 350974 267 233108 268 128603 269 58277 270 21335 271 6157 272 1349 273 211 274 21 275 1 276 0 277 12 278 132 279 946 280 4840 281 18832 282 57882 283 144111 284 295680 285 505912 286 727672 287 884236 288 909960 289 793092 290 584082 291 361711 292 186880 293 79612 294 27492 295 7506 296 1560 297 232 298 22 299 1 300 1 301 12 302 144 303 1078 304 5786 305 23672 306 76714 307 201993 308 439791 309 801592 310 1233584 311 1611908 312 1794196 313 1703052 314 1377174 315 945793 316 548591 317 266492 318 107104 319 34998 320 9066 321 1792 322 254 323 23 324 1 325 0 326 13 327 156 328 1222 329 6864 330 29458 331 100386 332 278707 333 641784 334 1241383 335 2035176 336 2845492 337 3406104 338 3497248 339 3080226 340 2322967 341 1494384 342 815083 343 373596 344 142102 345 44064 346 10858 347 2046 348 277 349 24 350 1 351 1 352 13 353 169 354 1378 355 8086 356 36322 357 129844 358 379093 359 920491 360 1883167 361 3276559 362 4880668 363 6251596 364 6903352 365 6577474 366 5403193 367 3817351 368 2309467 369 1188679 370 515698 371 186166 372 54922 373 12904 374 2323 375 301 376 25 377 1 378 0 379 14 380 182 381 1547 382 9464 383 44408 384 166166 385 508937 386 1299584 387 2803658 388 5159726 389 8157227 390 11132264 391 13154948 392 13480826 393 11980667 394 9220544 395 6126818 396 3498146 397 1704377 398 701864 399 241088 400 67826 401 15227 402 2624 403 326 404 26 405 1 406 1 407 14 408 196 409 1729 410 11011 411 53872 412 210574 413 675103 414 1808521 415 4103242 416 7963384 417 13316953 418 19289491 419 24287212 420 26635774 421 25461493 422 21201211 423 15347362 424 9624964 425 5202523 426 2406241 427 942952 428 308914 429 83053 430 17851 431 2950 432 352 433 27 434 1 435 0 436 15 437 210 438 1925 439 12740 440 64883 441 264446 442 885677 443 2483624 444 5911763 445 12066626 446 21280337 447 32606444 448 43576703 449 50922986 450 52097267 451 46662704 452 36548573 453 24972326 454 14827487 455 7608764 456 3349193 457 1251866 458 391967 459 100904 460 20801 461 3302 462 379 463 28 464 1 465 1 466 15 467 225 468 2135 469 14665 470 77623 471 329329 472 1150123 473 3369301 474 8395387 475 17978389 476 33346963 477 53886781 478 76183147 479 94499689 480 103020253 481 98759971 482 83211277 483 61520899 484 39799813 485 22436251 486 10957957 487 4601059 488 1643833 489 492871 490 121705 491 24103 492 3681 493 407 494 29 495 1 496 0 497 16 498 240 499 2360 500 16800 501 92288 502 406952 503 1479452 504 4519424 505 11764688 506 26373776 507 51325352 508 87233744 509 130069928 510 170682836 511 197519942 512 201780224 513 181971248 514 144732176 515 101320712 516 62236064 517 33394208 518 15559016 519 6244892 520 2136704 521 614576 522 145808 523 27784 524 4088 525 436 526 30 527 1 528 1 529 16 530 256 531 2600 532 19160 533 109088 534 499240 535 1886404 536 5998876 537 16284112 538 38138464 539 77699128 540 138559096 541 217303672 542 300752764 543 368202778 544 399300166 545 383751472 546 326703424 547 246052888 548 163556776 549 95630272 550 48953224 551 21803908 552 8381596 553 2751280 554 760384 555 173592 556 31872 557 4524 558 466 559 31 560 1 561 0 562 17 563 272 564 2856 565 21760 566 128248 567 608328 568 2385644 569 7885280 570 22282988 571 54422576 572 115837592 573 216258224 574 355862768 575 518056436 576 668955542 577 767502944 578 783051638 579 710454896 580 572756312 581 409609664 582 259187048 583 144583496 584 70757132 585 30185504 586 11132876 587 3511664 588 933976 589 205464 590 36396 591 4990 592 497 593 32 594 1 595 1 596 17 597 289 598 3128 599 24616 600 150008 601 736576 602 2993972 603 10270924 604 30168268 605 76705564 606 170260168 607 332095816 608 572120992 609 873919204 610 1187011978 611 1436458486 612 1550554582 613 1493506534 614 1283211208 615 982365976 616 668796712 617 403770544 618 215340628 619 100942636 620 41318380 621 14644540 622 4445640 623 1139440 624 241860 625 41386 626 5487 627 529 628 33 629 1 630 0 631 18 632 306 633 3417 634 27744 635 174624 636 886584 637 3730548 638 13264896 639 40439192 640 106873832 641 246965732 642 502355984 643 904216808 644 1446040196 645 2060931182 646 2623470464 647 2987013068 648 3044061116 649 2776717742 650 2265577184 651 1651162688 652 1072567256 653 619111172 654 316283264 655 142261016 656 55962920 657 19090180 658 5585080 659 1381300 660 283246 661 46873 662 6016 663 562 664 34 665 1 666 1 667 18 668 324 669 3723 670 31161 671 202368 672 1061208 673 4617132 674 16995444 675 53704088 676 147313024 677 353839564 678 749321716 679 1406572792 680 2350257004 681 3506971378 682 4684401646 683 5610483532 684 6031074184 685 5820778858 686 5042294926 687 3916739872 688 2723729944 689 1691678428 690 935394436 691 458544280 692 198223936 693 75053100 694 24675260 695 6966380 696 1664546 697 330119 698 52889 699 6578 700 596 701 35 702 1 703 0 704 19 705 342 706 4047 707 34884 708 233529 709 1263576 710 5678340 711 21612576 712 70699532 713 201017112 714 501152588 715 1103161280 716 2155894508 717 3756829796 718 5857228382 719 8191373024 720 10294885178 721 11641557716 722 11851853042 723 10863073784 724 8959034798 725 6640469816 726 4415408372 727 2627072864 728 1393938716 729 656768216 730 273277036 731 99728360 732 31641640 733 8630926 734 1994665 735 383008 736 59467 737 7174 738 631 739 36 740 1 741 1 742 19 743 361 744 4389 745 38931 746 268413 747 1497105 748 6941916 749 27290916 750 92312108 751 271716644 752 702169700 753 1604313868 754 3259055788 755 5912724304 756 9614058178 757 14048601406 758 18486258202 759 21936442894 760 23493410758 761 22714926826 762 19822108582 763 15599504614 764 11055878188 765 7042481236 766 4021011580 767 2050706932 768 930045252 769 373005396 770 131370000 771 40272566 772 10625591 773 2377673 774 442475 775 66641 776 7805 777 667 778 37 779 1 780 0 781 20 782 380 783 4750 784 43320 785 307344 786 1765518 787 8439021 788 34232832 789 119603024 790 364028752 791 973886344 792 2306483568 793 4863369656 794 9171780092 795 15526782482 796 23662659584 797 32534859608 798 40422701096 799 45429853652 800 46208337584 801 42537035408 802 35421613196 803 26655382802 804 18098359424 805 11063492816 806 6071718512 807 2980752184 808 1303050648 809 504375396 810 171642566 811 50898157 812 13003264 813 2820148 814 509116 815 74446 816 8472 817 704 818 38 819 1 820 1 821 20 822 400 823 5130 824 48070 825 350664 826 2072862 827 10204539 828 42671853 829 153835856 830 483631776 831 1337915096 832 3280369912 833 7169853224 834 14035149748 835 24698562574 836 39189442066 837 56197519192 838 72957560704 839 85852554748 840 91638191236 841 88745372992 842 77958648604 843 62076995998 844 44753742226 845 29161852240 846 17135211328 847 9052470696 848 4283802832 849 1807426044 850 676017962 851 222540723 852 63901421 853 15823412 854 3329264 855 583562 856 82918 857 9176 858 742 859 39 860 1 861 0 862 21 863 420 864 5530 865 53200 866 398734 867 2423526 868 12277401 869 52876392 870 196507709 871 637467632 872 1821546872 873 4618285008 874 10450223136 875 21205002972 876 38733712322 877 63888004640 878 95386961258 879 129155079896 880 158810115452 881 177490745984 882 180383564228 883 166704021596 884 140035644602 885 106830738224 886 73915594466 887 46297063568 888 26187682024 889 13336273528 890 6091228876 891 2483444006 892 898558685 893 286442144 894 79724833 895 19152676 896 3912826 897 666480 898 92094 899 9918 900 781 901 40 902 1 903 1 904 21 905 441 906 5950 907 58730 908 451934 909 2822260 910 14700927 911 65153793 912 249384101 913 833975341 914 2459014504 915 6439831880 916 15068508144 917 31655226108 918 59938715294 919 102621716962 920 159274965898 921 224542041154 922 287965195348 923 336300861436 924 357874310212 925 347087585824 926 306739666198 927 246866382826 928 180746332690 929 120212658034 930 72484745592 931 39523955552 932 19427502404 933 8574672882 934 3382002691 935 1185000829 936 366166977 937 98877509 938 23065502 939 4579306 940 758574 941 102012 942 10699 943 821 944 41 945 1 946 0 947 22 948 462 949 6391 950 64680 951 510664 952 3274194 953 17523187 954 79854720 955 314537894 956 1083359442 957 3292989845 958 8898846384 959 21508340024 960 46723734252 961 91593941402 962 162560432256 963 261896682860 964 383817007052 965 512507236502 966 624266056784 967 694175171648 968 704961896036 969 653827252022 970 553606049024 971 427612715516 972 300958990724 973 192697403626 974 112008701144 975 58951457956 976 28002175286 977 11956675573 978 4567003520 979 1551167806 980 465044486 981 121943011 982 27644808 983 5337880 984 860586 985 112711 986 11520 987 862 988 42 989 1 990 1 991 22 992 484 993 6853 994 71071 995 575344 996 3784858 997 20797381 998 97377907 999 394392614 1000 1397897336 1001 4376349287 1002 12191836229 1003 30407186408 1004 68232074276 1005 138317675654 1006 254154373658 1007 424457115116 1008 645713689912 1009 896324243554 1010 1136773293286 1011 1318441228432 1012 1399137067684 1013 1358789148058 1014 1207433301046 1015 981218764540 1016 728571706240 1017 493656394350 1018 304706104770 1019 170960159100 1020 86953633242 1021 39958850859 1022 16523679093 1023 6118171326 1024 2016212292 1025 586987497 1026 149587819 1027 32982688 1028 6198466 1029 973297 1030 124231 1031 12382 1032 904 1033 43 1034 1 1035 0 1036 23 1037 506 1038 7337 1039 77924 1040 646415 1041 4360202 1042 24582239 1043 118175288 1044 491770521 1045 1792289950 1046 5774246623 1047 16568185516 1048 42599022637 1049 98639260684 1050 206549749930 1051 392472049312 1052 678611488774 1053 1070170805028 1054 1542037933466 1055 2033097536840 1056 2455214521718 1057 2717578296116 1058 2757926215742 1059 2566222449104 1060 2188652065586 1061 1709790470780 1062 1222228100590 1063 798362499120 1064 475666263870 1065 257913792342 1066 126912484101 1067 56482529952 1068 22641850419 1069 8134383618 1070 2603199789 1071 736575316 1072 182570507 1073 39181154 1074 7171763 1075 1097528 1076 136613 1077 13286 1078 947 1079 44 1080 1 1081 1 1082 23 1083 529 1084 7843 1085 85261 1086 724339 1087 5006617 1088 28942441 1089 142757527 1090 609945809 1091 2284060471 1092 7566536573 1093 22342432139 1094 59167208153 1095 141238283321 1096 305189010614 1097 599021799242 1098 1071083538086 1099 1748782293802 1100 2612208738494 1101 3575135470306 1102 4488312058558 1103 5172792817834 1104 5475504511858 1105 5324148664846 1106 4754874514690 1107 3898442536366 1108 2932018571370 1109 2020590599710 1110 1274028762990 1111 733580056212 1112 384826276443 1113 183395014053 1114 79124380371 1115 30776234037 1116 10737583407 1117 3339775105 1118 919145823 1119 221751661 1120 46352917 1121 8269291 1122 1234141 1123 149899 1124 14233 1125 991 1126 45 1127 1 1128 0 1129 24 1130 552 1131 8372 1132 93104 1133 809600 1134 5730956 1135 33949058 1136 171699968 1137 752703336 1138 2894006280 1139 9850597044 1140 29908968712 1141 81509640292 1142 200405491474 1143 446427293935 1144 904210809856 1145 1670105337328 1146 2819865831888 1147 4360991032296 1148 6187344208800 1149 8063447528864 1150 9661104876392 1151 10648297329692 1152 10799653176704 1153 10079023179536 1154 8653317051056 1155 6830461107736 1156 4952609171080 1157 3294619362700 1158 2007608819202 1159 1118406332655 1160 568221290496 1161 262519394424 1162 109900614408 1163 41513817444 1164 14077358512 1165 4258920928 1166 1140897484 1167 268104578 1168 54622208 1169 9503432 1170 1384040 1171 164132 1172 15224 1173 1036 1174 46 1175 1 1176 1 1177 24 1178 576 1179 8924 1180 101476 1181 902704 1182 6540556 1183 39680014 1184 205649026 1185 924403304 1186 3646709616 1187 12744603324 1188 39759565756 1189 111418609004 1190 281915131766 1191 646832785409 1192 1350638103791 1193 2574316147184 1194 4489971169216 1195 7180856864184 1196 10548335241096 1197 14250791737664 1198 17724552405256 1199 20309402206084 1200 21447950506396 1201 20878676356240 1202 18732340230592 1203 15483778158792 1204 11783070278816 1205 8247228533780 1206 5302228181902 1207 3126015151857 1208 1686627623151 1209 830740684920 1210 372420008832 1211 151414431852 1212 55591175956 1213 18336279440 1214 5399818412 1215 1409002062 1216 322726786 1217 64125640 1218 10887472 1219 1548172 1220 179356 1221 16260 1222 1082 1223 47 1224 1 1225 0 1226 25 1227 600 1228 9500 1229 110400 1230 1004180 1231 7443260 1232 46220570 1233 245329040 1234 1130052330 1235 4571112920 1236 16391312940 1237 52504169080 1238 151178174760 1239 393333740770 1240 928747917175 1241 1997470889200 1242 3924954250975 1243 7064287316400 1244 11670828033400 1245 17729192105280 1246 24799126978760 1247 31975344142920 1248 38033954611340 1249 41757352712480 1250 42326626862636 1251 39611016586832 1252 34216118389384 1253 27266848437608 1254 20030298812596 1255 13549456715682 1256 8428243333759 1257 4812642775008 1258 2517368308071 1259 1203160693752 1260 523834440684 1261 207005607808 1262 73927455396 1263 23736097852 1264 6808820474 1265 1731728848 1266 386852426 1267 75013112 1268 12435644 1269 1727528 1270 195616 1271 17342 1272 1129 1273 48 1274 1