Statistics

Problem Statement for "BuffaloBuffaloBuffalo"

Problem Statement

Did you know that "Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo." is a grammatically correct sentence in American English?

We say that a string A is produced by interleaving strings B and C if we can color each character of A either red or blue in such a way that the red characters, in order, produce the string B and the blue characters, in order, produce the string C. For example, each of the strings "dogcat", "catdog", "cadogt" and "cdaotg" can be obtained by interleaving the strings "cat" and "dog".

Interleaving more than two strings is defined in the same way. For example, the string "aaabcbcbc" can be obtained by interleaving three copies of the string "abc".

A string is called good if it can be obtained by interleaving one or more copies of the string "buffalo". For example, the strings "buffalo", "bbuuffaalloo", and "buffalobuffalobuffalo" are good, but "buffaloolaffub" and "bubufffflaaloo" are not good.

A pattern is a string that consists of lowercase letters and question marks ('?'). We say that a string S of lowercase letters matches a pattern P if we can obtain S from P by replacing each '?' by some lowercase letter. Different question marks may be replaced by different letters. For example, the string "abcde" matches the pattern "a?c?e".

You are given a String pattern that contains a pattern. Let X be the number of good strings that match pattern. Compute and return the value X modulo (10^9 + 7).

Definition

Class:
BuffaloBuffaloBuffalo
Method:
count
Parameters:
String
Returns:
int
Method signature:
int count(String pattern)
(be sure your method is public)

Constraints

  • pattern will contain between 1 and 100 characters, inclusive.
  • Each character in pattern will be a lowercase English letter ('a' - 'z') or '?'.

