在参加了联合省选后，你成为了 bitset 大师。因此，你决定使用 bitset 解决这样的一道题。

给定两个整数序列 $a_1, a_2, \cdots, a_n$ 与 $b_1, b_2, \cdots, b_m$（$m$ 的值很小）。两个整数序列 $(x_1, x_2, \cdots, x_p)$ 与 $(y_1, y_2, \cdots, y_q)$ 是 贴贴 的，当且仅当：

• $p = q$
• $x_i = x_j \Longleftrightarrow y_i = y_j$，对每个 $1 \leq i,j \leq p$。

输出 $a_1, a_2, \cdots, a_n$ 有多少子序列与 $b_1, b_2, \cdots, b_m$ 贴贴。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 3000$，$1 \leq m \leq \min(5, n)$）。

接下来一行，包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \leq a_i \leq n$）。

接下来一行，包含 $m$ 个整数 $b_1, b_2, \cdots, b_m$（$1 \leq a_i \leq m$）。

输出格式

输出一行一个整数，表示答案。

样例数据

input

6 4
1 1 4 5 1 4
1 3 2 1

output

3

子任务

子任务一（1 分）

$m \leq 3$

子任务二（1 分）

$m \leq 4$

子任务三（5 分）

没有额外的限制。