好的，我们先来一步步分析这个问题。

---

题意理解

我们有：

• $N$ 道题，编号 $1 \dots N$
• $M$ 个验题人，每个验题人对每道题的评分是 E（简单）或 H（困难）
• 我们要选一个 非空子集 的题目，并按一定顺序排列，形成一套题
• 要求：对于任意一个验题人，不能 出现他认为是 简单 的题排在 困难 的题后面
• 问满足条件的 不同非空套题 的数量（顺序不同算不同套题）

---

条件转化

对于一套题 $p_1, p_2, \dots, p_k$，条件是说：

对任意验题人 $j$，不存在 $a < b$ 使得验题人 $j$ 认为 $p_a$ 是 H，$p_b$ 是 E。

换句话说，对于每个验题人，所有他认为是 H 的题必须出现在所有他认为是 E 的题之前。

---

等价形式

设对于验题人 $j$，题目 $x$ 的评分是 $r_j(x) \in \{0,1\}$（0 表示 E，1 表示 H）。

那么条件就是：
对于每个 $j$，序列 $r_j(p_1), r_j(p_2), \dots, r_j(p_k)$ 必须是 全 1 在前，全 0 在后（即形如 111...000，允许没有 1 或没有 0）。

---

多个验题人

对于 $M$ 个验题人，每个验题人给出一个 0/1 向量。
条件等价于：存在一个分割点 $t_j$ 使得前 $t_j$ 个题对 $j$ 来说都是 1，后面的都是 0。

但不同验题人的分割点可能不同。
不过关键点是：对于任意两道题 $u, v$，如果它们在最终排列中 $u$ 在 $v$ 前面，那么必须满足：对每个验题人 $j$，不能出现 $r_j(u) = 0$ 且 $r_j(v) = 1$。

因为如果 $u$ 在 $v$ 前，且对某个 $j$ 有 $r_j(u)=0$ 且 $r_j(v)=1$，那么 $u$（E）在 $v$（H）前面，这是不允许的。

---

偏序关系

定义偏序关系 $\preceq$：

$u \preceq v$ 当且仅当 不存在 验题人 $j$ 使得 $r_j(u) = 0$ 且 $r_j(v) = 1$。

换句话说，对每个验题人 $j$，要么 $r_j(u) = 1$，要么 $r_j(v) = 0$（即不能出现 u 是 E 且 v 是 H）。

那么允许的排列就是：排列中任意相邻元素 $p_i, p_{i+1}$ 满足 $p_i \preceq p_{i+1}$。

---

进一步简化

这个偏序 $\preceq$ 可以这样理解：

设题目 $u$ 的评分向量是 $s_u \in \{0,1\}^M$。

$u \preceq v$ 当且仅当 $s_u \ge s_v$（按分量比较）？
不对，我们检查一下：

条件：对每个 $j$，不能 $s_u[j]=0$ 且 $s_v[j]=1$。
即：对每个 $j$，$s_u[j] \ge s_v[j]$ 吗？
如果 $s_u[j]=1$ 且 $s_v[j]=0$，这是允许的（H 在 E 前是允许的）。
所以实际上是：对每个 $j$，$s_u[j] \ge s_v[j]$ 吗？
检查：$s_u[j]=1, s_v[j]=0$ 时 $1 \ge 0$ 成立；
$s_u[j]=0, s_v[j]=1$ 时 $0 \ge 1$ 不成立，这正是我们要禁止的情况。
$s_u[j]=0, s_v[j]=0$ 允许；$s_u[j]=1, s_v[j]=1$ 允许。

所以 $u \preceq v$ 当且仅当 $s_u \ge s_v$ 按分量比较。

---

问题变成

我们要求的是：在偏序集 $(P, \le)$（这里 $\le$ 是 $s_u \ge s_v$ 按分量）中，计算所有非空链（全序子集）的数量，链中元素可以任意排列吗？
注意：在链中任意排列都合法吗？

如果 $u$ 和 $v$ 可比（比如 $s_u \ge s_v$），那么排列 $(u,v)$ 是合法的，$(v,u)$ 呢？
如果 $s_u \ge s_v$ 且 $s_u \ne s_v$，则 $s_v \ge s_u$ 不成立，所以 $(v,u)$ 不合法。
所以链中元素的顺序是唯一确定的（按 $s$ 降序排列）？
等一下，$s_u \ge s_v$ 意味着 $u$ 可以排在 $v$ 前面，如果 $s_u = s_v$，那么两个方向都合法，所以它们可以任意顺序。

所以：

