#PU1309. USACO 2023 February Contest, Platinum — Problem 2. Problem Setting

USACO 2023 February Contest, Platinum — Problem 2. Problem Setting

USACO 2023 February Contest, Platinum — Problem 2. Problem Setting

题目描述

Note: The memory limit for this problem is 512MB, twice the default. Farmer John created NN (1≤N≤1051\le N\le 10^5) problems. He then recruited MM (1≤M≤201\le M\le 20) test-solvers, each of which rated every problem as "easy" or "hard." His goal is now to create a problemset arranged in increasing order of difficulty, consisting of some subset of his NN problems arranged in some order. There must exist no pair of problems such that some test-solver thinks the problem later in the order is easy but the problem earlier in the order is hard. Count the number of distinct nonempty problemsets he can form, modulo 109+710^9+7.

输入格式

The first line contains NN and MM. The next MM lines each contain a string of length NN. The iith character of this string is E if the test-solver thinks the iith problem is easy, or H otherwise.

输出格式

The number of distinct problemsets FJ can form, modulo 109+710^9+7.

数据范围

Inputs 3-4: M=1M=1 Inputs 5-14: M≤16M\le 16 Inputs 15-22: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

3 1
EHE
9
The nine possible problemsets are as follows:
[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
33