0 1 1 1 2 1 3 3 4 2 5 1 6 5 7 7 8 3 9 1 10 11 11 16 12 12 13 4 14 1 15 21 16 41 17 34 18 18 19 5 20 1 21 43 22 94 23 99 24 60 25 25 26 6 27 1 28 85 29 219 30 261 31 195 32 95 33 33 34 7 35 1 36 171 37 492 38 678 39 576 40 340 41 140 42 42 43 8 44 1 45 341 46 1101 47 1692 48 1644 49 1106 50 546 51 196 52 52 53 9 54 1 55 683 56 2426 57 4149 58 4488 59 3430 60 1932 61 826 62 264 63 63 64 10 65 1 66 1365 67 5311 68 9959 69 11925 70 10130 71 6454 72 3150 73 1194 74 345 75 75 76 11 77 1 78 2731 79 11528 80 23568 81 30860 82 28915 83 20448 84 11256 85 4872 86 1665 87 440 88 88 89 12 90 1 91 5461 92 24881 93 55014 94 78278 95 80035 96 62271 97 38004 98 18516 99 7227 100 2255 101 550 102 102 103 13 104 1 105 10923 106 53398 107 127031 108 195012 109 216143 110 183202 111 122787 112 66264 113 29073 114 10362 115 2981 116 676 117 117 118 14 119 1 120 21845 121 114083 122 290457 123 478599 124 571225 125 523887 126 381997 127 226083 128 109791 129 43945 130 14443 131 3861 132 819 133 133 134 15 135 1 136 43691 137 242724 138 658602 139 1159080 140 1482110 141 1461516 142 1151458 143 740608 144 394020 145 174460 146 64350 147 19656 148 4914 149 980 150 150 151 16 152 1 153 87381 154 514581 155 1482240 156 2774880 157 3783640 158 3991400 159 3376968 160 2344232 161 1354210 162 656370 163 267696 164 91728 165 26208 166 6160 167 1160 168 168 169 17 170 1 171 174763 172 1087410 173 3314025 174 6575280 175 9522740 176 10698072 177 9671284 178 7202416 179 4486482 180 2359500 181 1052766 182 398736 183 127764 184 34328 185 7620 186 1360 187 187 188 18 189 1 190 349525 191 2291335 192 7365915 193 15439065 194 23665300 195 28203612 196 27123292 197 21562164 198 14397318 199 8158722 200 3947658 201 1634958 202 578916 203 174412 204 44268 205 9316 206 1581 207 207 208 19 209 1 210 699051 211 4815680 212 16285300 213 35955540 214 58149845 215 73265056 216 74669472 217 63090288 218 44932446 219 27275040 220 14211912 221 6380088 222 2469402 223 821984 224 233920 225 56304 226 11271 227 1824 228 228 229 20 230 1 231 1398101 232 10097401 233 35832810 234 83118970 235 141435985 236 187822125 237 202181112 238 180884088 239 136817370 240 88524930 241 49382268 242 23861916 243 10007322 244 3640210 245 1144440 246 308856 247 70737 248 13509 249 2090 250 250 251 21 252 1 253 2796203 254 21126862 255 78500811 256 190862860 257 340854645 258 475788222 259 539342181 260 509245776 261 407566350 262 279892380 263 166331022 264 86004360 265 38808042 266 15291500 267 5252490 268 1565904 269 402135 270 87894 271 16055 272 2380 273 273 274 22 275 1 276 5592405 277 44117867 278 171293293 279 435601611 280 814589475 281 1192287117 282 1419492627 283 1410356133 284 1190446866 285 864508590 286 544987938 287 300059214 288 144827046 289 61379962 290 22832870 291 7436106 292 2109513 293 517047 294 108129 295 18935 296 2695 297 297 298 23 299 1 300 11184811 301 91963996 302 372412782 303 988620624 304 1931900376 305 2958453036 306 3690464106 307 3848340312 308 3415935699 309 2614740216 310 1742158572 311 1017055872 312 522502344 313 236790008 314 94717812 315 33400784 316 10349889 317 2802348 318 657286 319 131824 320 22176 321 3036 322 322 323 24 324 1 325 22369621 326 191384541 327 806963364 328 2232236628 329 4549699950 330 7274927646 331 9487902396 332 10359516684 333 9645169743 334 7759693095 335 5446874664 336 3359332872 337 1829212308 338 882052276 339 377173560 340 142990808 341 47969699 342 14186331 343 3675892 344 826980 345 159390 346 25806 347 3404 348 348 349 25 350 1 351 44739243 352 397682154 353 1743173469 354 5016441240 355 10645737330 356 17741533668 357 24143758254 358 27544099704 359 26836557825 360 22634343270 361 16690884903 362 10840319280 363 6233549868 364 3184844600 365 1448661460 366 586965936 367 211660285 368 67760726 369 19176795 370 4766520 371 1030722 372 191268 373 29854 374 3800 375 375 376 26 377 1 378 89478485 379 825190479 380 3754782351 381 11224087965 382 24761578470 383 42937126290 384 60861096714 385 72406891326 386 73670997015 387 64990287285 388 50218977501 389 34249869927 390 20732293764 391 11182499020 392 5387853180 393 2321609012 394 894565619 395 307793673 396 94289305 397 25597275 398 6116022 399 1273602 400 227930 401 34350 402 4225 403 403 404 27 405 1 406 178956971 407 1710033272 408 8066319768 409 25011752796 410 57277141095 411 103181772096 412 152085739512 413 188356187448 414 199751003991 415 183929970840 416 148591034592 417 106149485988 418 67449263427 419 38284481984 420 19467675120 421 8883394064 422 3639495201 423 1337880744 424 440436568 425 129419620 426 33774741 427 7772160 428 1561240 429 269880 430 39325 431 4680 432 432 433 28 434 1 435 357913941 436 3539371201 437 17285917742 438 55526248494 439 131812050831 440 246333165771 441 376989705036 442 485255709612 443 535449185469 444 513661549401 445 432958960434 446 323240260434 447 215063336943 448 128098743451 449 68527863464 450 32994287208 451 14312020503 452 5592963291 453 1966895922 454 621050738 455 175426405 456 44094105 457 9789260 458 1899820 459 317655 460 44811 461 5166 462 462 463 29 464 1 465 715827883 466 7317351686 467 36957928479 468 122835671828 469 301892581515 470 584508760794 471 927494349831 472 1238957789544 473 1420206903063 474 1416970676550 475 1243802579019 476 968498192844 477 673202124231 478 419731044362 479 235561957155 480 119288938800 481 54585298113 482 22580745282 483 8440732349 484 2846785900 485 864026625 486 235064830 487 57005845 488 12228840 489 2296125 490 371826 491 50841 492 5684 493 493 494 30 495 1 496 1431655765 497 15111921971 498 78847115649 499 270846097295 500 688352355005 501 1379067673851 502 2265982520697 503 3136963558599 504 3730063063545 505 3864500678415 506 3526691176437 507 2858781292731 508 2071826990961 509 1349130655495 510 792348728445 511 420839470371 512 202498277919 513 88351969977 514 34955269475 515 12529619725 516 4061665335 517 1187279665 518 311649195 519 73034325 520 15160275 521 2757573 522 432999 523 57449 524 6235 525 525 526 31 527 1 528 2863311531 529 31178281108 530 167874894578 531 595364556600 532 1562983615330 533 3236437550444 534 5500038894210 535 7880861658384 536 9707440428270 537 10428505095060 538 9878797012890 539 8322468854856 540 6277012532154 541 4260419735180 542 2612603298250 543 1451766076416 544 732508344516 545 336011738460 546 140188704150 547 53178461000 548 18319338310 549 5719074660 550 1612940550 551 409141200 552 92786850 553 18661500 554 3292254 555 501816 556 64670 557 6820 558 558 559 32 560 1 561 5726623061 562 64265436581 563 356747406984 564 1304931645768 565 3535052881940 566 7557556513476 567 13268441486048 568 19654827669792 569 25048428213744 570 27864946880160 571 27360684460824 572 23918828453208 573 18743135368932 574 13235693578324 575 8457720490320 576 4906048315408 577 2589270976770 578 1245224022930 579 546110981560 580 218426404600 581 79621129980 582 26412972300 583 7955313600 584 2168150400 585 532248600 586 116963496 587 22819752 588 3908968 589 578956 590 72540 591 7440 592 592 593 33 594 1 595 11453246123 596 132348621858 597 756762632721 598 2852408165952 599 7965951758368 600 17565484496304 601 31826075787944 602 48684992472608 603 64118136740076 604 73770385284024 605 74983225366764 606 67924450623744 607 55215988886448 608 40499668417616 609 26918620665144 610 16267300958560 611 8960335981210 612 4506518476620 613 2071712412790 614 870894308160 615 334686211200 616 117472251600 617 37594167000 618 10941746400 619 2885972700 620 686535096 621 146367756 622 27732352 623 4617264 624 665136 625 81096 626 8096 627 627 628 34 629 1 630 22906492245 631 272332741143 632 1602606068547 633 6219034090209 634 17888465688200 635 40646549281624 636 75928443256344 637 119820723600136 638 162899985640172 639 193618415784420 640 203474979572436 641 190745332896924 642 160626710248056 643 122187044460712 644 84333730063400 645 52998018254520 646 30406178893310 647 15957302503690 648 7670452852530 649 3379459530150 650 1364822779320 651 504984407400 652 170977045800 653 52872214200 654 14892216300 655 3806434788 656 878542356 657 181918044 658 33507528 659 5427480 660 761112 661 90376 662 8789 663 663 664 35 665 1 666 45812984491 667 559936477104 668 3388464075132 669 13526456490660 670 40039403295145 671 93665983962432 672 180227144113856 673 293119151801696 674 410956982720460 675 504059171992640 676 547059846090384 677 530069213716848 678 461804020917876 679 363813091544000 680 260358015854400 681 169866350235040 682 101324869110250 683 55376518350240 684 27771180181800 685 12791700999000 686 5413654731870 687 2104751689920 688 751149787200 689 245732752800 690 73536375900 691 20071721280 692 4977712656 693 1115925104 694 224660100 695 40265280 696 6350784 697 867680 698 100419 699 9520 700 700 701 36 702 1 703 91625968981 704 1150414943881 705 7153612689330 706 29352988746210 707 89342791162205 708 214998485820825 709 425750014588976 710 712987743115824 711 1029876105802500 712 1302252986281940 713 1458068977227896 714 1458619725601080 715 1313126655130836 716 1069991201383300 717 792838567525200 718 536220402598480 719 332003577131910 720 188615992467870 721 98488604237100 722 47321800241100 723 20935001289510 724 8528375236590 725 3197855568720 726 1102626968400 727 349053561300 728 101220966756 729 26806518648 730 6457473848 731 1407600260 732 275780340 733 48138288 734 7399216 735 985677 736 111265 737 10290 738 738 739 37 740 1 741 183251937963 742 2361913867070 743 15080955783475 744 63559514416860 745 198774586498705 746 491673244907894 747 1001202788637513 748 1724976061308192 749 2564777814359244 750 3340247436069720 751 3854441655690604 752 3976827130262672 753 3695354422567668 754 3110744039602136 755 2383545800617300 756 1668791670593760 757 1070873717950890 758 631372606300260 759 342646957068570 760 171393806476200 761 79084110994350 762 33672879905940 763 13228530379710 764 4791948042720 765 1598753281500 766 490417970616 767 137982910716 768 35495842704 769 8314394308 770 1763911160 771 336620196 772 57272864 773 8585731 774 1115982 775 122955 776 11100 777 777 778 38 779 1 780 366503875925 781 4845995692795 782 31750095029205 783 137346447692755 784 441019683239975 785 1120444803048249 786 2344376062723359 787 4152154336177353 788 6349506087272436 789 8509531222992844 790 10110827046216116 791 10748508237155436 792 10298434863092012 793 8946080864936404 794 7079966975269836 795 5124778276408020 796 3403672542808470 797 2079478309186890 798 1170996771843030 799 608684364026970 800 292347920049570 801 129813741373470 802 53297121423090 803 20225732359230 804 7088808446820 805 2291613185628 806 682013918628 807 186393701116 808 46625437532 809 10629866148 810 2196807932 811 408691492 812 67829949 813 9924243 814 1259517 815 135531 816 11951 817 817 818 39 819 1 820 733007751851 821 9936327302860 822 66758002288950 823 296215571555680 824 975915303930140 825 2544810976104012 826 5467226443046634 827 9946482521517096 828 15631216052168277 829 21539532182404720 830 26329241580590168 831 28812989543896896 832 28437651945382784 833 25466003807232688 834 20793139441440840 835 15542328592865376 836 10670198255118270 837 6745896064595880 838 3935768995167060 839 2122468748822400 840 1059200506065240 841 489507421234920 842 209567923555980 843 83106749867760 844 30512047369050 845 10361257573680 846 3249592925688 847 939399305152 848 249647927264 849 60783126000 850 13499914472 851 2720045152 852 493692903 853 79986156 854 11429670 855 1417248 856 149036 857 12844 858 858 859 40 860 1 861 1466015503701 862 20361326440301 863 140194519650220 864 637666469230140 865 2154170241965770 866 5761615886130650 867 12700789544597364 868 23718017636918436 869 38276710748230245 870 54189810680558685 871 68090427855427120 872 76639247598797936 873 77847511215463704 874 71795817482488280 875 60419077199213200 876 46585024587122256 877 33019871933600586 878 21575050938087930 879 13023658603449000 880 7275606472043400 881 3766365094986780 882 1808335410047100 883 805669587637080 884 333126138142200 885 127796414130450 886 45456531313986 887 14974878336624 888 4561779633072 889 1282298107480 890 331690785560 891 78676656336 892 17037342608 893 3349397953 894 593527545 895 93934860 896 13117980 897 1590186 898 163514 899 13780 900 900 901 41 902 1 903 2932031007403 904 41699996549722 905 294071850668421 906 1370292131991720 907 4743667319056190 908 13005408080304444 909 29396858316821282 910 56311772224549992 911 93257160489485235 912 135545585793598370 913 174938721697166141 914 202355654542018848 915 211362062705027208 916 200575336312417360 917 173801173564583160 918 138088758972066208 919 100945293030959382 920 68086715000880276 921 42470247531871050 922 24544202573137200 923 13160372579160660 924 6553715347503720 925 3033140844796140 926 1305009225514800 927 521946647010750 928 193975460591796 929 66930595501986 930 21415456580000 931 6343373595080 932 1735555145040 933 437367270840 934 101154089248 935 21374126367 936 4102897810 937 710321745 938 109887336 939 15006238 940 1779388 941 179010 942 14760 943 943 944 42 945 1 946 5864062014805 947 85354680437727 948 616160886518583 949 2939696921120421 950 10422299934979450 951 29272307171621934 952 67803845486320454 953 133144665815208146 954 226122354210495717 955 337182367644200975 956 446665163201618751 957 530572871436780861 958 569412739677973464 959 555529033982421128 960 495214664275426920 961 405059981710893880 962 305073795870226762 963 212182109908015518 964 136604279739649326 965 81565663049095050 966 45237305342271420 967 23330758746758580 968 11198195367574020 969 5004402346595340 970 2082548700786450 971 806835170230518 972 290855812767030 973 97469611348130 974 30323426390040 975 8742310311240 976 2330275728552 977 572596045304 978 129227011521 979 26664079267 980 5001089275 981 846445041 982 128073946 983 17112654 984 1985958 985 195570 986 15785 987 987 988 43 989 1 990 11728124029611 991 174618735551976 992 1289659268293152 993 6296442071622444 994 22849331494212251 995 65705423267210272 996 155869869291584952 997 313572055750628584 998 545781341004674333 999 834395893441893432 1000 1133724974240152008 1001 1381949343722437308 1002 1522709736524808741 1003 1526092446285229312 1004 1398346045387014368 1005 1176452163930453216 1006 912024363643039406 1007 653429335780002832 1008 433726884711406944 1009 267258347935018776 1010 153123713549687790 1011 81675494784037440 1012 40595235803924880 1013 18812616165198960 1014 8130844341403290 1015 3277334792200560 1016 1231552174001520 1017 431156337275160 1018 140479784928330 1019 42536846991360 1020 11947320581472 1021 3105179952352 1022 744571309559 1023 164096886408 1024 33085812032 1025 6067308988 1026 1004531463 1027 148745376 1028 19456632 1029 2211048 1030 213241 1031 16856 1032 1032 1033 44 1034 1 1035 23456248059221 1036 357056220457041 1037 2696599776882294 1038 13465495182156438 1039 49990373435793595 1040 147099369104666391 1041 357182983531436132 1042 735731256672629828 1043 1311598105176294351 1044 2054541969734969715 1045 2861451194085282942 1046 3576820060836151038 1047 4043484559603192977 1048 4159860250774880309 1049 3914867820223097520 1050 3384918172739255344 1051 2698624119313946146 1052 1989817919239073274 1053 1360364779970708428 1054 864116558744615820 1055 510856672169249406 1056 281460725827242390 1057 144667121323110360 1058 69416656662314520 1059 31108557908175150 1060 13021849474064886 1061 5090598591736140 1062 1857647733972940 1063 632282974983570 1064 200501252542170 1065 59144719029936 1066 16197692624432 1067 4108205284953 1068 961996354501 1069 207184876990 1070 40846011102 1071 7327988343 1072 1187502147 1073 172173924 1074 22058820 1075 2455859 1076 232071 1077 17974 1078 1078 1079 45 1080 1 1081 46912496118443 1082 729749939620214 1083 5632974533925639 1084 28754979102283620 1085 109154531606374535 1086 328500589074880530 1087 816022091219272427 1088 1720058351705323128 1089 3138892043858272845 1090 5034931861795050930 1091 7183443112300556673 1092 9202169942366308596 1093 10665724093488961497 1094 11255529702948531910 1095 10871420161772006565 1096 9652690320823259296 1097 7907591019339280302 1098 5995300710113025084 1099 4217636468632595590 1100 2758998034585361800 1101 1681220658013240806 1102 955668387564566676 1103 507318318758202510 1104 251709010315822800 1105 116786903253296250 1106 50685076966641156 1107 20575552413804066 1108 7810559000259400 1109 2770890278813170 1110 917857921508460 1111 283540612735050 1112 81552771559072 1113 21795040528503 1114 5398395412270 1115 1235352855555 1116 260165506068 1117 50183062371 1118 8812981242 1119 1398589335 1120 198654840 1121 24941161 1122 2721642 1123 252109 1124 19140 1125 1125 1126 46 1127 1 1128 93824992236885 1129 1490774876652739 1130 11755924027310441 1131 61318944000522135 1132 237890257580245345 1133 731853858890587847 1134 1858888647357025221 1135 4007542956269855211 1136 7482146605916184675 1137 12282907845123263205 1138 17941277362266173487 1139 23539253176339167345 1140 27954863155061656047 1141 30240974297987254025 1142 29956685505166733515 1143 27293946828073776549 1144 22957529578790431890 1145 17882527567930451934 1146 12933666738687037530 1147 8704867620707189030 1148 5461932036937101418 1149 3199810497232292262 1150 1752320948968989906 1151 897860642398654350 1152 430713029385469350 1153 193515679168067178 1154 81441826563917502 1155 32101406882009346 1156 11846015229039710 1157 4089750705405970 1158 1319687972303382 1159 397488769542986 1160 111564222657481 1161 29117428649775 1162 7048118021805 1163 1577210383827 1164 325004545125 1165 61371047907 1166 10555918425 1167 1641361815 1168 228507719 1169 28126945 1170 3009699 1171 273405 1172 20355 1173 1173 1174 47 1175 1 1176 187649984473771 1177 3044099748130052 1178 24512647971814458 1179 130584826232399816 1180 517518264793516550 1181 1626745294620594252 1182 4222786688686157922 1183 9306548307037526688 1184 17767473649902585576 1185 29834918174629549740 1186 44591071431990550038 1187 59884870423337958024 1188 72825564518378746386 1189 80706896858945973892 1190 81940500126698000670 1191 76556012974887028656 1192 66066658445542769043 1193 52830658566946933992 1194 39251467243882680644 1195 27156530428564950160 1196 17529240973670772060 1197 10573079309298527032 1198 5966768083717687188 1199 3153599611999289856 1200 1562147478290716200 1201 725598862486818840 1202 316108610559592812 1203 129164351446445648 1204 49489202668675396 1205 17771481777462600 1206 5976519903179452 1207 1880282284964512 1208 552643073257473 1209 151478442131796 1210 38636252382690 1211 9145659417768 1212 2002581053694 1213 404001555516 1214 74724145002 1215 12594589920 1216 1919751856 1217 262077948 1218 31640862 1219 3321384 1220 296010 1221 21620 1222 1222 1223 48 1224 1 1225 375299968947541 1226 6213299485909301 1227 51068595774565392 1228 277735362205258544 1229 1123883606186407056 1230 3607971277195286496 1231 9567309278020802616 1232 21544420908263395032 1233 42038315168772481614 1234 72168207514778661726 1235 110308544331152446752 1236 151554448208006842752 1237 188620161251840016504 1238 214014409973299228328 1239 222560767995977441592 1240 213084406757732582424 1241 188537730578010661479 1242 154662372148350606903 1243 117949459288203689696 1244 83817732913862008864 1245 55609635476109925056 1246 34501941277433883616 1247 20044489290954194032 1248 10916088980514285744 1249 5577173149060944756 1250 2674777699113669396 1251 1204591126174246656 1252 509475775770057152 1253 202345584573200464 1254 75440185856949936 1255 26387377625248816 1256 8651779727229936 1257 2656053803536947 1258 762356372688819 1259 204210930558096 1260 50936332568112 1261 11798249561712 1262 2529324705024 1263 499837537368 1264 90601458552 1265 14971357214 1266 2238083694 1267 299738208 1268 35509056 1269 3658104 1270 319976 1271 22936 1272 1272 1273 49 1274 1 1275 750599937895083 1276 12676798951116946 1277 106307191204103609 1278 589973610444623568 1279 2436655497978698700 1280 7985345472622882056 1281 21620853932588404956 1282 49724826800359251024 1283 99117683376841047798 1284 173876359032810242820 1285 271658894709912208554 1286 381632733385835205552 1287 485825738496604352028 1288 564048364943031192616 1289 600456178222672671260 1290 588757200703484081328 1291 533755454226828781989 1292 448861419860255136366 1293 351114765924319657887 1294 256080253059195598880 1295 174485850337313478040 1296 111257735372140862736 1297 66479966735823452024 1298 37267777495467059488 1299 19617557086156662900 1300 9703148573148251832 1301 4511586046407101676 1302 1972395604837195104 1303 810799765680608408 1304 313328733985075600 1305 113780603288557656 1306 38799721922407776 1307 12413119677281829 1308 3721367060489358 1309 1043839808012295 1310 273438581961744 1311 66739744237212 1312 15135577377768 1313 3178610532396 1314 615628175760 1315 109412319478 1316 17733596804 1317 2601103626 1318 341890032 1319 39759180 1320 4021320 1321 345356 1322 24304 1323 1323 1324 50 1325 1