0 0 2 1 1 1 2 3 2 2 4 9 4 7 14 11 15 15 19 24 26 26 36 48 42 60 71 74 91 103 114 131 154 162 201 222 242 298 328 361 415 483 514 590 668 729 849 920 1033 1177 1309 1428 1617 1814 1966 2229 2447 2713 3029 3336 3680 4091 4525 4935 5519 6030 6634 7343 8046 8853 9718 10718 11692 12895 14087 15409 16946 18452 20218 22075 24177 26335 28789 31429 34222 37406 40635 44323 48209 52490 57023 62003 67453 73171 79581 86259 93728 101597 110165 119437 129310 140211 151606 164236 177612 192164 207734 224541 242771 261992 283183 305550 329826 355816 383752 413840 446043 480789 517675 557970 600540 646408 695774 748483 805143 865566 930821 1000075 1074933 1154489 1239781 1331546 1428936 1533689 1645400 1765280 1892713 2029601 2175703 2331360 2498475 2676000 2866341 3069070 3285668 3516481 3763257 4026236 4306096 4605875 4924123 5264225 5626240 6012245 6423523 6861298 7328054 7824159 8353776 8915916 9515130 10152718 10830613 11552325 12319074 13135673 14002648 14925410 15905429 16947334 18054665 19230303 20480187 21806536 23216283 24711782 26300529 27986482 29775635 31674996 33689016 35827340 38093608 40498716 43048120 45751524 48617865 51655008 54875502 58286590 61902631 65731687 69789136 74086469 78636165 83455454 88556107 93957307 99672880 105723054 112124337 118898591 126065004 133644342 141663884 150142192 159109453 168589230 178612231 189206932 200404351 212239248 224743306 237958165 251915339 266661573 282236463 298684238 316054204 334392901 353756863 374195169 395771118 418540985 442571521 467928470 494680375 522905996 552677791 584081465 617198710 652125498 688951047 727777159 768710186 811855492 857335422 905262201 955770971 10746724 66819999 125891881 188117691 253663345 322689756 395386915 471932521 552529562 637382595 726704915 820729634 919689448 25593995 135188134 250511352 371842180 499487990 633765805 775003213 923555378 81533409 245818317 418557667 600178787 791115330 991830979 204568902 426313175 659361993 904259217 163353057 433731712 717793975 17964809 331425224 660675400 8222358 371372454 752711514 154879608 575284867 18400880 481729871 968073774 480304520 17808029 580051994 171800129 790870012 442159175 125349620 840214200 591830385 380115059 206786583 73664130 980879179 933924173 933119333 980607985 80433354 231422487 437816166 702190464 28993418 417542790 872529059 398793752 996027250 671121808 425806692 263759980 188811050 204948763 316362287 527395129 842621702 268532797 806601619 465506292 248912691 162479812 212082890 403904750 744352097 241907560 900037154 729578544 736394744 928428035 315763026 903514275 704264194 725662679 977548701 471939597 217783418 226237122 508931736 79792667 947932384 131853744 640032554 490347300 696015327 274376101 239965150 609720574 403102417 636746655 331648738 506054896 182581751 381233004 126390536 439955368 348238740 875149519 50893407 898030120 450820028 735928419 786595792 635554270 316961610 864573299 318945750 715107720 96707556 502059684 976420731 566909259 318912137 281601354 506101348 47418641 957478042 299222536 129227641 509958249 508271412 191822674 629358467 895939789 69595815 226261089 450232833 827507842 449227170 406674201 796617694 721492615 286006631 597317623 770519693 923375607 180257351 665055317 513837099 862678947 856623195 644723118 381887959 229253458 354245025 931046224 144136243 178173393 230537546 504484201 213160851 574373157 818203461 183606719 913629558 269736649 514608005 926699722 795136965 418615158 107386073 183857418 982891833 855919050 164367373 281845970 600140756 525937215 479991921 899196462 240804252 972544906 589045109 596738120 524978677 921781870 359444224 426961974 739313477 934864011 676430627 650058421 569815962 176773487 238418794 553011795 949095825 288258545 459247382 389836605 40757284 407390745 525936765 469822567 352732413 330113468 600786263 410047541 48131199 851556659 213975137 571879510 422554131 315357696 857160641 718233410 626945569 377788355 829677864 913951525 631488396 56918430 339757892 712106370 488343942 65977689 928972021 659408729 926983881 504490278 262450282 178392215 338247858 940806809 304803671 862724940 180877820 946226190 988569596 272852191 904493848 146046521 405655546 257762166 438291927 856040505 598148881 931553517 317850343 409674830 67754583 359664782 573906084 223979618 54803596 53849201 458372474 765270388 738797922 419512516 134043074 505073338 464746320 260606823 467701528 3888765 134167355 490164672 80589624 298986193 944381292 234464931 810285007 765798027 651485470 495334161 816958443 648402858 545957786 611896045 512663970 496832802 416054587 744404302 602666952 774776586 736375444 673709872 510246158 929289191 405337537 221629095 504673435 252689153 359304063 649720963 909175926 916221136 475401179 450037104 801456949 625275073 186396431 957389622 668339655 335746449 313086584 334937561 561181442 626544925 687205988 473746421 340816662 323653839 192927703 510714978 693492800 70982904 944808702 666934281 691828131 655933593 446382353 274376028 751938701 974547365 597879858 921535108 981277520 634039773 650141212 811390760 10117140 343134364 228681428 503660459 542815619 368886401 772371484 438571969 66480195 503547403 882224542 756155352 242425900 169590098 232853612 149555299 819487458 498240053 959972297 686164473 41225930 462512168 662657395 823512743 806845756 368999051 378204121 48935037 170159559 352719312 277243591 949342845 971984416 811809414 86882313 851025225 907608012 106575591 663679061 501912260 576847857 235690874 571186128 800616942 644022335 719682110 953130025 996846170 663028670 366911505 589868706 354534795 707755419 232058179 554564699 892026751 597097473 724003629 619571875 523210515 189455239 527351052 266030103 626692708 34151451 825892866 14670369 35302235 550365049 260912655 739067753 303766944 898315754 23501594 664561260 285696024 814433708 690786212 920998528 182446127 944666005 646542322 881682575 643999472 592225232 366277543 932132226 977965738 340771739 480379264 4521786 226023561 778956746 277728346 19902950 749568341 474907925 322808483 468408252 112312667 514457689 99425104 605884439 324093612 372666219 67428494 341539286 251694986 545712733 318085002 731003683 829848640 430485567 93823858 193284953 69188118 272417146 909470237 85863979 436485701 784475344 887591318 299756534 344786927 214429475 173511100 896446730 931627233 287048071 155158566 780816487 464715772 707583726 518917781 861234682 274473506 637301500 124776091 311440296 472419957 55557559 340955444 301830195 652092563 110491327 855310935 224348813 598232280 549165627 197490401 816727163 697524341 245408198 355476016 54062045 409665595 739673786 99176447 71111196 874187528 785022181 874378564 99928741 722372145 102292956 828892022 257754076 402790696 248919807 454180655 482487690 157457969 659942952 988058366 871169630 170714129 771705948 987685643 476016916 691251592 895581606 726489065 346762398 193047046 336484013 477004284 577357496 171526522 348585342 445870608 463282065 213489077 237968438 511232038 940602431 698763086 401665031 161526989 535025332 398989430 755378013 530648027 353912891 373616784 124403065 471865946 681495921 614582384 110084599 562843811 751832990 927356423 213354445 343443735 789679711 295320666 855691327 220261623 888644886 722382717 147454486 23663490 234347766 16537002 87808664 636633535 203045115 499259199 256844408 105283751 575937025 277556300 279154162 803238293 255227980 653068995 559043923 525737541 170769756 916305900 502088952 292975072 511866355 444859062 692277999 576361427 756361583 163859455 323554241 177037145 468082304 818941534 572445299 503040562 516743521 419732383 883849468 716642366 532819456 970708828 561082860 358796120 484748175 702116103 149801125 369931180 794279824 798525200 488620626 373488997 76286336 228036291 740415384 586130647 277316902 234592881 185219152 816921555 860022713 772592992 276601577 899094184 763474807 828406674 804131819 960183436 85932151 793808375 473750246 79449424 60970538 681888515 987009021 712858365 411153675 91834141 671644609 543562419 572981278 854252302 548860767 149133544 515052258 38921838 303586908 615077332 776781567 532944497 37805406 807428940 574316120 434320109 798288834 567578825 997472652 763334644 684405873 638358899 179353779 375696109 437981912 675301576 363860763 105883525 292649678 288562945 940453917 115484069 870038531 980810041 514504386 144987652 967202095 571777337 98464842 125735796 168272891 608711974 944974903 194663499 353302352 867621644 992497876 43348337 517196869 102234256 584086563 747329892 338492667 206069353 770648291 4614389 76177795 956060717 206645131 223596082 318808550 954915043 517284281 76443602 592700878 36597459 995436588 306406465 319559849 507477788 996407700 858483664 888880258 671837742 835566032 394557581 95986274 836973627 158547945 918807203 349400141 618378691 260364408 688269825 257112347 227920491 174925681 382439579 808590626 347091977 88380081 401446963 742091498 98329314 88698899 877602042 2348377 352689393 734066546 290972474 350381445 267581546 891671280 446468498 619060205 849832708 797501835 143902565 941392457 861426846 743934297 15525680 610668539 193734523 498582314 839121084 909883127 51599414 411538387 525996400 813604767 915658738