Counting Valid Increasing Problemsets

Farmer John has created N problems and recruited M test‐solvers. Each test‐solver rates every problem as either easy or hard (with easy corresponding to 0 and hard corresponding to 1). He wishes to form a nonempty problemset (an ordered subset of his problems) such that the problems can be arranged in an order in which the difficulty ratings are non‐decreasing for every test‐solver. In other words, there must exist no pair of problems such that some test‐solver thinks the later problem is easy but the earlier one is hard.

Equivalently, if we represent each problem by an M‐bit binary number (where the j^th bit is 0 if test‐solver j rated it as easy and 1 if rated hard), the chosen problems (which may come from the same binary pattern) must form a chain under the coordinate‐wise partial order. Two different problems with the same rating (binary pattern) are always comparable, and a valid chain that mixes different binary patterns must follow the rule that for any two distinct chosen patterns P and Q with P appearing before Q we have P ≤ Q (i.e. for every j, P_j ≤ Q_j).

Your task is to count the total number of distinct nonempty problemsets Farmer John can form, modulo \(10^9+7\). Note that within a group of problems having the same rating pattern, any nonempty subset is allowed. For problems of different rating patterns, a valid chain can only be formed if the patterns are comparable under the subset relation (when viewing the set of indices where the rating is hard).

Note: The memory limit for this problem is 512MB, twice the default.

inputFormat

The first line contains two integers, N and M (1 ≤ N ≤ 10^5 and 1 ≤ M ≤ 20), representing the number of problems and the number of test‐solvers respectively.

Each of the next N lines contains M tokens. Each token is either easy or hard, representing the rating given by one test‐solver for that problem.

outputFormat

Output a single integer: the number of valid nonempty problemsets that can be formed, modulo \(10^9+7\).

sample

3 2
easy easy
easy hard
hard hard

7