P9874 [EC Final 2021] String-dle Count

最近大多数人都热衷于玩 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$ 取模。

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