Đố vui

Cho một mảng a gồm n phần tử $a_1, a_2, ..., a_n$. Ta định nghĩa các hàm sau:

• $f(a, x) = |a_1 - x| + |a_2 - x| + ... + |a_n - x|$.
• $g(a, x) = (a_1 - x)^2 + (a_2 - x)^2 + ... + (a_n - x)^2$.

Gọi:

• $p(a)$ là số thực x nhỏ nhất sao cho $f(a, x)$ đạt giá trị nhỏ nhất.
• $q(a)$ là số thực x nhỏ nhất sao cho $g(a, x)$ đạt giá trị nhỏ nhất.

Yêu cầu: Cho hai số nguyên n và m, hãy đếm số lượng mảng a gồm n số nguyên dương thỏa mãn tất cả các điều kiện sau:

• a là mảng không giảm, tức là $a_i \leq a_{i + 1}$ với mọi $i\leq n-1$.
• $1 \leq a_i \leq m$ $(1 \leq i \leq n)$.
• $p(a) = q(a)$.

Đầu vào:

• Gồm hai số nguyên n và m ($1 \leq n \cdot m \leq 5000$).

Đầu ra:

• In ra kết quả của bài toán theo modulo $10^9 + 7$.

Subtask (tham khảo)

• $25\%$ số test có $n \leq 10$ và $m \leq 10$.
• $75\%$ số test thỏa mãn giới hạn gốc của đề bài.

Giải thích: Có 4 mảng a thỏa mãn các điều kiện:

• $\{1, 1, 1, 1\}$
• $\{1, 2, 2, 3\}$
• $\{2, 2, 2, 2\}$
• $\{3, 3, 3, 3\}$

Ví dụ 1:

Đầu vào:

4 3

Đầu ra:

4