시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB544100.000%

문제

It’s just a problem to waste your time.

You are given two sequences a1, a2, . . . , an and b1, b2, . . . , bm.

Two sequences (x1, x2, . . . , xp) and (y1, y2, . . . , yq) match iff p = q and xi = xj ⇔ yi = yj for every possible pair 1 ≤ i, j ≤ p.

Output the number of subsequences of a1, a2, . . . , an that match b1, b2, . . . , bm.

입력

The first line contains two integers n, m (1 ≤ n ≤ 3000, 1 ≤ m ≤ min(5, n)).

The second line contains n integers a1, a2, . . . , an (1 ≤ ai ≤ n).

The third line contains m integers b1, b2, . . . , bm (1 ≤ bi ≤ m).

출력

Output one integer: the answer.

예제 입력 1

10 5
1 5 5 4 1 4 3 3 4 2
3 4 3 2 1

예제 출력 1

20

예제 입력 2

4 2
2 2 2 2
2 2

예제 출력 2

6