0 1 1 1 4 2 5 4 6 9 9 12 13 17 19 25 25 34 37 46 54 57 74 78 101 107 130 142 167 195 212 260 270 334 357 416 470 520 605 660 766 835 962 1049 1204 1326 1494 1674 1829 2096 2261 2602 2815 3171 3496 3861 4329 4706 5301 5739 6453 7025 7799 8565 9400 10426 11351 12608 13677 15162 16493 18198 19865 21743 23861 25933 28598 30927 34104 36912 40466 44055 47911 52428 56720 62131 67165 73404 79479 86517 93864 101811 110694 119698 130241 140526 152845 164959 179010 193473 209179 226524 244232 264756 284983 308666 332324 359189 387264 417355 450543 484552 523242 562322 606577 651942 702131 755065 811907 873463 937836 1009062 1082271 1164144 1248176 1341144 1438418 1543014 1655944 1773840 1903949 2037899 2186022 2339618 2507081 2683814 2872479 3075378 3288469 3520481 3762112 4025602 4300560 4598419 4912486 5248198 5606703 5984699 6392960 6819773 7282711 7766243 8288258 8837940 9424505 10049923 10708838 11418051 12160452 12960870 13800242 14700171 15650212 16660433 17734833 18869363 20082302 21357298 22723103 24157659 25691958 27308699 29028123 30850681 32775454 34827739 36984900 39289807 41710996 44292310 47013135 49899686 52956825 56183316 59613276 63222212 67063492 71103830 75397556 79922579 84716330 89783698 95133180 100803029 106772225 113107983 119771670 126841502 134284448 142161833 150475863 159246330 168527921 178294219 188641531 199521881 211040363 223166104 235976630 249486526 263727236 278768528 294598282 311330566 328926867 347521667 367082267 387728942 409472957 432382690 456543121 481956377 508781244 536974326 566729303 598009133 630985039 665685276 702211831 740689941 781141077 823776955 868572459 915778888 965383445 19371984 74289132 132055311 192830746 256697926 323922481 394520465 468831644 546860980 628954885 715188023 805829433 901099414 2900073 108102545 218513465 334611643 456448604 584496810 718915723 860085949 10091130 165681003 329111438 500555690 680637671 869515183 69605580 277644569 495986908 725071741 965357628 219281575 483649786 761102532 53671831 358803809 678648717 15835658 367514187 736137820 124438378 529449014 954139837 400792584 867204015 357564099 869613930 407828476 969806993 560378070 178748198 824810293 502971786 213338907 955175294 733868171 549034310 402370429 295758501 230671532 209472690 233566707 305585415 427144567 600887133 828900451 115429497 459642261 865616380 338345423 876612858 487573908 171980607 931890561 773819145 699764608 713472208 818513121 21197163 321494392 726360660 241280743 868238390 615156061 485714238 485334528 619277129 894013014 316566139 890696608 625599494 527237518 602145401 858191405 304824986 946417046 795471115 858210117 146586126 665493566 429498270 446234387 727143412 284933849 129344997 273171400 728050899 510202450 630197534 105404023 946054896 173648705 798682797 841285158 319488366 248672743 649018177 540428109 943106278 878669140 370345040 438691930 109549325 406492029 356152699 985215495 323349070 398136468 239779706 879505551 352660286 690017460 929241427 107732778 261966778 431451136 659707966 987701034 463589835 130890312 38446187 236632104 776682491 716181423 109288154 15326743 492525819 608221383 426259986 15901171 446243782 791720536 132510455 541953798 109158000 913305939 51495039 608871989 686259421 383248194 800885351 52119227 242598686 493273812 921258955 656704762 824952595 564634485 14844158 318833793 630906137 106614786 908789511 207236830 177801294 409375 864590563 968462765 514927552 714934025 785955905 959120765 467272022 557667853 481641445 505515608 900391581 951696569 954438570 212415343 44147871 772495203 746677461 314166495 843620676 715023044 323070695 76929667 396806150 728159046 521905295 256373427 414750330 511241849 70061580 636335197 779490658 84678193 162232382 637744147 174360979 440005551 145972442 14108948 800978175 292025420 292695682 647996581 223705525 926865814 687261633 479883906 301972800 197339675 242268860 550788317 285721693 635891169 852403220 213042731 56116601 753057665 740962805 496492471 551184004 497326505 971383319 687879474 398417432 938980082 194639112 128137187 763116959 203088756 622360966 267574300 477714396 654733771 310172546 18127360 463617039 415141410 741657236 417706071 508810739 208457503 795394007 694768401 420262741 633565213 107120828 752201325 620037365 890067610 907783741 143683688 251024605 16447114 419638115 591043234 852494309 706351023 836366636 143081838 698610050 823349827 18203661 37680334 842339382 656428531 935027862 392992191 18658569 50189664 43116817 802722305 481356469 499627670 631892925 967490940 942658563 360794353 362810880 508752553 705361182 309928334 53325028 132014332 167816431 248973225 946579742 304353491 900847967 801600021 658419057 633490276 510172758 634820397 986480116 184176453 476175588 832373922 870486599 987907693 272279737 628545756 724465017 68862686 14611736 773251756 501205630 232145338 24873832 869178791 845185439 41695670 670331272 68616313 721211867 356787923 887425751 579867896 945355920 937506487 855517003 498293583 145281976 618143478 374403086 462275024 706315841 609699437 565766474 770400447 403929232 606077309 578685413 666027606 353144438 449798640 14404531 592726235 131328679 197754925 953373674 301960865 962334723 509913929 575810931 781489633 30071449 399574559 437223790 118818922 40249881 517813432 652069321 560165587 334362927 368574751 279048512 239773599 950971790 906675153 482842791 70075774 329397467 190303801 229851295 602682499 462784638 927820737 430687510 823740653 581362075 91847468 698639554 155288443 575948888 942464592 101041627 186206152 771880368 156295392 684500099 888994678 987008192 904083220 870482910 449060297 93652119 313847811 87708859 243833792 682101621 979787118 472805975 975331048 873518050 808927243 914712630 357593978 799885417 756374109 289266993 211678000 942481576 686578767 291955873 555012418 961690839 233066203 846262435 880833724 347102620 230832907 776709548 579747640 985815515 62325748 272999974 223602747 662799085 19216652 643337030 285878292 413682992 800268951 759174708 996458089 641801841 446571417 592860230 203797573 31751003 124664405 603181956 269973292 675611818 512464200 92777025 475944663 334906054 939291377 223846345 859087521 295166461 145097348 19120702 357577421 12511700 498439348 431328526 52112838 714767841 476244404 872343524 349469628 525392651 353548099 905858442 340387124 56244096 697706008 432308271 271705800 207761824 90721126 492993295 183398091 795784577 755857485 990927241 46512771 128306574 158131934 390918217 242398243 580896809 354329628 460831852 378342205 364592107 415206026 477518032 55824521 212391050 975352107 133611162 336733207 921078605 446263048 877936922 240531948 502393385 99806356 706349526 597791558 263361325 791405608 100183515 682881417 112795519 544422937 184124961 818008984 144496323 343840159 444124216 697919674 365238357 501980962 620450341 548047860 262807215 705497326 838523435 571952578 814029973 907877551 306117310 955563661 259913392 771020130 246399057 794923486 114591914 934677504 813461716 493521812 774020253 362423571 286247202 973426266 422919301 580507816 116847492 519726350 71520166 220031905 317296402 774054146 288112750 30848575 404985261 209949128 271423766 237647685 672295155 12328789 711591372 12033824 521405972 744906552 127847028 685011283 172218343 469394703 347794915 309171956 543413745 677261692 869851032 530539738 902647904 464265402 642396344 415368173 892320678 689321955 938834187 301032271 613647337 819066037 55131428 153557199 685053358 896303291 182736946 170265307 438739653 56439070 818340650 85255270 258271838 435470147 55135769 859579785 509597098 643752549 881388019 234537391 461604066 527072532 927421084 163806223 525665733 551653703 970740845 763444734 446098645 837076583 425962865 479712248 593292609 624322019 524832986 790352335 347600081 697788683 98094941 153652263 51156517 762836556 877538251 650850565 112871733 946987199 14543740 510881885 643633521 3855899 626816246 175223767 842050232 976352891 68364585 920393238 395856071 939423721 123222227 912404391 694349368 905430899 259662513 175108115 364710703 983951179 402362809 378098883 473448285 132172150 531535238 357082188 844097492 398474281 101199325 28022703 811089745 272120484 57980935 671461245 93884418 254104045 890439909 79200122 293601686 893742567 184141098 152495128 837159954 466469850 497343854 552207821 177407423 638413591 758453006 510184410 608966591 528336673 202287004 304569416 623891424 144918306 348625891 932325590 261962571 798099924 711918558 732768574 213283366 283825863 436432114 541472431 356389998 916583283 662247500 569759908 109841192 970986238 108636594 809462861 704311783 365498359 135550745 641257328 363696164 820822197 444766624 177347555 199546476 321553291 542142652 675357289 918746568 268827973 658342777 453563856 652168933 880172509 694983922 90637015 957899974 390245837 549415386 337516138 910455388 47698539 897244304 854939095 826402973 497041034 615831181 941834656 270176244 447233289 601233363 127008239 34606469 574134737 775203128 688760278 555438300 977656528 406548921 206785594 881879579 361788251 423888070 545400956 487864226 568388408 567558715 840739670 243656646 495941065 130913868 713106390 955809011 896101436 2618812 691842341 915091136 18530378