409945: GYM103861 C String-dle Count

C. String-dle Counttime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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 O (capital letter O), - (dash), and 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 G are Prof. Pang's guesses and strings after 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$$$.

ExamplesInput

2 5
CRANE
xx--x
NASAL
OOxOO

Output

21

Input

1 5
BBBAA
xxxx-

Output

0

Input

2 5
ABCDE
-xxxx
ABCDE
xxxxx

Output

0

Input

1 3
ABC
---

Output

2

Input

1 15
AAAAAAAAAAAAAAB
-xxxxxxxxxxxxxx

Output

918547951

Input

1 15
AAAAAAAAAAAAAAA
-xxxxxxxxxxxxxx

Output

0

Input

1 1
K
x

Output

25

Note

For the second example:

If the answer is ACDEF, the guess BBBAA will produce a grade of xxx-x.