# Bảng đẹp

Nguồn: tham khảo bài ôn tập thi HSG của thầy Đặng Trung Kiên.

Rating: 1800.

## Đề bài

Cho một bảng gồm $N$ hàng và $M$ cột, bao gồm các ô vuông có kích thước $1 \times 1$. Hãy cắt một số ô ra khỏi bảng sao cho bảng kết quả là ***đẹp***.

Một bảng được gọi là ***đẹp*** nếu thỏa mãn ba điều kiện sau:
- Ô phía trên bên trái và ô phía dưới bên phải của bảng không bị cắt đi.
- Bảng kết quả là một vùng liên thông các ô, nghĩa là từ một ô có thể đến bất kỳ ô nào khác trong bảng bằng cách di chuyển đến ô liền kề trái, phải, trên hoặc dưới.
- Tất cả các ô trong cùng hàng hay cùng cột tạo thành một đoạn ô liên tục.

Bảng không đáp ứng những điều kiện này gọi là xấu.

#### Yêu cầu:

Cần đếm xem có bao nhiêu bảng ***đẹp*** khác nhau được lấy từ bảng ban đầu bằng cách cắt bỏ một số ô, hoặc không cắt. Hai bảng được coi là khác nhau nếu tập hợp các ô bị cắt khác nhau.

#### Ví dụ:
<!--imagine-->
Hình minh họa: các ô phía bên trái trên cùng và bên phải dưới cùng được tô màu xám:

*Bảng tốt*

*Bảng xấu*

## Input:

- Gồm một dòng duy nhất chứa hai số nguyên $N$ và $M$ ($1 \le N, M \le 10^5$).

## Output

- In ra số cách cắt bảng thỏa mãn. Vì kết quả bài toán có thể rất lớn, hãy đưa ra kết quả chia lấy dư cho $998244353$.

## Sample

| Input | Output | |
| -------- | -------- | -------- |
| 2 2 | 3 ||
| 2 4 | 10 ||

## Giới hạn

- Subtask 1:($30\%$) $1 \le N, M \le 50$.
- Subtask 2:($30\%$) $1 \le N, M \le 200$.
- Subtask 3:($40\%$) Không giới hạn gì thêm.

## Lời giải:

<details>
<summary>Lời giải</summary>

Để đáp ứng điều kiện của một bảng đẹp thì trong mỗi hàng, một số ô ở bên trái hoặc một số ô ở bên phải có thể bị cắt bỏ hoặc không cắt bỏ ô nào. Số ô bị cắt cắt bên trái trong hàng $i$ sẽ không nhỏ hơn số ô bị cắt bên trái trong hàng $i-1$. Tương tự số ô bị cắt bỏ ở bên phải của hàng $i$ không lớn hơn số ô bị cắt bỏ trong hàng $i-1$.

Điều này dẫn tới bất kỳ cách cắt nào sẽ quy về hai đường đi bao quanh bảng có hình dạng sau:

Để thỏa mãn điều kiện của một bảng đẹp, các đường đi không được cắt nhau. Vì vậy, vấn đề bây giờ là tính toán số cặp đường đi không giao nhau mà bắt đầu và kết thúc ở các điểm trong hình.

***Tính số cặp đường đi thỏa mãn:***

Gọi $S$ là tập các cặp đường đi xanh, đỏ sao cho: đường màu đỏ bắt đầu tại đỉnh $(0,1)$ và kết thúc tại $(N-1,M)$, đường màu xanh bắt đầu tại đỉnh $(1,0)$ và kết thúc tại $(N,M-1)$.

Mỗi đường đi bao gồm $N+M-2$ đoạn có chiều dài $1$. Mỗi trong số chúng đi xuống hoặc sang phải nên số lượng các đường đi là: $C^{M-1}_{N+M-2}$. Vì thế số cặp đường đi là $|S| = (C^{M-1}_{N+M-2})^2$.

Gọi $T$ là tập các cặp đường đi xanh, đỏ sao cho: đường màu đỏ bắt đầu tại đỉnh $(0,1)$ và kết thúc tại $(N,M-1)$, đường màu xanh bắt đầu tại đỉnh $(1,0)$ và kết thúc tại $(N-1,M)$. Tưởng tự trên ta có: $|T| = (C^{M-2}_{N+M-2})^2$

Bây giờ ta cần trừ số cặp đường đi giao nhau trong câu trả lời.

Với hình trên, ta có nhận xét là:
- Với mỗi cặp đường thẳng giao nhau trong $S$, khi ta đổi hướng đi của $2$ đường từ điểm giao nhau nhau cuối cùng, ta sẽ đươc tương ứng duy nhất $1$ cặp đường thẳng mới thuộc $T$.
- Và ngược lại, với mỗi cặp đường thẳng thuộc $T$, cũng ứng với duy nhất $1$ cặp đường thẳng có giao nhau trong $S$.

Vậy nên, số cặp đường thẳng có giao nhau trong $S$ bằng số cặp đường thẳng trong $T$.

=> Đáp số bài toán: $|S| - |T| = (C^{M-1}_{N+M-2})^2 - (C^{M-2}_{N+M-2})^2$.

</details>

<details>
<summary>Code </summary>

#include <bits/stdc++.h>

using namespace std;
#define ll long long

const ll N = 1e5 + 5;
ll n, m, i, mod = 1e9 + 7;
ll gt[N + 1], igt[N + 1];

ll pow(ll a, ll b) {
    if (b == 1) return a % mod;
    ll k = pow(a, b / 2);
    if(b & 1) return k * k % mod * a % mod; 
    return k * k % mod;
}

ll C(ll k, ll n) {
    return gt[n] * igt[k] % mod * igt[n - k] % mod;
}

int main() {
    cin >> n >> m;
    
    gt[0] = 1;
    for(i = 1; i <= N; i++) 
        gt[i] = gt[i - 1] * i % mod;
    
    igt[N] = pow(gt[N], mod - 2);
    for(i = N - 1; i >= 0; i--) 
        igt[i] = igt[i + 1] * (i + 1) % mod;
    
    cout << (C(n - 1, n + m - 2) * C(m - 1, n + m - 2) % mod - C(n - 2, n + m - 2) * C(m - 2, n + m - 2) % mod + mod) % mod;
    
    return 0;
}
    

</details>