Problem Setting

시간 제한1초메모리 제한1024 MB

요약

어떤 검증자도 어려운 문제 뒤에 쉬운 문제를 보지 않도록 정렬할 수 있는 N개 문제의 비어 있지 않은 부분집합의 수를 센다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 정렬, 비트 연산, 조합론
정답자: 아직 제출이 없습니다

문제

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$ .

예제2

예제 1
입력
```
3 1
EHE
```
예상 출력
```
9
```

예제 2

입력

10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

예상 출력