3867. [USACO23 Feb Platinum] Problem Setting

【题目描述】

农夫约翰想要创建一个问题集。

为此，他一共找到了 $N$ 个问题，编号 $1 \sim N$。

然后，他找了 $M$ 头奶牛来做这些题，每个奶牛对每个问题都有一个评价，要么是“简单”，要么是“困难”。

约翰希望创建的问题集满足以下所有条件：

$1$、问题集由按某种顺序排列的若干个问题组成，且问题集非空。

$2$、问题集内不存在两个问题 $a,b$ 满足，虽然问题 $a$ 排在问题 $b$ 的前面，但存在某个奶牛认为问题 $a$ 困难，而问题 $b$ 简单。

请你计算，约翰一共可以创建多少个不同的问题集。

结果对 $10^9+7$ 取模。

注意，包含问题相同，但是问题排列不同的问题集应被视为不同的问题集，例如 $[1,2,3]$ 和 $[1,3,2]$ 应被视为两个不同的问题集。

【输入格式】

第一行包含两个整数 $N,M$。

接下来 $M$ 行，每行包含一个长度为 $N$ 的字符串，每个字符要么为 $E$，要么为 $H$，其中第 $i$ 行第 $j$ 个字符表示第 $i$ 个奶牛对第 $j$ 个问题的评价，$E$ 表示简单，$H$ 表示困难。

【输出格式】

一个整数，表示可以创建的不同问题集数量对 $10^9+7$ 取模的结果。

【样例1输入】

3 1
EHE

【样例1输出】

9

【样例1解释】

$9$ 个可能的问题集如下：

$[1]$

$[1,2]$

$[1,3]$

$[1,3,2]$

$[2]$

$[3]$

$[3,1]$

$[3,2]$

$[3,1,2]$

【样例2输入】

10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

【样例2输出】

33

【样例3】

点击下载样例3

【数据规模与约定】

测试点 $1 \sim 2$：$M = 1$;

测试点 $3 \sim 12$：$M \leq 16$;

对于 $100\%$ 的数据，$1≤N≤10^5,1≤M≤20$。