Problem Setting

题目描述

注意：本题的内存限制为 512MB，是默认值的两倍。 农夫约翰创建了 $N$ 道题目（$1\le N\le 10^5$）。随后他招募了 $M$ 名（$1\le M\le 20$）测评者，每人将每道题评为“简单（easy）”或“困难（hard）”。 他的目标是制作一个按难度递增排列的题单，该题单由他这 $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

提示

这九种可能的题单如下： [1] [1,2] [1,3] [1,3,2] [2] [3] [3,1] [3,2] [3,1,2] 注意题单中题目的顺序是重要的。 SCORING: Inputs 3-4: $M=1$ Inputs 5-14: $M\le 16$ Inputs 15-22: No additional constraints. Problem credits: Benjamin Qi

标签: USACO|2023|Platinum

来源

USACO|2023|Platinum