0 1 1 1 2 1 3 2 4 2 5 3 6 3 7 5 8 5 9 8 10 7 11 11 12 11 13 15 14 14 15 21 16 20 17 28 18 26 19 38 20 35 21 51 22 45 23 65 24 61 25 82 26 74 27 108 28 97 29 130 30 116 31 161 32 148 33 201 34 176 35 238 36 224 37 288 38 258 39 354 40 317 41 416 42 373 43 501 44 453 45 596 46 525 47 705 48 638 49 833 50 727 51 993 52 876 53 1148 54 1007 55 1336 56 1199 57 1583 58 1366 59 1816 60 1607 61 2096 62 1821 63 2457 64 2143 65 2750 66 2417 67 3179 68 2806 69 3660 70 3135 71 4124 72 3676 73 4670 74 4061 75 5320 76 4682 77 5965 78 5203 79 6721 80 5915 81 7637 82 6572 83 8465 84 7551 85 9409 86 8239 87 10681 88 9378 89 11776 90 10278 91 13122 92 11611 93 14698 94 12718 95 16147 96 14409 97 17923 98 15649 99 20088 100 17511 101 21932 102 19195 103 24283 104 21409 105 26888 106 23338 107 29538 108 26171 109 32469 110 28163 111 35998 112 31512 113 39267 114 34210 115 43056 116 37919 117 47577 118 41041 119 51986 120 45566 121 56781 122 49210 123 62578 124 54448 125 67669 126 58876 127 74325 128 64907 129 81413 130 69737 131 88403 132 77269 133 96369 134 83008 135 105041 136 91455 137 113877 138 98373 139 123975 140 107537 141 135129 142 115819 143 145889 144 127226 145 157678 146 136121 147 172580 148 148925 149 185433 150 159114 151 200841 152 174477 153 217935 154 186626 155 233638 156 203518 157 252596 158 217128 159 273878 160 235939 161 293885 162 252567 163 316342 164 274100 165 340492 166 292287 167 365718 168 318456 169 392529 170 336738 171 424232 172 365932 173 452200 174 389431 175 484679 176 421063 177 521969 178 447245 179 556775 180 482834 181 595272 182 512526 183 640055 184 553750 185 678604 186 586749 187 727199 188 631468 189 780330 190 667260 191 828159 192 721472 193 882597 194 761014 195 942480 196 818767 197 1001541 198 865479 199 1067051 200 926804 201 1139582 202 979656 203 1208081 204 1052979 205 1279793 206 1107648 207 1370074 208 1187466 209 1446773 210 1250403 211 1536874 212 1338419 213 1636341 214 1409267 215 1725722 216 1511581 217 1832654 218 1584943 219 1950396 220 1690338 221 2054753 222 1782052 223 2178080 224 1900997 225 2309320 226 1995306 227 2438393 228 2132541 229 2577271 230 2228901 231 2738498 232 2380894 233 2879244 234 2498934 235 3038722 236 2656403 237 3224641 238 2785906 239 3393637 240 2964208 241 3579551 242 3103939 243 3794081 244 3299449 245 3978430 246 3459403 247 4201779 248 3671441 249 4443874 250 3834924 251 4668202 252 4086275 253 4915470 254 4262764 255 5189351 256 4525484 257 5450627 258 4734909 259 5744684 260 5003498 261 6058935 262 5238027 263 6356971 264 5563322 265 6673085 266 5798675 267 7055059 268 6137615 269 7387621 270 6405321 271 7770839 272 6782417 273 8188410 274 7078705 275 8567875 276 7496339 277 9005473 278 7808067 279 9490392 280 8248572 281 9928479 282 8617655 283 10428739 284 9091092 285 10954253 286 9478007 287 11487878 288 10028639 289 12039771 290 10413912 291 12667397 292 11008306 293 13237696 294 11481081 295 13869829 296 12101906 297 14585956 298 12600325 299 15249167 300 13278610 301 15980298 302 13826655 303 16782827 304 14580641 305 17500414 306 15179258 307 18358881 308 15978213 309 19257689 310 16595199 311 20117244 312 17523903 313 21043109 314 18203013 315 22062126 316 19154284 317 23031672 318 19931784 319 24103755 320 20927633 321 25250440 322 21789229 323 26362170 324 22918828 325 27494290 326 23796421 327 28856418 328 25027626 329 30090930 330 25960468 331 31440596 332 27291475 333 32889974 334 28354248 335 34250305 336 29823343 337 35800738 338 30908933 339 37471198 340 32408135 341 39007099 342 33697095 343 40764941 344 35362811 345 42520915 346 36683861 347 44353574 348 38496497 349 46242778 350 39860510 351 48330981 352 41860060 353 50290251 354 43417230 355 52396248 356 45471297 357 54801569 358 47165005 359 56993591 360 49389552 361 59378269 362 51214801 363 61990301 364 53638836 365 64350688 366 55594829 367 67138086 368 58200391 369 70009533 370 60193091 371 72835551 372 63106100 373 75751040 374 65326587 375 78911497 376 68380117 377 82026151 378 70799737 379 85411060 380 73887298 381 88970765 382 76597233 383 92416004 384 80133889 385 96012797 386 82858691 387 100108331 388 86572048 389 103857463 390 89452715 391 108020982 392 93643965 393 112408399 394 96790878 395 116510687 396 101088186 397 121150337 398 104487967 399 126205656 400 108982627 401 130720486 402 112791158 403 135791991 404 117641477 405 141012153 406 121650158 407 146377896 408 126984881 409 151914796 410 130893463 411 157975856 412 136661386 413 163692840 414 141204101 415 169627170 416 147185761 417 176393201 418 152012115 419 182717978 420 158299390 421 189444906 422 163506116 423 196810430 424 170437023 425 203441317 426 175873306 427 211303987 428 183087323 429 219122604 430 188726945 431 226843256 432 196856001 433 234983774 434 203001962 435 243637882 436 211211760 437 252202465 438 217911515 439 261294215 440 226491639 441 271071935 442 233732308 443 280174395 444 243206533 445 289688455 446 250618280 447 300743661 448 260796569 449 310698346 450 268343417 451 321626432 452 279175493 453 333248430 454 287720020 455 344072401 456 299298562 457 356126930 458 308024164 459 369037802 460 319666836 461 380926221 462 329771626 463 394058607 464 342400093 465 407500180 466 352522550 467 421185145 468 366119128 469 435440520 470 376369202 471 450689543 472 391309646 473 464871566 474 402705855 475 480115524 476 417875395 477 497099021 478 429918287 479 512851520 480 445925953 481 529550416 482 458862632 483 548221831 484 475947251 485 564311985 486 489682197 487 583422184 488 507840575 489 603097985 490 521690135 491 621803115 492 541464951 493 641664587 494 556414506 495 662752660 496 576890538 497 683626726 498 593068855 499 705391225 500 613660414 501 728674969 502 631351421 503 750756646 504 654818210 505 773572691 506 672016610 507 799862483 508 696017071 509 823505327 510 714558967 511 849723496 512 740564140 513 877010305 514 760503252 515 902164954 516 787662683 517 930550122 518 808575495 519 960878865 520 836234243 521 988583775 522 859403008 523 1019090477 524 888878980 525 1050817705 526 912593840 527 1081909980 528 944842564 529 1114466563 530 968086394 531 1149987624 532 1002461969 533 1182329872 534 1028851517 535 1217222698 536 1063840744 537 1256101534 538 1091230705 539 1292207991 540 1127690746 541 1329878586 542 1157191655 543 1371530423 544 1196580172 545 1408407513 546 1227577210 547 1451350157 548 1267886896 549 1495630169 550 1299175103 551 1537413750 552 1344764793 553 1582246510 554 1377505287 555 1629068119 556 1423057570 557 1674735734 558 1459386725 559 1723340478 560 1506166665 561 1775153286 562 1544491601 563 1823844180 564 1595804270 565 1874167025 566 1634427908 567 1932673082 568 1688202424 569 1983774436 570 1728564892 571 2040556426 572 1784795136 573 2100585318 574 1829190480 575 2155693161 576 1889094854 577 2217317829 578 1933594776 579 2283143672 580 1993702183 581 2343588748 582 2044524799 583 2408924593 584 2109120584 585 2476560730 586 2159430508 587 2544288918 588 2229222200 589 2614133257 590 2278974937 591 2690270813 592 2353096641 593 2759818789 594 2409433630 595 2834811022 596 2483552618 597 2916842572 598 2542423587 599 2992918014 600 2621775643 601 3073662150 602 2683585171 603 3161866338 604 2766103211 605 3239939853 606 2832104193 607 3330468234 608 2918649850 609 3424576892 610 2983722647 611 3511497112 612 3078784003 613 3604974746 614 3148346439 615 3704195830 616 3245856788 617 3799676636 618 3320448963 619 3901601307 620 3416739875 621 4009052462 622 3497864073 623 4111542366 624 3605944035 625 4215447431 626 3685334223 627 4335658931 628 3795880266 629 4442573394 630 3880828014 631 4559971016 632 3998693084 633 4683939276 634 4088184213 635 4797721967 636 4211535331 637 4925293142 638 4303788110 639 5059452780 640 4428959298 641 5182795647 642 4531933868 643 5317867093 644 4663750036 645 5456654366 646 4767242732 647 5594761019 648 4910378960 649 5737088382 650 5011071786 651 5893225745 652 5161105886 653 6033684717 654 5276921570 655 6184990306 656 5429109646 657 6351890261 658 5547942591 659 6506745320 660 5705793132 661 6669864900 662 5831529836 663 6847385453 664 6001052068 665 7007657685 666 6131754952 667 7188077904 668 6304620556 669 7375299023 670 6436957107 671 7552389750 672 6630809630 673 7739693154 674 6767736795 675 7937561578 676 6958999924 677 8129236044 678 7111524524 679 8334693155 680 7306440017 681 8547022442 682 7466045751 683 8750120430 684 7678946310 685 8958519001 686 7839751881 687 9196494573 688 8060611956 689 9409327015 690 8225994669 691 9642771216 692 8457950766 693 9888491635 694 8637101402 695 10113158664 696 8883254806 697 10364091361 698 9063346500 699 10629275468 700 9308792224 701 10872940292 702 9510523892 703 11138987807 704 9772570657 705 11410658135 706 9974638354 707 11685204530 708 10252056492 709 11961732242 710 10452915555 711 12263291209 712 10749069667 713 12542250434 714 10973605542 715 12837236872 716 11265877046 717 13162746322 718 11499352024 719 13465447816 720 11808902779 721 13786229774 722 12053060447 723 14127604925 724 12377752790 725 14436225641 726 12634756249 727 14789658410 728 12974985402 729 15149807064 730 13226007894 731 15495791298 732 13594127722 733 15856989724 734 13864786787 735 16241929551 736 14238406410 737 16609374820 738 14525845667 739 17001854119 740 14897312670 741 17410822813 742 15211222574 743 17804014353 744 15621056317 745 18204384158 746 15925148185 747 18657196970 748 16344477289 749 19073191712 750 16663952541 751 19514759068 752 17112706182 753 19979928520 754 17450341051 755 20413805880 756 17913982017 757 20891468140 758 18262706689 759 21394462303 760 18731931177 761 21861002320 762 19114347058 763 22371243245 764 19604646383 765 22878688288 766 19993411525 767 23396877293 768 20521645914 769 23927108664 770 20901844966 771 24496553573 772 21451564845 773 25025430635 774 21875760287 775 25582532484 776 22439300983 777 26198778958 778 22873888691 779 26767290541 780 23446708475 781 27364389676 782 23914486504 783 28005195382 784 24533448032 785 28591270216 786 25004696573 787 29254255130 788 25632761635 789 29927277650 790 26112804989 791 30582137937 792 26803382569 793 31250365034 794 27307654308 795 31961004399 796 27995004689 797 32655835070 798 28543379949 799 33388966425 800 29236705916 801 34144113615 802 29811941749 803 34879593175 804 30563041793 805 35630835058 806 31137689705 807 36462321705 808 31924667251 809 37228386277 810 32503644039 811 38052440433 812 33333515726 813 38908623804 814 33964458537 815 39713580162 816 34820699122 817 40598345248 818 35462932090 819 41522685387 820 36312442515 821 42382599064 822 37026213970 823 43312053894 824 37939940329 825 44250459413 826 38651529447 827 45208049912 828 39594134858 829 46176863326 830 40303680623 831 47214987693 832 41322469172 833 48200633460 834 42092489907 835 49207108337 836 43108156361 837 50311528696 838 43913667803 839 51365731673 840 44973365868 841 52456239940 842 45810748397 843 53622839993 844 46914783173 845 54684474889 846 47784788259 847 55903329950 848 48942622974 849 57108660688 850 49804158106 851 58287801436 852 51035621244 853 59513154759 854 51974535508 855 60785312130 856 53221580661 857 62050896430 858 54185774653 859 63370393649 860 55433277668 861 64747919398 862 56486807372 863 66058793000 864 57841194276 865 67397362655 866 58877839088 867 68901003216 868 60276266583 869 70278628231 870 61323878194 871 71753595133 872 62820374245 873 73279391402 874 63946932223 875 74746795968 876 65450454022 877 76309891178 878 66623593302 879 77951230529 880 68153964617 881 79498473547 882 69416241499 883 81154490348 884 71016678890 885 82817780250 886 72299604904 887 84526232823 888 74001927605 889 86269162740 890 75248663591 891 88075485478 892 77035552100 893 89818987545 894 78414425977 895 91617461476 896 80245712338 897 93571866871 898 81647253864 899 95435170771 900 83466099756