Giải bài trực tuyến

Đề bài

Có N quân bài hai mặt, mỗi mặt có một số khác nhau. Mặt trước của các quân bài chứa N số phân biệt từ 1 đến N. Mặt sau của các quân bài cũng vậy.

Ta có thể bày N quân bài lên mặt bàn theo thứ tự bất kỳ và với mỗi quân bài có thể lật mặt trước hay mặt sau tùy ý. Đếm số cách bày bài khác nhau, biết rằng hai cách bày bài là khác nhau nếu có ít nhất một vị trí với hai lá bài tương ứng mang số khác nhau. Trả về phần dư của kết quả cho 1,000,000,007.

Dữ liệu

• Mỗi test bắt đầu bằng thẻ "[CASE]", các test cách nhau bởi một dòng trắng. Thẻ "[END]" báo hiệu kết thúc file input.
• Tiếp theo là dòng "<<".
• Các dòng tiếp theo cho biết các số ở mặt trước của quân bài.
• Kết thúc bằng dòng ">>'.
• Tiếp theo là dòng "<<".
• Các dòng tiếp theo cho biết các số ở mặt sau của quân bài.
• Kết thúc bằng dòng ">>'.

Kết quả

• Với mỗi test in ra kết quả tìm được.

Giới hạn

• Số quân bài N nằm trong phạm vi từ 1 đến 50.

Ví dụ

Dữ liệu
[CASE]
<<
1
2 
3
>>
<<
1 
3
2
>>

[END]
Kết quả
12

Giải thích

Có 12 khả năng: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1), (1,3,3), (3,1,3), (3,3,1), (1,2,2), (2,1,2), (2,2,1).