0 1 1 2 2 1 3 3 4 3 5 1 6 5 7 7 8 4 9 1 10 8 11 17 12 12 13 5 14 1 15 13 16 43 17 35 18 18 19 6 20 1 21 21 22 116 23 103 24 60 25 25 26 7 27 1 28 34 29 333 30 312 31 196 32 93 33 33 34 8 35 1 36 55 37 1010 38 976 39 643 40 331 41 135 42 42 43 9 44 1 45 89 46 3202 47 3147 48 2137 49 1161 50 518 51 187 52 52 53 10 54 1 55 144 56 10504 57 10415 58 7213 59 4066 60 1929 61 768 62 250 63 63 64 11 65 1 66 233 67 35364 68 35220 69 24716 70 14301 71 7088 72 3022 73 1093 74 325 75 75 76 12 77 1 78 377 79 121450 80 121217 81 85853 82 50633 83 25917 84 11616 85 4528 86 1506 87 413 88 88 89 13 90 1 91 610 92 423612 93 423235 94 301785 95 180568 96 94715 97 44082 98 18165 99 6549 100 2021 101 515 102 102 103 14 104 1 105 987 106 1495974 107 1495364 108 1071752 109 648517 110 346732 111 166164 112 71449 113 27367 114 9202 115 2653 116 632 117 117 118 15 119 1 120 1597 121 5336926 122 5335939 123 3839965 124 2344601 125 1272849 126 624332 127 277600 128 111436 129 39987 130 12620 131 3418 132 765 133 133 134 16 135 1 136 2584 137 19202185 138 19200588 139 13863662 140 8527723 141 4687758 142 2343157 143 1070308 144 445976 145 168376 146 56940 147 16953 148 4333 149 915 150 150 151 17 152 1 153 4181 154 69591626 155 69589042 156 50386857 157 31186269 158 17322607 159 8794884 160 4107126 161 1763969 162 693661 163 247685 164 79309 165 22369 166 5416 167 1083 168 168 169 18 170 1 171 6765 172 253796271 173 253792090 174 184200464 175 114611422 176 64224565 177 33038296 178 15715689 179 6920805 180 2813679 181 1049710 182 356049 183 108364 184 29055 185 6686 186 1270 187 187 188 19 189 1 190 10946 191 930671387 192 930664622 193 676868351 194 423076261 195 238875797 196 124264375 197 60039810 198 27001514 199 11285825 200 4365020 201 1551341 202 501631 203 145582 204 37218 205 8163 206 1477 207 207 208 20 209 1 210 17711 211 3429369548 212 3429358602 213 2498687215 214 1568022593 215 891154242 216 468077981 217 229202184 218 104937809 219 44897999 220 17896485 221 6610660 222 2245640 223 694299 224 192668 225 47086 226 9868 227 1705 228 228 229 21 230 1 231 28657 232 12691424545 233 12691406834 234 9262037286 235 5832678684 236 3333991469 237 1765968876 238 874814634 239 406736653 240 177534469 241 72596660 242 27698661 243 9802176 244 3191516 245 945876 246 251577 247 58909 248 11823 249 1955 250 250 251 22 252 1 253 46368 254 47151181533 255 47151152876 256 34459728331 257 21768321497 258 12506284211 259 6673605527 260 3339614058 261 1573645182 262 698830548 263 292093895 264 114559426 265 41962766 266 14264105 267 4461929 268 1270413 269 324537 270 72960 271 14051 272 2228 273 273 274 23 275 1 276 75025 277 175791436738 278 175791390370 279 128640208837 280 81489055961 281 47029327630 282 25261006133 283 12754721922 284 6081116395 285 2741502337 286 1167857155 287 469026607 288 176932712 289 62373286 290 20410520 291 6146415 292 1684486 293 414073 294 89536 295 16576 296 2525 297 297 298 24 299 1 300 121393 301 657484795561 302 657484720536 303 481693283798 304 305901893428 305 177261684591 306 95772628630 307 48743301000 308 23482294867 309 10727572945 310 4646456550 311 1904954213 312 737097058 313 268070451 314 91137739 315 28764453 316 8353933 317 2207518 318 523032 319 108959 320 19423 321 2847 322 322 323 25 324 1 325 196418 326 2466239993273 327 2466239871880 328 1808755076319 329 1151270355783 330 669577071985 331 363675178557 332 186413493966 333 90640865336 334 41897564336 335 18415269469 336 7687696524 337 3041239974 338 1136285761 339 399188703 340 131118252 341 39980513 342 11216060 343 2862127 344 654609 345 131577 346 22618 347 3195 348 348 349 26 350 1 351 317811 352 9275575337610 353 9275575141192 354 6809335147919 355 4343095276039 356 2534340199720 357 1383069843937 358 713492771952 359 349817593395 360 163404099429 361 72763234093 362 30865669757 363 12450400288 364 4762703764 365 1721463790 366 585178029 367 185989326 368 54871074 369 14890561 370 3674501 371 812374 372 157765 373 26188 374 3570 375 375 376 27 377 1 378 514229 379 34971114804487 380 34971114486676 381 25695539149066 382 16419964007874 383 9610628859955 384 5267533583916 385 2733193384196 386 1350123540259 387 636630768307 388 286813174912 389 123409075483 390 50645841390 391 19780171633 392 7329771345 393 2567067581 394 845603791 395 260425762 396 74436436 397 19565362 398 4674801 399 1000300 400 187926 401 30161 402 3973 403 403 404 28 405 1 406 832040 407 132147594130253 408 132147593616024 409 97176478811537 410 62205364324861 411 36509825175795 412 20089861167921 413 10479232307966 414 5211698724050 415 2478505339854 416 1128381799595 417 491751031288 418 204937856376 419 81528780893 420 30882939503 421 11102767870 422 3772996525 423 1205928944 424 360325153 425 99899391 426 25462955 427 5897593 428 1222792 429 222492 430 34566 431 4405 432 432 433 29 434 1 435 1346269 436 500400211601104 437 500400210769064 438 368252616638811 439 236105023022787 440 138928544211250 441 76723179886389 442 40213354710594 443 20123493542673 444 9644261234707 445 4432562510657 446 1954057170803 447 825675371208 448 333924339920 449 128986483544 450 47457702651 451 16574763148 452 5471995278 453 1698998753 454 493069809 455 132744656 456 32845265 457 7382310 458 1484717 459 261925 460 39433 461 4867 462 462 463 30 464 1 465 2178309 466 1898537974133085 467 1898537972786816 468 1398137761185712 469 897737550416648 470 529484933777837 471 293379910755050 472 154451366543800 473 77728186657411 474 37514831946817 475 17391338404144 476 7747077169437 477 3314514658780 478 1360457487977 479 534782116769 480 200857776849 481 71871293305 482 24413590654 483 7838827506 484 2366832228 485 667833475 486 174763666 487 42019010 488 9173745 489 1791435 490 306718 491 44793 492 5360 493 493 494 31 495 1 496 3524578 497 7216166904477861 498 7216166902299552 499 5317628928166467 500 3419090955379651 501 2020953194193939 502 1123215643777291 503 593730709999454 504 300350799244404 505 145899432700604 506 68171246043193 507 30656414096376 508 13265075692232 509 5517998522795 510 2203483864015 511 843026376038 512 308244259269 513 107386482420 514 35515189115 515 11101598461 516 3262770955 517 895938727 518 228105252 519 53341586 520 11322576 521 2148831 522 357396 523 50678 524 5885 525 525 526 32 527 1 528 5702887 529 27474327419930159 530 27474327416405581 531 20258160511927720 532 13041993609628168 533 7724364681461701 534 4305273726082050 535 2284320531888111 536 1161104888110820 537 567374178111366 538 267023378866962 539 121123946166358 540 52952700123165 541 22296286026789 542 9031210334557 543 3513211811762 544 1309727947747 545 466701571709 546 158457312440 547 51070830020 548 15555640905 549 4454042444 550 1191271489 551 295332762 552 67227510 553 13885924 554 2563348 555 414517 556 57121 557 6443 558 558 559 33 560 1 561 9227465 562 104769195240683127 563 104769195234980240 564 77294867815050081 565 49820540398644500 566 29562379886716780 567 16520386277088612 568 8796021595626911 569 4490747869544861 570 2206427337656750 571 1045322449545930 572 477948271434564 573 210924892567602 574 89800946401244 575 36848246278079 576 14551960251290 577 5520749916733 578 2007538104971 579 697810157224 580 231108585515 581 72651273075 582 21580443055 583 6024802150 584 1570759706 585 379488217 586 84155455 587 16927945 588 3042021 589 478673 590 64156 591 7035 592 592 593 34 594 1 595 14930352 596 400113717949904594 597 400113717940677129 598 295344522699994002 599 190575327465013762 600 113280459649963681 601 63459919251319181 602 33897539364602401 603 17377153087513789 604 8581131491886878 605 4090383622342017 606 1883956284685267 607 838633835139337 608 360685563704773 609 149760671137171 610 59959724735927 611 23111478457848 612 8559518206558 613 3038768289825 614 1031230184854 615 333420027630 616 102311442115 617 29660169040 618 8079725985 619 2054923835 620 484164129 621 104675912 622 20520457 623 3592512 624 550491 625 71818 626 7662 627 627 628 35 629 1 630 24157817 631 1530163085752561595 632 1530163085737631243 633 1130049367787726649 634 729935649847049520 635 434591127147055518 636 244015799682041756 637 130735340032078075 638 67275420780758894 639 33377881416156493 640 16000728328642704 641 7419596836755826 642 3329213214413809 643 1445256929728542 644 606623094589205 645 245937530884432 646 96176859747261 647 36217135011334 648 13105656553486 649 4546138346928 650 1507370057103 651 476139872249 652 142719844619 653 40408402504 654 10748233464 655 2668507479 656 613583644 657 129419515 658 24743603 659 4223146 660 630634 661 80143 662 8325 663 663 664 36 665 1 666 39088169 667 5859506340759498215 668 5859506340735340398 669 4329343254982778803 670 2799180169245147560 671 1669130801457420911 672 939195151610371391 673 504604024463315873 674 260588224781274117 675 129852884749196042 676 62577463968437148 677 29199582552280655 678 13198854223637951 679 5779257386882125 680 2450044172468316 681 1004787242739774 682 398164148150569 683 152226617266137 684 56049757518876 685 19832622507542 686 6726965954056 687 2180827607128 688 673457550025 689 197317677776 690 54597833157 691 14189430653 692 3441197189 693 772689710 694 159106066 695 29686551 696 4942948 697 719802 698 89168 699 9025 700 700 701 37 702 1 703 63245986 704 22465753307279814564 705 22465753307240726395 706 16606246966481228180 707 10746740625745887782 708 6417397370763108979 709 3618217201517961419 710 1949086400060540508 711 1009891248450169117 712 505287223986853244 713 244698999205579127 714 114846114456383085 715 52268650487945937 716 23069067935665282 717 9870213712027331 718 4090956325145206 719 1640912152676890 720 636124909937116 721 237960761786547 722 85734144520410 723 29684387001534 724 9851764493992 725 3124798539936 726 943970932808 727 270513382783 728 73195705007 729 18597871850 730 4408441197 731 967244008 732 194554298 733 35448232 734 5761681 735 818733 736 98931 737 9763 738 738 739 38 740 1 741 102334155 742 86235862358521508635 743 86235862358458262649 744 63770109051178448085 745 41304355743937721690 746 24698108777456493510 747 13951368151710605728 748 7533970780947496749 749 3915753579429535330 750 1966667179368994822 751 956775930918825705 752 451488706931972461 753 206789707726393334 754 91943593270010249 755 39674942782064312 756 16605874846399030 757 6735661134371699 758 2644704809226493 759 1003792656549603 760 367667746612487 761 129706984825940 762 43972840305530 763 14288453303996 764 4436688810004 765 1311890270068 766 367919337260 767 97405954477 768 24210249470 769 5612377620 770 1203936423 771 236692415 772 42138117 773 6689885 774 928204 775 109471 776 10540 777 777 778 39 779 1 780 165580141 781 331386282777429766963 782 331386282777327432808 783 245150420418805924173 784 158914558060347661524 785 95144449009169213439 786 53840093265231491749 787 29141984487774998239 788 15190616336064392511 789 7656645555116895762 790 3740891975687360432 791 1774224796318365610 792 817448865399539905 793 365960158467567444 794 159170450741174110 795 67226857471163861 796 27551914689099549 797 10946039842700519 798 4210378708328820 799 1565673899102327 800 561881242552724 801 194213495940237 802 64506511114297 803 20533670808767 804 6245217504771 805 1808528694767 806 496638424699 807 128719087439 808 31313132962 809 7102883492 810 1490505872 811 286569449 812 49877034 813 7738917 814 1049032 815 120828 816 11357 817 817 818 40 819 1 820 267914296 821 1274781379652933777388 822 1274781379652768197247 823 943395096875338430284 824 612008814098010997476 825 366858393679205073303 826 207943835618857411779 827 112799386609688198340 828 58959293344456706591 829 29817308856681708352 830 14626692520617315841 831 6970046965500420079 832 3229154989813059647 833 1454930193494694037 834 637481328095154132 835 271521169627586688 836 112350718886412578 837 45123861415248717 838 17571946726149168 839 6625906883448649 840 2415528175119829 841 849854276017502 842 287973033464778 843 93759537524541 844 29253026410244 845 8719355601477 846 2474138096706 847 665609401939 848 168970977240 849 40251889801 850 8938756839 851 1835873347 852 345367475 853 58798026 854 8920992 855 1182075 856 133043 857 12215 858 858 859 41 860 1 861 433494437 862 4908720076436831453561 863 4908720076436563539265 864 3633938696783629761877 865 2359157317130861564630 866 1415762220255523134346 867 803753406157512136870 868 436895012478307063567 869 228951176859449651788 870 116151790249761453448 871 57192496905304746857 872 27375188048623038505 873 12748495528005722664 874 5778448562505302585 875 2549293572692242938 876 1094363379197548901 877 456882051102394769 878 185360881474808081 879 73010162588395503 880 27886301173146786 881 10314354446997618 882 3688447563548969 883 1272919388429140 884 423065112411638 885 135092078946860 886 41332541422319 887 12079515012075 888 3360159410598 889 886021313892 890 220411911953 891 51440934713 892 11189044912 893 2250288073 894 414414726 895 69047251 896 10249225 897 1328233 898 146158 899 13115 900 900 901 42 902 1 903 701408733 904 18919547090004155473789 905 18919547090003721979352 906 14010827013566890525791 907 9102106937130326986526 908 5468168240346697224649 909 3109010923215835660019 910 1693248702960312525673 911 889495296802800388803 912 452600284324493325236 913 223649107465043673448 914 107497317215282220000 915 50304820309977473143 916 22929632261354434638 917 10181136733348711974 918 4402688170843409389 919 1853394598151166451 920 759031218953617550 921 302149167851222781 922 116788286376414700 923 43778123788019197 924 15891822614872411 925 5577468167874793 926 1889020604325824 927 616101215896684 928 193036103485046 929 57944024538186 930 16611483115867 931 4531968103792 932 1171808693194 933 285787379302 934 65375467349 935 13934532636 936 2745487724 937 495199651 938 80784925 939 11737674 940 1488449 941 160216 942 14058 943 943 944 43 945 1 946 1134903170 947 72986615669983329020610 948 72986615669982627611877 949 54067068579978472138088 950 35147521489974750158736 951 21136694476407859632945 952 12034587539277532646419 953 6566419298930835421770 954 3457408375714999761751 955 1764159672754687236078 956 874664375951886847275 957 422064091627393522039 958 198414984162349848591 959 90917666947067628591 960 40612846637090155448 961 17683214375735720810 962 7502077642387008836 963 3099389471543599447 964 1245994873392432996 965 486963654438815446 966 184814486587592665 967 68026200211177965 968 24248076423158768 969 8356253808286357 970 2778785640411564 971 889765036085740 972 273663820189056 973 80627716704010 974 22683692165824 975 6072209049957 976 1540240946165 977 368432252971 978 82644873669 979 17269406320 980 3334873684 981 589385960 982 94186309 983 13401384 984 1663710 985 175261 986 15045 987 987 988 44 989 1 990 1836311903 991 281804071876977280114339 992 281804071876976145211169 993 208817456206992816190559 994 135830840537010188578682 995 81763771957031716440594 996 46616250467056966281858 997 25479555990649106648913 998 13444968451371574002494 999 6878549152440738580724 1000 3421140776725738818973 1001 1656981103971051582895 1002 782316728019164735620 1003 360252636391771213581 1004 161837652229421364990 1005 70919985282353736399 1006 30307138645263580951 1007 12623924269527860141 1008 5121846627140851305 1009 2022457155597251858 1010 776462282204818862 1011 289498627766003416 1012 104684141178410751 1013 36657940967232786 1014 12409864544074018 1015 4053610735787661 1016 1274825095376097 1017 385060059290357 1018 111396239101301 1019 30768522397291 1020 8084830231467 1021 2012621181510 1022 472380235345 1023 103947982374 1024 21303108705 1025 4033702385 1026 698828701 1027 109442741 1028 15256432 1029 1855048 1030 191338 1031 16077 1032 1032 1033 45 1034 1 1035 2971215073 1036 1088944286345042653883689 1037 1088944286345040817571786 1038 807140214468063537457447 1039 525336142591087392246278 1040 316518686384094576055719 1041 180687845847084387477037 1042 98924073890052671036443 1043 52307823422995704754585 1044 26828267432346598105672 1045 13383298980975024103178 1046 6504749828534285522454 1047 3083609051808546703481 1048 1426627947837495120586 1049 644311219818330384966 1050 284058583426559171385 1051 122220931197137806395 1052 51300945914784069996 1053 20993807269520489045 1054 8369882999992628904 1055 3248036372851777599 1056 1225579217254525741 1057 449116935049706879 1058 159618307283703463 1059 54934166105292712 1060 18276225138059926 1061 5866360593985908 1062 1812749858198247 1063 537924762822150 1064 152864703531793 1065 41468464430492 1066 10699942033201 1067 2615111801734 1068 602490620224 1069 130110384879 1070 26162402505 1071 4859293800 1072 825591415 1073 126762714 1074 17319973 1075 2063541 1076 208493 1077 17155 1078 1078 1079 46 1080 1 1081 4807526976 1082 4211166331892264700339788 1083 4211166331892261729124715 1084 3122222045547219075241026 1085 2033277759202178257669240 1086 1226137544734114720211793 1087 700801402143027327965515 1088 384282715758932751909796 1089 203594869911848364432759 1090 104670796021795693396316 1091 52362972598799988641731 1092 25534705166453390536059 1093 12151406185478366432881 1094 5646656356944080910427 1095 2563047305135534206946 1096 1136419357298039086360 1097 492108137479708701394 1098 208049554053149530009 1099 85828622856011723614 1100 34527676941227653618 1101 13533869671707164573 1102 5163986671714535669 1103 1915950298862758070 1104 690371081608232329 1105 241254146558525450 1106 81635839274821987 1107 26701673169529275 1108 8425448031469349 1109 2559087437483441 1110 746337579285194 1111 208412816463044 1112 55548112931251 1113 14079648500759 1114 3379706467558 1115 764594665824 1116 162104045600 1117 31993660721 1118 5831258216 1119 971964416 1120 146373001 1121 19610287 1122 2290314 1123 226773 1124 18280 1125 1125 1126 47 1127 1 1128 7778742049 1129 16297557183847728817523517 1130 16297557183847724009996541 1131 12086390851955459309656753 1132 7875224520063197580532038 1133 4753002474515978505291012 1134 2719724715313800247621772 1135 1493587170579685527409979 1136 792785768436658199444464 1137 408503052677725447534668 1138 204908182765877083101909 1139 100237386744081389705593 1140 47874414145281401063862 1141 22339708978828010527803 1142 10188302793349644094922 1143 4541646436405563184495 1144 1978599131270028977549 1145 842179773971989891189 1146 350071636492281189795 1147 142022082439131659786 1148 56193459583119936172 1149 21665782641892282554 1150 8131912970185117981 1151 2967926298470582312 1152 1051975999607824242 1153 361604917999591913 1154 120350771441066463 1155 38714932166244476 1156 12013258996715201 1157 3587810965245852 1158 1028723527762411 1159 282385948477217 1160 73973132014173 1161 18425019082922 1162 4345370582163 1163 965664114605 1164 201069448781 1165 38965403181 1166 6971742460 1167 1140484244 1168 168519828 1169 22146827 1170 2536540 1171 246226 1172 19453 1173 1173 1174 48 1175 1 1176 12586269025 1177 63117825984464213794339115 1178 63117825984464206015597066 1179 46820268800616477198073549 1180 30522711616768753188077008 1181 18436320764813293878420255 1182 10561096244750096297888217 1183 5808093770234117792597205 1184 3088369054920317544975433 1185 1594781884340632017565454 1186 801996115903973818120990 1187 393493063226248370586322 1188 188584880460371287484413 1189 88347493716289897778820 1190 40473079571008496714958 1191 18133370592180486187155 1192 7945067798830842092233 1193 3403421362425278907738 1194 1424822231155249930189 1195 582642457183260039000 1196 232570820690978849205 1197 90548738251847189419 1198 34355278668727253247 1199 12689496026834970693 1200 4557583056649852712 1201 1589656758179270400 1202 537680758571446158 1203 176075840571854245 1204 55725069130787782 1205 17010136964543306 1206 4996877967828105 1207 1409067002582253 1208 380343474819842 1209 97957526342625 1210 23984394328452 1211 5559375245530 1212 1214004663367 1213 248340548762 1214 47271099981 1215 8305696800 1216 1333954340 1217 193470096 1218 24950268 1219 2803441 1220 266901 1221 20675 1222 1222 1223 49 1224 1 1225 20365011074 1226 244612055167672354976284022 1227 244612055167672342390014997 1228 181494229183208128595675882 1229 118376403198743922580078816 1230 71556134398127445382005267 1231 41033422781358692193928259 1232 22597102016545398315508004 1233 12036005771795302017619787 1234 6227912001561184225022582 1235 3139542946640866680047149 1236 1544761062300234662481695 1237 742764946396260844360705 1238 349271883170012473774383 1239 160687002709641186289970 1240 72339508993351288511150 1241 31866429422342791796192 1242 13733058830162305609037 1243 5787991031331463516804 1244 2384569668906184609066 1245 959747437750934678877 1246 377104980567674639877 1247 144534159876695790672 1248 53985421624848601253 1249 19630142956121348006 1250 6940646929286377313 1251 2383063872636524601 1252 793407114457254201 1253 255726355885808043 1254 79650515313953798 1255 23925446183166016 1256 6915309218622710 1257 1918431250794605 1258 509364248212352 1259 129020773392510 1260 31063247049885 1261 7078852721433 1262 1519477475903 1263 305472812536 1264 57132263774 1265 9861163793 1266 1555466993 1267 221512653 1268 28042557 1269 3092289 1270 288848 1271 21947 1272 1272 1273 50 1274 1