1 1 2 2 4 5 6 9 10 12 17 19 23 28 34 41 45 55 64 75 85 99 122 135 153 188 211 247 288 330 392 436 508 601 674 767 888 1021 1155 1299 1503 1701 1911 2162 2455 2795 3100 3504 4010 4460 5003 5663 6362 7143 7954 8989 10112 11212 12542 14106 15750 17465 19492 21860 24242 26866 29973 33364 36998 40872 45519 50601 55755 61735 68586 75805 83597 92394 102386 112903 124176 137227 151557 166684 183155 202036 222560 244061 268124 295211 324106 355145 389596 428113 469135 513077 562648 616882 674456 737242 807315 883330 964162 1052923 1151524 1257257 1370582 1495189 1632524 1779380 1937074 2111543 2301511 2504150 2723920 2965611 3227245 3506872 3810816 4144509 4503032 4887419 5306638 5763836 6253758 6780293 7355495 7978875 8645526 9365241 10149236 10995162 11900643 12879190 13943600 15086757 16311790 17638816 19075783 20615923 22269470 24060375 25992942 28061524 30286723 32693729 35282556 38053788 41037019 44259644 47715604 51416203 55403908 59699363 64298828 69228628 74537245 80243477 86347533 92893989 99938703 107493380 115572476 124240867 133556811 143529123 154194521 165639217 177917101 191044795 205088552 220149551 236283595 253519580 271959225 291722640 312859891 335432176 359581520 385434924 413053525 442542790 474082501 507809369 543806308 582236705 623318370 667200449 714004600 763964833 817337220 874284228 934998994 1548194 70705248 144432588 223012097 306833046 396225548 491455685 592922981 701102731 816372504 939103564 71589314 210877934 359178303 517012136 685069331 864003193 56144421 258691152 474255987 703617963 947513972 208652211 484564621 777932553 91498400 422980780 775380731 151604695 549443766 972199027 423123650 900158665 408521282 946603616 519729750 128002906 771871551 457160272 184325062 954025660 772549435 640932975 561946856 538686892 574598425 673079459 837607125 73895038 382654697 769791093 241476483 799183616 451559192 201976093 56048975 19962922 99959469 302448824 634509064 105507734 719561647 488194061 418542716 519899826 801619296 275539641 949180440 837358141 949900649 301184800 901277503 767474663 912408671 353558862 105784642 185946275 611942577 405024348 583658929 170303672 185505353 653220003 599809877 50830897 32150372 573089707 705400750 460638734 871162477 974446187 807127740 408222933 817873862 82994282 244979309 353730973 460423195 617830577 881113650 311192599 966886988 915926616 226061296 966302702 217578892 54648322 560722975 826016977 942309255 6949043 118322417 385744356 920577843 841377183 272578121 342901591 189284759 952642662 788019446 851609394 309466285 333925700 110601989 828907156 692182218 910551226 708429296 317148540 977914351 951568378 507233620 923175838 498131253 542022677 381526093 355782559 822963605 163179993 765108360 44705621 432092206 385160781 377147433 905093013 496530538 697090111 81364422 248618457 832442103 495345542 924652413 849429595 32061102 263844445 379287301 254568589 804197828 985703857 802236442 307624484 600167830 830810126 208458111 994975393 515762512 150203619 348834368 631071918 582115392 860755953 211177885 449903889 478931220 290595000 970736836 701405386 757874625 529598594 514559051 320954364 675554113 439854072 600052047 276260813 731357067 387496804 811246016 732757753 56322875 861985263 415612610 168225775 781591234 131484080 298010919 598666400 597293036 101612924 171252520 148154459 660854634 627971667 272231162 147958327 147615337 503657270 817860326 85186405 688595114 425018030 526033197 686301264 63299094 295760658 551104519 533992441 492680423 257527961 277127253 629774098 41749793 926074211 433155770 441980250 602698458 389372874 127362664 7810251 135739694 589340047 445461094 798616649 833082849 875234478 419503685 166419210 105199295 565516131 247351788 277719389 306841037 552112135 838390672 687148656 406349721 137542491 914186297 779972322 868611597 462849044 77149694 589303140 332389638 149835801 522535639 712109293 841555910 986978154 335829829 326671307 746603263 856260786 574318246 623884292 643260221 355083495 776055921 371003796 182334921 57964830 874644930 700034274 968183228 758110382 24684253 774726018 324592075 594158574 366703975 497074664 232343778 551428797 431403750 120068824 523774392 582032226 551746653 369383060 103705652 349191472 571244113 556657581 928101832 571640082 50894412 166980906 529417493 20979610 320119831 572652846 2232704 443742033 14069780 859340030 839465948 158406070 173363571 256284413 526863768 639476318 747333498 448061407 617544521 381568643 232231763 68612373 176628637 404957331 439640682 953412188 783884428 332541218 993964373 459929872 127533855 753115011 39895651 122074344 294111073 890925768 58496511 505154172 564460573 319376036 591221581 44161003 583271460 758535305 29016905 272899463 577442041 907984937 757011306 128122421 699935818 851295091 766626173 948702213 797097976 38410798 410344632 746445269 988124832 148102849 664449702 83859318 577273970 575207141 874160148 944801298 82064753 817669549 884949880 198174911 758752047 36527280 800396277 900979921 99505212 524121488 488136720 159307234 532064186 99855532 704145642 321274061 355837535 648677455 504811769 787242999 781794098 634385685 728666199 388550065 478360727 426528004 195346739 870430033 214311647 429609679 41727652 679374678 770923172 302224605 953290009 413586736 395812644 730124477 185634207 575457028 405209010 677804410 841250771 24904568 613638063 297896327 585865152 506825686 554861148 537374852 146676843 482724038 943872565 500378255 781029997 927779424 78273638 729680536 886328537 802060865 860785296 747956410 187084710 351046555 32666757 312902954 598348623 618095186 816004433 313227841 68801989 538215583 324788651 271546134 780588654 367311082 632739782 486653796 864556517 545129707 583983020 842653808 603365570 87966896 635363438 960362390 347159283 467371191 722198983 927075020 25437728 870662256 399871514 791808169 787554968 276862906 282699445 967082329 796791885 20500490 830387323 864632916 682895810 499485193 325939150 919720579 251666251 262517221 254603480 506628687 700082714 21274166 447893193 590192133 454504163 716289147 91716609 224542623 701552047 991254881 460082734 578711857 764638185 103978818 13181891 610308372 698278861 27493869 151637598 437890103 366131639 789874646 68060597 53492192 838838170 87803503 240591872 931853500 152102611 460788356 82924044 204893409 560861583 233580103 435715460 531609111 10659260 491079967 477205471 194928420 959594264 319117342 538391750 741192560 915813178 578644678 492677033 46817920 521166640 448381591 947571362 806060544 264967313 385756034 313838447 192167005 830675518 675977670 338309015 520455497 238787682 556436766 23129814 959754817 737564312 249438959 196472586 889182440 259867870 888673806 882781270 546851329 261851600 93250340 131412059 80586294 25674097 34749365 488230266 972412752 40750928 960992904 2377239 742448199 310517613 885933660 834308621 816221576 853207811 174067853 825896781 755296484 307801857 808258666 919931663 892887640 141308230 822600861 238140192 259912715 547630541 52517413 647974399 244470648 982009210 434528635 328400710 935701401 868779781 528354951 11086258 898175432 713256046 854564858 163688910 989409089 107035834 323006238 582131591 416593123 524898465 138590921 308479774 104684824 705321498 698621698 17183911 117744070 579847861 429489651 706833499 825589934 578299064 70515565 912794700 68458653 551252872 499009973 646357200 865772488 578996082 101116886 146035564 696683529 295589677 277105037 216262281 585608981 980103705 34271927 750695083 834147998 611810960 78816273 65619374 191505736 793141492 937384654 113102468 499885622 135939491 611586471 243853798 612509571 384897349 281358399 401365886 857546850 747554012 624915035 855592733 515542763 925707036 991748797 165016030 959854576 578225598 47533401 377910913 483186534 429284318 252056766 714088817 46161735 82864141 294328269 744274930 450338518 196457225 795105045 121532156 869827382 207779659 689531979 538915080 102090115 854440842 980729735 407136263 118112027 8696927 325484423 968095180 320292241 78360866 474076883 854821478 245257060 687036098 261937193 378748883 67930314 17768440 258016848 620072448 810075532 130881112 565571861 619937774 110397895 651211074 824306430 972739694 938887562 965654106 102404113 495380925 888899921 970229311 925670216 922160737 711766404 886298111 648334128 908225541 914552317 367232329 718857009 388010846 124161034 908524831 780605311 922744981 535439625 326953877 31527811 643614797 804987553 325646122 942261344 766850228 536249306 993853054 952056492 937668442 37356371 242762460 876178537 776853881 497932438 651657216 430114131 107501130 611252749 195630115 130109786 442230548 26823769 688294984 212431499 958811770 490428938 741508961 972130020 1580670 339457232 386961830 629516484 472402359 643294370 138904597 244577727 213990363 648933033 920393089 854401695 285997008 765866275 194127787 556136382 197258516 503100316 308008637 920448858 285882627 205421117 144091106 549579843 907225317 747282874 373224282 86742221 508610632 418166500 770054519 420982993 927891986 83698785 837720024 246789631 356386383 165483583 385958623 153107925 828552812 647469680 412239344 770718827 780827573 919058863 437274407 782755636 465069072 14543978 682507588 962908747 171936759 895778575 749440900 623043475 735503714 42159691 898558621 609268873 556952926 510789396