Tranh trừu tượng
Đề bài
Mô tả
Gon đang luyện tập để trở thành một họa sĩ hiện đại.
Mỗi ngày, Gon luyện vẽ trên một tấm vải hình chữ nhật được chia thành ô vuông đơn vị, gồm hàng và cột. Gon muốn tô màu tất cả các cạnh của tất cả các ô vuông đơn vị.
Trái với suy nghĩ của nhiều người, tạo ra một bức tranh hiện đại đẹp không hề dễ. Một bức tranh hiện đại đẹp chỉ nên dùng ít màu, đơn giản nhưng thanh lịch. Vì vậy, khi vẽ, Gon tuân thủ nghiêm ngặt các quy tắc sau:
- Chỉ dùng màu: Đỏ, Xanh lục và Xanh lam.
- Mọi cạnh của mọi ô vuông đơn vị đều phải được tô. Mỗi cạnh được tô đúng một màu.
- Với mỗi ô vuông đơn vị, cạnh của nó được tô bằng đúng màu, và mỗi màu tô đúng cạnh.
Ví dụ, một ô có hai cạnh đỏ và hai cạnh xanh lam là hợp lệ; một ô có ba cạnh xanh lam thì không hợp lệ, và bức tranh chứa ô đó không phải là một bức tranh đẹp. Lưu ý mỗi cạnh nằm giữa hai ô kề nhau thuộc về cả hai ô.
Gon tự hỏi có bao nhiêu bức tranh đẹp khác nhau? Hai bức tranh cùng có hàng và cột được coi là khác nhau nếu có một cạnh được tô màu khác nhau ở hai bức tranh. Hãy giúp Gon!
Dữ liệu vào
Dòng đầu tiên chứa đúng một số nguyên , số bộ dữ liệu ().
dòng tiếp theo, mỗi dòng chứa đúng hai số nguyên và (, ).
Dữ liệu ra
In ra đúng dòng, mỗi dòng chứa một số nguyên là số bức tranh đẹp khác nhau, theo modulo .
Ràng buộc
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 1 1 2 2 1 |
18 108 108 |
Với một ô: chọn trong màu ( cách) và chọn trong cạnh tô màu thứ nhất ( cách), tổng . |
| 3 2 2 1 3 3 1 |
1296 648 648 |
Ví dụ bổ sung (không có trong đề gốc). |
Bình luận