Nguồn: (Dựa trên bài Genetic trên http://cope-edu.com/).
Rating 1600.

**Đề Bài**:
Thầy 5Trứng vì muốn các bạn trong lớp đoàn kết với nhau hơn nên thầy đã tổ chức một trò chơi như sau:

Thầy cho mỗi bạn trong lớp $n$ số nguyên dương phân biệt từ $1$ đến $n$, sau đó thầy yêu cầu mỗi bạn xếp $n$ số đó theo một hàng ngang và theo một thứ tự bất kì. Từ cách xếp của 1 bạn thầy sẽ biết được rằng bạn đó có hợp với hai bạn khác không ?

Cụ thể hai bạn được coi là hợp với một bạn thứ ba khác nếu với mọi cặp số $(x, y)$ trong cách xếp của cả hai bạn đó mà số $x$ đứng bên trái số $y$ thì trong cách xếp của bạn thứ ba số $x$ cũng phải đứng bên trái số $y$.

Cubill có hai đứa bạn thân là ChongChong và Ugnmad, hai đứa bạn của Cubill rất nhanh đã xếp xong. Còn Cubill vì để tránh mất lòng hai đứa bạn nên cậu cố gắng xếp sao cho cách xếp của cậu hợp với cả hai đứa bạn. Với bộ óc thiên tài Cubill biết được rằng chắc chắn không chỉ có một cách xếp mà sẽ có rất nhiều cách.

Nhưng nhiều là bao nhiêu thì cậu lại không biết vì thế Cubill rất mong bạn sẽ tính hộ cậu ấy xem có bao nhiêu cách xếp mà hợp với cả hai đứa bạn thân của mình?
**Input**:
* Dòng đầu chứa một số nguyên dương $n$ ($1\le n \le 20$).
* Dòng thứ hai chứa $n$ số nguyên dương $a_1$,$a_2$,$a_3$,...,$a_n$ thể hiện cách xếp của ChongChong.
* Dòng thứ ba chứa $n$ số nguyên dương $b_1$,$b_2$,$b_3$,...,$b_n$ thể hiện cách xếp của Ugnmad.

**Output**:
* Một số nguyên duy nhất là số cách Cubill có thể xếp.

**Scoring:**

| Subtask | Điểm | Giới Hạn |
| -------- | -------- | -------- |
| 1 | 50 | $n \le 9$ |
| 2 | 50 | Không có ràng buộc gì thêm |

**Lời Giải:**
Subtask 1:
Ta sinh mọi cách xếp của Cubill ra rồi thử với từng hoán vị.
Đpt ($n!*n^2$).
Subtask 2:
Để tiện cho lời giải ta sẽ đánh số cho n số mà thầy cho từ 0 đến n-1
Gọi dp[mask] là số cách xếp thỏa mãn khi chỉ xét những $a_i$ mà bit thứ i của mask là 1.

Ta sẽ chuẩn bị trước một mảng c[i][j] là số i có đứng trước số j trong cả 2 cách xếp của 2 bạn không?

Để chuyển trạng thái ta sẽ thử bật 1 bit x bất kì mà chưa được bật và thử cho số đó xuống cuối dãy cũ nếu không tồn tại c[x][i] = 1 (i là các bit 1 của mask cũ) nếu thỏa mãn ta sẽ có công thức là dp[mask | (1<<x)]+=dp[mask].