After participating in the Joint Provincial Selection, you have become a bitset master. Therefore, you decide to use a bitset to solve the following problem.
Given two integer sequences $a_1, a_2, \cdots, a_n$ and $b_1, b_2, \cdots, b_m$ (where $m$ is very small). Two integer sequences $(x_1, x_2, \cdots, x_p)$ and $(y_1, y_2, \cdots, y_q)$ are "tie-tie" (equivalent) if and only if:
- $p = q$
- $x_i = x_j \Longleftrightarrow y_i = y_j$ for every $1 \leq i, j \leq p$.
Output the number of subsequences of $a_1, a_2, \cdots, a_n$ that are "tie-tie" with $b_1, b_2, \cdots, b_m$.
Input
The first line contains two integers $n$ and $m$ ($1 \leq n \leq 3000$, $1 \leq m \leq \min(5, n)$).
The next line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \leq a_i \leq n$).
The next line contains $m$ integers $b_1, b_2, \cdots, b_m$ ($1 \leq b_i \leq m$).
Output
Output a single integer representing the answer.
Examples
Input 1
6 4 1 1 4 5 1 4 1 3 2 1
Output 1
3
Subtasks
Subtask 1 (1 point)
$m \leq 3$
Subtask 2 (1 point)
$m \leq 4$
Subtask 3 (5 points)
No additional constraints.