0 1 1 1 2 1 3 1 4 5 5 1 6 1 7 13 8 9 9 1 10 1 11 25 12 41 13 13 14 1 15 1 16 41 17 129 18 85 19 17 20 1 21 1 22 61 23 321 24 377 25 145 26 21 27 1 28 1 29 85 30 681 31 1289 32 833 33 221 34 25 35 1 36 1 37 113 38 1289 39 3653 40 3649 41 1561 42 313 43 29 44 1 45 1 46 145 47 2241 48 8989 49 13073 50 8361 51 2625 52 421 53 33 54 1 55 1 56 181 57 3649 58 19825 59 40081 60 36365 61 16641 62 4089 63 545 64 37 65 1 66 1 67 221 68 5641 69 40081 70 108545 71 134245 72 85305 73 29961 74 6017 75 685 76 41 77 1 78 1 79 265 80 8361 81 75517 82 265729 83 433905 84 369305 85 177045 86 50049 87 8473 88 841 89 45 90 1 91 1 92 313 93 11969 94 134245 95 598417 96 1256465 97 1392065 98 880685 99 335137 100 78889 101 11521 102 1013 103 49 104 1 105 1 106 365 107 16641 108 227305 109 1256465 110 3317445 111 4673345 112 3800305 113 1884961 114 590557 115 118721 116 15225 117 1201 118 53 119 1 120 1 121 421 122 22569 123 369305 124 2485825 125 8097453 126 14218905 127 14546705 128 9173505 129 3707509 130 982729 131 172041 132 19649 133 1405 134 57 135 1 136 1 137 481 138 29961 139 579125 140 4673345 141 18474633 142 39753273 143 50250765 144 39490049 145 20103025 146 6814249 147 1560549 148 241601 149 24857 150 1625 151 61 152 1 153 1 154 545 155 39041 156 880685 157 8405905 158 39753273 159 103274625 160 158819253 161 152951073 162 96220561 163 40754369 164 11847485 165 2383409 166 330409 167 30913 168 1861 169 65 170 1 171 1 172 613 173 50049 174 1303777 175 14546705 176 81270333 177 251595969 178 464387817 179 540279585 180 413442773 181 214828609 182 77500017 183 19665841 184 3522221 185 441729 186 37881 187 2113 188 69 189 1 190 1 191 685 192 63241 193 1884961 194 24331777 195 158819253 196 579168825 197 1267854873 198 1759885185 199 1616336765 200 1014889769 201 446304145 202 139703809 203 31388293 204 5060441 205 579081 206 45825 207 2381 208 73 209 1 210 1 211 761 212 78889 213 2668525 214 39490049 215 298199265 216 1267854873 217 3256957317 218 5334940545 219 5812626185 220 4354393801 221 2300409629 222 872893441 223 240673265 224 48442297 225 7095093 226 746241 227 54809 228 2665 229 77 230 1 231 1 232 841 233 97281 234 3707509 235 62390545 236 540279585 237 2653649025 238 7923848253 239 15167050785 240 19403906105 241 17152640321 242 10753517061 243 4876601009 244 1621925137 245 398796225 246 72616013 247 9737793 248 947241 249 64897 250 2965 251 81 252 1 253 1 254 925 255 118721 256 5064793 257 96220561 258 948062325 259 5334940545 260 18359266785 261 40704778785 262 60592003085 263 62596382081 264 46082942185 265 24680949041 266 9765268709 267 2883810113 268 638878193 269 106114625 270 13115773 271 1186369 272 76153 273 3281 274 85 275 1 276 1 277 1013 278 143529 279 6814249 280 145198913 281 1616336765 282 10343052825 283 40704778785 284 103706427393 285 178153920965 286 213252565321 287 182668423833 288 114375683009 289 53215656781 290 18618616249 291 4934985233 292 993696769 293 151620757 294 17372905 295 1468169 296 88641 297 3613 298 89 299 1 300 1 301 1105 302 172041 303 9041957 304 214828609 305 2684641785 306 19403906105 307 86716873725 308 252055236609 309 495998874593 310 682650581801 311 674851875285 312 489658242241 313 265280226953 314 108721541721 315 34016124973 316 8166636545 317 1505789553 318 212358985 319 22670725 320 1797441 321 102425 322 3961 323 93 324 1 325 1 326 1201 327 204609 328 11847485 329 312193553 330 4354393801 331 35330137025 332 178153920965 333 586889743905 334 1314016698401 335 2064947317889 336 2338787421261 337 1951212466609 338 1220435354425 339 580301276417 340 211939849045 341 59864549953 342 13120103057 343 2229491905 344 292164445 345 29189457 346 2179241 347 117569 348 4325 349 97 350 1 351 1 352 1301 353 241601 354 15345233 355 446304145 356 6911195501 357 62596382081 358 354071970265 359 1314016698401 360 3326741166725 361 5931412422529 362 7646224014049 363 7283926286641 364 5220495115997 365 2856092476225 366 1206226549225 367 396469547585 368 101925936373 369 20529927745 370 3233240945 371 395555537 372 37129037 373 2618881 374 134137 375 4705 376 101 377 1 378 1 379 1405 380 283401 381 19665841 382 628496897 383 10753517061 384 108167252025 385 682650581801 386 2838240338817 387 8079317057869 388 16248650965289 389 23697618246945 390 25615290838529 391 20896564339669 392 13058529727833 393 6325929820185 394 2397196917505 395 715097053725 396 168502295625 397 31375587985 398 4602162177 399 527810725 400 46710137 401 3121929 402 152193 403 5101 404 105 405 1 406 1 407 1513 408 330409 409 24957661 410 872893441 411 16429137361 412 182668423833 413 1279919346549 414 5931412422529 415 18885056428537 416 42612705597769 417 69925435608077 418 85275509086721 419 78706989441761 420 55818956905529 421 30796649047845 422 13348247055105 423 4578268733705 424 1248543693033 425 271309578045 426 46943003137 427 6440955121 428 695049433 429 58175189 430 3694209 431 171801 432 5513 433 109 434 1 435 1 436 1625 437 383041 438 31388293 439 1196924561 440 24680949041 441 302016962625 442 2338787421261 443 12023876986657 444 42612705597769 445 107347191941249 446 197194672920085 447 269902623450929 448 280307431594273 449 224299997320321 450 140059477112925 451 68954032430145 452 26980550851385 453 8438973867969 454 2117321780133 455 426577839057 456 68896982545 457 8877094337 458 904317037 459 71789409 460 4341801 461 193025 462 5941 463 113 464 1 465 1 466 1741 467 441729 468 39146185 469 1621925137 470 36503969061 471 489658242241 472 4173176558289 473 23697618246945 474 93065296937533 475 260543813797441 476 533285164334169 477 815272900198321 478 947976806209685 479 851399012552577 480 598318746037217 481 332538522833985 482 147430556426925 483 52481589415425 484 15067897531881 485 3497529199185 486 656419017477 487 99365842753 488 12064362225 489 1163673953 490 87841821 491 5071041 492 215929 493 6385 494 117 495 1 496 1 497 1861 498 506921 499 48442297 500 2173806145 501 53215656781 502 779594526361 503 7283926286641 504 45502030254593 505 197194672920085 506 610916200215241 507 1387226559025961 508 2358243122728129 509 3055999837011997 510 3065796686624825 511 2412395979060257 512 1505357362548737 513 751675396751845 514 302494131826281 515 98626554128025 516 26142331229505 517 5641568932845 518 990508528857 519 141039488273 520 16186729985 521 1482288821 522 106646281 523 5888521 524 240577 525 6845 526 121 527 1 528 1 529 1985 530 579081 531 59511829 532 2883810113 533 76541925481 534 1220435354425 535 12455603988461 536 85275509086721 537 406245192637777 538 1387226559025961 539 3480518973469125 540 6552204905872321 541 9422714414390009 542 10512455241722713 543 9219367921133597 544 6427269150511105 545 3595308677723617 546 1626023734694217 547 598081495249269 548 179666804231745 549 44190686315145 550 8904955165305 551 1468131923021 552 197282315777 553 21462603121 554 1870535785 555 128542501 556 6801089 557 267033 558 7321 559 125 560 1 561 1 562 2113 563 658689 564 72616013 565 3789356689 566 108721541721 567 1880753390593 568 20896564339669 569 156245621038881 570 815272900198321 571 3057236753252161 572 8443414161166173 573 17534423944871729 574 27873393043294921 575 34441804691444289 576 33521787490731877 577 25991659563764801 578 16209464357137953 579 8195643365216385 580 3381030024132717 581 1143593778271185 582 318188799587385 583 72949645000065 584 13780562423541 585 2140653163361 586 272262367121 587 28149447873 588 2340095869 589 153897073 590 7815849 591 295361 592 7813 593 129 594 1 595 1 596 2245 597 746241 598 88043969 599 4934985233 600 152631941021 601 2856092476225 602 34438743316681 603 280307431594273 604 1596599277225781 605 6552204905872321 606 19848915420382545 607 45308321651001521 608 79321148551544333 609 108145975850252801 610 116356718921844697 611 99928969289077825 612 69175175263888037 613 38917020105075585 614 17914163519447265 615 6783340321069905 616 2121256630823805 617 549206075985345 618 117843056783593 619 20941889768801 620 3074466656021 621 371098222145 622 36548814961 623 2904062449 624 183104493 625 8940161 626 325625 627 8321 628 133 629 1 630 1 631 2381 632 842249 633 106114625 634 6373401601 635 211939849045 636 4278048511801 637 55818956905529 638 493056718134145 639 3055999837011997 640 13680563328752681 641 45308321651001521 642 113298482073315329 643 217698278506411045 644 326340796061585497 645 386733690827821609 646 366485940838832897 647 280480443737756653 648 174827809500822345 649 89381627584964385 650 37697391926830593 651 13174519143904245 652 3827287423284345 653 925915872294425 654 186615439927937 655 31297149356221 656 4354500989801 657 500025187729 658 47011777025 659 3577050821 660 216588185 661 10181641 662 357889 663 8845 664 137 665 1 666 1 667 2521 668 947241 669 127178701 670 8166636545 671 291280485825 672 6325929820185 673 89070157349221 674 851399012552577 675 5725317599159785 676 27873393043294921 677 100609937775369981 678 274738209148561921 679 577524957781467857 680 948749584925712825 681 1234185215187333909 682 1286011828550830849 683 1084121251192378617 684 745778857519239785 685 421706584726671405 686 197202428180582913 687 76635448004226273 688 24840589975722585 689 6732637908060357 690 1527671538372225 691 290159704685321 692 46056248792841 693 6088348442461 694 666582405121 695 59944796145 696 4375311865 697 254801525 698 11548161 699 392217 700 9385 701 141 702 1 703 1 704 2665 705 1061761 706 151620757 707 10387323409 708 396469547585 709 9241603253505 710 140059477112925 711 1444888121447969 712 10512455241722713 713 55500139308246721 714 217698278506411045 715 647253432721564081 716 1483995132002718769 717 2663401037135674433 718 3791213892445982829 719 4329547032027650625 720 4006674738164575049 721 3030987219469437185 722 1888383038494338485 723 975091467850382673 724 419476929219862305 725 150959635451019393 726 45583730842102909 727 11571040346249313 728 2470866568011321 729 443586466649665 730 66813020691781 731 8411100666097 732 879822563089 733 75816037825 734 5316849805 735 298228865 736 13047849 737 428673 738 9941 739 145 740 1 741 1 742 2813 743 1186369 744 179861305 745 13120103057 746 534752607445 747 13348247055105 748 217220308282305 749 2412395979060257 750 18940335748972909 751 108145975850252801 752 459714107961041353 753 1483995132002718769 754 3700493639315972933 755 7234795815417701569 756 11235483572753317329 757 14019400249152942657 758 14197284855104916701 759 11771593265706723521 760 8052432236270744665 761 4574158343052828113 762 2169512126573877429 763 863001025298535297 764 288902926601894369 765 81589331684644449 766 19464572294259021 767 3923599811244673 768 667591158166249 769 95645361691505 770 11490977583397 771 1150545969985 772 95162147825 773 6421544065 774 347386557 775 14689089 776 467321 777 10513 778 149 779 1 780 1 781 2965 782 1321641 783 212358985 784 16463164225 785 715097053725 786 19073863045145 787 332538522833985 788 3966313256529921 789 33521787490731877 790 206482376223837001 791 948749584925712825 792 3316457434033106881 793 8970232353223635949 794 19052199454802607033 795 32190100727675415089 796 43761350039110851585 797 48352401113804333109 798 43806954894570455273 799 32795827996211988521 800 20424130116241366593 801 10641091030862068925 802 4660143848163879513 803 1721983008537982497 804 538410649217200129 805 142717361936022021 806 32100078290806665 807 6125198288977561 808 990185170709185 809 135236278032525 810 15535843407865 811 1491560803345 812 118595508225 813 7711275221 814 402823977 815 16480521 816 508225 817 11101 818 153 819 1 820 1 821 3121 822 1468169 823 249612805 824 20529927745 825 948532193753 826 26980550851385 827 502868697794525 828 6427269150511105 829 58339232568589249 830 386733690827821609 831 1916059529122973621 832 7234795815417701569 833 21171672197891407465 834 48724817858045813081 835 89329910005371197453 836 131955581594696793089 837 158637214941948137041 838 156595962085612928585 839 127920352401606571877 840 87063177396677721409 841 49660208205347665913 842 23856878884258909817 843 9692168624686040125 844 3340604559333629953 845 979130504510523361 846 244393929862920041 847 51973669799734549 848 9411918605728705 849 1448868573239945 850 189019196608153 851 20800710844525 852 1917971421185 853 146811989105 854 9210055049 855 465124549 856 18431041 857 551449 858 11705 859 157 860 1 861 1 862 3281 863 1626561 864 292164445 865 25450883345 866 1248543693033 867 37800717566273 868 751675396751845 869 10273391096237089 870 99928969289077825 871 711308148730832129 872 3791213892445982829 873 15426407003737736881 874 48724817858045813081 875 121210066804943671425 876 240533731866135708533 877 385095408183758079553 878 502419710692163379889 879 538924271301317121857 880 479026341947461717885 881 355266665307415369809 882 221164921352046545609 883 116165516313999621313 884 51702521846719301893 885 19567836037813959265 886 6314558836537699361 887 1740717582111859841 888 410339827566269581 889 82725309576604145 890 14250435177285945 891 2093334656696833 892 261351290279573 893 27596341933185 894 2447496684689 895 180599212225 896 10944160669 897 534906769 898 20549801 899 597057 900 12325 901 161 902 1 903 1 904 3445 905 1797441 906 340600625 907 31375587985 908 1631529095373 909 52481589415425 910 1111317778023353 911 16209464357137953 912 168612948663355621 913 1286011828550830849 914 7357626162379304385 915 32190100727675415089 916 109490419586806465597 917 293733710358893793729 918 629449455702738124233 919 1089618887377372884545 920 1538970127854641140053 921 1789299122206885302209 922 1726055481860430298193 923 1391133027965039868369 924 942486784715757604525 925 539600582537344279169 926 262252292999433884121 927 108603909620923653217 928 38437442974263294661 929 11652578441855567745 930 3030311505461311201 931 676451066002195825 932 129591333740102685 933 21281058718583873 934 2988810763035625 935 357718985217153 936 36299061664053 937 3100820307521 938 220845343089 939 12942272785 940 612825229 941 22846209 942 645113 943 12961 944 165 945 1 946 1 947 3613 948 1981449 949 395555537 950 38474834945 951 2117321780133 952 72239609939769 953 1626023734694217 954 25263074887360385 955 280480443737756653 956 2287525628180930089 957 14019400249152942657 958 65809907928007336961 959 240533731866135708533 960 694369081413633415257 961 1603243841366167489593 962 2993989196011368428289 963 4567285830356704736957 964 5742120737293369519433 965 5996828248668531353009 966 5239027908779624672769 967 3852538184056016992837 968 2397512484385887298681 969 1268590558201750897961 970 572989488521591875201 971 221640513367874091661 972 73610130453448492393 973 21028690719298560289 974 5173141652821372417 975 1096245836064052245 976 200009855448385433 977 31373017464377369 978 4220155682940417 979 484980267148125 980 47361908425353 981 3901975312529 982 268548427777 983 15235618021 984 699571641 985 25329929 986 695681 987 13613 988 169 989 1 990 1 991 3785 992 2179241 993 457713341 994 46943003137 995 2729791359153 996 98626554128025 997 2355733197701973 998 38917020105075585 999 460303333510031065 1000 4006674738164575049 1001 26252031769940004845 1002 131955581594696793089 1003 517193560532560855489 1004 1603243841366167489593 1005 3980084795965961529093 1006 8001035989283143418625 1007 13153923911808640610793 1008 17842588149138004133609 1009 20127244268485089653533 1010 19014888343931063144449 1011 15139150213413396160465 1012 10214101061074009065689 1013 5867807989178643390133 1014 2882172733469598065281 1015 1214608727562738029561 1016 440397640617979797385 1017 137683074852407297101 1018 37169485797428001281 1019 8671669432790370017 1020 1748417590899730553 1021 304422531707969125 1022 45694582661391873 1023 5896851467940105 1024 651648883704105 1025 61327253534589 1026 4878764742145 1027 324826290929 1028 17858115353 1029 795875861 1030 28010881 1031 748825 1032 14281 1033 173 1034 1 1035 1 1036 3961 1037 2391489 1038 527810725 1039 57000596369 1040 3497529199185 1041 133609462331073 1042 3381030024132717 1043 59290063767904545 1044 745778857519239785 1045 6915701017797120001 1046 48352401113804333109 1047 259749713692011443761 1048 1089618887377372884545 1049 3619870045170340302081 1050 9642641465118083682429 1051 20824104716955953041473 1052 36819195261943829644377 1053 53770521261359329972545 1054 65373789034233276428741 1055 66637705026765084273873 1056 57309839432226127686449 1057 41817403004003318583361 1058 26015752032538663824525 1059 13858597376999183325537 1060 6344332561891307436361 1061 2503512348055260609921 1062 853607938952248383829 1063 251936597738500359025 1064 64439313198589629729 1065 14290577765009652865 1066 2747190406466646173 1067 457326387039602817 1068 65801335681221945 1069 8159046922883265 1070 868226052618981 1071 78841030559249 1072 6063220834321 1073 390927011265 1074 20846526637 1075 902506913 1076 30899241 1077 804609 1078 14965 1079 177 1080 1 1081 1 1082 4141 1083 2618881 1084 606639529 1085 68896982545 1086 4454628476805 1087 179666804231745 1088 4809429031090353 1089 89381627584964385 1090 1193641560393864605 1091 11771593265706723521 1092 87669346579975861561 1093 502419710692163379889 1094 2251514999031597280501 1095 8001035989283143418625 1096 22825924943586514532289 1097 52853228343044936894529 1098 100304632503612626984973 1099 157392783289498471414401 1100 205818152096910170963145 1101 225885627529471092492113 1102 209387038274445694447973 1103 164861382990041565101249 1104 110806813686435908272337 1105 63854980589626470088545 1106 31669988728679848174461 1107 13561817585877199009601 1108 5027450562796758167641 1109 1616706489055934255089 1110 451655667950566623445 1111 109711635839353997185 1112 23177381083482822625 1113 4256366678764775553 1114 678641527939830765 1115 93746463846312705 1116 11184831450420201 1117 1147585831377041 1118 100668723849029 1119 7492104941377 1120 468239991025 1121 24240611233 1122 1020274013 1123 34005441 1124 863097 1125 15665 1126 181 1127 1 1128 1 1129 4325 1130 2862121 1131 695049433 1132 82913343041 1133 5641568932845 1134 239903624366745 1135 6783340321069905 1136 133400413679081985 1137 1888383038494338485 1138 19772988122558702281 1139 156595962085612928585 1140 955715888269839848641 1141 4567285830356704736957 1142 17330148267714850440249 1143 52853228343044936894529 1144 130973644638922564173825 1145 266292543511521410721669 1146 448111992256946539740777 1147 629038929120942200990649 1148 741826524466038914184513 1149 739640163043597585393805 1150 627051230328391157600473 1151 454308165399455364053809 1152 282557489542945636163073 1153 151449992972562823717461 1154 70193385403724338486025 1155 28210533109246967978281 1156 9853825895927030383553 1157 2996621193032906591581 1158 794338657694234594425 1159 183648780720772032545 1160 37031591398614032385 1161 6508195755703812645 1162 995474931539956905 1163 132217643424004761 1164 15198941441387585 1165 1505420884101421 1166 127713274680089 1167 9207450534673 1168 558307635713 1169 28083284725 1170 1150027593 1171 37340169 1172 924353 1173 16381 1174 185 1175 1 1176 1 1177 4513 1178 3121929 1179 793950709 1180 99365842753 1181 7106217293385 1182 318188799587385 1183 9490098306210765 1184 197202428180582913 1185 2954578249211727665 1186 32795827996211988521 1187 275754453263019264933 1188 1789299122206885302209 1189 9103361685027990245593 1190 36819195261943829644377 1191 119832622033954836836349 1192 317241780630136241094657 1193 689784660561398585462721 1194 1242552205005085102403145 1195 1868927786242277043560277 1196 2363816443751602555222593 1197 2530128772364495659782249 1198 2304965156691455852075897 1199 1796400916424952426221613 1200 1203197543301130646660609 1201 695356045315643558926161 1202 347959256213385305465193 1203 151214148579231174904069 1204 57209987476590859209409 1205 18880762189892645812473 1206 5443337521681744659865 1207 1372172687496013484125 1208 302557549412667613185 1209 58339401126650980833 1210 9828483546498297225 1211 1444377361553054901 1212 184705829428862273 1213 20483127179054729 1214 1960755997052601 1215 161035072652429 1216 11257151703553 1217 662837660529 1218 32420781737 1219 1292660325 1220 40914369 1221 988441 1222 17113 1223 189 1224 1 1225 1 1226 4705 1227 3399041 1228 904317037 1229 118609031569 1230 8904955165305 1231 419317958443905 1232 13174519143904245 1233 288870650661524769 1234 4574158343052828113 1235 53743653756459544001 1236 479026341947461717885 1237 3299498080158151739441 1238 17842588149138004133609 1239 76797690600945805848513 1240 266292543511521410721669 1241 751874920284981143173185 1242 1745319075862302066540609 1243 3359666797841277698956545 1244 5404985616172088539429005 1245 7318630159618237812765393 1246 8393972501898545210254425 1247 8201675219780657071569153 1248 6862422667788729220767509 1249 4939661657969614719759713 1250 3071429600635372683210161 1251 1655651147012495326979905 1252 776125608655926563276701 1253 317228814417776557063537 1254 113299248944253239264969 1255 35417996629578280344385 1256 9702423067180822781605 1257 2330731137447761565825 1258 491047705386258602529 1259 90695926327455074433 1260 14669716953106628781 1261 2074210197267821585 1262 255712131617022521 1263 27388436390531713 1264 2536537346124341 1265 201874209484193 1266 13695599622545 1267 783716039873 1268 37302822845 1269 1449108145 1270 44739241 1271 1055425 1272 17861 1273 193 1274 1 1275 1 1276 4901 1277 3694209 1278 1027188385 1279 141039488273 1280 11103947097341 1281 549206075985345 1282 18154539163583145 1283 419476929219862305 1284 7010414357595701141 1285 87063177396677721409 1286 821406528503346394161 1287 5996828248668531353009 1288 34415626826089780214125 1289 157392783289498471414401 1290 580518694381636300184505 1291 1745319075862302066540609 1292 4318185617347381737154821 1293 8867962331174090943697665 1294 15233926646210294478801345 1295 22045323993262457897848401 1296 27045905803020076598121693 1297 28292255492540992406275137 1298 25367101182644465948634825 1299 19585658438676188230123361 1300 13076117390069923456738165 1301 7576934722050827973274561 1302 3822800113575612228045649 1303 1684012080282598135980785 1304 649220350965499138583373 1305 219450050254546253510401 1306 65131683777501636337625 1307 16989321948376477300865 1308 3896633837317577048805 1309 785798072503676228481 1310 139243424896651828449 1311 21654403884743524241 1312 2949761933621924029 1313 350999923643244225 1314 36349701278913257 1315 3260306209228705 1316 251675182111573 1317 16584369526337 1318 923020616305 1319 42782785585 1320 1620351277 1321 48826241 1322 1125369 1323 18625 1324 197 1325 1