0 1 1 1 2 0 3 1 4 0 5 1 6 1 7 0 8 1 9 2 10 1 11 0 12 2 13 2 14 4 15 1 16 0 17 4 18 4 19 4 20 8 21 1 22 0 23 9 24 8 25 8 26 8 27 17 28 1 29 0 30 21 31 18 32 16 33 16 34 17 35 38 36 1 37 0 38 51 39 42 40 36 41 32 42 34 43 38 44 89 45 1 46 0 47 127 48 102 49 84 50 72 51 68 52 76 53 89 54 216 55 1 56 0 57 323 58 254 59 204 60 168 61 153 62 152 63 178 64 216 65 539 66 1 67 0 68 835 69 646 70 508 71 408 72 357 73 342 74 356 75 432 76 539 77 1374 78 1 79 0 80 2188 81 1670 82 1292 83 1016 84 867 85 798 86 801 87 864 88 1078 89 1374 90 3562 91 1 92 0 93 5798 94 4376 95 3340 96 2584 97 2159 98 1938 99 1869 100 1944 101 2156 102 2748 103 3562 104 9360 105 1 106 0 107 15511 108 11596 109 8752 110 6680 111 5491 112 4826 113 4539 114 4536 115 4851 116 5496 117 7124 118 9360 119 24871 120 1 121 0 122 41835 123 31022 124 23192 125 17504 126 14195 127 12274 128 11303 129 11016 130 11319 131 12366 132 14248 133 18720 134 24871 135 66706 136 1 137 0 138 113634 139 83670 140 62044 141 46384 142 37196 143 31730 144 28747 145 27432 146 27489 147 28854 148 32058 149 37440 150 49742 151 66706 152 180340 153 1 154 0 155 310572 156 227268 157 167340 158 124088 159 98566 160 83144 161 74315 162 69768 163 68453 164 70074 165 74802 166 84240 167 99484 168 133412 169 180340 170 490912 171 1 172 0 173 853467 174 621144 175 454536 176 334680 177 263687 178 220324 179 194732 180 180360 181 174097 182 174498 183 181662 184 196560 185 223839 186 266824 187 360680 188 490912 189 1344379 190 1 191 0 192 2356779 193 1706934 194 1242288 195 909072 196 711195 197 589418 198 516022 199 472608 200 450065 201 443802 202 452374 203 477360 204 522291 205 600354 206 721360 207 981824 208 1344379 209 3701158 210 1 211 0 212 6536382 213 4713558 214 3413868 215 2484576 216 1931778 217 1589730 218 1380479 219 1252368 220 1179332 221 1147290 222 1150526 223 1188720 224 1268421 225 1400826 226 1623060 227 1963648 228 2688758 229 3701158 230 10237540 231 1 232 0 233 18199284 234 13072764 235 9427116 236 6827736 237 5279724 238 4318092 239 3723315 240 3350376 241 3125122 242 3006312 243 2974270 244 3023280 245 3158617 246 3402006 247 3787140 248 4418208 249 5377516 250 7402316 251 10237540 252 28436824 253 1 254 0 255 50852019 256 36398568 257 26145528 258 18854232 259 14508939 260 11801736 261 10113426 262 9036360 263 8360429 264 7966452 265 7793656 266 7815600 267 8033333 268 8471662 269 9197340 270 10309152 271 12099411 272 14804632 273 20475080 274 28436824 275 79288843 276 1 277 0 278 142547559 279 101704038 280 72797136 281 52291056 282 40065243 283 32431746 284 27640908 285 24544944 286 22549065 287 21312114 288 20652476 289 20479680 290 20767285 291 21546038 292 22903180 293 25036512 294 28231959 295 33310422 296 40950160 297 56873648 298 79288843 299 221836402 300 1 301 0 302 400763223 303 285095118 304 203408076 305 145594272 306 111118494 307 89557602 308 75958563 309 67083552 310 61248726 311 57481290 312 55250182 313 54269280 314 54417748 315 55699510 316 58249820 317 62345824 318 68563329 319 77724318 320 92137860 321 113747296 322 158577686 323 221836402 324 622599625 325 1 326 0 327 1129760415 328 801526446 329 570190236 330 406816152 331 309387828 332 248382516 333 209753331 334 184348872 335 167398308 336 156133116 337 149016270 338 145182960 339 144202058 340 145952728 341 150583900 342 158564576 343 170736133 344 188759058 345 214988340 346 255931416 347 317155372 348 443672804 349 622599625 350 1752360040 351 1 352 0 353 3192727797 354 2259520830 355 1603052892 356 1140380472 357 864484323 358 691572792 359 581737998 360 509064264 361 460018713 362 426725928 363 404764308 364 391575600 365 385774081 366 386761388 367 394583920 368 409911520 369 434234417 370 470047066 371 522114540 372 597173304 373 713599587 374 887345608 375 1245199250 376 1752360040 377 4945087837 378 1 379 0 380 9043402501 381 6385455594 382 4519041660 383 3206105784 384 2423308503 385 1932376722 386 1619736276 387 1411858512 388 1270303881 389 1172663658 390 1106257464 391 1063614240 392 1040478285 393 1034676766 394 1045611320 395 1074115456 396 1122556465 397 1195474034 398 1300167580 399 1450278024 400 1665065703 401 1996527618 402 2490398500 403 3504720080 404 4945087837 405 13988490338 406 1 407 0 408 25669818476 409 18086805002 410 12770911188 411 9038083320 412 6812974791 413 5416807242 414 4525829691 415 3931045344 416 3523109898 417 3238214346 418 3040049454 419 2906953920 420 2826191214 421 2790645510 422 2797253740 423 2846307776 424 2941501252 425 3090466930 426 3306725420 427 3611476648 428 4043730993 429 4658564442 430 5603396625 431 7009440160 432 9890175674 433 13988490338 434 39658308814 435 1 436 0 437 73007772802 438 51339636952 439 36173610004 440 25541822376 441 19205927055 442 15229002474 443 12686732751 444 10984036104 445 9809414076 446 8980988868 447 8394846798 448 7988451120 449 7724236212 450 7580069604 451 7544523900 452 7614536032 453 7794709442 454 8098133704 455 8548345900 456 9185094152 457 10069683061 458 11313656502 459 13074592125 460 15771240360 461 19780351348 462 27976980676 463 39658308814 464 112666081616 465 1 466 0 467 208023278209 468 146015545604 469 102679273904 470 72347220008 471 54276372549 472 42930895770 473 35667926847 474 30790272744 475 27409238241 476 25005816216 477 23282592684 478 22059451440 479 21226577757 480 20717015832 481 20492755560 482 20537303520 483 20852662669 484 21459314084 485 22399737520 486 23744748040 487 25610296289 488 28173223054 489 31752580875 490 36799560840 491 44505790533 492 55953961352 493 79316617628 494 112666081616 495 320689359825 496 1 497 0 498 593742784829 499 416046556418 500 292031091208 501 205358547808 502 153737842517 503 121323656286 504 100548676935 505 86564856168 506 76833134301 507 69870674106 508 64825849608 509 61180535520 510 58615450509 511 56931369702 512 56008554480 513 55784294208 514 56242095465 515 57408661738 516 59357256920 517 62219770912 518 66206183905 519 71653157846 520 79070152375 521 89370362040 522 103846844577 523 125896413042 524 158633235256 525 225332163232 526 320689359825 527 914432144654 528 1 529 0 530 1697385471211 531 1187485569658 532 832093112836 533 584062182416 534 436386914092 535 343649295038 536 284152773933 537 244028249640 538 216011377197 539 195860346066 540 181134891678 541 170345298240 542 162566356722 543 157211299974 544 153914238780 545 152463521664 546 152767163286 547 154837944930 548 158794482940 549 164876705552 550 173483988484 551 185233395670 552 201099678875 553 222549725080 554 252199479687 555 293758297098 556 356924779326 557 450664326464 558 641378719650 559 914432144654 560 2611817615865 561 1 562 0 563 4859761676391 564 3394770942422 565 2374971139316 566 1664186225672 567 1241132137634 568 975453102088 569 804862822589 570 689629204152 571 608940863685 572 550648668402 573 507754405158 574 475974897840 575 452634392364 576 436015897692 577 425021524860 578 418977191904 579 417526474788 580 420577388172 581 428287485900 582 441083577064 583 459716711714 584 485378047576 585 519870686875 586 566012292920 587 628026155299 588 713413007238 589 832824485094 590 1013994734544 591 1282757439300 592 1828864289308 593 2611817615865 594 7471579292256 595 1 596 0 597 13933569346707 598 9719523352782 599 6789541884844 600 4749942278632 601 3536395729553 602 2774295366476 603 2284613844364 604 1953374940216 605 1720880282583 606 1552290810210 607 1427518600326 608 1334245152240 609 1264740564549 610 1214001438504 611 1178771129880 612 1156971092448 613 1147383111993 614 1149476042376 615 1163332620360 616 1189654532040 617 1229849243773 618 1286207458796 619 1362247979500 620 1463220633400 621 1597263371351 622 1776538272926 623 2022573749514 624 2365987713936 625 2886204238425 626 3657728578616 627 5223635231730 628 7471579292256 629 21405148638963 630 1 631 0 632 40002464776083 633 27867138693414 634 19439046705564 635 13579083769688 636 10093627342093 637 7904884571942 638 6497691779378 639 5544680790816 640 4874393948039 641 4386807993078 642 4024206598230 643 3751143767280 644 3545300339889 645 3392134779414 646 3282058876560 647 3208788360384 648 3168404195241 649 3158816214786 650 3179493272880 651 3231390058416 652 3317048746905 653 3440904431422 654 3609832625750 655 3834163767520 656 4129148343895 657 4518282379174 658 5036605219378 659 5745970162416 660 6734476556325 661 8229889301886 662 10447270463460 663 14943158584512 664 21405148638963 665 61407613415046 666 1 667 0 668 114988706524270 669 80004929552166 670 55734277386828 671 38878093411128 672 28855553010587 673 22562225823502 674 18514071760601 675 15769678925232 676 13836032158564 677 12425635036374 678 11372496412914 679 10574557484400 680 9967382119233 681 9508777470654 682 9170653106460 683 8934246907008 684 8787374696778 685 8722811450082 686 8737402551180 687 8831681303328 688 9009908385462 689 9280525877670 690 9657142783375 691 10160183511920 692 10819852187356 693 11680389432230 694 12809633746922 695 14308592365232 696 16355157351075 697 19203075037734 698 23506358542785 699 29886317169024 700 42810297277926 701 61407613415046 702 176396319939316 703 1 704 0 705 330931069469828 706 229977413048540 707 160009859104332 708 111468554773656 709 82615948498647 710 64500647906018 711 52843107849781 712 44933028093144 713 39351189540278 714 35270330586024 715 32212599708562 716 29883932179920 717 28098271281465 718 26733311553438 719 25707026790060 720 24963866351328 721 24466735224636 722 24192182530356 723 24127619283660 724 24269890868808 725 24624894548196 726 25208157704868 727 26046455311875 728 27180856580440 729 28671619278926 730 30606816859544 731 33114687859690 732 36391144361968 733 40727548697775 734 46636039377354 735 54848169933165 736 67244213630304 737 85620594555852 738 122815226830092 739 176396319939316 740 507327389409144 741 1 742 0 743 953467954114363 744 661862138939656 745 459954826097080 746 320019718208664 747 236870678894019 748 184670943702858 749 151067306937779 750 128248441523064 751 112124546954651 752 100312679829948 753 91435893411512 754 84646247409360 755 79406333039187 756 75361798242990 757 72273639635820 758 69978307283808 759 68364386451201 760 67358425570872 761 66916472180280 762 67019309629896 763 67670410968681 764 68896175041944 765 70748485787250 766 73309982273400 767 76703257439707 768 81105266979724 769 86772379685032 770 94076178149360 771 103582663223475 772 116132882371058 773 133202698409115 774 156903165137376 775 192646337750667 776 245630453660184 777 352792639878632 778 507327389409144 779 1460795343523507 780 1 781 0 782 2750016719520991 783 1906935908228726 784 1323724277879312 785 919909652194160 786 680041901193411 787 529475635174866 788 432518789198799 789 366635261781576 790 320027361022831 791 285823984259166 792 260053686720724 793 240269500935360 794 224918463602371 795 212974100426682 796 203740993241100 797 196739475329376 798 191637944820861 799 188211356938002 800 186315897921360 801 185873944530768 802 186866280116697 803 189330048505734 804 193362010735500 805 199127680785360 806 206877749660895 807 216975473632718 808 229938874503572 809 246513386575808 810 267775615453875 811 295361582723242 812 331700837214855 813 381050543905056 814 449508121418223 815 552668520735414 816 705585279757264 817 1014654778818288 818 1460795343523507 819 4210812063044498 820 1 821 0 822 7939655757745265 823 5500033439041982 824 3813871816457452 825 2647448555758624 826 1954808010912590 827 1520093661491154 828 1240087671856923 829 1049708522100456 830 914890768982729 831 815802586355046 832 740978916980458 833 683352753426720 834 638434055316596 835 603249207231706 836 575776530910980 837 554612944848480 838 538777660973517 839 527591038373322 840 520599578593260 841 517529836034016 842 518262166186026 843 522819373669158 844 531368234149875 845 544233962342880 846 561930111269658 847 585208493290230 848 615140028013954 849 653237941209568 850 701668319297100 851 763550840786090 852 843617089924395 853 948890570116512 854 1091662580587113 855 1289559881715966 856 1587566879453844 857 2029309557636576 858 2921590687047014 859 4210812063044498 860 12150467820789763 861 1 862 0 863 22944749046030949 864 15879311515490530 865 11000066878083964 866 7627743632914904 867 5625828180987076 868 4369570847922260 869 3560219365071387 870 3009650978888712 871 2619411543574749 872 2332207637443914 873 2114911799560898 874 1947097884036240 875 1815776317358542 876 1712330911260056 877 1630887207030340 878 1567348388280864 879 1518826176957285 880 1483288008912234 881 1459336337164860 882 1446069914347656 883 1443000171788412 884 1450007464977564 885 1467329721607875 886 1495581466258680 887 1535805819712764 888 1589568111068292 889 1659105349233690 890 1747563591945776 891 1859356908265350 892 2000777532502952 893 2180867709247275 894 2413320111398688 895 2718453877148301 896 3131788284167346 897 3704322718725636 898 4565946504682296 899 5843181374094028 900 8421624126088996 901 12150467820789763 902 35095216866820712 903 1 904 0 905 66368199913921497 906 45889498092061898 907 31758623030981060 908 22000133756167928 909 16208955219944171 910 12575380639853464 911 10233994880660030 912 8640532391633928 913 7510193877875073 914 6677312543361234 915 6046087048453582 916 5557432465999440 917 5173746952336039 918 4870056492530212 919 4629295063961840 920 4439514808570912 921 4292236203003063 922 4181421798060570 923 4102829525991420 924 4053599846912616 925 4031997750724017 926 4037263681536168 927 4069548982056750 928 4129925342711160 929 4220469280980879 930 4344433421253336 931 4506532263770076 932 4713385524405360 933 4974212660245575 934 5301877574703892 935 5714656943512620 936 6238768709033760 937 6913863010385049 938 7798766903710842 939 8996212316905116 940 10653875177592024 941 13147158091711563 942 16843248252177992 943 24300935641579526 944 35095216866820712 945 101463416780742209 946 1 947 0 948 192137918101841817 949 132736399827842994 950 91778996184123796 951 63517246061962120 952 46750284231856847 953 36231782256345794 954 29452865182814692 955 24837560609242320 956 21561328514308737 957 19144724282375418 958 17310471091304742 959 15887528010534960 960 14766976801482059 961 13876400796209554 962 13166221747112680 963 12601621927690112 964 12157760410891879 965 11816790027688926 966 11565967438979100 967 11396433238123752 968 11302431025584237 969 11280828929395638 970 11330867393668500 971 11454094622975280 972 11654479167397023 973 11938714883301846 974 12316760284981608 975 12802697518352544 976 13416039368278875 977 14183756995728194 978 15143318536785270 979 16347815491456128 980 17873299113534105 981 19834659133059858 982 22402332632293132 983 25873696859866344 984 30676702213993647 985 37897308567400482 986 48601871283159052 987 70190433733641424 988 101463416780742209 989 293601334882584026 990 1 991 0 992 556704809728838604 993 384275836203683634 994 265472799655685988 995 183557992368247592 996 134974147881669505 997 104500635341797658 998 84858647916178307 999 71481111005482848 1000 61978912816581530 1001 54963386602338042 1002 49631374012970334 1003 45487369291019760 1004 42215674054488781 1005 39606206204803274 1006 37514917992211060 1007 35840391761775424 1008 34509964892946404 1009 33471061513796158 1010 32685678530899380 1011 32126798083521960 1012 31776052268620989 1013 31622237602442718 1014 31660447959892875 1015 31891698038211360 1016 32322983126185734 1017 32967780270301302 1018 33847057848558138 1019 34990930299644352 1020 36441214714354050 1021 38255268771600090 1022 40511903039682015 1023 43320216736500288 1024 46834465222051044 1025 51275357201563410 1026 56976011340399068 1027 64430578454961288 1028 74500562519698857 1029 88427053323934458 1030 109354210387107867 1031 140380867467282848 1032 202926833561484418 1033 293601334882584026 1034 850306144611422630 1035 1 1036 0 1037 1614282136160911722 1038 1113409619457677208 1039 768551672407367268 1040 530945599311371976 1041 390060733782526133 1042 301706918794320070 1043 244751488037368199 1044 205949078088702408 1045 178371846444237292 1046 157994482764346980 1047 142488779532407646 1048 130418209085177520 1049 120867132653520561 1050 113225795242600966 1051 107075573816061860 1052 102121123552136608 1053 98150116591779958 1054 95008054010995208 1055 92582194840087540 1056 90791038443196728 1057 89577396172549845 1058 88903871444243646 1059 88750056778065375 1060 89111046048920760 1061 89997057950508708 1062 91434116452477116 1063 93465869388350106 1064 96156782678562672 1065 99597135859569900 1066 103910582325612636 1067 109265389959712275 1068 115891666402182816 1069 124107051808707474 1070 134359858152120648 1071 147290927149328860 1072 163866746779153512 1073 185521008627485389 1074 214751415215269398 1075 255159824236585023 1076 315856951801386408 1077 405853667122968836 1078 587202669765168052 1079 850306144611422630 1080 2464588280772334352 1081 1 1082 0 1083 4684478925507420069 1084 3228564272321823444 1085 2226819238915354416 1086 1537103344814734536 1087 1128259398536665449 1088 871900463749176062 1089 706629362439328585 1090 594003611416534056 1091 513919227267641657 1092 454699289451543672 1093 409589772639449740 1094 374423070304136880 1095 346541803221949797 1096 324175262385338046 1097 306106495878191740 1098 291475457985974048 1099 279662126735337211 1100 270213302368304716 1101 262795793440789040 1102 257165645282096824 1103 253147693038068871 1104 250621985585626830 1105 249515032353591375 1106 249794646191142360 1107 251467700643792903 1108 254580508392517992 1109 259221855882270948 1110 265529055164874864 1111 273697785861763275 1112 283997020029482088 1113 296791282961203410 1114 312573519691529760 1115 332015260538955093 1116 356041342580436708 1117 385955148027223408 1118 423618370156635240 1119 471836895958092761 1120 534773132006651246 1121 619673858860277913 1122 736999554203234952 1123 913170751026679881 1124 1174405339530336104 1125 1700612289222845260 1126 2464588280772334352 1127 7149067206279754421 1128 1 1129 0 1130 13603677110519480289 1131 9368957851014840138 1132 6457128544643646888 1133 4453638477830708832 1134 3266344607731310889 1135 2521991596729016886 1136 2042082665096754461 1137 1714965643672977240 1138 1482259011821814149 1139 1310064968953134762 1140 1178776469451527336 1141 1076294293067167200 1142 994901301445960293 1143 929452676841437142 1144 876409420720352940 1145 833266896443134432 1146 798215331325626191 1147 769927020329466022 1148 747419994371387080 1149 729968110113960224 1150 717040921087596343 1151 708263247051866394 1152 703388410718844375 1153 702281457486808920 1154 704910200204939883 1155 711342976449292422 1156 721752825065689176 1157 736428547885353312 1158 755793948759003675 1159 780437659201415418 1160 811157420594424780 1161 849025441296218304 1162 895484393311017105 1163 952493491680778506 1164 1022745863008154168 1165 1110032328027207072 1166 1219764111842128345 1167 1360092296363372854 1168 1543109413240299901 1169 1789856060207856312 1170 2130731752395586389 1171 2642412013943256234 1172 3401224578445690520 1173 4929176561544668704 1174 7149067206279754421 1175 20752744316799234710 1176 1 1177 0 1178 39532221379621112004 1179 27207354221038960578 1180 18737915702029680276 1181 12914257089287293776 1182 9463981765390256268 1183 7301240887869989046 1184 5906769792339013233 1185 4956065793942684984 1186 4279474453424697835 1187 3778522972621841634 1188 3396252852555361006 1189 3097514810237590080 1190 2859884119965119170 1191 2668404415353392598 1192 2512779895985140380 1193 2385715324080458592 1194 2281929382401172969 1195 2197535858012131982 1196 2129646631595765860 1197 2076109185802460848 1198 2035330206982063268 1199 2006155872659641402 1200 1987791129139276125 1201 1979747006019816600 1202 1981809339574218651 1203 1994025151776984942 1204 2016705073317395466 1205 2050442016496762944 1206 2096148159151653150 1207 2155114475445509466 1208 2229100145159453955 1209 2320463323954530432 1210 2432352660439921542 1211 2568987507218449410 1212 2736083318578730476 1213 2941484203794216912 1214 3196220211629433316 1215 3516028072642155830 1216 3924601106115093449 1217 4457092542086230424 1218 5174634255817852659 1219 6165628032534264546 1220 7652755301502803670 1221 9858353123089337408 1222 14298134412559508842 1223 20752744316799234710 1224 60284965696420346714 1225 1 1226 0 1227 114956499435014161638 1228 79064442759242224008 1229 54414708442077921156 1230 37475831404059360552 1231 27442796314735499274 1232 21154782769695866952 1233 17100274711063921713 1234 14335531181407043352 1235 12367219735810681511 1236 10909087011141994110 1237 9795559554933769942 1238 8924460050510437680 1239 8230586628784092188 1240 7670436657407954620 1241 7214044497718808220 1242 6840156395130626784 1243 6533361542744856189 1244 6282291815856362338 1245 6078465509398280660 1246 5915521350332368216 1247 5788701835477448086 1248 5694500170708963352 1249 5630419005846662125 1250 5594808610060031880 1251 5586764486940572355 1252 5606072472761239374 1253 5653195115503885026 1254 5729297722992382704 1255 5836316735233365300 1256 5977077810537801828 1257 6155476908900698835 1258 6376746363823851552 1259 6647839823100016836 1260 6977992742805337164 1261 7379540044661284860 1262 7869155137125232584 1263 8469691401749293586 1264 9213256793941361624 1265 10145640630359452105 1266 11335755047983089976 1267 12885853931154260543 1268 14973668079011785326 1269 17856429036839875230 1270 22181294526951009168 1271 28596268825119017684 1272 41505488633598469420 1273 60284965696420346714 1274 175241465131434508352