• 如果 $s_u = s_v$，它们可以任意顺序（两个方向都合法）
• 如果 $s_u > s_v$（按分量），则只能 $u$ 在 $v$ 前
• 如果 $s_u$ 与 $s_v$ 不可比（即存在某位 $s_u[j]=0, s_v[j]=0$ 或 1,1 不构成全序），则不能相邻？不对，如果不可比，则两个方向都不行（因为两个方向都会违反某位的关系）。

检查不可比情况：
$s_u = 01, s_v = 10$
$u \preceq v$? 对 j=1: 0,1 不行；对 j=2: 1,0 允许？等等，我们条件是对所有 j 不能出现 (0,1)，这里 j=1 已经出现了 (0,1)，所以 $u \preceq v$ 不成立。
$v \preceq u$? 对 j=1: 1,0 允许；对 j=2: 0,1 不行。所以也不成立。
所以不可比时，两个方向都不允许。

---

结论

允许的排列是：序列中任意相邻对 $(a,b)$ 必须满足 $s_a \ge s_b$（按分量），即 $a$ 的向量每个分量 $\ge b$ 的对应分量。

所以这个排列必须是 $s$ 向量的一个 非递增链（按分量偏序）。

---

问题转化为

给定 $N$ 个 $M$ 维 0/1 向量，计算所有非空序列的数量，使得序列中每个相邻对满足前一个向量 $\ge$ 后一个向量（按分量）。

---

解法思路

设 $dp[x]$ 表示以向量 $x$ 结尾的序列的个数（$x$ 是 $M$ 位二进制数，0=E, 1=H）。

初始：$dp[x] = 1$（单独一个题）

转移：
$dp[x] = 1 + \sum_{y \ge x} dp[y]$
其中 $y \ge x$ 按分量，即 $y$ 的二进制位包含 $x$ 的二进制位（$y \ \&\ x = x$）。

因为 $y \ge x$ 意味着 $y$ 的每个分量 $\ge x$ 的对应分量，即 $y$ 的 1 位包含 $x$ 的 1 位。

所以 $y$ 是 $x$ 的超集（在二进制表示下）。

---

算法

1. 将 $N$ 道题按它们的评分向量（转成 $[0,2^M)$ 的整数）分组，统计每个整数值的出现次数 $cnt[val]$。
2. 设 $dp[mask]$ 表示以 $mask$ 结尾的序列总数。
3. 按 $mask$ 从大到小遍历（按二进制包含关系，用 SOS DP 技巧）：
   • 初始 $dp[mask] = cnt[mask]$（单独一个题）
   • 对每个 $mask$，枚举它的超集 $sup$（$sup \ \&\ mask = mask$ 且 $sup > mask$），把 $dp[sup]$ 加到 $dp[mask]$ 中。
   • 注意：这里 $dp[mask]$ 表示以 恰好 $mask$ 向量 结尾的序列数，但转移时 $sup$ 是 $mask$ 的超集，所以 $mask \le sup$，所以 $mask$ 可以接在 $sup$ 后面。 等等，我们要求序列是递减的，所以 $sup$ 在 $mask$ 前面，所以应该是 $dp[sup]$ 从 $dp[mask]$ 转移？不对，我们定义 $dp[x]$ 是以 $x$ 结尾的序列数，那么要得到 $dp[x]$，就要找所有 $y \ge x$ 的 $dp[y]$ 加到 $dp[x]$ 上？不对，这样会重复计数。

让我们重新考虑：

设 $f[mask]$ = 以 $mask$ 结尾的序列总数。

那么 $f[mask] = cnt[mask] \cdot \left(1 + \sum_{y \ge mask} f[y]\right)$？
不对，这样会重复。我们仔细想：

如果我们有一个以 $y$ 结尾的序列（$y \ge mask$），我们可以在末尾加上一个 $mask$ 题（因为 $y \ge mask$ 允许 $mask$ 在 $y$ 后面）。
所以 $f[mask] = cnt[mask] + \sum_{y \ge mask} f[y] \cdot cnt[mask]$？
不对，这样会多乘 $cnt[mask]$。

正确做法：

$dp[mask]$ = 以 $mask$ 结尾的序列总数（包括不同题目 id，只要向量相同就视为相同？不对，题目是不同的，但题目向量相同时，它们可以互换位置，但这里我们只按向量做 DP，最后乘上题目数）。

更精确：
$dp[mask]$ = 以 某个 $mask$ 向量 结尾的序列个数（不乘 $cnt$ 在 dp 里，而在最后统计答案时乘）。

我们定义 $ways[mask]$ = 以 $mask$ 结尾的序列个数（不同题目区别）。

初始 $ways[mask] = cnt[mask]$（长度为 1 的序列）

转移：
$ways[mask] += cnt[mask] \cdot ways[sup]$ 对于 $sup \ge mask$。

