Evil Subsequence

Time limit3sMemory limit512 MB

Summary

Count the subsequences of a whose equal-and-different pattern matches b exactly, so positions i and j hold equal values in the subsequence precisely when b_i equals b_j.

Level: Medium6 of 10
Topics: Dynamic programming, Hash map
Solved: No attempts yet

Problem

It's just a problem to waste your time.

You are given two sequences $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_m$ .

Two sequences $(x_1, x_2, \ldots, x_p)$ and $(y_1, y_2, \ldots, y_q)$ match if and only if $p = q$ and, for every pair $1 \le i, j \le p$ , $x_i = x_j$ exactly when $y_i = y_j$ .

Output the number of subsequences of $a_1, a_2, \ldots, a_n$ that match $b_1, b_2, \ldots, b_m$ .

Input

The first line contains two integers $n$ and $m$ ( $1 \le n \le 3000$ , $1 \le m \le \min(5, n)$ ).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le n$ ).

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ( $1 \le b_i \le m$ ).

Output

Output one integer: the answer.

Examples2

Example 1
Input
```
10 5
1 5 5 4 1 4 3 3 4 2
3 4 3 2 1
```
Expected output
```
20
```
Example 2
Input
```
4 2
2 2 2 2
2 2
```
Expected output
```
6
```