1 1 2 1 3 1 4 1 5 1 6 2 7 1 8 2 9 3 10 3 11 1 12 2 13 6 14 6 15 6 16 1 17 3 18 9 19 15 20 16 21 11 22 1 23 3 24 13 25 26 26 43 27 37 28 23 29 1 30 4 31 17 32 46 33 88 34 116 35 96 36 47 37 1 38 4 39 23 40 68 41 169 42 273 43 329 44 239 45 106 46 1 47 5 48 28 49 103 50 287 51 585 52 869 53 918 54 622 55 235 56 1 57 5 58 35 59 141 60 467 61 1104 62 2031 63 2695 64 2609 65 1607 66 551 67 1 68 6 69 42 70 195 71 711 72 1972 73 4211 74 6882 75 8399 76 7391 77 4235 78 1301 79 1 80 6 81 50 82 253 83 1051 84 3270 85 8108 86 15513 87 23152 88 25903 89 21099 90 11185 91 3159 92 1 93 7 94 58 95 330 96 1489 97 5222 98 14552 99 32191 100 56291 101 76900 102 79822 103 60248 104 29862 105 7741 106 1 107 7 108 68 109 412 110 2063 111 7958 112 24846 113 62014 114 124958 115 200451 116 253536 117 244815 118 172683 119 80070 120 19320 121 1 122 8 123 77 124 517 125 2776 126 11789 127 40503 128 113025 129 256944 130 474398 131 704766 132 829018 133 749421 134 495509 135 216176 136 48629 137 1 138 8 139 88 140 627 141 3674 142 16903 143 63701 144 195972 145 497222 146 1036383 147 1770047 148 2447211 149 2693986 150 2287730 151 1424937 152 586218 153 123867 154 1 155 9 156 99 157 763 158 4759 159 23731 160 96921 161 326549 162 913243 163 2122741 164 4091994 165 6501238 166 8413102 167 8702226 168 6971239 169 4102693 170 1597578 171 317955 172 1 173 9 174 111 175 906 176 6083 177 32512 178 143558 179 524874 180 1605803 181 4114753 182 8839432 183 15850725 184 23562241 185 28659197 186 27970240 187 21202139 188 11830006 189 4370721 190 823065 191 1 192 10 193 123 194 1078 195 7651 196 43813 197 207397 198 818782 199 2717838 200 7614272 201 18027081 202 36009922 203 60405210 204 84384801 205 96861090 206 89487673 207 64386566 208 34148859 209 12003882 210 2144505 211 1 212 10 213 137 214 1257 215 9520 216 57954 217 293421 218 1242832 219 4451308 220 13530069 221 35006028 222 77050904 223 143930941 224 226874714 225 299066401 226 325042660 227 285152322 228 195245051 229 98686001 230 33077327 231 5623756 232 1 233 11 234 150 235 1469 236 11695 237 75636 238 407133 239 1842950 240 7080458 241 23211772 242 65140040 243 156633988 244 322326595 245 565656116 246 841255651 247 1050005364 248 1083881001 249 905296702 250 591321440 251 285459772 252 91433267 253 14828074 254 1 255 11 256 165 257 1689 258 14241 259 97266 260 555529 261 2674809 262 10976838 263 38597676 264 116783645 265 304529062 266 684411471 267 1322891808 268 2189987737 269 3083695632 270 3655614230 271 3593598541 272 2864623758 273 1788808786 274 826473782 275 253454781 276 39299897 277 1 278 12 279 180 280 1945 281 17163 282 123720 283 746266 284 3810062 285 16628471 286 62435590 287 202578291 288 569382696 289 1387402096 290 2928117682 291 5337994647 292 8365463239 293 11187293406 294 12630471852 295 11852857149 296 9037124057 297 5405736883 298 2394774727 299 704429853 300 104636890 301 1 302 12 303 196 304 2210 305 20533 306 155480 307 988855 308 5333905 309 24674844 310 98520474 311 341245418 312 1028336019 313 2700187280 314 6177372078 315 12293795646 316 21213190363 317 31570135454 318 40207774089 319 43338590285 320 38909739290 321 28431220763 322 16320419577 323 6944343654 324 1962537755 325 279793450 326 1 327 13 328 212 329 2514 330 24356 331 193613 332 1293599 333 7353288 334 35933801 335 152038502 336 559890597 337 1800759055 338 5068551845 339 12492963171 340 26945794375 341 50749443714 342 83148596715 343 117839488029 344 143283383286 345 147769999282 346 127177862435 347 89219598489 348 49230045026 349 20151175658 350 5479855546 351 751065460 352 1 353 13 354 230 355 2828 356 28710 357 238710 358 1673051 359 9993347 360 51449040 361 229930291 362 897081056 363 3067043053 364 9211825774 365 24334251143 366 56537316934 367 115384728014 368 206314672964 369 321865820225 370 435470736824 371 506640185388 372 500937458525 373 414032183552 374 279326815350 375 148381726358 376 58513084011 377 15332668869 378 2023443032 379 1 380 14 381 247 382 3185 383 33602 384 292020 385 2140731 386 13407967 387 72526042 388 341404099 389 1406704239 390 5094454880 391 16262374490 392 45832803493 393 114106491677 394 250809771480 395 485888054838 396 827154816133 397 1231810301131 398 1594591842152 399 1778689983755 400 1689143955429 401 1342953771169 402 872627651988 403 446899014625 404 170007600051 405 42983656210 406 5469566585 407 1 408 14 409 266 410 3552 411 39117 412 354253 413 2712810 414 17774859 415 100795125 416 498468323 417 2162978712 418 8271452198 419 27964169415 420 83750099144 421 222417248038 422 523784068895 423 1092702126395 424 2015150561573 425 3274358339964 426 4665272075760 427 5790099285913 428 6203573928936 429 5667782149817 430 4341214079532 431 2720683771829 432 1345056178294 433 494230862633 434 120716987723 435 14830871802 436 1 437 15 438 285 439 3965 440 45261 441 426887 442 3406619 443 23308815 444 138258395 445 716669727 446 3266609919 447 13153492248 448 46949520451 449 148895577516 450 420136317534 451 1055257929186 452 2358287149401 453 4682783112333 454 8241949604953 455 12811669097993 456 17500031131650 457 20861851069021 458 21505083584493 459 18931283719082 460 13989131401586 461 8466830143388 462 4045711489980 463 1437544937650 464 339596063606 465 40330829030 466 1 467 15 468 305 469 4390 470 52125 471 510729 472 4242613 473 30255144 474 187370792 475 1015848796 476 4852602392 477 20522322330 478 77120375603 479 258183924764 480 771334506621 481 2058144231522 482 4905003191234 483 10432298155977 484 19767773639997 485 33281226415470 486 49593781479786 487 65065460982702 488 74628046228357 489 74129292312253 490 62966232399826 491 44946356097620 492 26303421187836 493 12161626634326 494 4183397121048 495 956840683968 496 109972410221 497 1 498 16 499 325 500 4864 501 59718 502 607502 503 5242575 504 38906076 505 251100659 506 1421169390 507 7099695424 508 31463188265 509 124164577710 510 437575312446 511 1379806706915 512 3897614197470 513 9866673059559 514 22376025403199 515 45409236893382 516 82298830835281 517 132816426348165 518 190083981189280 519 239936826594682 520 265190450924731 521 254190751377607 522 208603530355572 523 144014988886147 524 81583351413853 525 36538257552935 526 12179789126942 527 2699962177860 528 300628862480 529 1 530 16 531 347 532 5350 533 68137 534 718154 535 6431921 536 49592152 537 333032067 538 1964160615 539 10242107842 540 47462685711 541 196248207184 542 726207150056 543 2410276447736 544 7185308886539 545 19253573415237 546 46374596044497 547 100337615582406 548 194738561988610 549 338282315219617 550 524291698154632 551 721897640483245 552 878075259647715 553 936527925075057 554 867370522612973 555 688549088786221 556 460264205629802 557 252658198710728 558 109718223481369 559 35476580153739 560 7629190921875 561 823779631721 562 1 563 17 564 368 565 5889 566 77390 567 844638 568 7837623 569 62702281 570 437440566 571 2684117149 572 14583521753 573 70533543111 574 304930524216 575 1182127520135 576 4119268154093 577 12923754390850 578 36542817479392 579 93156934459059 580 214046290109321 581 442867307908029 582 823757855743366 583 1374132477179896 584 2048829019523493 585 2718307007190373 586 3190671656137649 587 3288293430227527 588 2946206338223768 589 2264902284174948 590 1467447531599634 591 781354703380179 592 329305098572354 593 103377060797608 594 21585754676694 595 2262366343746 596 1 597 17 598 391 599 6441 600 87582 601 988049 602 9490791 603 78672760 604 569420944 605 3629501557 606 20514204738 607 103369976865 608 466363289459 609 1890138792372 610 6899391023589 611 22723812356745 612 67614019995244 613 181865417785750 614 442222664426959 615 971565324178972 616 1926349994652908 617 3440543496736560 618 5520901993297582 619 7931514722689777 620 10154672649731491 621 11517338311163494 622 11483376019367645 623 9964613602475625 624 7426048415656587 625 4668066096050574 626 2413141868640273 627 987914989042474 628 301354156417735 629 61149363914307 630 6226306037178 631 1 632 18 633 414 634 7049 635 98721 636 1150624 637 11424328 638 98011366 639 734980718 640 4859807589 641 28531145339 642 149542299177 643 702843319444 644 2972413521416 645 11341959821568 646 39126864036609 647 122204544575792 648 345858197924560 649 887248108321170 650 2062680162395292 651 4342302233873379 652 8266325857941124 653 14201247834496984 654 21955988844137271 655 30436789166551846 656 37653415800378254 657 41316727347624846 658 39899230900554800 659 33566815339785071 660 24274139822203467 661 14817945457520307 662 7443391055181487 663 2962468289318511 664 878803205370538 665 173429626124445 666 17169677490714 667 1 668 18 669 438 670 7671 671 110919 672 1333579 673 13675863 674 121283654 675 941196183 676 6447409769 677 39262362843 678 213735515530 679 1044808271640 680 4602688939634 681 18324427682125 682 66074996055770 683 216134178174599 684 642019786729268 685 1732808950224549 686 4249644346509456 687 9465798099163485 688 19131014042764113 689 35028339208039516 690 57976083759800477 691 86487486150483410 692 115846016827426011 693 138649529498754015 694 147356811319288557 695 137971242352349728 696 112645933767973994 697 79119641139119782 698 46942707720142534 699 22932050951770119 700 8879968867789770 701 2563652312314298 702 492418372319906 703 47436313524262 704 1 705 19 706 462 707 8352 708 124185 709 1539451 710 16285029 711 149141680 712 1196327052 713 8479995075 714 53495190570 715 302043650853 716 1533374703182 717 7025071571289 718 29130978320259 719 109587780543045 720 374652099273420 721 1165431782040024 722 3301135151340667 723 8516890369093073 724 20010716096322982 725 42788162790422410 726 83168717035134348 727 146699007691765453 728 234266181528833619 729 337658336032617790 730 437548772931839456 731 507216473550590139 732 522680746972007345 733 474966550691212932 734 376678564611012248 735 257187123131439669 736 148431335310938518 737 70571154234949779 738 26607402750144649 739 7481210788441334 740 1399587075745443 741 131290543779126 742 1 743 19 744 488 745 9048 746 138636 747 1769626 748 19296806 749 182307040 750 1510004962 751 11062959299 752 72210004954 753 422325822822 754 2223546105366 755 10578688995006 756 45617038004577 757 178723836332243 758 637398528461238 759 2072103265143523 760 6145871368346972 761 16639400991513380 762 41124274350993274 763 92747184414325233 764 190714622745252775 765 357088200534450829 766 607671843948196789 767 937547519009582040 768 1307274612225352542 769 1640732096653296995 770 1844156488214025323 771 1844432740650592045 772 1628165898336983997 773 1255343587215069501 774 833878607569752949 775 468494612334686933 776 216945039075272657 777 79695858530024949 778 21838496936144646 779 3981963576144024 780 363990257783343 781 1 782 20 783 513 784 9807 785 154283 786 2026918 787 22758452 788 221604787 789 1893371037 790 14322528915 791 96619102299 792 584639626842 793 3188229903211 794 15729747437624 795 70431338838897 796 286930809762094 797 1065659475217923 798 3613643310728257 799 11200123891357339 800 31749483565865333 801 82337608273194807 802 195319358302271197 803 423581670849396239 804 838967057781485771 805 1515427546561235234 806 2491418777686614229 807 3718413407201494810 808 5021579093765158558 809 6110816046913318955 810 6666308022660232965 811 6477021657955023154 812 5559003137802385595 813 4170324255953062090 814 2697144448477709663 815 1476202328404401365 816 666245514538512555 817 238626942440688901 818 63768325016542133 819 11339789834655338 820 1010748076717151 821 1 822 20 823 540 824 10581 825 171250 826 2312892 827 26723182 828 267942834 829 2359302044 830 18408816238 831 128212564210 832 801759357886 833 4523240506979 834 23112839560012 835 107312809081141 836 453919390487873 837 1752839601245111 838 6189386387936417 839 20008626906829986 840 59265543992723129 841 160912388875057069 842 400501609367471925 843 913500036788234480 844 1908070864918822038 845 3645632569523924142 846 6361448748408376475 847 10116567190295019069 848 14623014355460528926 849 19146850248076402268 850 22614108434968905949 851 23966066820239348843 852 22640693418950266250 853 18908234876026827593 854 13812281249271085168 855 8703777206551788708 856 4643944665470341200 857 2044104141973705199 858 714268085884984889 859 186256950678743101 860 32322377801566481 861 2810986483493475 862 1 863 21 864 567 865 11421 866 189547 867 2630700 868 31246779 869 322351560 870 2922573984 871 23499769199 872 168810685473 873 1089799345152 874 6353479322428 875 33583795766898 876 161483845241999 877 708237820392994 878 2839400676053870 879 10423701933974634 880 35086307626965770 881 108388226537248190 882 307473675412949127 883 801154529801819914 884 1917154564624762620 885 4211390993103484356 886 8485042232571031640 887 15660280359411032721 888 26431730747310929180 889 40707720409741371440 890 57048522431488130422 891 72497007191519378598 892 83182617800560089893 893 85715800613548235256 894 78797458160665729726 895 64083559644992163217 896 45615932751381993467 897 28026171479155071645 898 14586893541764684635 899 6265796975004840104 900 2137312810371029506 901 544176029259657255 902 92209099445683274 903 7828986221515605 904 1 905 21 906 595 907 12278 908 209305 909 2982050 910 36391680 911 385959114 912 3600129251 913 29805013357 914 220625241398 915 1468951638614 916 8840532404182 917 48286761065938 918 240166880109465 919 1090773888257835 920 4533932715061330 921 17279211457542406 922 60464232558538777 923 194472349422275564 924 575323424637660658 925 1566131542456226270 926 3923127696923335945 927 9040827367871405948 928 19155402244179632615 929 37278710472366199642 930 66546592621226905821 931 108769101290790311990 932 162406756779939569543 933 220889576784483318286 934 272693861819751237717 935 304228574685459452284 936 305067751338929409785 937 273111936719246589599 938 216452681920179294944 939 150239923509414555498 940 90057265222070820881 941 45751509945584055015 942 19189919641327888998 943 6393615589350453334 944 1590304847089513777 945 263268750948156219 946 21835027912963086 947 1 948 22 949 623 950 13204 951 230536 952 3370449 953 42223141 954 460037360 955 4411270570 956 37570783074 957 286329006517 958 1964364103854 959 12191943019542 960 68738793704052 961 353257381122215 962 1659475004951609 963 7142564313583446 964 28220635610299681 965 102509847380911263 966 342731661678949109 967 1055585976024999229 968 2996460970313375818 969 7841362527091810401 970 18914820286968203772 971 42040246990690614087 972 86032716620066821865 973 161930526110125973665 974 279914814668482296237 975 443541921419941576018 976 642720722213744729394 977 849196442660215418266 978 1019333762399878636621 979 1106654029005726291534 980 1080717758046046235632 981 942899728179938504180 982 728740987696888378672 983 493547887265475138995 984 288812408197116786422 985 143299542389258249101 986 58723393957625958604 987 19120647563252261393 988 4648687853183178382 989 752252995615564169 990 60978390985918906 991 1 992 22 993 653 994 14147 995 253377 996 3797806 997 48813807 998 545972471 999 5377974040 1000 47084693779 1001 369136306572 1002 2607170073347 1003 16672480511333 1004 96935800663918 1005 514194113378123 1006 2495654598027760 1007 11109609337912976 1008 45449282706419446 1009 171144011681843999 1010 593945132374142231 1011 1901457869559850776 1012 5618994707444442544 1013 15332477408091769582 1014 38634402250278311011 1015 89876359683499767761 1016 192929315131539210445 1017 381828255688262587403 1018 695894415331424817999 1019 1166138392289201188901 1020 1793211873717596799193 1021 2524186543445892182526 1022 3242705639120211465007 1023 3787775855448716551231 1024 4004867967420498139859 1025 3811621711391940255846 1026 3243174399379457825774 1027 2445936134910976335350 1028 1617341569057654388695 1029 924474938135983535022 1030 448238085261855920919 1031 179558801105394683543 1032 57166545456921071195 1033 13592042123406075077 1034 2151060854736807212 1035 170508699155987862 1036 1 1037 23 1038 682 1039 15163 1040 277839 1041 4267953 1042 56239466 1043 645317923 1044 6525115320 1045 58681827800 1046 472893818939 1047 3435702585387 1048 22617746367693 1049 135484450609683 1050 741076347018308 1051 3712349525620466 1052 17073221783404917 1053 72235135794378367 1054 281625686442908863 1055 1013131745805791303 1056 3366473915182334881 1057 10340013181274825290 1058 29370055820502346212 1059 77163311308171203475 1060 187502614318397618975 1061 421253206125691890888 1062 874467271549787338326 1063 1675719536817376763202 1064 2960506280398731247063 1065 4814240510616703246342 1066 7191127102112565940931 1067 9841839267712034228616 1068 12303385966072828806800 1069 13996166639124055710944 1070 14422479577109331147935 1071 13386969143825638372502 1072 11115591460558113570213 1073 8185433366125058825512 1074 5287523588943795895659 1075 2953887519003311057378 1076 1400306851923082584222 1077 548624376963333572033 1078 170871578077478780414 1079 39750166728731688110 1080 6155334607289720921 1081 477355090753926460 1082 1 1083 23 1084 713 1085 16197 1086 304067 1087 4783006 1088 64584010 1089 759759881 1090 7880835022 1091 72750594943 1092 602184986055 1093 4496906512533 1094 30450539892340 1095 187765385851495 1096 1058088525157234 1097 5465309573015177 1098 25940934508769987 1099 113382531515870424 1100 457140253793706341 1101 1702576613491919001 1102 5864071322407965685 1103 18693393020241677734 1104 55184853028951733922 1105 150914274673268511861 1106 382336557350023177207 1107 897185827880826314762 1108 1949136894897643561779 1109 3917494124308264455452 1110 7276706963320631870282 1111 12474871008108555665548 1112 19704687811570352058216 1113 28616422594076445114919 1114 38110778752216329466643 1115 46398000106523844942693 1116 51441221571696938155964 1117 51697531235429661892043 1118 46829161533399055473013 1119 37968578501592274277707 1120 27316273517954710098741 1121 17247541888864829735257 1122 9422086318147986813868 1123 4369305243374456007996 1124 1675061083356645131671 1125 510612151239596056305 1126 116275704560602783248 1127 17625756050785853010 1128 1337946100045842285 1129 1 1130 24 1131 744 1132 17307 1133 332073 1134 5347190 1135 73934808 1136 891177767 1137 9476800815 1138 89740165329 1139 762447013849 1140 5847989929892 1141 40700428510541 1142 258134146941783 1143 1497305243165996 1144 7967343001828516 1145 38991337107490846 1146 175877106709596634 1147 732514371553542693 1148 2821165369254291878 1149 10059121430081248956 1150 33235898907388034947 1151 101825710119285376162 1152 289395177266599758429 1153 763109364301513532364 1154 1866889229751518667866 1155 4236001252255447911419 1156 8909628922430604215297 1157 17356959566905458949175 1158 31283667790418371103478 1159 52092307683035242076368 1160 79996190677580745634306 1161 113046460264552989055810 1162 146617191200036649026879 1163 173964508712348247145514 1164 188105857125790124601571 1165 184490145075300537288965 1166 163189688259834465968524 1167 129274420984908047798015 1168 90915725774908592736169 1169 56139627657346880683515 1170 30004542997115715085368 1171 13617547495800039929879 1172 5110774399099889789871 1173 1525493922238049223243 1174 340197332334784181445 1175 50504339120076683261 1176 3754194185716399992 1177 1 1178 24 1179 776 1180 18436 1181 362008 1182 5962789 1183 84388146 1184 1041603924 1185 11348628778 1186 110167595514 1187 960104492748 1188 7558330379141 1189 54027070033684 1190 352167103959483 1191 2100964362215257 1192 11506912691067829 1193 58009867228906716 1194 269776667179736220 1195 1159495372226920390 1196 4612769186909742410 1197 17006891207505414172 1198 58168458695059390278 1199 184702297453688043653 1200 544754330273377044768 1201 1492780947448133786412 1202 3800884768968000023643 1203 8990728090328362425809 1204 19749415465352716364615 1205 40261053753985759966402 1206 76102226708204726256977 1207 133222802035111452587851 1208 215665786415679846802349 1209 322259654934970597344069 1210 443485263873006895911135 1211 560564022569722817826329 1212 648677300086561230927565 1213 684519475957715684341974 1214 655599630518547909270140 1215 566612648051060805115873 1216 438793152316490170075827 1217 301818104518529816013847 1218 182355791028294432224277 1219 95399076281365147494132 1220 42393955495079440322549 1221 15583170148398249807966 1222 4556507974323950042733 1223 995545409378209728646 1224 144804797963653034389 1225 10545233702911509534 1226 1 1227 25 1228 808 1229 19644 1230 393885 1231 6634437 1232 96044080 1233 1213292562 1234 13536186686 1235 134626818861 1236 1202718319570 1237 9711687292100 1238 71247860027515 1239 476961112793131 1240 2924312982371666 1241 16472084737462947 1242 85468812635148871 1243 409427731252036781 1244 1814184443908964898 1245 7447487810675815268 1246 28361610424528149900 1247 100300376557231206774 1248 329670264906632948649 1249 1007674131206531666761 1250 2865414052368835781275 1251 7581471463948981925436 1252 18663734884341610139292 1253 42737513177736404554820 1254 90986200096871609945422 1255 179963849776590360040518 1256 330382295064161255520228 1257 562248809783252837727795 1258 885617412897086857729483 1259 1288679451464714748499232 1260 1728334331167056277916896 1261 2130573733656364978802720 1262 2406105995987088846693376 1263 2479465619234145450647167 1264 2320325844325395248953954 1265 1960500685619748232910946 1266 1484992977763441758456044 1267 999511757298186218664166 1268 591173565582938865448638 1269 302863558987460895731685 1270 131840055038008847448154 1271 47484263680197092274187 1272 13606929487419209249424 1273 2913909445399222777049 1274 415431756134296703464 1275 29650945107763261531