← 返回题目

题库练习「USACO 2023.2 Platinum」Problem Setting

← 上一题下一题 →

A6158 | $「USACO 2023.2 Platinum」Problem Setting$

时间限制2s

内存限制512MB

通过 / 提交0/0

题目描述

**题目译自 [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$ 取模。

输入格式

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

输出格式

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

输入输出样例

输入 #1

3 1
EHE

输出 #1

输入 #2

10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

输出 #2

C++ 编辑器

输入

输出