| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 63 | 41 | 38 | 67.857% |
Farmer John created $N$ (1ドル\le N\le 10^5$) problems. He then recruited $M$ (1ドル\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 $N$ 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 10ドル^9+7$.
The first line contains $N$ and $M$.
The next $M$ lines each contain a string of length $N$. The $i$th character of this string is E if the test-solver thinks the $i$th problem is easy, or H otherwise.
The number of distinct problemsets FJ can form, modulo 10ドル^9+7$.
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]
10 6 EHEEEHHEEH EHHHEEHHHE EHEHEHEEHH HEHEEEHEEE HHEEHEEEHE EHHEEEEEHE
33