#include <iostream>
#define ll long long
using namespace std;
const ll md = 1000000007;
inline ll qp(ll x, ll y) {
    ll rt = 1;

    for (; y; y >>= 1, (x *= x) %= md)
        if (y & 1)
            (rt *= x) %= md;

    return rt;
}
int main() {
    int n, m;
    cin >> n >> m;

    if (n > m)
        swap(n, m);

    if (n == 1)
        cout << qp(2, m);

    if (n == 2)
        cout << 4 * qp(3, m - 1) % md;

    if (n == 3)
        cout << 112 * qp(3, m - 3) % md;

    if (n > 3) {
        if (n == m)
            cout << (83 * qp(8, n) + 5 * qp(2, n + 7)) % md * 190104168 % md;
        else
            cout << (83 * qp(8, n) % md + qp(2, n + 8))*qp(3, m - n - 1) % md * 570312504 % md;
    }
}

算法标签

• $快速幂$
• $分类讨论$
• $数学公式$
• $模运算$

问题核心

给定 $n\times m$ 的棋盘，每个格子填 $0$ 或 $1$，满足约束：若路径移动字符串 $w(P_1) > w(P_2)$（字典序），则数字字符串 $s(P_1) \le s(P_2)$（字典序）。求合法填法数，答案对 $10^9+7$ 取模。

核心思路

1. 行列对称：交换 $n$ 和 $m$ 使 $n\le m$，填法数不变，简化讨论。
2. 分类计算：按 $n$ 的取值套用预推导公式，大指数通过快速幂高效求解。
3. 模运算保障：所有运算后取模 $10^9+7$，逆元预存为常量，避免除法溢出。

核心分类公式（$n\le m$）

代码关键

• 快速幂（qp）：$O(\log y)$ 计算大指数幂，避免超时。
• 模运算：所有乘法后取模，防止数值溢出。
• 逆元常量：$190104168$、$570312504$ 是模意义下除法的转化系数。

复杂度

• 时间：$O(\log \max(n,m))$（仅快速幂开销）
• 空间：$O(1)$（仅用常量级变量）