Note: The memory limit for this problem is 512MB, twice the default.
Farmer John created N (1≤N≤105) problems. He then recruited M (1≤M≤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 109+7.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N and M.
The next M lines each contain a string of length N. The ith character of this string is E if the test-solver thinks the ith problem is easy, or H otherwise.
OUTPUT FORMAT (print output to the terminal / stdout):
The number of distinct problemsets FJ can form, modulo 109+7.
SAMPLE INPUT:
3 1
EHE
SAMPLE OUTPUT:
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]
Note that the order of the problems within the problemset matters.
SAMPLE INPUT:
10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE
SAMPLE OUTPUT:
33
SCORING:
Inputs 3-4: M=1
Inputs 5-14: M≤16
Inputs 15-22: No additional constraints.
Problem credits: Benjamin Qi