如今大多数人都喜欢玩 Wordle，而 Prof. Pang 则沉迷于 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

系统随后会将由 O（大写字母 O）、-（短横线）和 x（小写字母 x）组成的评分返回给玩家，玩家可以根据之前的评分进行下一次猜测。以下是 Prof. Pang 进行的一局游戏示例：

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

G 后的字符串是 Prof. Pang 的猜测，A 后的字符串是该猜测的评分。

Prof. Pang 非常喜欢这个游戏。他相信自己已经开发出了一套完美的策略。然而，今天他快疯了，因为他认为评分系统出 bug 了！他希望有人能写一个分析程序，根据他提供的猜测列表和评分，计算出有多少种可能的字符串可以作为谜题的答案。

由于评分系统可能存在 bug，它可能不符合上述伪代码。因此，具体任务是找出有多少个字符串与输入一致。如果对于输入中的任意猜测 $g$ 及其对应的评分 $d$，都有 grading(s, g)=d，则称字符串 $s$ 与输入一致。

输入格式

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

接下来的行中，每两行分别包含一个猜测和一个评分。

输出格式

一个整数，表示可能的答案数量，对 $10^9 + 7$ 取模。

样例

样例 1

2 5
CRANE
xx--x
NASAL
OOxOO

21

样例 2

1 5
BBBAA
xxxx-

0

样例 3

2 5
ABCDE
-xxxx
ABCDE
xxxxx

0

样例 4

1 3
ABC
---

2

样例 5

1 15
AAAAAAAAAAAAAAB
-xxxxxxxxxxxxxx

918547951

样例 6

1 15
AAAAAAAAAAAAAAA
-xxxxxxxxxxxxxx

0

样例 7

1 1
K
x

25

说明

对于第二个样例： 如果答案是 ACDEF，那么猜测 BBBAA 将产生评分 xxx-x。