trang chủ / đề bài / icpc19_reg_a

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 R·C ô vuông đơn vị, gồm R hàng và C 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 3 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ị, 4 cạnh của nó được tô bằng đúng 2 màu, và mỗi màu tô đúng 2 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ó R hàng và C 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 T, số bộ dữ liệu (1≤T≤5).

T dòng tiếp theo, mỗi dòng chứa đúng hai số nguyên R và C (1≤R≤14, 1≤C≤2000).

Dữ liệu ra

In ra đúng T dòng, mỗi dòng chứa một số nguyên là số bức tranh đẹp khác nhau, theo modulo 109+7.

Ràng buộc

  • 1≤T≤5
  • 1≤R≤14, 1≤C≤2000

Ví dụ

Input Output Giải thích
3
1 1
1 2
2 1
18
108
108
Với một ô: chọn 2 trong 3 màu (3 cách) và chọn 2 trong 4 cạnh tô màu thứ nhất (6 cách), tổng 18.
3
2 2
1 3
3 1
1296
648
648
Ví dụ bổ sung (không có trong đề gốc).

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0