이 문제는 n×m 격자에 0과 1을 채워넣는 방식의 수를 세는 조합 문제입니다. 핵심 조건은 오른쪽 우선 경로의 01 문자열이 아래쪽 우선 경로의 01 문자열보다 사전순으로 작거나 같아야 한다는 것입니다.

작은 케이스 분석과 패턴 발견

먼저 n ≤ 3인 경우를 완전탐색으로 해결할 수 있습니다. DFS를 통해 모든 가능한 배치를 검증하면 다음과 같은 결과를 얻습니다:

2 : 12 36 108 324 972 2916 ...
3 : 112 336 1008 3024 9072 27216 ...

각 항이 이전 항의 3배라는 패턴이 명확히 보입니다. 따라서 n = 2, 3인 경우 각각 12 × 3^(m-2), 112 × 3^(m-3)으로 O(log m)에 계산 가능합니다.

대각선 구조의 핵심 성질

문제의 핵심 관찰은 왼쪽 아래에서 오른쪽 위로 가는 대각선의 구조입니다. 두 경로의 사전순 비교를 분석하면, 각 대각선은 반드시 1이 연속으로 나온 뒤 0이 연속으로 나오는 형태(111...000...)를 가져야 합니다.

더 정확히 말하면, 경로가 교차하지 않는 영역에서는 대각선이 1...0 형태를, 교차하는 영역에서는 모든 대각선이 동일한 값(전부 0 또는 전부 1)을 가져야 합니다.

효율적인 검증과 DP 설계

이 구조적 성질을 이용하면 완전탐색을 최적화할 수 있습니다. 대각선별로 0과 1의 경계 위치만 결정하면 되므로, 상태 공간이 크게 줄어듭니다.

또한 DP를 설계하여 효율적으로 계산할 수 있습니다. dp[i][j][k]를 i번째 대각선까지 고려했고, j개의 1을 배치했으며, 강제로 일치해야 하는 위치의 상태가 k인 경우의 수로 정의하면, O(n³m·2ⁿ) 정도의 복잡도로 충분히 큰 표를 만들 수 있습니다.

점화식 도출

표를 통해 더 깊은 패턴을 발견할 수 있습니다. n ≥ 4일 때:

• f(n, n+1) = 3 × f(n, n) − 3 × 2ⁿ
• f(n+1, n+1) = 2 × (f(n, n) + f(n, n+1)) − 2^(n+2)

그리고 m ≥ n+2인 경우에는 f(n, m) = 3 × f(n, m−1)이 성립합니다.

이 점화식을 행렬 형태로 변환하면 행렬 거듭제곱을 통해 O(log n)에 계산 가능합니다.

분류 논증을 통한 직접 계산

더 우아한 방법은 경우를 나누어 직접 계산하는 것입니다:

케이스 1: 두 번째 대각선의 두 값이 같은 경우
제약을 받는 영역의 구조가 단순화되어, 답은 2^(3n−3) × 3^(m−n)이 됩니다.

케이스 2: 두 번째 대각선의 값이 다르고, 세 번째 대각선이 모두 같은 경우
답은 5 × 2^(3n−9) × 3^(m−n)이 됩니다.

케이스 3: 두 번째 대각선의 값이 다르고, 세 번째 대각선이 (1,1,0) 또는 (1,0,0)인 경우
이 경우는 위쪽 2×m 영역의 제약 상태를 추적하는 DP가 필요합니다:

dp[i][0]: i번째 대각선까지 고려, 위쪽 영역이 제약되지 않은 상태
dp[i][1]: i번째 대각선까지 고려, 위쪽 영역이 제약된 상태

전이 방정식은 i ≤ n, i = n+1, i > n+1에 따라 달라지며, 각각 다른 계수를 갖습니다. 이 DP 역시 행렬 형태로 변환하여 로그 시간에 계산 가능합니다.

최종 구현

모든 경우를 종합하면 다음과 같은 코드로 해결할 수 있습니다:

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

const int MOD = 1e9 + 7;

long long power(long long base, long long exp) {
    long long res = 1;
    while (exp > 0) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

struct Matrix {
    long long a[5][5];
    Matrix() { memset(a, 0, sizeof(a)); }
    Matrix operator*(const Matrix& o) const {
        Matrix res;
        for (int i = 0; i < 4; i++)
            for (int k = 0; k < 4; k++)
                for (int j = 0; j < 4; j++)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * o.a[k][j]) % MOD;
        return res;
    }
};

Matrix mat_pow(Matrix base, long long exp) {
    Matrix res;
    for (int i = 0; i < 4; i++) res.a[i][i] = 1;
    while (exp > 0) {
        if (exp & 1) res = res * base;
        base = base * base;
        exp >>= 1;
    }
    return res;
}

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;
    }
    if (n == 2) {
        cout << 12 * power(3, m - 2) % MOD << "\n";
        return 0;
    }
    if (n == 3) {
        cout << 112 * power(3, m - 3) % MOD << "\n";
        return 0;
    }
    
    // n >= 4: 행렬 거듭제곱으로 기본값 계산
    // f(4,4) = 912, f(4,5) = 2688을 초기값으로 사용
    
    Matrix trans;
    // [f(n,n), f(n,n+1), 2^n] -> [f(n+1,n+1), f(n+1,n+2), 2^(n+1)]
    trans.a[0][0] = 2; trans.a[0][1] = 2; trans.a[0][2] = MOD - 2;
    trans.a[1][0] = 6; trans.a[1][1] = 6; trans.a[1][2] = MOD - 9;
    trans.a[2][0] = 0; trans.a[2][1] = 0; trans.a[2][2] = 2;
    
    Matrix init;
    init.a[0][0] = 912;   // f(4,4)
    init.a[1][0] = 2688;  // f(4,5)
    init.a[2][0] = 16;    // 2^4
    
    Matrix pw = mat_pow(trans, n - 4);
    Matrix cur = pw * init;
    
    long long fnn = (cur.a[0][0] % MOD + MOD) % MOD;
    long long fnnp1 = (cur.a[1][0] % MOD + MOD) % MOD;
    
    if (n == m) {
        cout << fnn << "\n";
    } else {
        long long ans = fnnp1 * power(3, m - n - 1) % MOD;
        cout << ans << "\n";
    }
    
    return 0;
}

이 풀이는 O(log n + log m) 시간에 동작하며, 대각선의 구조적 성질과 행렬 거듭제곱을 효과적으로 활용합니다.