1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 10 3 11 4 12 3 13 2 14 1 15 1 16 3 17 6 18 10 19 13 20 14 21 13 22 10 23 6 24 3 25 1 26 1 27 4 28 10 29 20 30 33 31 47 32 59 33 66 34 66 35 59 36 47 37 33 38 20 39 10 40 4 41 1 42 1 43 5 44 15 45 35 46 68 47 115 48 174 49 239 50 301 51 350 52 377 53 377 54 350 55 301 56 239 57 174 58 115 59 68 60 35 61 15 62 5 63 1 64 1 65 6 66 21 67 56 68 124 69 239 70 413 71 652 72 952 73 1297 74 1659 75 2001 76 2283 77 2469 78 2534 79 2469 80 2283 81 2001 82 1659 83 1297 84 952 85 652 86 413 87 239 88 124 89 56 90 21 91 6 92 1 93 1 94 7 95 28 96 84 97 208 98 447 99 860 100 1512 101 2464 102 3760 103 5413 104 7393 105 9620 106 11965 107 14260 108 16316 109 17947 110 18996 111 19358 112 18996 113 17947 114 16316 115 14260 116 11965 117 9620 118 7393 119 5413 120 3760 121 2464 122 1512 123 860 124 447 125 208 126 84 127 28 128 7 129 1 130 1 131 8 132 36 133 120 134 328 135 775 136 1635 137 3147 138 5611 139 9371 140 14783 141 22169 142 31761 143 43642 144 57694 145 73563 146 90650 147 108134 148 125028 149 140264 150 152798 151 161721 152 166361 153 166361 154 161721 155 152798 156 140264 157 125028 158 108134 159 90650 160 73563 161 57694 162 43642 163 31761 164 22169 165 14783 166 9371 167 5611 168 3147 169 1635 170 775 171 328 172 120 173 36 174 8 175 1 176 1 177 9 178 45 179 165 180 493 181 1268 182 2903 183 6050 184 11661 185 21032 186 35815 187 57983 188 89736 189 133342 190 190916 191 264151 192 354026 193 460525 194 582406 195 717059 196 860486 197 1007424 198 1151616 199 1286216 200 1404295 201 1499399 202 1566100 203 1600478 204 1600478 205 1566100 206 1499399 207 1404295 208 1286216 209 1151616 210 1007424 211 860486 212 717059 213 582406 214 460525 215 354026 216 264151 217 190916 218 133342 219 89736 220 57983 221 35815 222 21032 223 11661 224 6050 225 2903 226 1268 227 493 228 165 229 45 230 9 231 1 232 1 233 10 234 55 235 220 236 713 237 1981 238 4884 239 10934 240 22595 241 43627 242 79442 243 137425 244 227160 245 360493 246 551364 247 815350 248 1168883 249 1628140 250 2207643 251 2918652 252 3767477 253 4753869 254 5869670 255 7097903 256 8412462 257 9778519 258 11153703 259 12490030 260 13736482 261 14842057 262 15759050 263 16446286 264 16872016 265 17016208 266 16872016 267 16446286 268 15759050 269 14842057 270 13736482 271 12490030 272 11153703 273 9778519 274 8412462 275 7097903 276 5869670 277 4753869 278 3767477 279 2918652 280 2207643 281 1628140 282 1168883 283 815350 284 551364 285 360493 286 227160 287 137425 288 79442 289 43627 290 22595 291 10934 292 4884 293 1981 294 713 295 220 296 55 297 10 298 1 299 1 300 11 301 66 302 286 303 999 304 2980 305 7864 306 18798 307 41393 308 85020 309 164462 310 301887 311 529047 312 889539 313 1440893 314 2256188 315 3424851 316 5052278 317 7257940 318 10171708 319 13928251 320 18659525 321 24485568 322 31504029 323 39779066 324 49330425 325 60123635 326 72062301 327 84983433 328 98656607 329 112787517 330 127026160 331 140979524 332 154228255 333 166346402 334 176923018 335 185584165 336 192013760 337 195971723 338 197308050 339 195971723 340 192013760 341 185584165 342 176923018 343 166346402 344 154228255 345 140979524 346 127026160 347 112787517 348 98656607 349 84983433 350 72062301 351 60123635 352 49330425 353 39779066 354 31504029 355 24485568 356 18659525 357 13928251 358 10171708 359 7257940 360 5052278 361 3424851 362 2256188 363 1440893 364 889539 365 529047 366 301887 367 164462 368 85020 369 41393 370 18798 371 7864 372 2980 373 999 374 286 375 66 376 11 377 1 378 1 379 12 380 78 381 364 382 1363 383 4343 384 12207 385 31005 386 72398 387 157418 388 321880 389 623767 390 1152814 391 2042353 392 3483245 393 5739422 394 9164207 395 14216199 396 21473140 397 31641868 398 45562255 399 64202982 400 88647157 401 120066166 402 159680770 403 208709308 404 268303896 405 339476658 406 423019198 407 519419617 408 628782283 409 750756165 410 884477749 411 1028534296 412 1180952447 413 1339215940 414 1500314537 415 1660824268 416 1817016925 417 1964994550 418 2100842638 419 2220794097 420 2321394829 421 2399661240 422 2453220125 423 2480422220 424 2480422220 425 2453220125 426 2399661240 427 2321394829 428 2220794097 429 2100842638 430 1964994550 431 1817016925 432 1660824268 433 1500314537 434 1339215940 435 1180952447 436 1028534296 437 884477749 438 750756165 439 628782283 440 519419617 441 423019198 442 339476658 443 268303896 444 208709308 445 159680770 446 120066166 447 88647157 448 64202982 449 45562255 450 31641868 451 21473140 452 14216199 453 9164207 454 5739422 455 3483245 456 2042353 457 1152814 458 623767 459 321880 460 157418 461 72398 462 31005 463 12207 464 4343 465 1363 466 364 467 78 468 12 469 1 470 1 471 13 472 91 473 455 474 1818 475 6161 476 18368 477 49373 478 121771 479 279189 480 601069 481 1224836 482 2377650 483 4420003 484 7903248 485 13642669 486 22806864 487 37022985 488 58495761 489 90136266 490 135694178 491 199884953 492 288501105 493 408494873 494 568018225 495 776405653 496 1044085782 497 1382409626 498 1803386471 499 2319322843 500 2942365704 501 3683957662 502 4554219212 503 5561280368 504 6710590947 505 8004244632 506 9440356187 507 11012533298 508 12709484057 509 14514797837 510 16406931167 511 18359421368 512 20341339539 513 22317981581 514 24251782089 515 26103422026 516 27833088081 517 29401830457 518 30772957401 519 31913399783 520 32794977940 521 33395506041 522 33699676323 523 33699676323 524 33395506041 525 32794977940 526 31913399783 527 30772957401 528 29401830457 529 27833088081 530 26103422026 531 24251782089 532 22317981581 533 20341339539 534 18359421368 535 16406931167 536 14514797837 537 12709484057 538 11012533298 539 9440356187 540 8004244632 541 6710590947 542 5561280368 543 4554219212 544 3683957662 545 2942365704 546 2319322843 547 1803386471 548 1382409626 549 1044085782 550 776405653 551 568018225 552 408494873 553 288501105 554 199884953 555 135694178 556 90136266 557 58495761 558 37022985 559 22806864 560 13642669 561 7903248 562 4420003 563 2377650 564 1224836 565 601069 566 279189 567 121771 568 49373 569 18368 570 6161 571 1818 572 455 573 91 574 13 575 1 576 1 577 14 578 105 579 560 580 2378 581 8539 582 26907 583 76280 584 198051 585 477240 586 1078309 587 2303145 588 4680795 589 9100798 590 17004046 591 30646715 592 53453578 593 90476550 594 148972220 595 239108031 596 374800391 597 574679183 598 863161920 599 1271607420 600 1839503874 601 2615630338 602 3659115051 603 5040299841 604 6841308662 605 9156211502 606 12090673958 607 15760988951 608 20292401299 609 25816658682 610 32468753868 611 40382862234 612 49687524243 613 60500172588 614 72921155540 615 87027458504 616 102866371446 617 120449387161 618 139746640918 619 160682212873 620 183130608491 621 206914707674 622 231805430051 623 257523302846 624 283742041035 625 310094160450 626 336178547443 627 361569808852 628 385829128988 629 408516272013 630 429202293997 631 447482474100 632 462988942716 633 475402478749 634 484462969667 635 489978076167 636 491829716104 637 489978076167 638 484462969667 639 475402478749 640 462988942716 641 447482474100 642 429202293997 643 408516272013 644 385829128988 645 361569808852 646 336178547443 647 310094160450 648 283742041035 649 257523302846 650 231805430051 651 206914707674 652 183130608491 653 160682212873 654 139746640918 655 120449387161 656 102866371446 657 87027458504 658 72921155540 659 60500172588 660 49687524243 661 40382862234 662 32468753868 663 25816658682 664 20292401299 665 15760988951 666 12090673958 667 9156211502 668 6841308662 669 5040299841 670 3659115051 671 2615630338 672 1839503874 673 1271607420 674 863161920 675 574679183 676 374800391 677 239108031 678 148972220 679 90476550 680 53453578 681 30646715 682 17004046 683 9100798 684 4680795 685 2303145 686 1078309 687 477240 688 198051 689 76280 690 26907 691 8539 692 2378 693 560 694 105 695 14 696 1 697 1 698 15 699 120 700 680 701 3058 702 11597 703 38504 704 114784 705 312835 706 790075 707 1868384 708 4171529 709 8852324 710 17953122 711 34957168 712 65603883 713 119057461 714 209534010 715 358506216 716 597614142 717 972413973 718 1547090778 719 2410244159 720 3681824672 721 5521252266 722 8136684553 723 11795322364 724 16834543896 725 23673549413 726 32825080120 727 44906653280 728 60650638185 729 80912392769 730 106675597873 731 139053875191 732 179287765205 733 228736181417 734 288861553614 735 361208029971 736 447372326555 737 548967090581 738 667576973868 739 804707984448 740 961731082270 741 1139821390920 742 1339894789932 743 1562544008481 744 1807976637369 745 2075957689453 746 2365759448604 747 2676121337365 748 3005222392349 749 3350668659103 750 3709497406873 751 4078199528282 752 4452760846842 753 4828722331054 754 5201258438357 755 5565272020863 756 5915503456112 757 6246650959343 758 6553498427019 759 6831046689012 760 7074643737710 761 7280109377580 762 7443849810645 763 7562957944192 764 7635295668762 765 7659554988898 766 7635295668762 767 7562957944192 768 7443849810645 769 7280109377580 770 7074643737710 771 6831046689012 772 6553498427019 773 6246650959343 774 5915503456112 775 5565272020863 776 5201258438357 777 4828722331054 778 4452760846842 779 4078199528282 780 3709497406873 781 3350668659103 782 3005222392349 783 2676121337365 784 2365759448604 785 2075957689453 786 1807976637369 787 1562544008481 788 1339894789932 789 1139821390920 790 961731082270 791 804707984448 792 667576973868 793 548967090581 794 447372326555 795 361208029971 796 288861553614 797 228736181417 798 179287765205 799 139053875191 800 106675597873 801 80912392769 802 60650638185 803 44906653280 804 32825080120 805 23673549413 806 16834543896 807 11795322364 808 8136684553 809 5521252266 810 3681824672 811 2410244159 812 1547090778 813 972413973 814 597614142 815 358506216 816 209534010 817 119057461 818 65603883 819 34957168 820 17953122 821 8852324 822 4171529 823 1868384 824 790075 825 312835 826 114784 827 38504 828 11597 829 3058 830 680 831 120 832 15 833 1 834 1 835 16 836 136 837 816 838 3874 839 15471 840 53975 841 168759 842 481594 843 1271669 844 3140053 845 7311582 846 16163906 847 34117028 848 69074196 849 134678079 850 253735540 851 463269550 852 821775765 853 1419389892 854 2391803745 855 3938893843 856 6349134944 857 10030948019 858 15552161781 859 23688731550 860 35483741079 861 52317494900 862 75989175929 863 108810084520 864 153707885476 865 214340570539 866 295218006140 867 401828000130 868 540762817860 869 719841049055 870 948218724256 871 1236482663728 872 1596718279726 873 2042543515503 874 2589100361925 875 3252995511121 876 4052182243303 877 5005776641020 878 6133802709576 879 7456862955612 880 8995733414680 881 10770884971929 882 12801936008102 883 15107044818521 884 17702253763117 885 20600800557593 886 23812415341505 887 27342624983173 888 31192088330038 889 35355987623266 890 39823501924349 891 44577388036151 892 49593692966433 893 54841619448677 894 60283562423572 895 65875329768321 896 71566555066413 897 77301304014191 898 83018869383290 899 88654742556566 900 94141742811305 901 99411279031463 902 104394712682996 903 109024785959409 904 113237075244498 905 116971427648270 906 120173337497568 907 122795220388436 908 124797544746394 909 126149784735056 910 126831163673536 911 126831163673536 912 126149784735056 913 124797544746394 914 122795220388436 915 120173337497568 916 116971427648270 917 113237075244498 918 109024785959409 919 104394712682996 920 99411279031463 921 94141742811305 922 88654742556566 923 83018869383290 924 77301304014191 925 71566555066413 926 65875329768321 927 60283562423572 928 54841619448677 929 49593692966433 930 44577388036151 931 39823501924349 932 35355987623266 933 31192088330038 934 27342624983173 935 23812415341505 936 20600800557593 937 17702253763117 938 15107044818521 939 12801936008102 940 10770884971929 941 8995733414680 942 7456862955612 943 6133802709576 944 5005776641020 945 4052182243303 946 3252995511121 947 2589100361925 948 2042543515503 949 1596718279726 950 1236482663728 951 948218724256 952 719841049055 953 540762817860 954 401828000130 955 295218006140 956 214340570539 957 153707885476 958 108810084520 959 75989175929 960 52317494900 961 35483741079 962 23688731550 963 15552161781 964 10030948019 965 6349134944 966 3938893843 967 2391803745 968 1419389892 969 821775765 970 463269550 971 253735540 972 134678079 973 69074196 974 34117028 975 16163906 976 7311582 977 3140053 978 1271669 979 481594 980 168759 981 53975 982 15471 983 3874 984 816 985 136 986 16 987 1 988 1 989 17 990 153 991 969 992 4843 993 20314 994 74289 995 243048 996 724642 997 1996311 998 5136364 999 12447946 1000 28611852 1001 62728880 1002 131803076 1003 266481155 1004 520216695 1005 983486245 1006 1805262010 1007 3224651901 1008 5616455630 1009 9555349337 1010 15904483465 1011 25935427610 1012 41487573920 1013 65176251495 1014 100659823815 1015 152976837121 1016 228964741381 1017 337771685848 1018 491472259742 1019 705796666375 1020 1000980555487 1021 1402739481421 1022 1943367621202 1023 2662954934717 1024 3610710389423 1025 4846371277386 1026 6441670167220 1027 8481821878978 1028 11066983347060 1029 14313629723237 1030 18355781018521 1031 23346005497760 1032 29456119475786 1033 36877498690319 1034 45820914610099 1035 56515810406099 1036 69208936329681 1037 84162273262726 1038 101650186455304 1039 121955769006757 1040 145366356348132 1041 172168218513445 1042 202640465794428 1043 237048234693438 1044 275635253954059 1045 318615923710484 1046 366167073161414 1047 418419592248166 1048 475450159160617 1049 537273306685635 1050 603834085111028 1051 675001586415643 1052 750563592843321 1053 830222601985207 1054 913593459824583 1055 1000202802847944 1056 1089490470712419 1057 1180813002908711 1058 1273449277595616 1059 1366608289902381 1060 1459439002416776 1061 1551042134475174 1062 1640483691598302 1063 1726809974409009 1064 1809063750046394 1065 1886301220753497 1066 1957609386039876 1067 2022123368362698 1068 2079043258982813 1069 2127650041413968 1070 2167320165048047 1071 2197538370909255 1072 2217908414312098 1073 2228161384183789 1074 2228161384183789 1075 2217908414312098 1076 2197538370909255 1077 2167320165048047 1078 2127650041413968 1079 2079043258982813 1080 2022123368362698 1081 1957609386039876 1082 1886301220753497 1083 1809063750046394 1084 1726809974409009 1085 1640483691598302 1086 1551042134475174 1087 1459439002416776 1088 1366608289902381 1089 1273449277595616 1090 1180813002908711 1091 1089490470712419 1092 1000202802847944 1093 913593459824583 1094 830222601985207 1095 750563592843321 1096 675001586415643 1097 603834085111028 1098 537273306685635 1099 475450159160617 1100 418419592248166 1101 366167073161414 1102 318615923710484 1103 275635253954059 1104 237048234693438 1105 202640465794428 1106 172168218513445 1107 145366356348132 1108 121955769006757 1109 101650186455304 1110 84162273262726 1111 69208936329681 1112 56515810406099 1113 45820914610099 1114 36877498690319 1115 29456119475786 1116 23346005497760 1117 18355781018521 1118 14313629723237 1119 11066983347060 1120 8481821878978 1121 6441670167220 1122 4846371277386 1123 3610710389423 1124 2662954934717 1125 1943367621202 1126 1402739481421 1127 1000980555487 1128 705796666375 1129 491472259742 1130 337771685848 1131 228964741381 1132 152976837121 1133 100659823815 1134 65176251495 1135 41487573920 1136 25935427610 1137 15904483465 1138 9555349337 1139 5616455630 1140 3224651901 1141 1805262010 1142 983486245 1143 520216695 1144 266481155 1145 131803076 1146 62728880 1147 28611852 1148 12447946 1149 5136364 1150 1996311 1151 724642 1152 243048 1153 74289 1154 20314 1155 4843 1156 969 1157 153 1158 17 1159 1 1160 1 1161 18 1162 171 1163 1140 1164 5983 1165 26297 1166 100586 1167 343634 1168 1068276 1169 3064587 1170 8200951 1171 20648897 1172 49260749 1173 111989629 1174 243792705 1175 510273860 1176 1030490555 1177 2013976800 1178 3819238810 1179 7043890711 1180 12660346340 1181 22215695660 1182 38120178972 1183 64055605613 1184 105543174690 1185 170719405871 1186 271379155397 1187 424355749470 1188 653319766209 1189 991089455746 1190 1482556579124 1191 2188340797553 1192 3189292741188 1193 4591969493729 1194 6535205311855 1195 9197893765417 1196 12808083938145 1197 17653471729286 1198 24093336634496 1199 32571933861573 1200 43633300753003 1201 57937375126903 1202 76277251661959 1203 99597321732109 1204 129011953633975 1205 165824276072799 1206 211544530859083 1207 267907364428061 1208 336887336016361 1209 420711837593239 1210 521870551788801 1211 643120524129183 1212 787485899921828 1213 958251378953852 1214 1158948477127078 1215 1393333756885799 1216 1665358300450435 1217 1979127852883533 1218 2338853255877727 1219 2748791026246915 1220 3213174202060472 1221 3736133879022870 1222 4321612183115377 1223 4973267764033260 1224 5694375237400795 1225 6487720340695683 1226 7355492885910167 1227 8299179878352012 1228 9319461412734750 1229 10416112142380735 1230 11587911233521047 1231 12832563754416671 1232 14146636400485315 1233 15525510316447044 1234 16963353542250918 1235 18453115281966489 1236 19986543778058824 1237 21554229075101837 1238 23145671387980299 1239 24749375164094831 1240 26352968263917027 1241 27943344998645360 1242 29506831078582379 1243 31029367863075991 1244 32496712684544768 1245 33894651466743350 1246 35209219391102556 1247 36426925002566710 1248 37534972902763546 1249 38521480064902882 1250 39375680828721234 1251 40088115797801666 1252 40650800163747588 1253 41057367415312290 1254 41303184944467485 1255 41385438720104870 1256 41303184944467485 1257 41057367415312290 1258 40650800163747588 1259 40088115797801666 1260 39375680828721234 1261 38521480064902882 1262 37534972902763546 1263 36426925002566710 1264 35209219391102556 1265 33894651466743350 1266 32496712684544768 1267 31029367863075991 1268 29506831078582379 1269 27943344998645360 1270 26352968263917027 1271 24749375164094831 1272 23145671387980299 1273 21554229075101837 1274 19986543778058824 1275 18453115281966489 1276 16963353542250918 1277 15525510316447044 1278 14146636400485315 1279 12832563754416671 1280 11587911233521047 1281 10416112142380735 1282 9319461412734750 1283 8299179878352012 1284 7355492885910167 1285 6487720340695683 1286 5694375237400795 1287 4973267764033260 1288 4321612183115377 1289 3736133879022870 1290 3213174202060472 1291 2748791026246915 1292 2338853255877727 1293 1979127852883533 1294 1665358300450435 1295 1393333756885799 1296 1158948477127078 1297 958251378953852 1298 787485899921828 1299 643120524129183 1300 521870551788801 1301 420711837593239 1302 336887336016361 1303 267907364428061 1304 211544530859083 1305 165824276072799 1306 129011953633975 1307 99597321732109 1308 76277251661959 1309 57937375126903 1310 43633300753003 1311 32571933861573 1312 24093336634496 1313 17653471729286 1314 12808083938145 1315 9197893765417 1316 6535205311855 1317 4591969493729 1318 3189292741188 1319 2188340797553 1320 1482556579124 1321 991089455746 1322 653319766209 1323 424355749470 1324 271379155397 1325 170719405871 1326 105543174690 1327 64055605613 1328 38120178972 1329 22215695660 1330 12660346340 1331 7043890711 1332 3819238810 1333 2013976800 1334 1030490555 1335 510273860 1336 243792705 1337 111989629 1338 49260749 1339 20648897 1340 8200951 1341 3064587 1342 1068276 1343 343634 1344 100586 1345 26297 1346 5983 1347 1140 1348 171 1349 18 1350 1