Description

当大多数人都沉迷于玩 Wordle 的时候，庞教授却已经沉迷于玩 String-dle 了。

String-dle 是一个有趣的猜字符串的游戏，玩家在玩的时候要通过几轮尝试，猜出一个长度为 $k$ 的字符串。并且在每轮尝试中，玩家要提交一个长度为 $k$ 的字符串来作为他的猜测，而系统通过以下伪代码来为提交的猜测评级：

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

返回的评级包括 $\tt{O}$（大写字母 O）、$\tt{-}$（破折号）和 $\tt{x}$（小写字母 x），且玩家可以基于先前的评级进行下一次猜测。下面是庞教授玩的一局游戏示例：

G: CRANE
A: xx--x
G: UTTER
A: xxOxx
G: NASAL
A: OOxOO
G: NATAL
A: OOOOO

在字符串 $\tt{G}$ 后面的是庞教授的猜测，以及在字符串 $\tt{A}$ 后面的是该次猜测的评级。

庞教授非常喜欢这个游戏。他确信他已经知道了这个游戏的完美策略。然而，今天他很生气，因为他认为评级系统出了问题！他想让人写一个分析程序，根据他的猜测与评级找出所有可能的可以作为答案的字符串。

由于评级系统可能出了问题，所以它可能不再符合上面给出的伪代码。具体来说，你需要找到所有符合输入的字符串。一个符合输入的字符串是指，对于输入中任意一个猜测 $g$ 和它的正确评级 $d$，都符合 grading(s, g)=d。

当然，你接受了这个任务。

Input Format

第一行是两个整数 $n$、$k$ $(1 \le n \le 10^4, 1 \le k \le 19)$，分别是猜测的次数和字符串的长度。

下面共有 $2n$ 行，每两行都对应一个猜测和它对应的评级。

Output Format

一个整数，表示有多少种可能的答案，并模 $10^9+7$.

样例 #1

样例输入 #1

2 5
CRANE
xx--x
NASAL
OOxOO

样例输出 #1

21

样例 #2

样例输入 #2

1 5
BBBAA
xxxx-

样例输出 #2

0

样例 #3

样例输入 #3

2 5
ABCDE
-xxxx
ABCDE
xxxxx

样例输出 #3

0

样例 #4

样例输入 #4

1 3
ABC
---

样例输出 #4

2

样例 #5

样例输入 #5

1 15
AAAAAAAAAAAAAAB
-xxxxxxxxxxxxxx

样例输出 #5

918547951

样例 #6

样例输入 #6

1 15
AAAAAAAAAAAAAAA
-xxxxxxxxxxxxxx

样例输出 #6

0

样例 #7

样例输入 #7

1 1
K
x

样例输出 #7

25

2 5
CRANE
xx--x
NASAL
OOxOO

21

1 5
BBBAA
xxxx-

0

2 5
ABCDE
-xxxx
ABCDE
xxxxx

0

1 3
ABC
---

2

1 15
AAAAAAAAAAAAAAB
-xxxxxxxxxxxxxx

918547951

1 15
AAAAAAAAAAAAAAA
-xxxxxxxxxxxxxx

0

1 1
K
x

25

Hint

对于第二个样例:

如果答案是 $\tt{ACDEF}$，则 $\tt{BBBAA}$ 的评级为 $\tt{xxx-x}$.