1 1 2 1 3 0 4 1 5 1 6 0 7 1 8 2 9 1 10 0 11 1 12 4 13 3 14 1 15 0 16 1 17 6 18 8 19 4 20 1 21 0 22 1 23 9 24 18 25 14 26 5 27 1 28 0 29 1 30 12 31 35 32 39 33 21 34 6 35 1 36 0 37 1 38 16 39 62 40 97 41 72 42 30 43 7 44 1 45 0 46 1 47 20 48 103 49 212 50 214 51 120 52 40 53 8 54 1 55 0 56 1 57 25 58 161 59 429 60 563 61 416 62 185 63 52 64 9 65 1 66 0 67 1 68 30 69 241 70 804 71 1344 72 1268 73 732 74 270 75 65 76 10 77 1 78 0 79 1 80 36 81 348 82 1427 83 2958 84 3499 85 2544 86 1203 87 378 88 80 89 11 90 1 91 0 92 1 93 42 94 487 95 2406 96 6086 97 8833 98 7949 99 4682 100 1867 101 511 102 96 103 12 104 1 105 0 106 1 107 49 108 664 109 3900 110 11820 111 20730 112 22668 113 16346 114 8056 115 2777 116 672 117 114 118 13 119 1 120 0 121 1 122 56 123 886 124 6094 125 21854 126 45625 127 59773 128 51901 129 31061 130 13138 131 3980 132 864 133 133 134 14 135 1 136 0 137 1 138 64 139 1159 140 9245 141 38713 142 95052 143 147228 144 151945 145 108692 146 55445 147 20503 148 5541 149 1089 150 154 151 15 152 1 153 0 154 1 155 72 156 1491 157 13645 158 66069 159 188638 160 341653 161 414116 162 349703 163 211891 164 93975 165 30846 166 7516 167 1350 168 176 169 16 170 1 171 0 172 1 173 81 174 1890 175 19682 176 109109 177 358822 178 752182 179 1059945 180 1044990 181 743088 182 389453 183 152596 184 44988 185 9981 186 1650 187 200 188 17 189 1 190 0 191 1 192 90 193 2364 194 27791 195 175019 196 657169 197 1580470 198 2565394 199 2924863 200 2415348 201 1478299 202 681428 203 238865 204 63890 205 13002 206 1991 207 225 208 18 209 1 210 0 211 1 212 100 213 2922 214 38530 215 273540 216 1163791 217 3185224 218 5907070 219 7722047 220 7339040 221 5192488 222 2783239 223 1143469 224 362396 225 88660 226 16667 227 2376 228 252 229 19 230 1 231 0 232 1 233 110 234 3574 235 52516 236 417672 237 1999495 238 6183637 239 13005279 240 19346165 241 20991721 242 17020341 243 10504028 244 4999864 245 1851050 246 534999 247 120570 248 21050 249 2808 250 280 251 20 252 1 253 0 254 1 255 121 256 4329 257 70521 258 624472 259 3343038 260 11606151 261 27498902 262 46229029 263 56861553 264 52432182 265 36943275 266 20176220 267 8626634 268 2904283 269 771213 270 161059 271 26251 272 3289 273 310 274 21 275 1 276 0 277 1 278 132 279 5198 280 93390 281 916038 282 5452829 283 21127675 284 56052155 285 105831924 286 146612710 287 152709107 288 121939535 289 75781243 290 37062573 291 14370166 292 4433566 293 1088451 294 211751 295 32354 296 3822 297 341 298 22 299 1 300 0 301 1 302 144 303 6192 304 122157 305 1320609 306 8696613 307 37405050 308 110506991 309 233008811 310 361446211 311 422668071 312 380006322 313 266807441 314 148051708 315 65485253 316 23210785 317 6605911 318 1507637 319 274460 320 39470 321 4410 322 374 323 23 324 1 325 0 326 1 327 156 328 7322 329 157945 330 1873896 331 13587910 332 64561161 333 211327231 334 495046641 335 855299399 336 1116703046 337 1123838933 338 885841162 339 553800942 340 277203559 341 111817329 342 36479925 343 9632248 344 2053317 345 351207 346 47692 347 5055 348 408 349 24 350 1 351 0 352 1 353 169 354 8600 355 202104 356 2620552 357 20834487 358 108866382 359 393002091 360 1017948120 361 1949299497 362 2827302880 363 3168283157 364 2787862737 365 1951513515 366 1097793806 367 499967091 368 185235717 369 55955938 370 13775457 371 2754433 372 444222 373 57143 374 5760 375 444 376 25 377 1 378 0 379 1 380 182 381 10039 382 256090 383 3615923 384 31396728 385 179684155 386 712326630 387 2031186319 388 4291731308 389 6883265229 390 8547632165 391 8353816693 392 6511874216 393 4091937187 394 2089712373 395 872329951 396 298681553 397 83974666 398 19359530 399 3644404 400 555966 401 67925 402 6528 403 481 404 26 405 1 406 0 407 1 408 196 409 11651 410 321628 411 4927965 412 46563312 413 290762751 414 1260881177 415 3942115307 416 9152560382 417 16163108315 418 22144509397 419 23927372236 420 20668104964 421 14430063887 422 8214319700 423 3837365411 424 1477617634 425 470066059 426 123563580 427 26779540 428 4762003 429 689130 430 80173 431 7361 432 520 433 27 434 1 435 0 436 1 437 210 438 13450 439 400567 440 6639493 441 68041054 442 461978659 443 2183476067 444 7457028087 445 18951522986 446 36706208439 447 55260123176 448 65735579434 449 62640607542 450 48359860685 451 30524334534 452 15864073161 453 6823781646 454 2437201878 455 723768881 456 178593857 457 36512856 458 6151428 459 846657 460 93998 461 8262 462 560 463 28 464 1 465 0 466 1 467 225 468 15450 469 495070 470 8850628 471 98068941 472 721658992 473 3705027759 474 13774178034 475 38182512974 476 80814659013 477 133188829780 478 173753182345 479 181916943905 480 154626015946 481 107711143056 482 61955631271 483 29596300518 484 11788895881 485 3924519665 486 1092475867 487 253961978 488 49131235 489 7863309 490 1031743 491 109546 492 9234 493 602 494 29 495 1 496 0 497 1 498 240 499 17665 500 607445 501 11681631 502 139551650 503 1109643254 504 6169083918 505 24885909121 506 74995707572 507 172870609803 508 310810391963 509 443079133769 510 507792236830 511 473329912016 512 362343773669 513 229607170694 514 121187922747 515 53524094575 516 19841915619 517 6183126522 518 1619414666 519 355792533 520 65314335 521 9954713 522 1247856 523 126938 524 10279 525 645 526 30 527 1 528 0 529 1 530 256 531 20110 532 740362 533 15275970 534 196226198 535 1681275261 536 10092371963 537 44043512380 538 143850260880 539 359984372056 540 703802522743 541 1092732858733 542 1366115316506 543 1391442087940 544 1166089962528 545 810658204183 546 470596962702 547 229290406423 548 94111546207 549 32613403795 550 9549722812 551 2361045413 552 491677299 553 85864125 554 12490317 555 1498738 556 146332 557 11400 558 690 559 31 560 1 561 0 562 1 563 272 564 22801 565 896657 566 19803834 567 272854810 568 2512561363 569 16240964556 570 76461184435 571 269877023945 572 731050070789 573 1549519595711 574 2612124582899 575 3550985199632 576 3938954542782 577 3601075061899 578 2736184763500 579 1739878888655 580 930990102042 581 420954390133 582 161299424967 583 52458167063 584 14483121703 585 3390277198 586 670939023 587 111720885 588 15542359 589 1788428 590 167857 591 12600 592 736 593 32 594 1 595 0 596 1 597 289 598 25753 599 1079581 600 25465914 601 375461896 602 3706772370 603 25735496224 604 130366379373 605 495927057697 606 1450138529008 607 3322898249534 608 6064467419457 609 8937957562908 610 10764302740551 611 10700838900218 612 8856213671436 613 6145811009240 614 3597017038024 615 1783718813496 616 751958202472 617 270076913539 618 82722339851 619 21600411965 620 4800278547 621 904938965 622 143980169 623 19191935 624 2121258 625 191683 626 13881 627 784 628 33 629 1 630 0 631 1 632 306 633 28983 634 1292574 635 32497699 636 511605805 637 5402827325 638 40194772913 639 218545555182 640 893770569473 641 2813879617526 642 6952202374007 643 13699419502799 644 21828949327786 645 28461040178113 646 30673645488639 647 27564118421124 648 20805175635077 649 13270611648201 650 7188460351106 651 3319319527569 652 1310067627312 653 442642658147 654 128090799368 655 31721577276 656 6708967023 657 1207412778 658 183911490 659 23528921 660 2501878 661 217949 662 15246 663 833 664 34 665 1 666 0 667 1 668 324 669 32508 670 1539546 671 41174075 672 690708240 673 7785852189 674 61929949838 675 360589766314 676 1581616104036 677 5348278955574 678 14212226321250 679 30160869065743 680 51823952026271 681 72955232718043 682 85005673203166 683 82701139612580 684 67685490981949 685 46895831750000 686 27648971271698 687 13929038746852 688 6014589596254 689 2230682559681 690 711335654184 691 195034068312 692 45924204844 693 9264257477 694 1594858515 695 232978026 696 28653422 697 2935254 698 246836 699 16698 700 884 701 35 702 1 703 0 704 1 705 342 706 36345 707 1824621 708 51814511 709 924428664 710 11100386299 711 94204347453 712 586117844494 713 2751119088781 714 9969292119973 715 28426894686858 716 64815215819813 717 119800792852240 718 181637369697166 719 228217427212507 720 239731425573258 721 212144265047755 722 159174733727167 723 101812640778414 724 55760688187089 725 26239150061569 726 10635405834074 727 3718948106421 728 1122559391760 729 292377438583 730 65609890566 731 12650169440 732 2086956636 733 292858236 734 34675597 735 3426692 736 278492 737 18239 738 936 739 36 740 1 741 0 742 1 743 361 744 40512 745 2152452 746 64788587 747 1227113088 748 15666780914 749 141578213970 750 939350542991 751 4708455288998 752 18244892018254 753 55701643395494 754 136146185001995 755 270076604139539 756 439977164194824 757 594666238673860 758 672774977877503 759 642029061993602 760 520225445400087 761 359921323194183 762 213608366184897 763 109155563589872 764 48164908017544 765 18388054306079 766 6080555696170 767 1741975525191 768 432018928761 769 92584424039 770 17093886311 771 2707051425 772 365468494 773 41717308 774 3981834 775 313110 776 19872 777 990 778 37 779 1 780 0 781 1 782 380 783 45028 784 2527932 785 80522183 786 1616300216 787 21901437438 788 210362017880 789 1485533159666 790 7935983685453 791 32816359793408 792 107047679165791 793 279887819570998 794 594598946788338 795 1038491981810190 796 1506460642827334 797 1831274301709622 798 1879977039820143 799 1640831987323021 800 1224557214545788 801 785230033861391 802 434355017819263 803 207917614843770 804 86328288549499 805 31138435783146 806 9764087166541 807 2661303094426 808 629827250044 809 129153762465 810 22873883014 811 3482668179 812 452987822 813 49911867 814 4606685 815 350847 816 21600 817 1045 818 38 819 1 820 0 821 1 822 400 823 49911 824 2956546 825 99504055 826 2113321751 827 30341624434 828 309208036950 829 2319863507210 830 13183707939880 831 58065961286536 832 201983944744950 833 563797343768131 834 1280070926753872 835 2391892915847419 836 3716019500356599 837 4843000617063791 838 5336220859302847 839 5004719878253474 840 4018787231434173 841 2776822205936286 842 1657883053249479 843 858199898666389 844 386187547366032 845 151357640185218 846 51724970288684 847 15418522040934 848 4007132209572 849 906755838522 850 178238405876 851 30329228238 852 4446101862 853 557883705 854 59405823 855 5307607 856 391908 857 23425 858 1102 859 39 860 1 861 0 862 1 863 420 864 55181 865 3444046 866 122293149 867 2743975123 868 41675743801 869 449876176496 870 3579785709504 871 21603393288847 872 101160987675950 873 374550855272863 874 1114021062048617 875 2697960591930696 876 5382881123976492 877 8938311589598107 878 12463257218616204 879 14707507050316964 880 14789340468450216 881 12748075745268205 882 9467861087020239 883 6084972303376065 884 3396498044134862 885 1651300558042487 886 700800679359061 887 260007001206130 888 84399234667584 889 23970461580081 890 5952242259973 891 1290214728809 892 243508643496 893 39870196696 894 5635045397 895 682940136 896 70358663 897 6091346 898 436459 899 25350 900 1160 901 40 902 1 903 0 904 1 905 441 906 60858 907 3996842 908 149526349 909 3539313921 910 56780032340 911 648218771069 912 5461767886033 913 34943125623955 914 173665732905864 915 683204854555256 916 2161375741190388 917 5573247424132796 918 11850799161883811 919 20992476715946545 920 31255692914733106 921 39422911752283188 922 42414390420965679 923 39159697237378912 924 31188804523736136 925 21524863996598858 926 12921328990669739 927 6767802919187476 928 3100447576814527 929 1244563334049718 930 438249491702976 931 135438738131418 932 36726747409050 933 8730012876436 934 1815748088528 935 329543898162 936 51990310989 937 7093300512 938 831286783 939 82944778 940 6965028 941 484716 942 27378 943 1220 944 41 945 1 946 0 947 1 948 462 949 66962 950 4621641 951 181927046 952 4536528202 953 76762849577 954 925437833261 955 8244006332560 956 55826681814885 957 294000665937029 958 1226874422993884 959 4121321971390908 960 11295256378303721 961 25552087446926673 962 48198403524122028 963 76486345940506056 964 102917573126819904 965 118237409134586709 966 116686942240902477 967 99449148173356506 968 73534456468877012 969 47358581236310505 970 26653347282392197 971 13143372674536256 972 5690564141961891 973 2166330718169676 974 725730602179069 975 213989189234750 976 55509501084320 977 12652623669267 978 2529072286094 979 442019162902 980 67279968181 981 8871531949 982 1006430604 983 97353035 984 7936184 985 536855 986 29511 987 1281 988 42 989 1 990 0 991 1 992 484 993 73514 994 5325877 995 220314188 996 5779970577 997 103017847066 998 1309680552685 999 12316904105750 1000 88150827218116 1001 491151644352860 1002 2170675054387104 1003 7730114684136189 1004 22480740361928711 1005 54013426345460160 1006 108306258195654747 1007 182864571558166357 1008 262023773470448403 1009 320850223210588719 1010 337813121511050165 1011 307470243825554132 1012 243065590909088958 1013 167570894057749861 1014 101093313095559299 1015 53521978480617208 1016 24923823195010071 1017 10226092984893263 1018 3700918172340845 1019 1182097489592950 1020 333209693416260 1021 82832214170192 1022 18133868328947 1023 3488536741080 1024 587922462140 1025 86441786431 1026 11028116287 1027 1212288559 1028 113788973 1029 9012745 1030 593104 1031 31752 1032 1344 1033 43 1034 1 1035 0 1036 1 1037 506 1038 80536 1039 6117311 1040 265612241 1041 7322292667 1042 137287518775 1043 1838050921819 1044 18223676211250 1045 137645153983313 1046 810204587511703 1047 3786584900297765 1048 14273342514629140 1049 43977889349195574 1050 112044953629435612 1051 238441764059673015 1052 427623011160214939 1053 651386148754039501 1054 848665425159781319 1055 951550651845257249 1056 923185356425255764 1057 778723628464861569 1058 573484090227222260 1059 370044204117830814 1060 209838854003718648 1061 104830328845486953 1062 46226689060687361 1063 18018067276306896 1064 6213043872689856 1065 1895887678346461 1066 511814094989493 1067 122127418320153 1068 25717549148247 1069 4768078389805 1070 775806923069 1071 110307846877 1072 13630037947 1073 1453222971 1074 132474272 1075 10203072 1076 653647 1077 34104 1078 1408 1079 44 1080 1 1081 0 1082 1 1083 529 1084 88049 1085 7004505 1086 318861679 1087 9225759697 1088 181738810033 1089 2559132323195 1090 26714056110183 1091 212654122883499 1092 1320519849076525 1093 6517029789290879 1094 25964439186062368 1095 84629812955478305 1096 228290389386540086 1097 514805332363486975 1098 979125542730679014 1099 1582999770641729583 1100 2190764810390882941 1101 2611384526631120179 1102 2695810740882163780 1103 2421896135476966715 1104 1901573454693765147 1105 1309666691911586764 1106 793712327111283371 1107 424384042750522818 1108 200616841689246659 1109 83982684044861092 1110 31168094131924459 1111 10261050315381005 1112 2996873485836711 1113 776125891492656 1114 178038697993662 1115 36112586010211 1116 6460749486886 1117 1016082194749 1118 139858981911 1119 16753892747 1120 1734078037 1121 153649107 1122 11515945 1123 718724 1124 36569 1125 1474 1126 45 1127 1 1128 0 1129 1 1130 552 1131 96076 1132 7996380 1133 381230480 1134 11563699697 1135 239052712995 1136 3536132370534 1137 38814844165942 1138 325220477586691 1139 2127688266307381 1140 11073170847266900 1141 46563639150596083 1142 160328009291363007 1143 457246862814456992 1144 1091015105595356458 1145 2197302203950993699 1146 3764703407624169701 1147 5525608770612590935 1148 6990901341057742784 1149 7666340088238168545 1150 7322708911080946468 1151 6118706955723770481 1152 4489427046802529220 1153 2901885898330717661 1154 1657017880822689458 1155 837764108499200186 1156 375706849399582960 1157 149654778316659298 1158 52993437979260282 1159 16688189810703678 1160 4673027362968896 1161 1162793516949635 1162 256792426933154 1163 50236153935853 1164 8682908789548 1165 1321349460459 1166 176246308530 1167 20486942417 1168 2060219130 1169 177571553 1170 12960595 1171 788529 1172 39150 1173 1541 1174 46 1175 1 1176 0 1177 1 1178 576 1179 104640 1180 9102734 1181 454026203 1182 14422168378 1183 312529993907 1184 4850784233196 1185 55921974251645 1186 492574386180725 1187 3390857009170844 1188 18585219145809813 1189 82377906345422964 1190 299227952951082865 1191 900991025922265867 1192 2271507540088153537 1193 4837430687895413426 1194 8770408349105177442 1195 13631858844476436109 1196 18277663875145310831 1197 21258180320827148732 1198 21553439106111907877 1199 19133465641388262788 1200 14928999506772124489 1201 10272718385699706559 1202 6251855529372393716 1203 3373286959020699642 1204 1616872711560648998 1205 689512127695699650 1206 261893582389415845 1207 88655002882374520 1208 26751916027408154 1209 7193610278000640 1210 1722348301481295 1211 366667656701163 1212 69266377690566 1213 11579176760314 1214 1706785692849 1215 220815173242 1216 24928290700 1217 2437573282 1218 204520140 1219 14546696 1220 863313 1221 41850 1222 1610 1223 47 1224 1 1225 0 1226 1 1227 600 1228 113764 1229 10333758 1230 538709167 1231 17901776114 1232 406215501492 1233 6608160770584 1234 79919914237593 1235 739164898671367 1236 5347616086212405 1237 30829987408828054 1238 143857752822271409 1239 550542937263177499 1240 1747887853348806955 1241 4649838339349310026 1242 10456502561587830680 1243 20033225426560787450 1244 32927191021531468965 1245 46719763922188416149 1246 57544851320159417831 1247 61834671762057893429 1248 58223772330543373816 1249 48229585154854996546 1250 35266776667757077732 1251 22832476281501860177 1252 13121411685481729968 1253 6707620533092199931 1254 3055308399540847215 1255 1241646577024428019 1256 450581567175201311 1257 146073708323735151 1258 42305057509967352 1259 10940304591950443 1260 2523829978049048 1261 518586125300010 1262 94706339356016 1263 15328267714145 1264 2190582131082 1265 275131731249 1266 30190113988 1267 2872672690 1268 234793099 1269 16284394 1270 943279 1271 44671 1272 1680 1273 48 1274 1 1275 0