Hang động

Điểm: 8,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho lưới $n \times m$ gồm các ô đen hoặc trắng (các hàng đánh số $1 . . n$ từ trên xuống, các cột đánh số $1 . . m$ từ trái sang phải). Lưới được gọi là một "hang động" nếu thỏa mãn đồng thời hai điều kiện sau:

Tồn tại một đoạn hàng $[l, r]$ ( $1 \leq l \leq r \leq n$ ) sao cho mỗi hàng trong $l, l + 1, \dots, r$ có đúng hai ô đen, còn tất cả các hàng khác toàn ô trắng.
Tồn tại một hàng t (l≤t≤r) sao cho:
- Với mọi $l \leq i \leq j \leq t$ : khoảng cột nằm giữa hai ô đen của hàng $i$ (bao gồm cả hai ô đen) là tập con của khoảng cột tương ứng của hàng $j$ .
- Với mọi $t \leq i \leq j \leq r$ : khoảng cột giữa hai ô đen của hàng $j$ (bao gồm cả hai ô đen) là tập con của khoảng cột tương ứng của hàng $i$ .

Nói cách khác, các khoảng cột giữa hai ô đen phình to dần từ hàng $l$ xuống hàng $t$ , rồi thu nhỏ dần từ hàng $t$ xuống hàng $r$ .

Đếm số cách tô hang động trên lưới $n \times m$ . Hai cách tô được coi là khác nhau nếu có ít nhất một ô có màu khác nhau giữa chúng. In ra kết quả lấy theo modulo $10^{9} + 7$ .

Dữ liệu vào

Một dòng chứa hai số nguyên $n$ và $m$ .

Dữ liệu ra

Một dòng duy nhất: số cách tô hang động lấy theo modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq n, m \leq 2000$ .

Ví dụ

Input	Output	Giải thích
3 5	451	Lưới $3 \times 5$ có 451 cách tô hang động hợp lệ.
1 1	0	Mỗi hàng của hang động cần đúng 2 ô đen nhưng lưới chỉ có 1 cột.
4 4	485	Lưới $4 \times 4$ có 485 cách.

Bình luận

Không có bình luận tại thời điểm này.