Spoiler Alert

Hint 1

• Khi chọn số \(-1\) tại các vị trí (i, j) bất kì không nằm trên cột cuối và hàng cuối, ta chỉ có 1 cách để chọn hàng cuối và cột cuối

Hint 2

• Có \(2 ^ {n - 1}\) cách chọn dãy {0, 1} độ dài n mà số số 1 được chọn là số lẻ <=> tổng lẻ

Hint 3

• Có \(2 ^ {n - 1}\) cách chọn dãy {-1, 1} độ dài n mà số số -1 được chọn là số lẻ <=> tích âm

Hint 4 (cuom1999)

• Công thức: (2 ^ {(n - 1) * (m - 1)}

Nếu không kể hàng cuối và cột cuối, chúng ta còn lại bảng con \((m−1) * (n−1)\).

Có \(2 ^ {(m−1) * (n−1)}\) cách điền số cho bảng con này, do mỗi ô có 2 cách điền.

Đồng thời với mỗi cách điền trên, chúng ta có đúng 1 cách điền số cho hàng cuối và cột cuối

Hint 5

• Dùng chia để trị để tính \(x ^ n\) \(\%\) \(m\) trong \(O(log_2 n)\)

Công thức: \(x ^ n\) \(\%\) \(m = (a ^ k * a ^ k * b)\) \(\%\) \(m\)

Với a = (x % m)

Với k = ⌊n / 2⌋

Với b = a (khi n lẻ)

Với b = 1 (khi n chẵn)

Reference AC code | O(1) time | O(1) auxiliary space | Divide and Conquer, Math

int mulMOD(int a, int b, int m = 1e9 + 7) { return (1LL * a * b) % MOD; }
int powMOD(int x, ll n, int m = 1e9 + 7)
{
    int res = 1;
    for (x %= m; n > 0; x = mulMOD(x, x, m), n >>= 1)
        if (n & 1) res = mulMOD(res, x, m);

    return res;
}

int main()
{
    int n = readInt();
    int m = readInt();
    cout << powMOD(2, 1LL * (n - 1) * (m - 1));
    return 0;
}