A6158. 「USACO 2023.2 Platinum」Problem Setting
编程题
省选/NOI-
知识点
题目描述
**题目译自 [USACO 2023 February Contest, Platinum](http://usaco.org/index.php?page=feb23results) Problem 2. [Problem Setting](http://usaco.org/index.php?page=viewproblem2&cpid=1309)**
FJ 造了 $N\ (1\le N\le 10^5)$ 道题。然后他招募了 $M\ (1\le M\le 20)$ 位验题人，每名验题人都将每道题评为了「简单」或「困难」中的一种。
他的目标是组一套按照难度顺序递增排序的题，这套题由这 $N$ 道题的某个子集按照一定顺序排列组成。必须不存在一对题目，满足某名验题人认为的简单题出现在困难题的后面。
计算他能组出的不同非空套题的数量，对 $10^9+7$ 取模。
FJ 造了 $N\ (1\le N\le 10^5)$ 道题。然后他招募了 $M\ (1\le M\le 20)$ 位验题人，每名验题人都将每道题评为了「简单」或「困难」中的一种。
他的目标是组一套按照难度顺序递增排序的题，这套题由这 $N$ 道题的某个子集按照一定顺序排列组成。必须不存在一对题目，满足某名验题人认为的简单题出现在困难题的后面。
计算他能组出的不同非空套题的数量，对 $10^9+7$ 取模。
输入格式
第一行两个整数 $N,M$。
接下来 $M$ 行，每行一个长度为 $N$ 的字符串。如果第 $i$ 个字符是
接下来 $M$ 行，每行一个长度为 $N$ 的字符串。如果第 $i$ 个字符是
E，则这位验题人认为这道题简单，否则第 $i$ 个字符为 H。输出格式
输出他能组出的不同非空套题的数量，对 $10^9+7$ 取模。
输入输出样例
输入 #1
3 1 EHE
输出 #1
9
输入 #2
10 6 EHEEEHHEEH EHHHEEHHHE EHEHEHEEHH HEHEEEHEEE HHEEHEEEHE EHHEEEEEHE
输出 #2
33
说明/提示
- 3-4 组数据：$M=1$
- 5-14 组数据：$M\le 16$
- 15-22 组数据：无附加限制
- 5-14 组数据：$M\le 16$
- 15-22 组数据：无附加限制