[EC Final 2021] String-dle Count

Luogu

IDLGP9874

Time1000ms

Memory1024MB

DifficultyP6

动态规划 DP2021O2优化ICPCEC Final

While most people love to play Wordle these days, Prof. Pang has become addicted to String-dle. String-dle is an interesting string-guessing game where the player tries to guess a string of $k$ capital letters through several rounds. In each round, the player submits a string of length $k$ as his guess, and the system grades the guess through the following pseudo-code: ``` def grading(answer, guess): let count be a hash map for i = 1 to k: if answer[i] not in count: count[answer[i]] = 1 else: count[answer[i]] = count[answer[i]] + 1 let grade be an array of length k for i = 1 to k: if answer[i] == guess[i]: grade[i] = 'O' count[guess[i]] = count[guess[i]] - 1 for i = 1 to k: if answer[i] != guess[i]: if count[guess[i]] > 0: grade[i] = '-' count[guess[i]] = count[guess[i]] - 1 else: grade[i] = 'x' return grade ``` The grade consisting of $\tt{O}$ (capital letter O), $\tt{-}$ (dash), and $\tt{x}$ (small letter x) is then returned to the player, and the player may base his next guess on the previous grades. The following is an example of one game Prof. Pang played: ``` G: CRANE A: xx--x G: UTTER A: xxOxx G: NASAL A: OOxOO G: NATAL A: OOOOO ``` Strings after $\tt{G}$ are Prof. Pang's guesses and strings after $\tt{A}$ are the grades of the guesses. Prof. Pang really enjoys the game. He believes that he has developed a perfect strategy for it. However, today he goes mad because he thinks the grading system is bugged! He wants to have someone write an analysis program to figure out the number of possible strings that can be the answer to the puzzle based on his list of guesses and grades. Since the grading system might be bugged, it might not conform to the pseudo-code given above. So specifically, the task is to find how many strings that are consistent with the input. A string s is consistent with the input if for any guess g in the input and its corresponding grade d, grading(s, g)=d. And of course, you will be doing the programming. ## Input The first line consists of two integers $n$ and $k$ $(1 \le n \le 10^4, 1 \le k \le 19)$, which are the number of guesses and the length of the string, respectively. The following lines consist of the guesses and the grades, one per line, correspondingly. ## Output An integer, denoting how many possible answers there are, modulo $10^9+7$. [samples] ## Note For the second example: If the answer is $\tt{ACDEF}$, the guess $\tt{BBBAA}$ will produce a grade of $\tt{xxx-x}$.

Samples

Input #1

2 5
CRANE
xx--x
NASAL
OOxOO

Output #1

Input #2

1 5
BBBAA
xxxx-

Output #2

Input #3

2 5
ABCDE
-xxxx
ABCDE
xxxxx

Output #3

Input #4

1 3
ABC
---

Output #4

Input #5

1 15
AAAAAAAAAAAAAAB
-xxxxxxxxxxxxxx

Output #5

918547951

Input #6

1 15
AAAAAAAAAAAAAAA
-xxxxxxxxxxxxxx

Output #6

Input #7

1 1
K
x

Output #7

API Response (JSON)

{
  "problem": {
    "name": "[EC Final 2021] String-dle Count",
    "description": {
      "content": "While most people love to play Wordle these days, Prof. Pang has become addicted to String-dle. String-dle is an interesting string-guessing game where the player tries to guess a string of $k$ capit",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9874"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "While most people love to play Wordle these days, Prof. Pang has become addicted to String-dle.\n\nString-dle is an interesting string-guessing game where the player tries to guess a string of $k$ capit...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments