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 ~10^9 + 7~.

Input

• 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 ">>".

Output

• 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~.

Sample Input

[CASE]
<<
1
2 
3
>>
<<
1 
3
2
>>

[END]

Sample Output

12

Note

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).