0 1 1 1 2 0 3 2 4 1 5 0 6 3 7 3 8 1 9 0 10 5 11 7 12 4 13 1 14 0 15 8 16 15 17 12 18 5 19 1 20 0 21 13 22 30 23 31 24 18 25 6 26 1 27 0 28 21 29 58 30 73 31 54 32 25 33 7 34 1 35 0 36 34 37 109 38 162 39 145 40 85 41 33 42 8 43 1 44 0 45 55 46 201 47 344 48 361 49 255 50 125 51 42 52 9 53 1 54 0 55 89 56 365 57 707 58 850 59 701 60 413 61 175 62 52 63 10 64 1 65 0 66 144 67 655 68 1416 69 1918 70 1806 71 1239 72 630 73 236 74 63 75 11 76 1 77 0 78 233 79 1164 80 2778 81 4184 82 4425 83 3458 84 2044 85 918 86 309 87 75 88 12 89 1 90 0 91 377 92 2052 93 5358 94 8880 95 10415 96 9122 97 6132 98 3198 99 1290 100 395 101 88 102 13 103 1 104 0 105 610 106 3593 107 10188 108 18422 109 23720 110 22995 111 17298 112 10248 113 4797 114 1760 115 495 116 102 117 14 118 1 119 0 120 987 121 6255 122 19139 123 37490 124 52557 125 55837 126 46425 127 30744 128 16335 129 6952 130 2343 131 610 132 117 133 15 134 1 135 0 136 1597 137 10835 138 35582 139 75051 140 113767 141 131389 142 119560 143 87417 144 51876 145 25047 146 9790 147 3055 148 741 149 133 150 16 151 1 152 0 153 2584 154 18687 155 65556 156 148123 157 241375 158 300993 159 297374 160 237721 161 155628 162 83875 163 37180 164 13455 165 3913 166 889 167 150 168 17 169 1 170 0 171 4181 172 32106 173 119825 174 288730 175 503265 176 673757 177 717927 178 622512 179 445225 180 264550 181 130845 182 53690 183 18109 184 4935 185 1055 186 168 187 18 188 1 189 0 190 6765 191 54974 192 217487 193 556678 194 1033370 195 1478015 196 1689058 197 1578160 198 1223365 199 793650 200 432575 201 197990 202 75712 203 23933 204 6140 205 1240 206 187 207 19 208 1 209 0 210 10946 211 93845 212 392286 213 1062895 214 2093313 215 3185142 216 3885000 217 3889730 218 3246750 219 2281565 220 1357070 221 684255 222 291811 223 104580 224 31128 225 7548 226 1445 227 207 228 20 229 1 230 0 231 17711 232 159765 233 703618 234 2011859 235 4189578 236 6756470 237 8759200 238 9352890 239 8359845 240 6321965 241 4071210 242 2239315 243 1051778 244 420324 245 141848 246 39916 247 9180 248 1671 249 228 250 21 251 1 252 0 253 28657 254 271321 255 1255669 256 3778372 257 8294750 258 14131190 259 19400670 260 22001820 261 20959485 262 16963375 263 11750245 264 6994780 265 3582904 266 1576682 267 593300 268 189312 269 50541 270 11058 271 1919 272 250 273 22 274 1 275 0 276 46368 277 459743 278 2230608 279 7045900 280 16262700 281 29182410 282 42291060 283 50755380 284 51321150 285 44244825 286 32784830 287 20984340 288 11629462 289 5579910 290 2311830 291 822528 292 249033 293 63270 294 13205 295 2190 296 273 297 23 298 1 299 0 300 75025 301 777432 302 3946020 303 13054880 304 31603350 305 59576300 306 90874140 307 115048260 308 123036015 309 112529350 310 88779900 311 60763950 312 36196706 313 18786054 314 8485040 315 3323670 316 1122102 317 323361 318 78394 319 15645 320 2485 321 297 322 24 323 1 324 0 325 121393 326 1312200 327 6954060 328 24046800 329 60920930 330 120362060 331 192741500 332 256677780 333 289405425 334 279810190 335 234094080 336 170528190 337 108590118 338 60562670 339 29582924 340 12631238 341 4694805 342 1508733 343 414960 344 96229 345 18403 346 2805 347 322 348 25 349 1 350 0 351 196418 352 2211025 353 12212280 354 44055740 355 116571080 356 240859290 357 403977700 358 564467540 359 669119220 360 681744965 361 602684170 362 465386220 363 315315014 364 187938842 365 98630634 366 45537832 367 18448145 368 6526899 369 2002087 370 526834 371 117117 372 21505 373 3151 374 348 375 26 376 1 377 0 378 317811 379 3719643 380 21377365 381 80314820 382 221547750 383 477792430 384 837578490 385 1225123020 386 1522992185 387 1630674375 388 1518523215 389 1238598580 390 889291352 391 563816526 392 316152400 393 156799704 394 68680782 395 26483777 396 8943946 397 2625150 398 662354 399 141427 400 24978 401 3524 402 375 403 27 404 1 405 0 406 514229 407 6248479 408 37309288 409 145747925 410 418433650 411 940199470 412 1719348620 413 2627169050 414 3417234425 415 3835411525 416 3751881760 417 3222508015 418 2443204946 419 1641046720 420 978599560 421 518489936 422 243928631 423 101691458 424 37429810 425 12095930 426 3404621 427 825286 428 169556 429 28850 430 3925 431 403 432 28 433 1 434 0 435 832040 436 10482351 437 64935132 438 263372033 439 785729325 440 1836425550 441 3497126580 442 5571640690 443 7567395660 444 8883320325 445 9105816500 446 8212988355 447 6555004313 448 4648068192 449 2935798680 450 1653889200 451 831099349 452 372103866 453 148065214 454 52150890 455 16162905 456 4371334 457 1019820 458 201930 459 33150 460 4355 461 432 462 29 463 1 464 0 465 1346269 466 17562870 467 112726771 468 474055090 469 1467535008 470 3562354345 471 7052900750 472 11695936320 473 16556270775 474 20286127510 475 21741018585 476 20541312870 477 17211197614 478 12844119225 479 8562466432 480 5108177816 481 2728917180 482 1304894673 483 557598890 484 212312034 485 71718416 486 21359525 487 5560710 488 1250600 489 239005 490 37908 491 4815 492 462 493 30 494 1 495 0 496 2178309 497 29391490 498 195224773 499 850153894 500 2727319423 501 6866314903 502 14112381675 503 24320477760 504 35819602755 505 45725718610 506 51132962595 507 50495319810 508 44307514797 509 34703385031 510 24342384337 511 15324533448 512 8668194345 513 4405915719 514 2010558777 515 822061814 516 300193355 517 97449275 518 27940055 519 7013240 520 1522755 521 281268 522 43155 523 5306 524 493 525 31 526 1 527 0 528 3524578 529 49132669 530 337343034 531 1519433757 532 5045008325 533 13155988671 534 28031597328 535 50128795755 536 76696351290 537 101831448875 538 118599699790 539 122169595275 540 112014032221 541 91855019053 542 67608235800 543 44775095601 544 26721644973 545 14379004737 546 6974073386 547 3044932625 548 1193973585 549 419002155 550 130950040 551 36203895 552 8775000 553 1841931 554 329238 555 48923 556 5829 557 525 558 32 559 1 560 0 561 5702887 562 82048737 563 581700476 564 2706930685 565 9291761505 566 25067311899 567 55299967674 568 102480870843 569 162644749800 570 224253518775 571 271564111260 572 291264614875 573 278491142293 574 238572436305 575 183805639190 576 127707864849 577 80164934919 578 45506565429 579 23363636900 580 10841067825 581 4539099565 582 1710425015 583 577892250 584 174167175 585 46501650 586 10898199 587 2214324 588 383467 589 55245 590 6385 591 558 592 33 593 1 594 0 595 9227465 596 136884293 597 1001092247 598 4808064918 599 17043700515 600 47515062075 601 108398876901 602 207909634272 603 341821971933 604 488729717450 605 614417329825 606 684998321410 607 681769789389 608 608918597651 609 489986311295 610 356288599640 611 234594444741 612 140050505085 613 75844275715 614 37249637350 615 16574140975 616 6668526735 617 2419267305 618 788263320 619 229443825 620 59241780 621 13441761 622 2646714 623 444541 624 62155 625 6975 626 592 627 34 628 1 629 0 630 14930352 631 228160495 632 1719677016 633 8516087850 634 31143526938 635 89626074489 636 211213906650 637 418789382016 638 712376356005 639 1054805208158 640 1374711158535 641 1590680266110 642 1645259253092 643 1529260823345 644 1282710548136 645 973982775784 646 671047979300 647 420151515255 648 239258417700 649 123934980890 650 58362877890 651 24953092725 652 9665686290 653 3381697800 654 1064208795 655 299583804 656 74897865 657 16471942 658 3146500 659 513081 660 69688 661 7600 662 627 663 35 664 1 665 0 666 24157817 667 379975140 668 2948929758 669 15043829784 670 56703315303 671 168284663502 672 409238858040 673 837912922938 674 1472987709954 675 2255911281613 676 3043933696518 677 3650389746055 678 3917709308591 679 3783438674088 680 3301957682776 681 2612981923560 682 1879625199825 683 1231249999640 684 735254208670 685 400443035940 686 198871999755 687 89984497350 688 37038046320 689 13835647410 690 4675350420 691 1423034379 692 387923430 693 94016521 694 20062983 695 3721736 696 589744 697 77880 698 8261 699 663 700 36 701 1 702 0 703 39088169 704 632293452 705 5048581914 706 26508847392 707 102890672025 708 314614053294 709 788737428192 710 1665941162994 711 3023276988897 712 4783704199725 713 6674556136666 714 8285003708683 715 9213358307738 716 9230408806024 717 8368106905000 718 6888922382120 719 5163655102685 720 3531026714720 721 2205762626010 722 1259632225500 723 657677913585 724 313809589830 725 136688229960 726 54255391530 727 19575206625 728 6397968603 729 1885855674 730 498411893 731 117226004 732 24297800 733 4381168 734 675224 735 86768 736 8959 737 700 738 37 739 1 740 0 741 63245986 742 1051356761 743 8629805124 744 46601259090 745 186102834720 746 585789388821 747 1512590339526 748 3292591514124 749 6162205861845 750 10062892470235 751 14502194032909 752 18609949591404 753 21416071325012 754 22227205787850 755 20900473393800 756 17870011210680 757 13932202684630 758 9925931817045 759 6472043549400 760 3865837887450 761 2116182138840 762 1061472000765 763 487535866110 764 204779268900 765 78505948575 766 27396209607 767 8671747707 768 2478284088 769 635700880 770 145245540 771 29268712 772 5134272 773 770253 774 96390 775 9695 776 738 777 38 778 1 779 0 780 102334155 781 1746896199 782 14729743799 783 81739911606 784 335594765835 785 1086506276835 786 2887117156539 787 6471123016644 788 12478074364866 789 21008802531805 790 31239642639810 791 41397147332996 792 49239379224154 793 52873685918886 794 51495786086650 795 45659406986600 796 36965868997995 797 27389161216395 798 18603737992455 799 11597513662350 800 6639697939875 801 3491463729435 802 1685696096835 803 746570526540 804 302860424100 805 112300126785 806 37953812988 807 11648443688 808 3231210972 809 805244220 810 178895420 811 35078208 812 5991293 813 875602 814 106785 815 10470 816 777 817 39 818 1 819 0 820 165580141 821 2900587115 822 25106445122 823 143070914495 824 603437512161 825 2007890431491 826 5486213772900 827 12650831687307 828 25111403243355 829 43549769366906 830 66750639204524 831 91246739564210 832 112052597882162 833 124340270930890 834 125269945399336 835 115025204283930 836 96557478669225 837 74280962031435 838 52464942758250 839 34067089542255 840 20353393741065 841 11192633670075 842 5664695692380 843 2637045892275 844 1127936899215 845 442556760492 846 158925687480 847 52080540764 848 15515355540 849 4181700732 850 1013408352 851 219107900 852 41839754 853 6963285 854 992082 855 117993 856 11285 857 817 858 40 859 1 860 0 861 267914296 862 4813063455 863 42736776036 864 249917271223 865 1082103192491 866 3697834220487 867 10381221360930 868 24608168476851 869 50240309295528 870 89669975142066 871 141540051211240 872 199394526101730 873 252538716670526 874 289266554731938 875 301106002416876 876 285954556669866 877 248548551951150 878 198227601917055 879 145349642782140 880 98129545962855 881 61060181223195 882 35037491140575 883 18543025459290 884 9048312111195 885 4067843215590 886 1682793786492 887 639436260960 888 222654671932 889 70827107276 890 20502300492 891 5374004504 892 1267594460 893 266938947 894 49678641 895 8062152 896 1120545 897 130055 898 12141 899 858 900 41 901 1 902 0 903 433494437 904 7981564866 905 72656284613 906 435724961754 907 1935457975875 908 6787827844469 909 19565269354317 910 47640221525088 911 99959881015734 912 183460053804500 913 297960665557830 914 432181316877180 915 563985840654418 916 666145542333354 917 715642502548150 918 702085763370672 919 631060587290241 920 521057115899640 921 396042187457445 922 277546278287250 923 179543120927115 924 107290306033845 925 59245212292245 926 30228383462760 927 14244092226000 928 6193193762574 929 2481155734932 930 914171473656 931 308997134748 932 95511108500 933 26889713348 934 6860706864 935 1576373161 936 323580873 937 58732875 938 9300690 939 1261885 940 143013 941 13039 942 900 943 42 944 1 945 0 946 701408733 947 13228122758 948 123374625515 949 758298517590 950 3453286130120 951 12421120040831 952 36734318559716 953 91813659356256 954 197840411836350 955 373089909962300 956 622960770573570 957 929536508536740 958 1248705874202124 959 1519397937719710 960 1682894047298380 961 1703682822588688 962 1581694902612063 963 1350345305106936 964 1062448946139225 965 771718011707550 966 518149580437560 967 321870918101535 968 185078543785380 969 98521907866200 970 48540318904350 971 22120079775066 972 9313785758466 973 3617981880520 974 1293995715680 975 425010543740 976 127774826352 977 35018014672 978 8704018972 979 1949632675 980 390375900 981 69154110 982 10692630 983 1417039 984 156910 985 13980 986 943 987 43 988 1 989 0 990 1134903170 991 21911096357 992 209259032886 993 1317398104859 994 6147042623585 995 22662234015420 996 68720707954864 997 176188199441060 998 389613952208340 999 754390375603150 1000 1294011346093700 1001 1984678595987490 1002 2742228223393282 1003 3434249354255188 1004 3917934487566240 1005 4088662633257740 1006 3916438312490992 1007 3453097323618639 1008 2808836438703606 1009 2111713236134025 1010 1469410713072225 1011 947310804572940 1012 566194674179160 1013 313828835114340 1014 161306318996550 1015 76853592441990 1016 33915021268464 1017 13845939112642 1018 5220974730948 1019 1814517367920 1020 579675083440 1021 169653547888 1022 45298406805 1023 10977232520 1024 2398741450 1025 468830700 1026 81108625 1027 12252682 1028 1586988 1029 171790 1030 14965 1031 987 1032 44 1033 1 1034 0 1035 1836311903 1036 36274122285 1037 354544754758 1038 2284955655335 1039 10917726858564 1040 41230396679836 1041 128117260530000 1042 336722566752180 1043 763642563485750 1044 1517094237773790 1045 2671362492270420 1046 4208226450617930 1047 5975612693582896 1048 7695875515368180 1049 9035077889119808 1050 9710279943412668 1051 9586795848360795 1052 8719880941216567 1053 7324382708461470 1054 5692267686545181 1055 4099273529643810 1056 2738592435746700 1057 1698584022537480 1058 978545417159700 1059 523675473015240 1060 260279991213606 1061 120082399468920 1062 51378942261626 1063 20360909559270 1064 7460502642608 1065 2521967277712 1066 784346646000 1067 223655973665 1068 58225272000 1069 13766349870 1070 2936726260 1071 560631955 1072 94778346 1073 13996580 1074 1772758 1075 187698 1076 15995 1077 1032 1078 45 1079 1 1080 0 1081 2971215073 1082 60021530545 1083 600077909929 1084 3956898514952 1085 19349725137484 1086 74810357553820 1087 238068365164700 1088 641028026723240 1089 1489979082446270 1090 3035127176862690 1091 5482468076137910 1092 8864267538875840 1093 12926067367594108 1094 17105737563206264 1095 20648887892054228 1096 22834020465790216 1097 23213514104264455 1098 21759774113196001 1099 18853100088381643 1100 15128363631140676 1101 11260951929261216 1102 7785176769963450 1103 5003371132463340 1104 2990958274811520 1105 1663527209171490 1106 860809056670836 1107 414277411950990 1108 185307280843188 1109 76960826551844 1110 29635929569798 1111 10562145003760 1112 3475967471600 1113 1053301026470 1114 292858478185 1115 74390363320 1116 17171906830 1117 3578466840 1118 667662983 1119 110361914 1120 15941128 1121 1975421 1122 204680 1123 17071 1124 1078 1125 46 1126 1 1127 0 1128 4807526976 1129 99266867903 1130 1014644195232 1131 6841932080216 1132 34224350511000 1133 135390479371140 1134 440995983248520 1135 1215818958640120 1136 2894649672655260 1137 6042200497082750 1138 11188957745271020 1139 18554962065631680 1140 27765947600052844 1141 37727680446168552 1142 46789703344380300 1143 53193188301257112 1144 55634330418415466 1145 53693169158677023 1146 47937256910039114 1147 39673731406067500 1148 30488589090045702 1149 21784721134971366 1150 14487131924964270 1151 8972874824434560 1152 5178160956998250 1153 2784616257055932 1154 1395168868090746 1155 650963635055804 1156 282629016954302 1157 114057258764250 1158 42720041851270 1159 14822459121360 1160 4752924471735 1161 1404384776655 1162 381015191375 1163 94498996410 1164 21311005625 1165 4340908169 1166 792021477 1167 128075800 1168 18104247 1169 2196096 1170 222783 1171 18194 1172 1125 1173 47 1174 1 1175 0 1176 7778742049 1177 164095925424 1178 1713988973064 1179 11813474790400 1180 60416007728700 1181 244425187435960 1182 814454827784360 1183 2297842968611880 1184 5600447713741650 1185 11971977346600700 1186 22713626318491680 1187 38608187349778540 1188 59246977033278632 1189 82599365609427660 1190 105166271682603080 1191 122816912111427628 1192 132041032823937033 1193 131087273690288490 1194 120483526157097780 1195 102739351947247290 1196 81423272425374418 1197 60058486994980518 1198 41275224192398976 1199 26450965024210350 1200 15814562990604300 1201 8823586270725018 1202 4594062537097668 1203 2231439783989738 1204 1010553478561950 1205 426322205288350 1206 167339445619280 1207 61018468444230 1208 20628684619565 1209 6450167726575 1210 1859790331350 1211 492686094615 1212 119388468875 1213 26319576777 1214 5243291560 1215 936038405 1216 148155468 1217 20505023 1218 2435950 1219 242055 1220 19365 1221 1173 1222 48 1223 1 1224 0 1225 12586269025 1226 271141535376 1227 2892729093720 1228 20369395843680 1229 106453833030100 1230 440231674535800 1231 1499875998468840 1232 4328116755036360 1233 10792940355008790 1234 23614625557425100 1235 45874561410363400 1236 79876775733901900 1237 125621111983110016 1238 179574023088874844 1239 234555340636411040 1240 281176372095287820 1241 310492275353780127 1242 316821475672902546 1243 299508056757425384 1244 262896609510412570 1245 214651213462667410 1246 163266480555326302 1247 115820843112343764 1248 76699064041043886 1249 47443688971812900 1250 27422765518385250 1251 14812817675913432 1252 7476465956143210 1253 3524622279505990 1254 1550932942614550 1255 636381692758900 1256 243180373184870 1257 86400077535530 1258 28483237122795 1259 8690973249300 1260 2446975422375 1261 633385569115 1262 150048953821 1263 32354889814 1264 6307405765 1265 1102298120 1266 170856587 1267 23163756 1268 2696199 1269 262545 1270 20585 1271 1222 1272 49 1273 1 1274 0