Xây nhà

View as PDF

Submit solution

Points: 0.82 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
IOICAMP4
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cùng với phần thưởng là tấm ảnh kèm chữ kí tặng của hoa hậu Việt Nam 2006 -- Mai Phương Thúy, BB còn được nhận được một khoản tiền. BB quyết định sẽ dùng khoản tiền này để xây ngôi nhà mơ ước của mình. Hiện nay, BB đã có một mảnh đất được chia thành ~M \times N~ ô. BB muốn xây ngôi nhà của mình trên mảnh đất này. BB muốn rằng ngôi nhà của mình phải là ngôi nhà thật đặc biệt. Nó sẽ phải đáp ứng đủ các yêu cầu:

  • Là tập hợp của một số ô liên thông. Hai ô được coi là kề nhau nếu chúng có chung cạnh.
  • Có ít nhất hai trục đối xứng: một trục ngang, một trục dọc (cả hai trục đều phải song song với cạnh của khu đất). BB vốn tin vào thuyết phong thủy mà.

BB lại là người cẩn thận, nên cậu muốn rằng ngôi nhà của mình sẽ có ít nhất một điểm có thể đặt camera để quan sát toàn bộ ngôi nhà. Một điểm ~A~ được coi là có thể quan sát được điểm ~B~ nếu đoạn thẳng ~AB~ nằm hoàn toàn bên trong ngôi nhà hoặc có điểm chung với tường ngôi nhà, nhưng không được đi ra bên ngoài ngôi nhà.

Với mảnh đất của mình, bạn hãy giúp BB tính xem có bao nhiêu cách để xây được ngôi nhà mơ ước.

Input

Dòng thứ nhất ghi hai số nguyên dương ~M, N~.

Output

Gồm một số duy nhất là phần dư của phép chia số cách xây dựng ngôi nhà cho 12051987.

Sample Input

2 2

Sample Output

9

Note

image


Comments

Please read the guidelines before commenting.


There are no comments at the moment.