1 1 2 1 3 0 4 1 5 0 6 1 7 2 8 0 9 1 10 1 11 4 12 0 13 1 14 1 15 2 16 8 17 0 18 2 19 1 20 2 21 4 22 17 23 0 24 4 25 2 26 2 27 4 28 8 29 37 30 0 31 8 32 4 33 4 34 4 35 8 36 17 37 82 38 0 39 17 40 8 41 8 42 8 43 8 44 17 45 37 46 185 47 0 48 37 49 17 50 16 51 16 52 16 53 17 54 37 55 82 56 423 57 0 58 82 59 37 60 34 61 32 62 32 63 34 64 37 65 82 66 185 67 978 68 0 69 185 70 82 71 74 72 68 73 64 74 68 75 74 76 82 77 185 78 423 79 2283 80 0 81 423 82 185 83 164 84 148 85 136 86 136 87 148 88 164 89 185 90 423 91 978 92 5373 93 0 94 978 95 423 96 370 97 328 98 296 99 289 100 296 101 328 102 370 103 423 104 978 105 2283 106 12735 107 0 108 2283 109 978 110 846 111 740 112 656 113 629 114 629 115 656 116 740 117 846 118 978 119 2283 120 5373 121 30372 122 0 123 5373 124 2283 125 1956 126 1692 127 1480 128 1394 129 1369 130 1394 131 1480 132 1692 133 1956 134 2283 135 5373 136 12735 137 72832 138 0 139 12735 140 5373 141 4566 142 3912 143 3384 144 3145 145 3034 146 3034 147 3145 148 3384 149 3912 150 4566 151 5373 152 12735 153 30372 154 175502 155 0 156 30372 157 12735 158 10746 159 9132 160 7824 161 7191 162 6845 163 6724 164 6845 165 7191 166 7824 167 9132 168 10746 169 12735 170 30372 171 72832 172 424748 173 0 174 72832 175 30372 176 25470 177 21492 178 18264 179 16626 180 15651 181 15170 182 15170 183 15651 184 16626 185 18264 186 21492 187 25470 188 30372 189 72832 190 175502 191 1032004 192 0 193 175502 194 72832 195 60744 196 50940 197 42984 198 38811 199 36186 200 34686 201 34225 202 34686 203 36186 204 38811 205 42984 206 50940 207 60744 208 72832 209 175502 210 424748 211 2516347 212 0 213 424748 214 175502 215 145664 216 121488 217 101880 218 91341 219 84471 220 80196 221 78255 222 78255 223 80196 224 84471 225 91341 226 101880 227 121488 228 145664 229 175502 230 424748 231 1032004 232 6155441 233 0 234 1032004 235 424748 236 351004 237 291328 238 242976 239 216495 240 198801 241 187206 242 180930 243 178929 244 180930 245 187206 246 198801 247 216495 248 242976 249 291328 250 351004 251 424748 252 1032004 253 2516347 254 15101701 255 0 256 2516347 257 1032004 258 849496 259 702008 260 582656 261 516324 262 471195 263 440586 264 422355 265 413694 266 413694 267 422355 268 440586 269 471195 270 516324 271 582656 272 702008 273 849496 274 1032004 275 2516347 276 6155441 277 37150472 278 0 279 6155441 280 2516347 281 2064008 282 1698992 283 1404016 284 1238144 285 1123764 286 1044270 287 994005 288 965709 289 956484 290 965709 291 994005 292 1044270 293 1123764 294 1238144 295 1404016 296 1698992 297 2064008 298 2516347 299 6155441 300 15101701 301 91618049 302 0 303 15101701 304 6155441 305 5032694 306 4128016 307 3397984 308 2983534 309 2694784 310 2490504 311 2355975 312 2272779 313 2232774 314 2232774 315 2272779 316 2355975 317 2490504 318 2694784 319 2983534 320 3397984 321 4128016 322 5032694 323 6155441 324 15101701 325 37150472 326 226460893 327 0 328 37150472 329 15101701 330 12310882 331 10065388 332 8256032 333 7220716 334 6493574 335 5972224 336 5618820 337 5386905 338 5254794 339 5212089 340 5254794 341 5386905 342 5618820 343 5972224 344 6493574 345 7220716 346 8256032 347 10065388 348 12310882 349 15101701 350 37150472 351 91618049 352 560954047 353 0 354 91618049 355 37150472 356 30203402 357 24621764 358 20130776 359 17544068 360 15715676 361 14391164 362 13473920 363 12847356 364 12454830 365 12266559 366 12266559 367 12454830 368 12847356 369 13473920 370 14391164 371 15715676 372 17544068 373 20130776 374 24621764 375 30203402 376 37150472 377 91618049 378 226460893 379 1392251012 380 0 381 226460893 382 91618049 383 74300944 384 60406804 385 49243528 386 42777899 387 38184148 388 34829336 389 32467870 390 30807936 391 29703816 392 29074005 393 28869129 394 29074005 395 29703816 396 30807936 397 32467870 398 34829336 399 38184148 400 42777899 401 49243528 402 60406804 403 74300944 404 91618049 405 226460893 406 560954047 407 3461824644 408 0 409 560954047 410 226460893 411 183236098 412 148601888 413 120813608 414 104642497 415 93104839 416 84624328 417 78578380 418 74237346 419 71229696 420 69339276 421 68425155 422 68425155 423 69339276 424 71229696 425 74237346 426 78578380 427 84624328 428 93104839 429 104642497 430 120813608 431 148601888 432 183236098 433 226460893 434 560954047 435 1392251012 436 8622571758 437 0 438 1392251012 439 560954047 440 452921786 441 366472196 442 297203776 443 256728917 444 227751317 445 206340454 446 190920740 447 179668404 448 171640956 449 166275456 450 163188756 451 162180225 452 163188756 453 166275456 454 171640956 455 179668404 456 190920740 457 206340454 458 227751317 459 256728917 460 297203776 461 366472196 462 452921786 463 560954047 464 1392251012 465 3461824644 466 21511212261 467 0 468 3461824644 469 1392251012 470 1121908094 471 905843572 472 732944392 473 631558024 474 558762937 475 504746162 476 465524195 477 436537692 478 415403544 479 400671066 480 391326336 481 386787420 482 386787420 483 391326336 484 400671066 485 415403544 486 436537692 487 465524195 488 504746162 489 558762937 490 631558024 491 732944392 492 905843572 493 1121908094 494 1392251012 495 3461824644 496 8622571758 497 53745962199 498 0 499 8622571758 500 3461824644 501 2784502024 502 2243816188 503 1811687144 504 1557506833 505 1374567464 506 1238339482 507 1138756585 508 1064414781 509 1009299912 510 969699684 511 942972246 512 927515520 513 922458384 514 927515520 515 942972246 516 969699684 517 1009299912 518 1064414781 519 1138756585 520 1238339482 521 1374567464 522 1557506833 523 1811687144 524 2243816188 525 2784502024 526 3461824644 527 8622571758 528 21511212261 529 134474581374 530 0 531 21511212261 532 8622571758 533 6923649288 534 5569004048 535 4487632376 536 3849835181 537 3389867813 538 3046338704 539 2793814685 540 2603751543 541 2460987366 542 2356065132 543 2282171004 544 2235017970 545 2212053504 546 2212053504 547 2235017970 548 2282171004 549 2356065132 550 2460987366 551 2603751543 552 2793814685 553 3046338704 554 3389867813 555 3849835181 556 4487632376 557 5569004048 558 6923649288 559 8622571758 560 21511212261 561 53745962199 562 336908488839 563 0 564 53745962199 565 21511212261 566 17245143516 567 13847298576 568 11138008096 569 9536218799 570 8379053041 571 7512680018 572 6872837320 573 6388019523 574 6020021298 575 5744820201 576 5544957492 577 5409165780 578 5330346744 579 5304500224 580 5330346744 581 5409165780 582 5544957492 583 5744820201 584 6020021298 585 6388019523 586 6872837320 587 7512680018 588 8379053041 589 9536218799 590 11138008096 591 13847298576 592 17245143516 593 21511212261 594 53745962199 595 134474581374 596 845139060165 597 0 598 134474581374 599 53745962199 600 43022424522 601 34490287032 602 27694597152 603 23668267204 604 20755299739 605 18569793226 606 16949339065 607 15714649656 608 14769463578 609 14052871803 610 13520332431 611 13142570940 612 12900446256 613 12782161664 614 12782161664 615 12900446256 616 13142570940 617 13520332431 618 14052871803 619 14769463578 620 15714649656 621 16949339065 622 18569793226 623 20755299739 624 23668267204 625 27694597152 626 34490287032 627 43022424522 628 53745962199 629 134474581374 630 336908488839 631 2122553644686 632 0 633 336908488839 634 134474581374 635 107491924398 636 86044849044 637 68980574064 638 58851018948 639 51513287444 640 45998231854 641 41895265205 642 38754434727 643 36333161616 644 34477183383 645 33073184493 646 32045679045 647 31344025488 648 30935246336 649 30800952004 650 30935246336 651 31344025488 652 32045679045 653 33073184493 654 34477183383 655 36333161616 656 38754434727 657 41895265205 658 45998231854 659 51513287444 660 58851018948 661 68980574064 662 86044849044 663 107491924398 664 134474581374 665 336908488839 666 845139060165 667 5336735929371 668 0 669 845139060165 670 336908488839 671 268949162748 672 214983848796 673 172089698088 674 146583719886 675 128087511828 676 114164582984 677 103776498695 678 95792957739 679 89602451922 680 84814527576 681 81141439473 682 78389541135 683 76426491084 684 75162915328 685 74544123496 686 74544123496 687 75162915328 688 76426491084 689 78389541135 690 81141439473 691 84814527576 692 89602451922 693 95792957739 694 103776498695 695 114164582984 696 128087511828 697 146583719886 698 172089698088 699 214983848796 700 268949162748 701 336908488839 702 845139060165 703 2122553644686 704 13432403613621 705 0 706 2122553644686 707 845139060165 708 673816977678 709 537898325496 710 429967697592 711 365690608437 712 319035155046 713 283869620808 714 257566437220 715 237283561881 716 221478753354 717 209164005867 718 199609486056 719 192320162235 720 186953054052 721 183270584704 722 181118766008 723 180410863504 724 181118766008 725 183270584704 726 186953054052 727 192320162235 728 199609486056 729 209164005867 730 221478753354 731 237283561881 732 257566437220 733 283869620808 734 319035155046 735 365690608437 736 429967697592 737 537898325496 738 673816977678 739 845139060165 740 2122553644686 741 5336735929371 742 33843022209066 743 0 744 5336735929371 745 2122553644686 746 1690278120330 747 1347633955356 748 1075796650992 749 913681357383 750 795914853657 751 707050884156 752 640437559140 753 588922178076 754 548613057966 755 517010218719 756 492263777277 757 473111260920 758 458668862772 759 448313078912 760 441623931194 761 438341634992 762 438341634992 763 441623931194 764 448313078912 765 458668862772 766 473111260920 767 492263777277 768 517010218719 769 548613057966 770 588922178076 771 640437559140 772 707050884156 773 795914853657 774 913681357383 775 1075796650992 776 1347633955356 777 1690278120330 778 2122553644686 779 5336735929371 780 13432403613621 781 85349327734485 782 0 783 13432403613621 784 5336735929371 785 4245107289372 786 3380556240660 787 2695267910712 788 2286067883358 789 1988600601363 790 1763919405402 791 1595175775230 792 1464351824412 793 1361621489736 794 1280658089301 795 1216774378089 796 1166755854015 797 1128334135584 798 1099887087232 799 1080292206382 800 1068813355556 801 1065032256016 802 1068813355556 803 1080292206382 804 1099887087232 805 1128334135584 806 1166755854015 807 1216774378089 808 1280658089301 809 1361621489736 810 1464351824412 811 1595175775230 812 1763919405402 813 1988600601363 814 2286067883358 815 2695267910712 816 3380556240660 817 4245107289372 818 5336735929371 819 13432403613621 820 33843022209066 821 215440028338359 822 0 823 33843022209066 824 13432403613621 825 10673471858742 826 8490214578744 827 6761112481320 828 5727444310263 829 4975559510838 830 4407168900318 831 3979574268285 832 3647347853634 833 3385664501832 834 3178509060396 835 3014006094531 836 2883979472355 837 2782623384228 838 2705743176704 839 2650378728902 840 2614511253868 841 2596880169388 842 2596880169388 843 2614511253868 844 2650378728902 845 2705743176704 846 2782623384228 847 2883979472355 848 3014006094531 849 3178509060396 850 3385664501832 851 3647347853634 852 3979574268285 853 4407168900318 854 4975559510838 855 5727444310263 856 6761112481320 857 8490214578744 858 10673471858742 859 13432403613621 860 33843022209066 861 85349327734485 862 544288586926914 863 0 864 85349327734485 865 33843022209066 866 26864807227242 867 21346943717484 868 16980429157488 869 14367364022805 870 12465614087043 871 11026915672668 872 9943003006815 873 9099242786403 874 8432875179324 875 7903345662252 876 7480564687476 877 7143749788545 878 6878070242196 879 6672725744768 880 6519982136944 881 6414417296348 882 6352439733764 883 6332002224409 884 6352439733764 885 6414417296348 886 6519982136944 887 6672725744768 888 6878070242196 889 7143749788545 890 7480564687476 891 7903345662252 892 8432875179324 893 9099242786403 894 9943003006815 895 11026915672668 896 12465614087043 897 14367364022805 898 16980429157488 899 21346943717484 900 26864807227242 901 33843022209066 902 85349327734485 903 215440028338359 904 1376230297675914 905 0 906 215440028338359 907 85349327734485 908 67686044418132 909 53729614454484 910 42693887434968 911 36083411959662 912 31270145226105 913 27626496084798 914 24877797554190 915 22734542010177 916 21037965591258 917 19685331323514 918 18600383812212 919 17730316637820 920 17037296315484 921 16493599758976 922 16079150835598 923 15779588681056 924 15585015838804 925 15489225494027 926 15489225494027 927 15585015838804 928 15779588681056 929 16079150835598 930 16493599758976 931 17037296315484 932 17730316637820 933 18600383812212 934 19685331323514 935 21037965591258 936 22734542010177 937 24877797554190 938 27626496084798 939 31270145226105 940 36083411959662 941 42693887434968 942 53729614454484 943 67686044418132 944 85349327734485 945 215440028338359 946 544288586926914 947 3482537223611046 948 0 949 544288586926914 950 215440028338359 951 170698655468970 952 135372088836264 953 107459228908968 954 90724510799307 955 78534484853382 956 69301402933530 957 62328070435215 958 56882747921202 959 52563551030622 960 49110097591863 961 46329078055734 962 44086336841340 963 42285447736464 964 40855405151104 965 39744339643286 966 38914583076652 967 38339435705888 968 38001120006247 969 37889453904481 970 38001120006247 971 38339435705888 972 38914583076652 973 39744339643286 974 40855405151104 975 42285447736464 976 44086336841340 977 46329078055734 978 49110097591863 979 52563551030622 980 56882747921202 981 62328070435215 982 69301402933530 983 78534484853382 984 90724510799307 985 107459228908968 986 135372088836264 987 170698655468970 988 215440028338359 989 544288586926914 990 1376230297675914 991 8819175375714063 992 0 993 1376230297675914 994 544288586926914 995 430880056676718 996 341397310937940 997 270744177672528 998 228350861431557 999 197459229386727 1000 174049398864252 1001 156350726130525 1002 142512290778897 1003 131516140583772 1004 122702031700317 1005 115579743478353 1006 109808451338130 1007 105142538087568 1008 101400425705984 1009 98448557156594 1010 96188811379964 1011 94550193040196 1012 93483478765784 1013 92957629505141 1014 92957629505141 1015 93483478765784 1016 94550193040196 1017 96188811379964 1018 98448557156594 1019 101400425705984 1020 105142538087568 1021 109808451338130 1022 115579743478353 1023 122702031700317 1024 131516140583772 1025 142512290778897 1026 156350726130525 1027 174049398864252 1028 197459229386727 1029 228350861431557 1030 270744177672528 1031 341397310937940 1032 430880056676718 1033 544288586926914 1034 1376230297675914 1035 3482537223611046 1036 22349794473772659 1037 0 1038 3482537223611046 1039 1376230297675914 1040 1088577173853828 1041 861760113353436 1042 682794621875880 1043 575331377554122 1044 496998933703977 1045 437612346208422 1046 392672424266910 1047 357493822449795 1048 329496502084542 1049 307005469276842 1050 288777054895227 1051 273945288143835 1052 261884749433976 1053 252131612471808 1054 244342837108024 1055 238264109555156 1056 233708547419572 1057 230542802747003 1058 228677538518152 1059 228061373093401 1060 228677538518152 1061 230542802747003 1062 233708547419572 1063 238264109555156 1064 244342837108024 1065 252131612471808 1066 261884749433976 1067 273945288143835 1068 288777054895227 1069 307005469276842 1070 329496502084542 1071 357493822449795 1072 392672424266910 1073 437612346208422 1074 496998933703977 1075 575331377554122 1076 682794621875880 1077 861760113353436 1078 1088577173853828 1079 1376230297675914 1080 3482537223611046 1081 8819175375714063 1082 56678600914995057 1083 0 1084 8819175375714063 1085 3482537223611046 1086 2752460595351828 1087 2177154347707656 1088 1723520226706872 1089 1450938571486245 1090 1252191821735442 1091 1101457096316922 1092 987296146933635 1093 897840191702178 1094 826546000841370 1095 769162080019437 1096 722531925722502 1097 684454828604265 1098 653338538791092 1099 627999146278656 1100 607557148671288 1101 591355832844976 1102 578906820320188 1103 569854188717871 1104 563949495154609 1105 561035320152872 1106 561035320152872 1107 563949495154609 1108 569854188717871 1109 578906820320188 1110 591355832844976 1111 607557148671288 1112 627999146278656 1113 653338538791092 1114 684454828604265 1115 722531925722502 1116 769162080019437 1117 826546000841370 1118 897840191702178 1119 987296146933635 1120 1101457096316922 1121 1252191821735442 1122 1450938571486245 1123 1723520226706872 1124 2177154347707656 1125 2752460595351828 1126 3482537223611046 1127 8819175375714063 1128 22349794473772659 1129 143830921235537742 1130 0 1131 22349794473772659 1132 8819175375714063 1133 6965074447222092 1134 5504921190703656 1135 4354308695415312 1136 3662480481752103 1137 3157925126175945 1138 2775127821143412 1139 2484994668519885 1140 2257439298123933 1141 2075857464502908 1142 1929452474356695 1143 1810209310531947 1144 1712533793797890 1145 1632372363908028 1146 1566704611393152 1147 1513278588672516 1148 1470403093889712 1149 1436808613388048 1150 1411555033306309 1151 1393966665668813 1152 1383588382201349 1153 1380157569822784 1154 1383588382201349 1155 1393966665668813 1156 1411555033306309 1157 1436808613388048 1158 1470403093889712 1159 1513278588672516 1160 1566704611393152 1161 1632372363908028 1162 1712533793797890 1163 1810209310531947 1164 1929452474356695 1165 2075857464502908 1166 2257439298123933 1167 2484994668519885 1168 2775127821143412 1169 3157925126175945 1170 3662480481752103 1171 4354308695415312 1172 5504921190703656 1173 6965074447222092 1174 8819175375714063 1175 22349794473772659 1176 56678600914995057 1177 365225623668676437 1178 0 1179 56678600914995057 1180 22349794473772659 1181 17638350751428126 1182 13930148894444184 1183 11009842381407312 1184 9252905977757538 1185 7971281048519283 1186 6998644874227770 1187 6260959108677210 1188 5681906728561683 1189 5219327738924838 1190 4845789970818138 1191 4540932170266545 1192 4290529605364665 1193 4084261985491128 1194 3914425918877568 1195 3775260774230022 1196 3662420109066984 1197 3572616879906576 1198 3503386657293164 1199 3452919540019727 1200 3419944694278993 1201 3403653764069128 1202 3403653764069128 1203 3419944694278993 1204 3452919540019727 1205 3503386657293164 1206 3572616879906576 1207 3662420109066984 1208 3775260774230022 1209 3914425918877568 1210 4084261985491128 1211 4290529605364665 1212 4540932170266545 1213 4845789970818138 1214 5219327738924838 1215 5681906728561683 1216 6260959108677210 1217 6998644874227770 1218 7971281048519283 1219 9252905977757538 1220 11009842381407312 1221 13930148894444184 1222 17638350751428126 1223 22349794473772659 1224 56678600914995057 1225 143830921235537742 1226 927972354829010775 1227 0 1228 143830921235537742 1229 56678600914995057 1230 44699588947545318 1231 35276701502856252 1232 27860297788888368 1233 23395915060490538 1234 20138677716295818 1235 17666082323745438 1236 15789625630879725 1237 14315598394434918 1238 13136890734121338 1239 12183768126753993 1240 11404480732897878 1241 10762845931201275 1242 10232584623018108 1243 9794052710631168 1244 9432523857848898 1245 9136844385435228 1246 8898528544543032 1247 8711152057455468 1248 8569918961556292 1249 8471360292533947 1250 8413129064491496 1251 8393866902566401 1252 8413129064491496 1253 8471360292533947 1254 8569918961556292 1255 8711152057455468 1256 8898528544543032 1257 9136844385435228 1258 9432523857848898 1259 9794052710631168 1260 10232584623018108 1261 10762845931201275 1262 11404480732897878 1263 12183768126753993 1264 13136890734121338 1265 14315598394434918 1266 15789625630879725 1267 17666082323745438 1268 20138677716295818 1269 23395915060490538 1270 27860297788888368 1271 35276701502856252 1272 44699588947545318 1273 56678600914995057 1274 143830921235537742 1275 365225623668676437