题目描述

注意：本题的内存限制为 512MB，是默认值的两倍。

农夫约翰创建了 $N(1 \le N \le 10^5)$ 个问题。然后他招募了 $M (1 \le M \le 20)$ 个测试解答者，每个解答者将每个问题评为“简单”或“困难”。

他的目标是创建一个按难度递增顺序排列的问题集，该问题集由他的 $N$ 个问题的某个子集按某种顺序排列而成。必须不存在这样的一对问题，使得某个测试解答者认为顺序中后面的那个问题简单，而前面的那个问题困难。

计算他可以形成的不同非空问题集的数量，结果对 $10^9+7$ 取模。

输入格式

第一行包含 $N$ 和 $M$。

接下来的 $M$ 行每行包含一个长度为 $N$ 的字符串。如果测试解答者认为第 $i$ 个问题简单，则该字符串的第 $i$ 个字符为 E，否则为 H。

输出格式

FJ 可以形成的不同问题集的数量，对 $10^9+7$ 取模。

输入输出样例 #1

输入 #1

3 1
EHE

输出 #1

9

输入输出样例 #2

输入 #2

10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

输出 #2

33

说明/提示

样例 1 的解释

九个可能的问题集如下：

$[1]$
$[1,2]$
$[1,3]$
$[1,3,2]$
$[2]$
$[3]$
$[3,1]$
$[3,2]$
$[3,1,2]$

注意问题集内问题的顺序很重要。

评分

• 输入 $3-4$：$M=1$
• 输入 $5-14$：$M \le 16$
• 输入 $15-22$：无额外限制。

题面翻译由 ChatGPT-4o 提供。