100 1 101 0 102 1 103 0 104 2 105 0 106 3 107 0 108 5 109 0 110 7 111 0 112 11 113 0 114 15 115 0 116 22 117 0 118 30 119 0 120 42 121 0 122 55 123 1 124 75 125 2 126 97 127 4 128 128 129 7 130 164 131 12 132 212 133 19 134 267 135 30 136 340 137 45 138 423 139 67 140 530 141 97 142 653 143 139 144 807 145 195 146 984 147 271 148 1204 149 370 150 1456 151 501 152 1763 153 670 154 2117 155 889 156 2543 157 1167 158 3032 159 1522 160 3618 161 1967 162 4289 163 2527 164 5086 165 3222 166 6002 167 4085 168 7082 169 5145 170 8323 171 6448 172 9783 173 8034 174 11461 175 9964 176 13427 177 12295 178 15693 179 15107 180 18342 181 18478 182 21397 183 22514 184 24967 185 27319 186 29091 187 33032 188 33904 189 39792 190 39478 191 47778 192 45978 193 57175 194 53515 195 68214 196 62308 197 81135 198 72515 199 96236 200 84417 201 113829 202 98250 203 134294 204 114374 205 158035 206 133121 207 185535 208 154966 209 217312 210 180366 211 253982 212 209937 213 296207 214 244314 215 344765 216 284295 217 400504 218 330735 219 464407 220 384684 221 537551 222 447279 223 621182 224 519881 225 716666 226 604009 227 825574 228 701420 229 949644 230 814107 231 1090856 232 944349 233 1251411 234 1094740 235 1433814 236 1268210 237 1640848 238 1468129 239 1875673 240 1698248 241 2141820 242 1962897 243 2443274 244 2266881 245 2784500 246 2615734 247 3170538 248 3015560 249 3607031 250 3473417 251 4100341 252 3997033 253 4657614 254 4595340 255 5286875 256 5278109 257 5997152 258 6056594 259 6798588 260 6943081 261 7702577 262 7951714 263 8721913 264 9097891 265 9870990 266 10399298 267 11165927 268 11875195 269 12624868 270 13547627 271 14268134 272 15440582 273 16118560 274 17581478 275 18201709 276 20000122 277 20546316 278 22730486 279 23184484 280 25809538 281 26152288 282 29279274 283 29490025 284 33185405 285 33242895 286 37579761 287 37461357 288 42518752 289 42201990 290 48066179 291 47527850 292 54291554 293 53509581 294 61273288 295 60225879 296 69096853 297 67764753 298 77858488 299 76224174 300 87663147 301 85713617 302 98628743 303 96354769 304 110884002 305 108283462 306 124573233 307 121650582 308 139854075 309 136624274 310 156902977 311 153391164 312 175912787 313 172159016 314 197098986 315 193158128 316 220697290 317 216644590 318 246970630 319 242902056 320 276206791 321 272245469 322 308726366 323 305023370 324 344880430 325 341622345 326 385059528 327 382469717 328 429691614 329 428038932 330 479252122 331 478852920 332 534262240 333 535490274 334 595300365 335 598589526 336 663000765 337 668856473 338 738066523 339 747069227 340 821268958 341 834086993 342 913462145 343 930856294 344 1015583252 345 1038421090 346 1128669056 347 1157930538 348 1253857361 349 1290650954 350 1392405708 351 1437975005 352 1545694393 353 1601435957 354 1715247579 355 1782718900 356 1902738235 357 1983677227 358 2110012222 359 2206346434 360 2339095503 361 2452963552 362 2592221547 363 2725983524 364 2871841612 365 3028102263 366 3180655844 367 3362276472 368 3521627176 369 3731750429 370 3898016990 371 4140080077 372 4313403272 373 4591164583 374 4771721437 375 5089274924 376 5277287922 377 5639091231 378 5834846842 379 6245737181 380 6449600003 381 6914823499 382 7127260656 383 7652489413 384 7874091012 385 8465453904 386 8696964125 387 9361064836 388 9603410706 389 10347359518 390 10601690305 391 11433123470 392 11700848999 393 12627961165 394 12910801816 395 13942366423 396 14242403109 397 15387805715 398 15707541936 399 16976801477 400 17319227833 401 18723030408 402 19091701103 403 20641422688 404 21040536587 405 22748277024 406 23182771830 407 25061378852 408 25537031733 409 27600135783 410 28123677465 411 30385717230 412 30964956129 413 33441214040 414 34085173648 415 36791804141 416 37510873549 417 40464939535 418 41271038411 419 44490542818 420 45397302429 421 48901227138 422 49924186069 423 53732527861 424 54889348676 425 59023161476 426 60333861596 427 64815299460 428 66302507341 429 71154871652 430 72844098322 431 78091889887 432 80011829872 433 85680804456 434 87863652090 435 93980884823 436 96462686315 437 103056638507 438 105877658549 439 112978259733 440 116183389579 441 123822119985 442 127461301058 443 135671296406 444 139799990805 445 148616147353 446 153295823505 447 162754932538 448 168053605785 449 178194488182 450 184187275092 451 195050955602 452 201820690492 453 213450571054 454 221088436948 455 233530521163 456 242136749795 457 255439867941 458 265124453343 459 279340550452 460 290224041458 461 305408467692 462 317622771959 463 333834652068 464 347523928039 465 364826534400 466 380148095154 467 398609317671 468 415734631285 469 435427455622 470 454543156094 471 475546257523 472 496855264290 473 519253615420 474 542976260846 475 566861879158 476 593237155805 477 618709870566 478 647996686864 479 675165072551 480 707643639017 481 736625978369 482 772599200955 483 803524642974 484 843319662066 485 876329421401 486 920299155471 487 955547942114 488 1004072791430 489 1041730294304 490 1095219850732 491 1135472490422 492 1194367421599 493 1237420175761 494 1302194115527 495 1348272654955 496 1419434287866 497 1468787206502 498 1546882358113 499 1599783764098 500 1685397705004 501 1742149928573 502 1835909689141 503 1896846406476 504 1999423325747 505 2064912830952 506 2177025120784 507 2247474072566 508 2369889643706 509 2445746995118 510 2579286303671 511 2661047776304 512 2806586961175 513 2894799740270 514 3053273794088 515 3148541843803 516 3320948106221 517 3423937754378 518 3611339453633 519 3722785677496 520 3926315836078 521 4047028871356 522 4267894277722 523 4398767023078 524 4638252613166 525 4780268416201 526 5039741750580 527 5193983091207 528 5474899293144 529 5642556920427 530 5946463744471 531 6128846819557 532 6457390247237 533 6655937018718 534 7010867026958 535 7227156637673 536 7610333568770 537 7846098480566 538 8259499645070 539 8516639329737 540 8962366295928 541 9242961646921 542 9723247834631 543 10029576988441 544 10546796056873 545 10881351047596 546 11438025672955 547 11803530660405 548 12402342230381 549 12801772683121 550 13445571493922 551 13882175121484 552 14573991633210 553 15051310416997 554 15794367144899 555 16316261305638 556 17113985944251 557 17684659164857 558 18540698505966 559 19164725303630 560 20082960587926 561 20765315111738 562 21749878372990 563 22495965578890 564 23551257653614 565 24366946103590 566 25497655866230 567 26389313148836 568 27600438692847 569 28574968685126 570 29871840002601 571 30936723029719 572 32325026959567 573 33488362032663 574 34974169040386 575 36244719289871 576 37834512887121 577 39221753349176 578 40922461732151 579 42436630651601 580 44255661420893 581 45907814209341 582 47853091757889 583 49655158832176 584 51735165321265 585 53700012929536 586 55923832468543 587 58065327792067 588 60442694786525 589 62775774414447 590 65317125735337 591 67857868845909 592 70574400847894 593 73340106189628 594 76243836260466 595 79253104330966 596 82356938066525 597 85629757565911 598 88947561308757 599 92505401330781 600 96052081218962 601 99917988267872 602 103709575599014 603 107908276940501 604 111962021071542 605 116520033526738 606 120854502174179 607 125800247932364 608 130435436171930 609 135799364740537 610 140756812662832 611 146571530599290 612 151874450982750 613 158174858571723 614 163848274636783 615 170671711204168 616 176742605896832 617 184129002983670 618 190626479953794 619 198618524115452 620 205573981931205 621 214217286435536 622 221664606339436 623 231007893606149 624 238983642429667 625 249078936581148 626 257622585283671 627 268525416702943 628 277679576256612 629 289449197640716 630 299259872883060 631 311959488774751 632 322476352063639 633 336173361463234 634 347450046959174 635 362216301092896 636 374310721596787 637 390222796615874 638 403197484017257 639 420336970774469 640 434259442166089 641 452713253047514 642 467656403789536 643 487517098861969 644 503559624791289 645 524925757449296 646 542152607802261 647 565129092300109 648 583631955663773 649 608330456999064 650 628208282178940 651 654747630817350 652 676107185097722 653 704613817332660 654 727570284339511 655 758178710936979 656 782856330756839 657 815709635019343 658 842242389175677 659 877492757256773 660 906025101355034 661 943834386396883 662 974522033476517 663 1015062356568285 664 1048073114181687 665 1091527504212401 666 1127042168713842 667 1173605244358553 668 1211818555656218 669 1261697252098595 670 1302818912882977 671 1356233256787855 672 1400489019706232 673 1457672955702137 674 1505305783081846 675 1566508055537613 676 1617779355408986 677 1683264449507794 678 1738455393136929 679 1808504539402090 680 1867917464401245 681 1942829711470003 682 2006789616409999 683 2086882976633647 684 2155739111533883 685 2241351785157787 686 2315479344570780 687 2406971027508983 688 2486772950967848 689 2584526233002000 690 2670435120372982 691 2774856979359857 692 2867337126315351 693 2978860526387522 694 3078410088503084 695 3197495688498946 696 3304648979641079 697 3431786961114989 698 3547116895690896 699 3682828917430121 700 3806949602732076 701 3951790892658127 702 4085360381997516 703 4239921974246829 704 4383645187759352 705 4548556317466377 706 4703188142583412 707 4879118807151392 708 5045467386297496 709 5233131087597032 710 5412061306554719 711 5612217983901162 712 5804655169239581 713 6018114339722218 714 6225048180269718 715 6452672297587446 716 6675160999307792 717 6917869049988057 718 7157043741013095 719 7415815090649188 720 7672884486861471 721 7948762997896835 722 8225018347791900 723 8519116783095468 724 8815937103574076 725 9129441840275012 726 9448299464220113 727 9782475533970799 728 10124941982709809 729 10481138466026677 730 10848890669974069 731 11228546463001160 732 11623373345168541 733 12028023330140348 734 12451832778538179 735 12883114418664820 736 13337940664186466 737 13797601058245955 738 14285612487020346 739 14775515907179523 740 15299023326179263 741 15821159278670656 742 16382624666955358 743 16939116502281615 744 17541162269097202 745 18134276386304666 746 18779695172222236 747 19411850847368932 748 20103615892572374 749 20777395781350518 750 21518671901418732 751 22236833250067729 752 23030988446687298 753 23796475067034346 754 24647092818747131 755 25463047866010649 756 26373940130147722 757 27243719745951586 758 28218940722203102 759 29146128586379291 760 30189989277518021 761 31178412138422697 762 32295495764517536 763 33349239997120580 764 34544418303773208 765 35667847573148654 766 36946298096804923 767 38144072182637183 768 39511296519133740 769 40788391387716636 770 42250234534665070 771 43611963720999042 772 45174634546724442 773 46626671942920980 774 48296764860914111 775 49845168981487920 776 51629686890592508 777 53280926721433070 778 55187305300238945 779 56948287810742469 780 58984421234842133 781 60862520671807331 782 63036788853084617 783 65039877905655022 784 67361175332018672 785 69497658299261789 786 71975424585870371 787 74254272647393349 788 76898524888909811 789 79329313624248813 790 82150680672655420 791 84743629942226206 792 87753388712247031 793 90519405061349675 794 93729519003170568 795 96680240715495842 796 100103400571196293 797 103251245550656290 798 106900912550907532 799 110259129173664432 800 114149580807430241 801 117732301941862668 802 121878680474749420 803 125700980828407429 804 130119344720735692 805 134197301733067339 806 138904680154751230 807 143255438613617452 808 148269889227859403 809 152911729851789587 810 158252400088546929 811 163204812274105148 812 168892004289029030 813 174175763290597196 814 180231002857346949 815 185868251622466487 816 192314361180673196 817 198328697136443839 818 205189873273440248 819 211606440313405587 820 218908335932175120 821 225753921930280249 822 233523733415381081 823 240826873545968157 824 249093433213914211 825 256884519438451968 826 265678393622169113 827 273989790654571164 828 283343383746502971 829 292209551895670632 830 302157216741528024 831 311614841979400844 832 322192996990185666 833 332281128685847147 834 343528382107295160 835 354288578816294413 836 366245860571746587 837 377722344367302550 838 390433045966071053 839 402672865746861950 840 416182988728140103 841 429236193040674881 842 443594506504169942 843 457514326364970415 844 472772534119132570 845 487615576431541703 846 503828494376276345 847 519654946483771985 848 536880690826634500 849 553754536860162650 850 572054723856468904 851 590043973480833031 852 609483931372619105 853 628660861659286111 854 649309855585538237 855 669751266687073639 856 691682737325308121 857 713470222756267791 858 736762039558910208 859 759982271837046808 860 784717001717779418 861 809462034256096933 862 835727226691250101 863 862094812782500425 864 889983302288427292 865 918077232168148317 866 947687459232729089 867 977617916160032979 868 1009054267707463148 869 1040938204155856926 870 1074311374748246767 871 1108272909755048399 872 1143700284741664307 873 1179871123626037518 874 1217477185583366649 875 1255997063203598319 876 1295913823023254286 877 1336930971914688522 878 1379298426037443341 879 1422970070737639753 880 1467936686053526214 881 1514429565102255640 882 1562152793186804013 883 1611643710259686543 884 1662290532647308465 885 1714966938473114298 886 1768714444828638225 887 1824775051519033623 888 1881811052609090081 889 1941466482232183290 890 2001990159769169031 891 2065463628985077432 892 2129686224468526136 893 2197214267260304305 894 2265359812122619960 895 2337193042652812034 896 2409499132081690997 897 2485903049932513557 898 2562621662936909400 899 2643877503001091431 900 2725275871366967090 901 2811681500898159501 902 2898043029888676921 903 2989913895242411219 904 3081539138992754626 905 3179209264846513301 906 3276416959626075361 907 3380240003504710392 908 3483368162133455544 909 3593718527339815576 910 3703125598283978251 911 3820399608390577658 912 3936465703196628890 913 4061082841545835251 914 4184211034527703388 915 4316615252263708955 916 4447232956514451684 917 4587894052982012185 918 4726454477055451553 919 4875869556499327162 920 5022853246288852543 921 5181548255120421372 922 5337464725756943654 923 5505996074780117340 924 5671385537580035093 925 5850341813924564127 926 6025777003736315098 927 6215780777401213149 928 6401868885938587427 929 6603578616230530315 930 6800963337322571980 931 7015075384662112062 932 7224439077623673337 933 7451689826601738076 934 7673755804297253642 935 7914923904090369450 936 8150458852574738901 937 8406367581268005791 938 8656184118287085589 939 8927703877921179021 940 9192663257907366636 941 9480714207541065066 942 9761729181169852192 943 10067284015563788617 944 10365321852336841400 945 10689408734376212392 946 11005494417162599198 947 11349200072503778078 948 11684419673420818435 949 12048892656400275835 950 12404396903921547440 951 12790851044190337609 952 13167859091874344088 953 13577577131821242691 954 13977380539602948334 955 14411717973119184878 956 14835684912675223294 957 15296074036463306666 958 15745653732758242901 959 16233607921950134825 960 16710335343707258249 961 17227453564262586627 962 17732954376752959271 963 18280925947750017777 964 18816921742004840396 965 19397531361705092661 966 19965845174964397373 967 20580978225262087843 968 21183540368267833928 969 21835188512971810422 970 22474042720486163967 971 23164309813710989499 972 23841619735526120579 973 24572728057380814165 974 25290784107931835357 975 26065080945632359369 976 26826307531311194706 977 27646272124838756461 978 28453235269030594365 979 29321486141515751367 980 30176901528477610827 981 31096204222578043295 982 32002945682290983177 983 32976220925022170485 984 33937329382367589227 985 34967661702036414873 986 35986354614757608166 987 37077001434985497887 988 38156682746248903554 989 39311083983376770277 990 40455354615965507428 991 41677142807630513364 992 42889811728304997096 993 44182822722409973929 994 45467918606308994226 995 46836202841281501163 996 48197986367901062548 997 49645820776709714051 998 51088797590470313678 999 52620698162736282162 1000 54149632532992469748