Statistics

Problem Statement for "ColorfulGardenHard"

Problem Statement

Our garden contains a single row of flowers. You are given the current contents of the row in the String garden. Each character in garden represents one flower. Different characters represent different colors. Flowers of the same color all look the same.


You may rearrange the flowers in your garden into any order you like. (Formally, you may swap any two flowers in your garden, and you can do so arbitrarily many times.)


You are also given a String forbid of the same length as garden. You want to rearrange garden into a new string G that will satisfy the following conditions:
  • No two adjacent flowers will have the same color. Formally, for each valid i, G[i] and G[i+1] must differ.
  • For each valid i, G[i] must not be equal to forbid[i].
Let X be the number of different strings G that satisfy all conditions given above. Compute and return the number (X modulo 1,000,000,007).

Definition

Class:
ColorfulGardenHard
Method:
count
Parameters:
String, String
Returns:
int
Method signature:
int count(String garden, String forbid)
(be sure your method is public)

Constraints

  • garden will contain between 1 and 15 elements, inclusive.
  • Each element in garden will be a lowercase English letter: 'a'-'z'.
  • garden and forbid will contain the same number of elements.
  • Each element in forbid will be a lowercase English letter: 'a'-'z'.

Examples

  1. "aaabbb"

    "cccccc"

    Returns: 2

    There are two solutions: "ababab" and "bababa".

  2. "aabbcc"

    "aabbcc"

    Returns: 5

    We have 5 solutions: "bcacba" "cbacba", "cbacab", "bcacab", "cbcaba".

  3. "aaaabb"

    "xxxxxx"

    Returns: 0

  4. "abcdefghijklmno"

    "zzzzzzzzzzzzzzz"

    Returns: 674358851

    The answer is (15!) % (10^9+7).

  5. "a"

    "b"

    Returns: 1

  6. "ba"

    "ac"

    Returns: 1

  7. "acabbcabacacb"

    "cacccbacacaaa"

    Returns: 6

  8. "cabbabbcb"

    "aaaccbbaa"

    Returns: 0

  9. "baaaacbacabcac"

    "aaabbaccacaabb"

    Returns: 0

  10. "acabccaabbb"

    "cabcaacccbc"

    Returns: 6

  11. "bcaabbc"

    "babcbca"

    Returns: 5

  12. "bccbbaca"

    "acbcabbc"

    Returns: 4

  13. "caaabb"

    "acaaab"

    Returns: 0

  14. "aabbcabcaacab"

    "aacacbaabcabb"

    Returns: 0

  15. "bbbbbcca"

    "cabcccbc"

    Returns: 0

  16. "ccaccdabcadaab"

    "cbabaaaabbabcb"

    Returns: 15

  17. "cdcbcdddac"

    "cbbaaababb"

    Returns: 63

  18. "adbabdcaaa"

    "bacababbcb"

    Returns: 34

  19. "aabdacbdabc"

    "bbbabccaccb"

    Returns: 245

  20. "adcabbcdaad"

    "bacbbacaccc"

    Returns: 468

  21. "ccdcdbbabca"

    "babccbbcbca"

    Returns: 234

  22. "dcdacdddddddddc"

    "acacbaaaaaccbca"

    Returns: 0

  23. "cddaccbdcdcda"

    "cacacaacbaaba"

    Returns: 187

  24. "bcccbcdbaccdaa"

    "acbcbbbbabaaba"

    Returns: 729

  25. "dccbacababdb"

    "baaabaaaabca"

    Returns: 192

  26. "abebbbbeeea"

    "abedccdddbb"

    Returns: 8

  27. "adadcdbcceadccd"

    "ebcabbaeabeecab"

    Returns: 41593

  28. "caadabcedaa"

    "debecdabdca"

    Returns: 198

  29. "becacaddbccdba"

    "eeaeccacbbdada"

    Returns: 71624

  30. "ebcbcdccaced"

    "debeabcddbce"

    Returns: 2552

  31. "cdeebaabdc"

    "abdaeccaac"

    Returns: 4168

  32. "dadbcbbbdc"

    "eabcebeecc"

    Returns: 194

  33. "cacabaeedca"

    "caeebceedbe"

    Returns: 1544

  34. "bebdcdcaaabeead"

    "cbdecddbecababc"

    Returns: 596037

  35. "bccebabaadb"

    "aaabebecdba"

    Returns: 811

  36. "ffeeececcfeff"

    "gebfabfcbbdfa"

    Returns: 78

  37. "ffgegcbbcddbe"

    "gbggdaffebfgc"

    Returns: 1006342

  38. "ccgbdegbgd"

    "cagfcgcgeb"

    Returns: 3084

  39. "eaacfeddcb"

    "dcggfcgbda"

    Returns: 26715

  40. "ecefffcgcgbedd"

    "gdbccgfgegfabg"

    Returns: 1882391

  41. "bgbebdgedb"

    "gaeffbgecd"

    Returns: 476

  42. "feeeeccgabbecgb"

    "eggfbgbabfaefee"

    Returns: 292446

  43. "cfaebbfaefbdgda"

    "fdggecfefefgaad"

    Returns: 30039183

  44. "cgbeaacedd"

    "ddgcacddfa"

    Returns: 12702

  45. "eecagccgdd"

    "cdeedgeeca"

    Returns: 1794

  46. "xoeqdaxzvtg"

    "omzgvfbidqy"

    Returns: 9345936

  47. "ifoojdqpnlb"

    "pimolvdxuqn"

    Returns: 7793214

  48. "olwngrojoefy"

    "nfcckigyjuty"

    Returns: 26051880

  49. "sgpjveswkrofmk"

    "gpvxanwcikqhrc"

    Returns: 596706657

  50. "dvsvpzzogxru"

    "stqrlytszeql"

    Returns: 53817120

  51. "skdmglfruiwhkbk"

    "dlrkeevtfkkccds"

    Returns: 357533612

  52. "ovdefdzezxtj"

    "ikjmdfaqykbz"

    Returns: 20452104

  53. "zsofismlmrpxw"

    "lmtjccmtkjmts"

    Returns: 516862080

  54. "jeupdqkrirq"

    "zrqlgnegvvv"

    Returns: 4186080

  55. "fsiuviffzosn"

    "awxxdlgoojkl"

    Returns: 6461232

  56. "fubjezameqoifzh"

    "grxdeefjetosojv"

    Returns: 564632252

  57. "yhniyjvgrcdzfkl"

    "zunnqobmkkvdzbx"

    Returns: 486487332

  58. "lgruepvsoajniet"

    "elbejvutrnlqswl"

    Returns: 605755796

  59. "wttqefxzdbdwpyk"

    "hnfqbckiekrznbc"

    Returns: 397820581

  60. "bjlpdxqktxaqmbt"

    "khtlnnmefqeezis"

    Returns: 737386540

  61. "vevikjpsopmkxon"

    "npojetneecdjwiw"

    Returns: 167219672

  62. "endvhoqzjamcqdg"

    "nhcsxlhhvflguli"

    Returns: 356269830

  63. "skjyycyfbyhykgr"

    "jxyquofwnklzmhr"

    Returns: 335041944

  64. "xfbxvvnkddffyel"

    "wcmzyoehtyxngjo"

    Returns: 476478823

  65. "phmrkziafuzxphz"

    "amumsdhbzqqswek"

    Returns: 10375405

  66. "fubjezameqoifzh"

    "grxdeefjetosojv"

    Returns: 564632252

  67. "yhniyjvgrcdzfkl"

    "zunnqobmkkvdzbx"

    Returns: 486487332

  68. "lgruepvsoajniet"

    "elbejvutrnlqswl"

    Returns: 605755796

  69. "wttqefxzdbdwpyk"

    "hnfqbckiekrznbc"

    Returns: 397820581

  70. "bjlpdxqktxaqmbt"

    "khtlnnmefqeezis"

    Returns: 737386540

  71. "vevikjpsopmkxon"

    "npojetneecdjwiw"

    Returns: 167219672

  72. "endvhoqzjamcqdg"

    "nhcsxlhhvflguli"

    Returns: 356269830

  73. "skjyycyfbyhykgr"

    "jxyquofwnklzmhr"

    Returns: 335041944

  74. "xfbxvvnkddffyel"

    "wcmzyoehtyxngjo"

    Returns: 476478823

  75. "phmrkziafuzxphz"

    "amumsdhbzqqswek"

    Returns: 10375405

  76. "orizaaahhaaanat"

    "gjroikmhdjqqvcc"

    Returns: 481344

  77. "aaegaaaiamaaaay"

    "mltxjzbbsutitnk"

    Returns: 0

  78. "zaagmakabarkbaa"

    "zjjmtrahqvobevd"

    Returns: 134730

  79. "sajawpkujagakay"

    "tjoeiaukosehpnz"

    Returns: 136581432

  80. "usazerhatxqaaaa"

    "awjmzjwzxhbqzoo"

    Returns: 19992720

  81. "gaaxfaqacafiaaa"

    "xkkpharspbeqrvu"

    Returns: 2160

  82. "hofpayffadgssra"

    "djdhckcackojcwp"

    Returns: 690711579

  83. "jarapaanyeapazr"

    "yfxyehealumhcfh"

    Returns: 7706352

  84. "ahlmauagtwhvaja"

    "vlhciilshlhdihe"

    Returns: 298324800

  85. "aspaztaaacjaaga"

    "lrafnzqsailuwsr"

    Returns: 0

  86. "acbdefghijklxyy"

    "abjfldsafjkldaw"

    Returns: 7869757

  87. "aaabbbcccddefgh"

    "zzzzzzzzzzzzzzz"

    Returns: 700479360

  88. "aabbcccdefg"

    "aaabbbfffee"

    Returns: 96228

  89. "abcdefghijklmno"

    "abcdefghijklmno"

    Returns: 66512367

  90. "aabcdefghijklmn"

    "zzzzzabceyjiama"

    Returns: 851355527

  91. "abbcccddddeeeee"

    "abcdeabcdeabcde"

    Returns: 64225

  92. "abcdefghzxvfj"

    "mmmmmmmmzmmmm"

    Returns: 431295986

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: