1 1 1 1 1 1 1 2 3 4 4 4 5 6 6 6 9 10 12 13 14 18 23 25 30 32 37 39 41 48 57 65 76 84 93 106 115 126 142 160 176 201 218 250 277 306 345 382 419 467 499 555 616 674 754 832 914 1010 1104 1201 1330 1449 1590 1745 1905 2093 2305 2496 2754 2994 3259 3576 3871 4215 4613 4987 5450 5943 6440 7037 7624 8269 8992 9736 10546 11476 12388 13454 14593 15752 17100 18501 19928 21613 23296 25151 27241 29312 31681 34210 36813 39775 42857 46115 49786 53508 57570 62049 66658 71723 77229 82860 89174 95834 102763 110510 118524 127105 136589 146312 156984 168483 180314 193446 207241 221789 237803 254439 272203 291561 311651 333382 356790 381149 407653 435781 465221 497363 531079 566805 605636 645989 689421 736079 784600 837244 892943 951424 1014801 1081294 1151803 1227759 1307183 1392042 1482774 1577843 1679870 1788114 1901759 2023945 2152671 2288624 2434658 2587637 2750351 2924119 3105981 3300539 3506795 3723316 3955212 4199251 4457114 4732440 5021558 5328352 5654563 5997032 6361455 6747275 7152960 7585084 8040717 8520887 9032045 9569549 10137877 10741566 11375076 12047316 12758326 13505552 14299285 15135457 16016430 16951270 17933895 18972136 20071349 21226337 22448370 23738645 25095368 26531578 28045021 29637805 31323324 33096049 34964644 36939839 39015277 41206233 43517718 45946126 48512041 51212941 54053846 57054415 60207790 63529018 67032466 70713054 74592580 78678831 82972167 87498236 92259380 97264427 102539048 108082603 113912339 120052615 126501219 133287330 140428560 147926254 155818972 164114342 172826534 181996298 191625171 201743214 212385248 223554756 235296048 247634482 260585021 274197703 288491956 303496276 319263414 335811542 353183486 371431344 390575064 410673046 431774390 453906155 477142412 501524026 527094222 553936297 582084932 611610425 642592371 675071315 709140256 744870729 782323240 821605290 862784201 905946483 951203124 385683 50092227 102195203 156784910 213991052 273936683 336728415 402521201 471442544 543625807 619245572 698433540 781361441 868214247 959141816 56112342 155800201 260149176 369398270 483744815 603426230 728696123 859782167 996963667 142266203 292454369 449596995 613994775 785969240 965868947 155789665 352591335 558423497 773667833 510988 235875417 481951893 739240779 9971241 291145751 585078108 892289877 215148450 550742879 901439063 269692967 652641636 54523786 472595099 909345652 367380278 844021535 343634808 863663018 408543784 975755844 569878998 190198274 836091576 512264649 218129672 953238060 722428085 525264958 363252615 237836991 150545448 103079042 97024203 134177796 216399425 345480411 523499228 752473676 36243907 373635615 768622805 225385888 742991173 327449133 978032329 701100313 497730757 371083196 324308085 360631479 483633256 696792264 5557689 410429787 917010444 531326971 256045604 95495320 54577638 138105223 351058288 698940882 188814098 822917209 610836721 556760288 667257019 949017053 410548155 57501632 895525051 935793774 186611350 652690770 346259048 274834081 447563245 874372225 567275573 534789373 788188922 340517257 201680678 384324928 900905942 766507539 993373834 597198633 591339568 991230546 814369515 77725852 794889447 987189447 673541688 871230391 602113538 885495511 744402534 201485532 278376233 627828 391980595 480070350 291714428 853674008 198139554 351896511 348335558 219468362 997685564 721473827 425056683 146599795 923125813 798653410 813869691 13760674 440253256 144003109 171541088 573716343 404683339 716673197 568251107 17602260 123393921 948974243 562497824 29964987 419951863 806233989 266423138 874920949 715835319 871955995 431478822 482902914 121819445 442741558 548280589 542510286 532882781 631680736 954501566 622988936 760283443 496649623 963984354 304610541 657858294 176259317 12156570 324499573 281060527 52660261 814699314 755214035 63726055 934325969 576803685 200138134 24297456 275867382 191340498 14951497 996298901 401947674 499169204 568936664 901742662 799592721 572691568 543630832 47060378 425838018 41586293 261540510 470390918 66939642 458477416 74087857 351660807 746962397 734157846 799754374 449896749 207969530 612917142 228444013 631905107 424522836 227513058 681725509 453810324 231847328 725352046 673129172 836892519 5806995 991396919 643618016 830657133 459112068 461150123 802177819 485748681 542415079 43599784 95229195 838890321 462983218 189436542 281838673 52978378 852845879 85626798 196826207 682274573 93579690 29617195 144011836 150400739 816771236 972947313 512878941 389058415 622171531 306216032 597070064 730265577 17385135 837447957 664377296 46486588 614056759 98660552 309727761 158934778 654273282 901530538 116128429 613674935 824053939 295686147 686864076 782941817 497765046 867705778 71135895 420136307 370795815 528566027 652189229 652928229 611855202 772248840 551400718 550101669 546480883 514105786 624782433 246702214 962845774 574505078 97734437 786878726 132242115 863284464 974970311 711411071 592598113 417372232 265463246 520257206 867571695 307259780 168698748 111873584 144779827 638122186 323437219 317125580 130461120 668658043 271741676 695834640 146920367 293656480 268770972 698521249 717111052 964234482 630012930 448018117 717958013 340765594 808208662 244990981 421161748 763514991 392481276 134537371 534029136 901808053 318752513 652939237 617500407 757638604 499895190 182959353 58229624 352152694 281432332 68310891 6899773 461949303 917037177 24775523 600034219 701652135 651784349 59547695 887768086 485531805 609948136 509951631 933333535 191441044 214412752 574428162 563262741 241099353 459290213 964411876 425149658 478075334 837373452 305073001 856663827 731181793 443610247 908265850 493589688 69374409 134854880 854085778 152038510 812965063 538159145 52399271 205242874 29351550 875613730 504117150 151159344 693868749 715747833 618861267 782069089 617212091 735018040 77279283 985160092 418927048 31693734 311560414 784928093 95820401 189362439 498772897 44326896 656354737 139005260 401888784 715852717 848263523 257195453 336323468 562685619 736552772 224706047 110187646 496189219 721692023 556660173 539274425 163130364 149732511 784729438 105495437 251103791 768976810 847563933 724299452 948582151 706598746 234351136 84069175 528678245 967301865 226828646 23350837 364414777 904155784 465294386 415456565 110732101 446710789 241270912 769082132 325171574 620026384 443973541 173062434 274967405 29258170 7434106 720981307 341848862 211605901 625417069 519737239 85059687 626013172 246020996 581200008 717865765 889012313 355358176 337710280 776364891 349985756 413432638 852114291 236749519 740980310 164857164 159506883 169062724 649763720 318716095 168953767 895939824 113317794 554410299 627287061 626108323 186490531 866461705 473047522 718245897 845257140 100560278 584199149 916250563 909561220 591503118 909567567 676547549 701290011 590853654 994419240 789121835 68917185 674709408 392366302 261308589 291694640 726970070 758289501 303127633 490003669 718413452 497182603 266221665 713769664 743719303 678341237 787598689 450800637 768644167 282060339 391448588 409409205 412442100 53626638 6274791 957867519 951587839 111459272 870828891 919930070 97668503 57662322 743512433 455425174 122814828 172577702 894353379 394890774 761522901 907241077 153435615 722792698 178279771 603738588 481027423 803984066 857912990 501460618 114119099 865625198 566980008 503372811 110177813 617798232 726852010 696425603 38154663 822125151 430436401 338245958 975046445 405567620 130123272 555265313 810345947 464362110 776782447 750403105 726649255 604677721 184354687 642441855 916564103 390761265 248327976 281909256 867690532 305152942 308043149 113578914 105991063 99207762 462134997 470490128 226710764 979230854 500210038 462058810 321636332 786389012 660567656 635034868 843982812 298382600 874863965 965549733 681681647 321100414 88514811 333648295 751012962 108853879 932252515 566523070 898213863 66598957 207726985 516773167 364451454 566592974 348277043 977868388 599035580 704930298 205777537 155497752 184754377 929349548 173485536 461599052 29727099 825416168 577997988 334834946 959275770 777876399 992290828 298743037 79877572 215591667 354441552 564152210 391544922 968948118 314283628 554824544 762047765 544874929 83977930 638096006 392072613 550894970 849477820 503951860 573573466 37075749 594278063 567254126 179007373 983806217 515806760 651118551 349236281 244410483 293267976 156394441 275132394 67424031 984154520 188698337 188910529 726971714 555336648 929250385 5726448 116726912 370341817 739879166 927152287 508188371 117572815 757947752 247952951 892306956 128225991 117314141 526598923 191865911 40185314 628781260 329408971 335129665 310817335 712220442 147345167 864186114 573652480 303383401 257198383 273376972 758809648 847331974 947537113 921426467 150966105 465154843 770541804 39619299 795301319 585962066 169044066 778304171 850319822 160950047 882349747 237535393 837330629 40194601 986474733 360291979 280125675 310558093 60266840 552417277 165285162 912739291 327282543 969424649 379697118 261421043 774904150 691946668 25356050 147270839 309711330 997994546 16718224 921351805