0 0 1 1 2 0 3 1 4 1 5 0 6 2 7 2 8 1 9 0 10 3 11 5 12 3 13 1 14 0 15 5 16 12 17 9 18 4 19 1 20 0 21 8 22 31 23 26 24 14 25 5 26 1 27 0 28 13 29 85 30 77 31 46 32 20 33 6 34 1 35 0 36 21 37 248 38 235 39 150 40 73 41 27 42 7 43 1 44 0 45 34 46 762 47 741 48 493 49 258 50 108 51 35 52 8 53 1 54 0 55 55 56 2440 57 2406 58 1644 59 903 60 410 61 152 62 44 63 9 64 1 65 0 66 89 67 8064 68 8009 69 5569 70 3163 71 1519 72 616 73 206 74 54 75 10 76 1 77 0 78 144 79 27300 80 27211 81 19147 82 11138 83 5569 84 2406 85 887 86 271 87 65 88 11 89 1 90 0 91 233 92 94150 93 94006 94 66706 95 39495 96 20348 97 9210 98 3641 99 1235 100 348 101 77 102 12 103 1 104 0 105 377 106 329462 107 329229 108 235079 109 141073 110 74367 111 34872 112 14524 113 5314 114 1673 115 438 116 90 117 13 118 1 119 0 120 610 121 1166512 122 1166135 123 836673 124 507444 125 272365 126 131292 127 56925 128 22053 129 7529 130 2215 131 542 132 104 133 14 134 1 135 0 136 987 137 4170414 138 4169804 139 3003292 140 1837157 141 1000484 142 493040 143 220675 144 89383 145 32458 146 10405 147 2876 148 661 149 119 150 15 151 1 152 0 153 1597 154 15031771 155 15030784 156 10860370 157 6690566 158 3687274 159 1850117 160 849633 161 356593 162 135918 163 46535 164 14077 165 3672 166 796 167 135 168 16 169 1 170 0 171 2584 172 54559855 173 54558258 174 39526487 175 24495703 176 13635333 177 6944767 178 3257493 179 1407376 180 557743 181 201150 182 65232 183 18697 184 4620 185 948 186 152 187 17 188 1 189 0 190 4181 191 199236416 192 199233832 193 144673977 194 90115719 195 50589232 196 26093529 197 12458196 198 5513429 199 2255936 200 848560 201 290817 202 89667 203 24435 204 5738 205 1118 206 170 207 18 208 1 209 0 210 6765 211 731434971 212 731430790 213 532194374 214 332960542 215 188286565 216 98170846 217 47581614 218 21488085 219 9029889 220 3516460 221 1260524 222 411964 223 121147 224 31480 225 7045 226 1307 227 189 228 19 229 1 230 0 231 10946 232 2697934577 233 2697927812 234 1966492841 235 1235062051 236 702867677 237 369907135 238 181620570 239 83449724 240 35868110 241 14380025 242 5350136 243 1833676 244 573152 245 161188 246 40041 247 8561 248 1516 249 209 250 20 251 1 252 0 253 17711 254 9993489968 255 9993479022 256 7295544445 257 4597616633 258 2631123792 259 1396061741 260 693194064 261 323286929 262 141666359 263 58216635 264 22348525 265 7968500 266 2618364 267 784688 268 211536 269 50348 270 10307 271 1746 272 230 273 21 274 1 275 0 276 28657 277 37157691565 278 37157673854 279 27164183886 280 17170704864 281 9875160419 282 5277543786 283 2646419994 284 1250358253 285 557164189 286 233877260 287 92210901 288 33994266 289 11645741 290 3677241 291 1058877 292 274189 293 62653 294 12305 295 1998 296 252 297 22 298 1 299 0 300 46368 301 138633745173 302 138633716516 303 101476024951 304 64318351097 305 37154167211 306 19983462347 307 10108301928 308 4830758142 309 2184338148 310 933979895 311 376815706 312 142938446 313 50727545 314 16733279 315 5087538 316 1410297 317 351420 318 77231 319 14578 320 2273 321 275 322 23 323 1 324 0 325 75025 326 518851050388 327 518851004020 328 380217258847 329 241583542331 330 140107517380 331 75789166283 332 38634999072 333 18651536725 334 8543234797 335 3712476655 336 1528138507 337 594158612 338 217342906 339 74404460 340 23676915 341 6943636 342 1856098 343 445801 344 94381 345 17150 346 2572 347 299 348 24 349 1 350 0 351 121393 352 1947388942885 353 1947388867860 354 1428537817472 355 909686813452 356 529469554605 357 287886012274 358 147778494894 359 71989328611 360 33354329539 361 14702792814 362 6159558017 363 2447081362 364 918942855 365 324784243 366 107441337 367 33036877 368 9359962 369 2416326 370 560228 371 114427 372 20046 373 2896 374 324 375 25 376 1 377 0 378 196418 379 7328186394725 380 7328186273332 381 5380797330447 382 3433408462587 383 2004870645115 384 1095183831663 385 565714277058 386 277828264784 387 130049769890 388 58060441279 389 24706111740 390 10003318926 391 3843760909 392 1396679547 393 477736692 394 152952449 395 45511112 396 12474235 397 3114273 398 697947 399 137719 400 23292 401 3246 402 350 403 26 404 1 405 0 406 317811 407 27642928409762 408 27642928213344 409 20314741818619 410 12986555545287 411 7605758214840 412 4172349752253 413 2167479107138 414 1072295275475 415 506580998417 416 228752733633 417 98702963743 418 40642522464 419 15936410724 420 5933091798 421 2089330889 422 692651342 423 214914650 424 61962201 425 16451089 426 3976854 427 862581 428 164634 429 26915 430 3623 431 377 432 27 433 1 434 0 435 514229 436 104504665720491 437 104504665402680 438 76861736992918 439 49218808779574 440 28904066960955 441 15917511415668 442 8311753200828 443 4139403448575 444 1971924341437 445 899629065962 446 393048067545 447 164295333912 448 65592370169 449 24949847705 450 9013436981 451 3080345183 452 991014294 453 298362952 454 83448302 455 21486101 456 5035012 457 1058158 458 195577 459 30943 460 4028 461 405 462 28 463 1 464 0 465 832040 466 395895545880613 467 395895545366384 468 291390879645893 469 186886214243213 470 110024477250295 471 60805668470721 472 31901601509766 473 15984090094098 474 7672336893270 475 3532933444695 476 1561009103258 477 661380037296 478 268331969751 479 104036635839 480 38444265670 481 13494417965 482 4480980984 483 1400635801 484 409621507 485 111258555 486 27810253 487 6324152 488 1289140 489 230982 490 35405 491 4462 492 434 493 29 494 1 495 0 496 1346269 497 1502642428252472 498 1502642427420432 499 1106746881539819 500 710851336173435 501 419460456527542 502 232574242284329 503 122549765034034 504 61744096563313 505 29842495053547 506 13858404959449 507 6186068066179 508 2653134621484 509 1092125518226 510 430745480930 511 162413511179 512 58376875340 513 19932609670 514 6438191705 515 1957210721 516 556574920 517 146953413 518 35694858 519 7884605 520 1560453 521 271313 522 40331 523 4926 524 464 525 30 526 1 527 0 528 2178309 529 5713524476225389 530 5713524474879120 531 4210882046626648 532 2708239619206216 533 1601492737666397 534 890641401492962 535 471180944965420 536 238606702681091 537 116056937647057 538 54312841083744 539 24470346030197 540 10611941070748 541 4425873004569 542 1772738383085 543 680612864859 544 249867383929 545 87453872750 546 29076997410 547 9144387740 548 2706196035 549 748985314 550 192410394 551 45456981 552 9762123 553 1877518 554 317065 555 45752 556 5421 557 495 558 31 559 1 560 0 561 3524578 562 21760802943704770 563 21760802941526461 564 16047278465301072 565 10333753990421952 566 6122871943795304 567 3414632324589088 568 1813139586922691 569 922498185429729 570 451317240464309 571 212710537783218 572 96653600136161 573 42340759052417 574 17870413022220 575 7258471951472 576 2832598946903 577 1059860563818 578 379247698959 579 129380315030 580 41926442280 581 12849444870 582 3705057130 583 998861095 584 249875781 585 57465387 586 12008406 587 2246283 588 368765 589 51700 590 5948 591 527 592 32 593 1 594 0 595 5702887 596 83008392296978357 597 83008392293453779 598 61247589349749009 599 39486786408222548 600 23439507942921476 601 13105753952499524 602 6982882008704220 603 3568249684115132 604 1755110097192441 605 832611911762712 606 381294671298403 607 168584133515185 608 71930533379024 609 29589774326607 610 11719361304387 611 4460889352915 612 1628290406012 613 568429842194 614 189182143235 615 59801828205 616 17875385925 617 5025941055 618 1320883925 619 322022830 620 72147049 621 14681662 622 2673256 623 426973 624 58208 625 6508 626 560 627 33 628 1 629 0 630 9227465 631 317105325652926237 632 317105325647223350 633 234096933350244993 634 151088541056791214 635 89840951707042205 636 50354165298819657 637 26914657355898181 638 13808903403398657 639 6826021394694437 640 3257771710579305 641 1502661613386864 642 670049701624152 643 288755030325749 644 120170896810564 645 48240363431540 646 18650589104933 647 6931227800546 648 2470338447631 649 842048041619 650 273618199425 651 84436056190 652 24634227985 653 6758842060 654 1732901005 655 412017080 656 89994250 657 17847201 658 3165539 659 492283 660 65310 661 7102 662 594 663 34 664 1 665 0 666 14930352 667 1213057760099635358 668 1213057760090407893 669 895952434437481656 670 578847108790258306 671 344750175440013313 672 193661634383222099 673 103820682676179894 674 53466517377360237 675 26551860021462056 676 12742956618063399 677 5916935223368962 678 2659163512789657 679 1156501899402793 680 486452197778641 681 197697167452892 682 77526270642328 683 29285907210788 684 10635318105855 685 3704090305309 686 1233751857678 687 391703816059 688 118085616634 689 33649560444 690 9015332459 691 2256490399 692 523589394 693 111572314 694 21578064 695 3730863 696 565324 697 73041 698 7731 699 629 700 35 701 1 702 0 703 24157817 704 4646448580659862857 705 4646448580644932505 706 3433390820545297147 707 2220333060454889254 708 1324380626017407598 709 745533517227149292 710 400783341787135979 711 207121707403913880 712 103301024727733986 713 49834507350373749 714 23282647328911693 715 10539690710848294 716 4622755487479332 717 1963591974689675 718 807090075286882 719 320637877508241 720 122940710055349 721 45414439413021 722 16128532202233 723 5493214096378 724 1789123791069 725 555371933391 726 163668117332 727 45582500698 728 11932940254 729 2917607795 730 661117396 731 137528002 732 25955688 733 4377624 734 646761 735 81437 736 8396 737 665 738 36 739 1 740 0 741 39088169 742 17819304726619951707 743 17819304726595793890 744 13172856145935931033 745 8526407565290998528 746 5093016744745701381 747 2872683684290812127 748 1548303058273404529 749 802769541046255237 750 401986199259119258 751 194864491855205378 752 91563467127471392 753 41728959777097643 754 18446312448185950 755 7906621737337656 756 3283866249858324 757 1320274275168649 758 513184199881767 759 192546322373526 760 69605612318177 761 24191172905156 762 8062640702923 763 2569426606545 764 780302815476 765 224930882085 766 61262764753 767 15680264055 768 3747323801 769 829716006 770 168598610 771 31070608 772 5114920 773 737296 774 90535 775 9098 776 702 777 37 778 1 779 0 780 63245986 781 68416557631901556928 782 68416557631862468759 783 50597252905242517052 784 32777948178646723162 785 19605092032710792129 786 11078684467419793601 787 5985667722674092220 788 3112984038383280093 789 1564680980109875564 790 761911439063620327 791 359925239804501069 792 165060747949295691 793 73497280821824299 794 31768321044726656 795 13322008596540706 796 5415386859203050 797 2131520609344726 798 811246334176077 799 298062134294310 800 105515811920784 801 35910199602607 802 11719026697451 803 3656385994528 804 1086959387983 805 306656572507 806 81725690422 807 20462925669 808 4782661614 809 1035337813 810 205621807 811 37023197 812 5952589 813 837669 814 100373 815 9838 816 740 817 38 818 1 819 0 820 102334155 821 262969725145528210035 822 262969725145464964049 823 194553167513563407121 824 126136609881700938362 825 75539356976458421310 826 42761408797811698148 827 23156316765100906019 828 12077632297681112418 829 6091964575007020198 830 2978980536623740105 831 1414299556513864541 832 652388117450244214 833 292462877645743145 834 127402129696447454 835 53904848874623155 836 22136527829896499 837 8814519233355793 838 3399132374152743 839 1267611764808017 840 456365430631940 841 158303296337630 842 52787484416846 843 16877284814239 844 5158258116788 845 1501872122260 846 414912734277 847 108256161770 848 26530471348 849 6067545679 850 1284884065 851 249546252 852 43924445 853 6901248 854 948659 855 110990 856 10617 857 779 858 39 859 1 860 0 861 165580141 862 1011811654507405567353 863 1011811654507303233198 864 748841929361775023163 865 485872204216310059114 866 291319036702746651993 867 165182426821045713631 868 89643069844587292321 869 46881661046775594173 870 23725344281674688154 871 11647711983993575736 872 5555747408986555538 873 2576766872362815433 874 1162467315848950892 875 510079198398706678 876 217616320752963533 877 90214191056516079 878 36309342181892924 879 14172814351996425 880 5358295118640632 881 1959162744487889 882 691550979679872 883 235185549047932 884 76882252710302 885 24094768293456 886 7217483479217 887 2059225362429 888 557353240169 889 142440505892 890 34184344122 891 7653872774 892 1586327095 893 301443030 894 51896778 895 7972333 896 1071085 897 122426 898 11436 899 819 900 40 901 1 902 0 903 267914296 904 3896908421929425886208 905 3896908421929260306067 906 2885096767421854738714 907 1873285112914551505516 908 1124443183552776482353 909 638570979336466423239 910 347251942633719771246 911 182069515812674057615 912 92426445968086765294 913 45544784921311171121 914 21819440639636482967 915 10171728655642907231 916 4615981246656351693 917 2039214374293536260 918 876747058444585368 919 366667860045878690 920 149051539292915157 921 58837348236399078 922 22528006054506154 923 8355191702509729 924 2996896583869097 925 1037733839381208 926 346182859701336 927 110997310653404 928 34115057943102 929 10020289649646 930 2802806170429 931 743580808000 932 186227567831 933 43787061939 934 9602717817 935 1948845043 936 362517948 937 61074918 938 9178140 939 1205807 940 134722 941 12296 942 860 943 41 944 1 945 0 946 433494437 947 15022638668074729587581 948 15022638668074461673285 949 11125730246145035787077 950 7228821824215775481010 951 4343725056793920742296 952 2470439943879369236780 953 1345996760326592754427 954 707425780990126331188 955 360173838356406559942 956 178104322543732502327 957 85677876575645737033 958 40133091654334565912 959 18313651014698082945 960 8141922359055175714 961 3525941112398824021 962 1486726738105287761 963 609979679660702393 964 243311819614823703 965 94260280321908546 966 35422932085509468 967 12894926031003314 968 4539734328493585 969 1542837744624488 970 505103905243280 971 158921045541944 972 47923734888540 973 13808676945438 974 3788387295792 975 985581125363 976 242000317363 977 55772749532 978 11985687593 979 2382969776 980 434124733 981 71606785 982 10531867 983 1353727 984 147920 985 13198 986 902 987 42 988 1 989 0 990 701408733 991 57963977001908599433029 992 57963977001908165938592 993 42941338333833436351011 994 27918699665758974677726 995 16792969419613938890649 996 9564147595398163409639 997 5220422538604242667343 998 2749982594724873430563 999 1403985834398280676136 1000 696560053408154344948 1001 336386215051747785006 1002 158281892508015282679 1003 72604015932369545646 1004 32470924278034979734 1005 14157273263336896789 1006 6015350904281721075 1007 2489409791882897054 1008 1002683053777609293 1009 392703374116906900 1010 149391554502083197 1011 55131274180174651 1012 19708342094665183 1013 6813416063661869 1014 2273681735168284 1015 730843990543796 1016 225740085300516 1017 66819039758572 1018 18895304870032 1019 5086627924594 1020 1298240628802 1021 312659503439 1022 70659186076 1023 14886436544 1024 2900748951 1025 517779175 1026 83654442 1027 12047657 1028 1515790 1029 162063 1030 14143 1031 945 1032 43 1033 1 1034 0 1035 1134903170 1036 223840094875068680681310 1037 223840094875067979272577 1038 165876117873159379839548 1039 107912140871251213900956 1040 64970802537417777549945 1041 37052102871658802872219 1042 20259133452044863981570 1043 10694985856646700571931 1044 5474563318042457904588 1045 2724580723317584474025 1046 1320594888919303797889 1047 624034835511149452941 1048 287648620459401667935 1049 129366727951386385256 1050 56762712019016839610 1051 24291787740981859876 1052 10134514477644963087 1053 4119163573363242012 1054 1629753781480344958 1055 627070727702735665 1056 234367353585828765 1057 84975799083745568 1058 29844524903570917 1059 10136182808905734 1060 3322766745243865 1061 1049085010075581 1062 318241019531785 1063 92500934231269 1064 25681894472697 1065 6786589602665 1066 1699961678071 1067 401721049269 1068 89061545830 1069 18402359754 1070 3515923210 1071 615174259 1072 97395084 1073 13740642 1074 1692985 1075 177195 1076 15132 1077 989 1078 44 1079 1 1080 0 1081 1836311903 1082 865104191469973973202379 1083 865104191469972838299209 1084 641264096594904157617899 1085 417424001719836178345322 1086 251547883846676798505774 1087 143635742975425584604818 1088 78664940438007807054873 1089 41612837566349004182654 1090 21353704114304140201084 1091 10658718257657439629153 1092 5184154939614981724565 1093 2459574216297397250540 1094 1138979327378093452651 1095 514944491866943999710 1096 227295871407542331775 1097 97929143456155946519 1098 41166431437139106909 1099 16874643696157247033 1100 6740129218512283946 1101 2620965645149041934 1102 991211863668696976 1103 364141135965961311 1104 129773782380132546 1105 44797983296386978 1106 14953458392816061 1107 4817275583910327 1108 1494508838666462 1109 445423828590881 1110 127182809059096 1111 34681874827827 1112 8999980355130 1113 2213390752465 1114 513429074394 1115 111708025125 1116 22646479295 1117 4244119541 1118 728196331 1119 113022072 1120 15626988 1121 1886346 1122 193361 1123 16166 1124 1034 1125 45 1126 1 1127 0 1128 2971215073 1129 3346062140422290727137409 1130 3346062140422288890825506 1131 2480957948952314917623127 1132 1615853757482342079323918 1133 974589660887437921706019 1134 557165659167601743360697 1135 305617775320924944854923 1136 161982032345499360250105 1137 83317091907491553195232 1138 41704254341142549012578 1139 20350550226838408811494 1140 9691831969180969182341 1141 4507677029565987457776 1142 2048102813268590207236 1143 909123485890496754585 1144 394178994023552754875 1145 166883122616010423100 1146 68953979159854476581 1147 27787547722715369672 1148 10912904026558122639 1149 4172774808045838693 1150 1551809162896796759 1151 560597299228099783 1152 196456163262138472 1153 66682380882005926 1154 21884397585618948 1155 6930939192802887 1156 2113663608892560 1157 619154770226098 1158 173730941635217 1159 46548132576121 1160 11866257748294 1161 2866277393164 1162 652886640699 1163 139457566305 1164 27749541180 1165 5103061885 1166 858942344 1167 130746013 1168 17723941 1169 2096953 1170 210607 1171 17246 1172 1080 1173 46 1174 1 1175 0 1176 4807526976 1177 12951495043425438090386108 1178 12951495043425435119171035 1179 9605432903003144392033626 1180 6259370762580855501208120 1181 3778412813628540583584993 1182 2162559056146198504261075 1183 1187969395258760582555056 1184 630803736091158839194359 1185 325185960770233894339436 1186 163203928424734534089331 1187 79886836517242980894099 1188 38182582176100431881521 1189 17832031949262023070027 1190 8140199980081053887686 1191 3632522950515066429910 1192 1584420137246476222674 1193 675296651355979468089 1194 281117657332426713214 1195 114234534716416290114 1196 45280555556561813533 1197 17493007833846443861 1198 6580103807288321222 1199 2407328999242482529 1200 855519836345685770 1201 294922537117585987 1202 98466373855447515 1203 31783992973441589 1204 9899595387822641 1205 2968656195019754 1206 854992586127194 1207 235837815901096 1208 62106874265879 1209 15558741689758 1210 3692483941464 1211 826206548300 1212 173319907601 1213 33862341296 1214 6112800116 1215 1009738231 1216 150795887 1217 20049874 1218 2325933 1219 228980 1220 18373 1221 1127 1222 47 1223 1 1224 0 1225 7778742049 1226 50166330941038775703953007 1227 50166330941038770896426031 1228 37214835897613332806039923 1229 24263340854187897686868888 1230 14657907951184753294835262 1231 8398537188603897793627142 1232 4620124374975357210042149 1233 2457565318829158705781074 1234 1269595923570398123226018 1235 638792187479239284031659 1236 313606226709005389692223 1237 150402298284270855602892 1238 70515461767027874708793 1239 32332879590927442827272 1240 14500847641665419757245 1241 6360647661584365869559 1242 2728124711069299439649 1243 1143704573822823216975 1244 468407922466843748886 1245 187290265134417035672 1246 73055730418000745558 1247 27775174861438932025 1248 10282167027592488164 1249 3702063220304166942 1250 1294734221061684413 1251 439214384715998643 1252 144291847598412656 1253 45825473742965141 1254 14041480769523552 1255 4141885381700911 1256 1173229186681157 1257 318236600553963 1258 82398784652867 1259 20291910386988 1260 4733168697230 1261 1040684755766 1262 214478207466 1263 41158299865 1264 7295958569 1265 1183158453 1266 173420222 1267 22624335 1268 2574461 1269 248528 1270 19548 1271 1175 1272 48 1273 1 1274 0