Triominos

View as PDF
Submit solution
Points: 1.90 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Kì thi HSG Duyên hải và đồng bằng Bắc Bộ
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Triomino là hình gồm ba ô vuông có cạnh chung. Cá ~2~ dạng cơ bản:

image

Nếu tính cả hướng thì có ~6~ dạng:

image

Với ~n~, ~m~ bất kì mà ~n \times m~ chia hết cho ~3~ thì có thể lát lướit ~n \times m~ bằng triomino. Nếu chúng ta phân biệt triomino có thể thu được bởi cách quay hoặc lấy đối xứng từ các triomono khác thì tổng cộng có ~41~ cách lát lướt kích thước ~2 \times 9~.

Input

Hai số nguyên ~m~ và ~n~. Trong đó ~1 \leq m~, ~n \leq 40~, ~min(m~, ~n)~ ~\leq 9~

Output

Số cách lát. Nếu kết quả quá to, lấy theo modulo ~(10^{9} + 7)~

Sample Input 1

2 9

Sample Output 1

41

Sample Input 2

1 3

Sample Output 2

1

Note

Đề bài gốc

Comments

Please read the guidelines before commenting.


  • 9
    marvinthang  commented on Aug. 26, 2022, 5:11 a.m.

    sao bài này trên đề có mod mà test lại ko mod ạ :>

    (em để mod thì bị wa còn bỏ mod thì ac)