题目描述

最近大多数人都热衷于玩 Wordle，但 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

系统随后返回由 $\tt{O}$（大写字母 O）、$\tt{-}$（破折号）和 $\tt{x}$（小写字母 x）组成的评分，玩家可基于之前的评分进行下一次猜测。以下是 Pang 教授玩过的一局游戏示例：

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

$\tt{G}$ 后的字符串是 Pang 教授的猜测，$\tt{A}$ 后的字符串是相应猜测的评分。

Pang 教授十分喜爱这个游戏。他相信自己已经为它开发出了一套完美的策略。然而，今天他发狂了，因为他认为评分系统有 bug！他想找人写一个分析程序，根据他的猜测和评分列表，计算出可能作为谜题答案的字符串数量。

由于评分系统可能存在 bug，它可能并不遵循上述伪代码。所以具体来说，任务是找出与输入一致的字符串有多少个。一个字符串 $s$ 与输入一致，当且仅当对于输入中的每个猜测 $g$ 及其对应评分 $d$，都有 $\text{grading}(s, g) = d$。

当然，编程实现就交给你了。

输入格式

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

接下来若干行，每行依次给出一个猜测和一个评分，一一对应。

输出格式

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

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

提示

对于第二个样例：如果答案是 $\tt{ACDEF}$，猜测 $\tt{BBBAA}$ 将得到评分 $\tt{xxx-x}$。

翻译由 DeepSeek V4 Pro 完成