因为对于每个以 $sup$ 结尾的序列，我们可以在末尾添加 任意一个 $mask$ 题目（只要 $sup \ge mask$），形成新的序列。

---

最终算法

1. 统计 $cnt[mask]$。
2. 初始化 $ways[mask] = cnt[mask]$。
3. 按 $mask$ 从大到小遍历（从 $2^M-1$ 到 0）：
   • 对每个 $mask$，枚举它的超集 $sup$（$sup \ \&\ mask = mask$ 且 $sup \neq mask$），做： $ways[mask] = (ways[mask] + cnt[mask] \cdot ways[sup]) \mod MOD$
4. 答案 = $\sum_{mask} ways[mask] - N$（减去长度为 1 的序列？不对，我们要求非空，已经包含所有长度，所以直接求和即可）。

---

复杂度

$O(3^M)$ 枚举超集，对于 $M \le 20$ 可接受（$3^{20} \approx 3.5 \times 10^9$ 有点大，但实际运行常数小，且可以用 SOS DP 优化到 $O(M \cdot 2^M)$）。

---

SOS DP 优化

我们想计算：
$ways[mask] = cnt[mask] + \sum_{sup \supset mask} cnt[mask] \cdot ways[sup]$

即 $ways[mask] = cnt[mask] \cdot \left(1 + \sum_{sup \supset mask} ways[sup]\right)$

那么设 $S[mask] = \sum_{sup \supset mask} ways[sup]$。

$S[mask]$ 是 $ways$ 的超集和，可以用 SOS DP 计算：

• 初始化 $S[mask] = ways[mask]$
• 对每一位 $bit$，从大到小遍历 $mask$，如果 $mask$ 的该位为 0，则 $S[mask] += S[mask | (1<<bit)]$

然后 $ways[mask] = cnt[mask] \cdot (1 + S[mask])$。

但这里 $S$ 依赖于 $ways$，而 $ways$ 又依赖于 $S$，所以要按 $mask$ 从大到小计算：

从 $mask = 2^M-1$ 到 0：

• $ways[mask] = cnt[mask] \cdot (1 + S[mask])$
• 更新 SOS 结构：$S[mask] = ways[mask]$ 然后加上子集贡献？
  不对，$S[mask]$ 是超集和，所以要从高 mask 往低 mask 推。

实际上我们可以直接做：

初始化 $ways[mask] = cnt[mask]$
然后对 $bit$ 从 0 到 M-1，对 $mask$ 从 $2^M-1$ 到 0，如果 $mask$ 的 $bit$ 位为 0，则
$ways[mask] += ways[mask | (1<<bit)] \cdot cnt[mask]$？
检查：$mask | (1<<bit)$ 是 $mask$ 的超集，所以 $ways[sup]$ 可以转移到 $ways[mask]$，乘上 $cnt[mask]$ 是因为末尾加上一个 $mask$ 题。

但这样会重复计数吗？我们试一下：

$ways[mask]$ 初始是 $cnt[mask]$（长度为 1）
然后对于每个超集 $sup$，我们把 $ways[sup]$（以 $sup$ 结尾的所有序列）后面接一个 $mask$ 题（有 $cnt[mask]$ 种选择）加到 $ways[mask]$。

这正是我们想要的。

所以算法：

ways[mask] = cnt[mask]
for bit = 0 to M-1:
  for mask = 2^M-1 down to 0:
    if ((mask >> bit) & 1) == 0:
      ways[mask] = (ways[mask] + ways[mask | (1<<bit)] * cnt[mask]) % MOD
ans = sum(ways) % MOD

---

最后答案

$\text{ans} = \sum_{mask} ways[mask]$ 就是所有非空合法序列的数量。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<int> cnt(1 << M, 0);
    for (int i = 0; i < M; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < N; j++) {
            if (s[j] == 'H') {
                cnt[j] |= (1 << i);
            }
        }
    }

    vector<int> freq(1 << M, 0);
    for (int i = 0; i < N; i++) {
        freq[cnt[i]]++;
    }

    vector<int> dp(1 << M, 0);
    for (int mask = 0; mask < (1 << M); mask++) {
        dp[mask] = freq[mask];
    }

    for (int bit = 0; bit < M; bit++) {
        for (int mask = (1 << M) - 1; mask >= 0; mask--) {
            if (!(mask >> bit & 1)) {
                int sup = mask | (1 << bit);
                dp[mask] = (dp[mask] + 1LL * dp[sup] * freq[mask]) % MOD;
            }
        }
    }

    int ans = 0;
    for (int mask = 0; mask < (1 << M); mask++) {
        ans = (ans + dp[mask]) % MOD;
    }

    cout << ans << "\n";

    return 0;
}

---

算法标签
动态规划、SOS DP（Sum Over Subsets）、偏序、排列计数