题目描述

题目译自 USACO 2023 February Contest, Platinum Problem 2. Problem Setting

FJ 造了 $N\ (1\le N\le 10^5)$ 道题。然后他招募了 $M\ (1\le M\le 20)$ 位验题人，每名验题人都将每道题评为了「简单」或「困难」中的一种。

他的目标是组一套按照难度顺序递增排序的题，这套题由这 $N$ 道题的某个子集按照一定顺序排列组成。必须不存在一对题目，满足某名验题人认为的简单题出现在困难题的后面。

计算他能组出的不同非空套题的数量，对 $10^9+7$ 取模。

输入格式

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

接下来 $M$ 行，每行一个长度为 $N$ 的字符串。如果第 $i$ 个字符是 E，则这位验题人认为这道题简单，否则第 $i$ 个字符为 H。

输出格式

输出他能组出的不同非空套题的数量，对 $10^9+7$ 取模。

3 1
EHE

9

10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

33

数据范围与提示

• 3-4 组数据：$M=1$
• 5-14 组数据：$M\le 16$
• 15-22 组数据：无附加限制