Bedao OI Contest 6 - Flagger

View as PDF
Submit solution
Points: 0.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: flagger.inp
Output: flagger.out
Author:
bedao
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một bảng ~n~ hàng, ~m~ cột. Các cột được đánh số từ trên xuống dưới, các hàng được đánh số từ trái sang phải, giao giữa hàng ~i~ và cột ~j~ là ô ~(i, j)~. Một số ô có thể được cắm cờ, mỗi ô chỉ chứa tối đa một cờ, mỗi cờ có thể quay được theo 4 hướng tuân theo quy tắc sau:

  • Nếu hai ô ~(i_1, j)~ và ~(i_2, j)~ (~1 \leq i_1 < i_2 \leq n; 1 \leq j \leq m~) hoặc hai ô ~(i, j_1)~ và ~(i, j_2)~ (~1\leq i \leq n; 1 \leq j_1 < j_2 \leq m~) đều đã được cắm cờ thì hướng của chúng phải hướng vào nhau.

  • Nếu ô ~(i, j)~ có cờ và không tồn tại một ô nào khác cùng hàng hoặc cùng cột có cờ thì cờ tại đó có thể cắm theo bất kỳ hướng nào.

Nhiệm vụ của bạn là đếm xem có bao nhiêu cách đặt cờ sao cho ít nhất một cờ được đặt trong bảng. Biết rằng hai cách cắm được gọi là khác nhau khi trạng thái cắm cờ là khác nhau (tồn tại ô mà cách cắm này có cờ mà cách cắm kia không có hoặc là vị trí cắm cờ tại một ô giữa hai cách cắm khác hướng nhau). Lưu ý là số lượng cờ được cắm là không giới hạn, miễn là tuân theo quy định cắm.

Input

Dữ liệu vào từ file văn bản flagger.inp:

Gồm một dòng duy nhất chứa hai số nguyên dương ~n~ và ~m~ (~1\leq n, m \leq 5000~).

Output

In ra file văn bản flagger.out một số nguyên dương là số cách cắm cờ khác nhau, lấy phần dư khi chia cho ~10^9 + 7~.

Scoring

Subtask Điểm Giới hạn
1 ~25\%~ ~n, m \leq 10~
2 ~25\%~ ~n, m \leq 500~
3 ~50\%~ Không có giới hạn gì thêm.

Sample Input 1

1 4

Sample Output 1

22

Sample Input 2

2 2

Sample Output 2

52

Notes

Ở ví dụ ~1~, ta có ~4 \times 4=16~ cách đặt 1 cờ và có ~C_4^2= 6~ cách đặt ~2~ cờ. Đáp án sẽ là ~16+6=22~.

Ở ví dụ ~2~, ta có ~4 \times 4=16~ cách đặt 1 cờ, ~4 \times 1= 4~ cách đặt ~2~ cờ cùng cột hoặc hàng và ~2 * 4^2= 32~ cách đặt ~2~ cờ khác hàng hoặc cột. Đáp án sẽ là ~16 + 4 + 32=52~.

Comments

Please read the guidelines before commenting.