Examples

  1. "buffa????ffalo"

    Returns: 6

    There are 6 good strings that match the given pattern: "buffalobuffalo" "buffalbouffalo" "buffalbuoffalo" "buffablouffalo" "buffabluoffalo" "buffabuloffalo"

  2. "buffal????????"

    Returns: 7

  3. "b??????b??????b??????b??????"

    Returns: 1

    The only good string is "buffalobuffalobuffalobuffalo".

  4. "???????????????????????????????????"

    Returns: 420429295

    Don't forget mod.

  5. "x"

    Returns: 0

  6. "??????????????????????????????????????????????????????????????????????????????????????????????????"

    Returns: 214380133

  7. "?????????????????????????????????????????????????????????????????????????oo???????????????????????"

    Returns: 537308020

  8. "???????u??b???????????f??????????????????????????f???????????????????????????"

    Returns: 800199380

  9. "bbbbbub?bb?uufubf?bbuu?bffaa?ufffu?falf?lo?oafofuuffa??a?l?llffbfaof??ffooaaooaf???o?lloloffaloolo"

    Returns: 9176151

  10. "buffalo"

    Returns: 1

  11. "?bb??????????f?????f????????l?a????"

    Returns: 981908113

  12. "bbbb?uuf?fff?ua?fu??bfof???l??uoa???uffffbf?a?b?fo??f?al??falol?fol?f??oal?lo"

    Returns: 218165483

  13. "bbbubbufuubffffbff?ualaoloufffbaloufuffaalolaalloofofalo"

    Returns: 1

  14. "?b??ubfu?f????a??l?????????o??????al??????????f??lo?????"

    Returns: 833875213

  15. "????u?f???bu?u????????f?????f??lo??u??a??oa???f???uff??o"

    Returns: 377587883

  16. "bbufuf??floalo"

    Returns: 2

  17. "?????b???????????????????????????????????????????l???????????f????????????????f??????al????"

    Returns: 721593975

  18. "bbu?ufb?????????fa??of??????ba???f?????????l?l????o????a??????o???fal?"

    Returns: 670421686

  19. "bbbubffbauuffabulofuffbuflfalfoffaalooloalouffalo"

    Returns: 1

  20. "b?????o"

    Returns: 1

  21. "??b????f?bb????????a????????o???o????????f?????????a??ff?o?a?of?????o????o???"

    Returns: 706995726

  22. "?b?bb?uuufbuff?u???bf?uoaf?l?af?llu?fobbu??f?fa??uflo??fal??b??ouffau?ofalo?al??fa?o"

    Returns: 519818004

  23. "???????f??????a?????????f????l???????f????"

    Returns: 702798372

  24. "b?b????????f??b??f?????f??a??????l??a???????????????????"

    Returns: 663533572

  25. "???b??f???l??o??ffa?o"

    Returns: 194

  26. "?????u??f??uo??????af?????aal??oo??f??o?lo"

    Returns: 120637892

  27. "???????????b?????????????????????u??????????????l???l??????l????????uff?????????uo???fo???????????"

    Returns: 377790151

  28. "bbbuufbbbbuufaffuf?alofbalfbufolfbfaub??ofuufff?aaalolofafubbffalalooolouffalolffaloouffalo"

    Returns: 9

  29. "?bbbbuufb?uf?a?blof?fuaafll?ooufafffuall?fof?ffla?lfo?lo"

    Returns: 18

  30. "bb??ubuubub?ff?ffauaufffllffa?ol?b??o?olouffffa?a?lofalo"

    Returns: 280

  31. "??ffal?"

    Returns: 1

  32. "bbu??ff????a??"

    Returns: 8

  33. "?????????????????????????????????????????????????????f???????o?????l???????????????????????"

    Returns: 772508208

  34. "???????"

    Returns: 1

  35. "????????????????????????????a?????????????"

    Returns: 794094937

  36. "????falo?uf??uf??lofffa?o???"

    Returns: 27

  37. "bbuf?f??o?fa??"

    Returns: 1

  38. "buffalo"

    Returns: 1

  39. "????ub??f???fu?bf?????????????lo????o?f?l?"

    Returns: 826973544

  40. "?b?bubu?f?f?f????l??lo?fb?u?o????fa?o?falo"

    Returns: 2305045

  41. "bubfbuffbbbbubuffbuba?ufubfbufaloaloffallff?ofoffffaf?faflalloloufaooloufffaloalaloo"

    Returns: 3

  42. "b??u?b?b?u?fuf?u?l??f??bf???buobu?f?b?f??afl?a?uff?lo?lfoaf?lb?ffa??uf?fual??flf?l?ff???l???o?f?lo"

    Returns: 61414199

  43. "???????f????f?l?????u???????o?????a???????f?????????f??????f?????ll??o????l????????????????"

    Returns: 665548064

  44. "buffa?o"

    Returns: 1

  45. "bbbbbuuffffaablolububfuuffaflfouoff?ufaalfolfo??laoalolo"

    Returns: 3

  46. "b????ub??uf?u????aalfu?ffbf?fa??f??ofbf?uuf?of?a??l?loafafflolla?l?ooobuff???l?ffa??"

    Returns: 571392518

  47. "?????????????????????"

    Returns: 831389

  48. "buff?aubbulbfuo??l?fobfbu?alaoflouffauf?fofaloalo"

    Returns: 1

  49. "???bu???u?a???ub?lof???b???a??lf??l?u?fo????l???f??oalfao?llo??b??????"

    Returns: 963959456

  50. "?ub??buff?uf?baflaobu??uffluf??f?uf??baufl?o??lalfo?flflalobo?falooubuffffal?louoffal?f?al?"

    Returns: 12344046

  51. "bbb???bau???u?uff??ffl??ff??obufa??alooalo"

    Returns: 5072

  52. "?????????a?ob??buu?????ff???????????????u??????u?a???????????f??l??a??????o?????a???"

    Returns: 720312547

  53. "???????????o?????????????????????????a?o????l????"

    Returns: 598207029

  54. "bbb?b?u?b?u?bfuu??f?ff??albuffoaf?luffalf?o?offu?fffulbaallf?bo?ffoallfoaal?fufooalfo??alofalo??l?"

    Returns: 195153378

  55. "bbbb?ubbuffuuffubffffuauluabolbalauffffoufafffa?llolooolf?aalofolofa??"

    Returns: 1

  56. "?????????f????f?f????????????????obl???????????l????????????????????????l?o??"

    Returns: 28574571

  57. "?????bu?b???bfff?f?fauflbfu?auf??fllfl??oo?ffffa??aulu?oaa??o??llobufo??l???a?????al?o?f?lo"

    Returns: 600978495

  58. "?????ba????b?f?ab?f?????????????f??????????????ou?fl????"

    Returns: 674055717

  59. "bbbb?uub?f??f??f?a?fubl?foufaaffla?ol?u?lab?ofo?ofbuufffaa??fa?o?al?lo"

    Returns: 1049124

  60. "?????b????u??fb???l??u??fof????o???"

    Returns: 31417513

  61. "bbbuuu?b?ufffufau?o?abfblf?loofubff?bbbauu??uuuaff?floffal?f?ofo?alalaoof?lloo??ffa?ooffalo"

    Returns: 858

  62. "bbuufbfabbubulofbfbubuubuubfffffuffafalalofloffuobuaffffaffalalfoloalfaoaflolloa?loo"

    Returns: 1

  63. "b??????u?????????????????????a???u???????l?????????????????f???"

    Returns: 441648747

  64. "???????b??????????????al??u??????l?????o??"

    Returns: 444363122

  65. "??b???f????ob?ub?f??b???fubfl?????fa?ll?f??fal???fo?lo??f????ul?uu?f?l?f?ffa?o?f?????lo?al?"

    Returns: 607876326

  66. "bubb?bf?u?ffbfufabulfaloffaoluobuffaloa?fofffalf?a?ofal?"

    Returns: 3

  67. "b?b?ub?????????????b?????????????l????????f???u???fo????"

    Returns: 933602526

  68. "bbubbffufafl?ab?bulbubfbfouffbff?uufabfulua?ofalobullfoffu?al??loffalo?aloffa?offalo"

    Returns: 64

  69. "bb?bbbuubbuubufffbfalu?ffuofbualoufffal?u??fffaloa?a?ofaflloaalouoffalfolao?o"

    Returns: 8

  70. "?b??????????????????????????"

    Returns: 155338326

  71. "?u??????b????ufb????u?o?????????????????o??a??????????????????f??o??????f???o"

    Returns: 679930942

  72. "b?b???????au??l???f?f???????"

    Returns: 1454040

  73. "b?bbbuufbbufffaaf?foaloflofualfofal?buffualo?falo"

    Returns: 1

  74. "b???b?b?f?u???f??u?ufaalloob?lbfbf???l??ufo?floffffffal?a?????f?????lo??l?o??"

    Returns: 574382904

  75. "bbbubbbufubuffaubblffffaflauol?f?faauuflof??lofaflol?uffalooalo"

    Returns: 12

  76. "???uf?fu???a??b??f?u??u?f??f?fffu?f??af?f??lfu??l?l?ob?o???f?lbu?uloflf?lof??o??a??of??????l???a?o"

    Returns: 248711597

  77. "bb?f?b?f?lbuobf?aul?fuu?f?afall?aofolbou??alofa??"

    Returns: 34

  78. "bubbubfbbuffalobuuf?ffbfualaaloofubfalflouofbfaflalfobuu?ffafbolalouofalouffaloffalo"

    Returns: 1

  79. "???????????????????????????????????"

    Returns: 420429295

  80. "b??????f?f??f???????al??a???????f????????????????"

    Returns: 118117230

  81. "bbbbuuufffbfaffl?obbba?blbauobff?ffafuulal??ofo?fafalo?ffa?ou?faloal?lo?ffal?"

    Returns: 299

  82. "bbb??b?bfu?ub?????a?u?lf?o??f?????l??????fl??a??lo?f?floa?oouf?b?f??a???f???o"

    Returns: 527716165

  83. "????ff?l?o?fa?ob???????????al??fal?"

    Returns: 33747

  84. "????????ufbbufa??fb??f?fb???llouufuf???o???a??o??aloof?a?o??lo?lof???o"

    Returns: 50521634

  85. "??????????????????b?????????????????????o??????a???u???????????"

    Returns: 959728046

  86. "bbuu?fa?lobfu?fffaalloo?falo"

    Returns: 1

  87. "??????????u????????????????????????"

    Returns: 935554933

  88. "b??u??fa??ao?o"

    Returns: 4

  89. "b???fbu??bbul???f????f?a?f?l??l???ffb???ol?o??fa??????lo"

    Returns: 599471193

  90. "b????b??????f???b??????u?u???a??????fa?oa?of?l?lo??ff???"

    Returns: 537034534

  91. "??????u?uf?????f???????u????f????????llaf??b?u????f??????l??l?f?f??????fff????????lo"

    Returns: 395166881

  92. "buffalo"

    Returns: 1

  93. "?????u?????f?f?l??u???????o?????o??u???????u?????????????????lo?u?fal?"

    Returns: 885100260

  94. "b?u??????u??u??u?l??????l???ualo?f???o???alf?fa?o"

    Returns: 418673076

  95. "b?ufubuffalof?falaloo"

    Returns: 1

  96. "b??uubff?ubffffffabaaufllo??lol?of?a?o?alo"

    Returns: 12

  97. "b????f?????f??????a??????fa?l??b???????????ou?f?????????"

    Returns: 733939226

  98. "?b???fbu?f?u?ff??aau?l????uba?fa??f?o?al?ofa?oalo??falo?"

    Returns: 178158486

  99. "bbbufuf?ufalabfufolfo???uf?o?aalolo"

    Returns: 9

  100. "??b???????????????o??"

    Returns: 121503

  101. "?????????f??????f???a????a??f??ol?l?????a???f?a?o"

    Returns: 631472292

  102. "????????u?f??????????"

    Returns: 83258

  103. "????b???????????b???f??????????l??????????????????????????f?????a??????????????????l???????fa?????"

    Returns: 994973098

  104. "?buubff?luoffaloffalo"

    Returns: 1

  105. "???u????????ba??????b????u????lofu??floffal???o?lo???a??"

    Returns: 127530202

  106. "bbufbbfauluofuffaflfofaloalo"

    Returns: 1

  107. "??b???ff?ba?lb?bbfou?a???blff????ooo?uu?a?ff??ufuafllof?fa?ouaflfooaa??ffalolouf???o"

    Returns: 7986052

  108. "?"

    Returns: 0

  109. "??????"

    Returns: 0

  110. "????????????????????????????????????????????????????????????????????????????????????????????????????"

    Returns: 0

  111. "????????????????????????????????????????????????l?????????????????????????????????????????????o???"

    Returns: 533950203

  112. "??????????????????????????????????????????????????????????????????????????????????cc??????????????"

    Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: