思路与算法

从任意格子出发，把向右子问题称R分支、向下子问题称D分支。由于R的字典序比D大，题意要求R分支所有数字串≤D分支所有数字串。于是除子问题自身合法外，只需maxString(R)≤minString(D)。满足时，本格最小串=本格数字接minString(R)，最大串=本格数字接maxString(D)；边界只有一个子分支，最小最大分别继承它。 从右下角向左上角逐条反对角线处理。同一条对角线上所有后缀串长度相同，只保存每格最小/最大后缀串的相对秩（相等串同秩），不保存指数多条路径。给新对角线枚举0/1赋值，每个新串等价于二元组(本格位,旧秩)，按字典序重新压成秩；不满足上述相邻分支条件的状态丢弃。下一条对角线必用的比较也可提前过滤。 令短边n、长边m。转置棋盘并补反所有位给出双射，所以可令n≤m。前n-1步对角线增长，中央有m-n次相同宽度转移，最后n-1步对角线缩小。枚举满宽可达秩状态闭包，构造每种位赋值贡献的转移次数矩阵，对中央阶段用矩阵快速幂。n=1时仅一条路径，直接2^m。

正确性说明

对从一格出发的全部路径，其移动串先按首步D、R分成两块。块内相对次序由后续路径决定，因此归纳题意条件等价于两块各自合法且所有R数字串不大于所有D数字串；后者严格等价max(R)≤min(D)。这个比较也说明最小值由R分支给出、最大值由D分支给出。边界只有一路，归纳起点为右下角单格，故局部递推与全部路径两两约束充要。 同长后缀串比较只用相对秩；添加新首位后，其顺序完全由(位,旧秩)确定，因此规范化没有丢失任何未来所需信息。每次枚举全部位赋值，给相同秩状态累加方式数，既不漏棋盘也不重复。提前过滤只检查下一对角线必须满足而与新首位无关的比较，不能成立的状态无任何后续扩展。增长、满宽、收缩三阶段完整覆盖所有格子，矩阵幂精确重复相同中央转移，故最后计数即答案。

复杂度

设S为满宽可达相对秩状态数，构造闭包与各对角线转移需O(n·S·2^n·n log n)，矩阵快速幂O(S³log m)，向量乘法O(S²log m)，空间O(S²+nS)。初始化包括状态闭包和矩阵清零O(S²)。n≤8时算法实际穷尽闭包的状态数依次为1、4、12、27、50、81、120、167；这一有限闭包由程序枚举而不是将答案硬编码。

易错点

路径移动串与数字串的大小关系相反，比较必须是max(R)≤min(D)。只比较相邻两个格子的数字会漏掉首位相等后的更长后缀。相等后缀必须同秩；不能任意打破平局。棋盘端点也各有两种赋值，边界无比较时仍须计数。所有计数对10^9+7取模。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using State = vector<int>;
using ll = long long;
const int MOD = 1000000007;
map<State, int> transitions(const State &s, int mode) {
    int old = s.size() / 2, len = old + (mode == 0 ? 1 : mode == 2 ? -1 : 0);
    vector<pair<int, int>> tails(len);
    for (int i = 0; i < len; i++) {
        if (mode == 2)
            tails[i] = {s[2 * (i + 1)], s[2 * i + 1]};
        else if (i == 0)
            tails[i] = {s[0], s[1]};
        else if (i == old)
            tails[i] = {s[2 * (old - 1)], s[2 * (old - 1) + 1]};
        else
            tails[i] = {s[2 * i], s[2 * (i - 1) + 1]};
    }
    map<State, int> out;
    for (int mask = 0; mask < (1 << len); mask++) {
        State a(2 * len), values;
        for (int i = 0; i < len; i++) {
            int z = (mask >> i & 1) * 32;
            a[2 * i] = z + tails[i].first;
            a[2 * i + 1] = z + tails[i].second;
        }
        bool ok = true;
        for (int i = 1; i < len; i++)
            if (a[2 * i + 1] > a[2 * (i - 1)]) {
                ok = false;
                break;
            }
        if (!ok)
            continue;
        values = a;
        sort(values.begin(), values.end());
        values.erase(unique(values.begin(), values.end()), values.end());
        for (int &v : a)
            v = lower_bound(values.begin(), values.end(), v) - values.begin();
        out[a]++;
    }
    return out;
}
using Matrix = vector<vector<int>>;
Matrix multiply(const Matrix &a, const Matrix &b) {
    int n = a.size();
    Matrix z(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
            if (a[i][k])
                for (int j = 0; j < n; j++)
                    if (b[k][j])
                        z[i][j] = (z[i][j] + (ll)a[i][k] * b[k][j]) % MOD;
    return z;
}
vector<int> multiply(const vector<int> &v, const Matrix &a) {
    int n = v.size();
    vector<int> z(n);
    for (int i = 0; i < n; i++)
        if (v[i])
            for (int j = 0; j < n; j++)
                z[j] = (z[j] + (ll)v[i] * a[i][j]) % MOD;
    return z;
}
ll power(ll a, int n) {
    ll z = 1;
    for (; n; n /= 2, a = a * a % MOD)
        if (n & 1)
            z = z * a % MOD;
    return z;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    if (n > m)
        swap(n, m);
    if (n == 1) {
        cout << power(2, m) << '\n';
        return 0;
    }
    map<State, int> dp;
    dp[{0, 0}] = 2;
    for (int len = 1; len < n; len++) {
        map<State, int> next;
        for (auto &x : dp)
            for (auto &y : transitions(x.first, 0))
                next[y.first] = (next[y.first] + (ll)x.second * y.second) % MOD;
        dp.swap(next);
    }
    if (m > n) {
        map<State, int> id;
        vector<State> states;
        vector<map<State, int>> trans;
        auto add = [&](const State &s) {
            auto it = id.find(s);
            if (it != id.end())
                return it->second;
            int j = states.size();
            id[s] = j;
            states.push_back(s);
            return j;
        };
        for (auto &x : dp)
            add(x.first);
        for (size_t i = 0; i < states.size(); i++) {
            auto row = transitions(states[i], 1);
            for (auto &x : row)
                add(x.first);
            trans.push_back(move(row));
        }
        int count = states.size();
        Matrix a(count, vector<int>(count));
        vector<int> v(count);
        for (auto &x : dp)
            v[id[x.first]] = x.second;
        for (int i = 0; i < count; i++)
            for (auto &x : trans[i])
                a[i][id[x.first]] = x.second;
        for (int exponent = m - n; exponent; exponent /= 2) {
            if (exponent & 1)
                v = multiply(v, a);
            if (exponent > 1)
                a = multiply(a, a);
        }
        dp.clear();
        for (int i = 0; i < count; i++)
            if (v[i])
                dp[states[i]] = v[i];
    }
    for (int len = n; len > 1; len--) {
        map<State, int> next;
        for (auto &x : dp)
            for (auto &y : transitions(x.first, 2))
                next[y.first] = (next[y.first] + (ll)x.second * y.second) % MOD;
        dp.swap(next);
    }
    int answer = 0;
    for (auto &x : dp)
        answer = (answer + x.second) % MOD;
    cout << answer << '\n';
}