配点 : $500$ 点

問題文

$1$ 以上 $10^5$ 以下の整数から成る、長さ $N$ の整数列 $S$ と 長さ $M$ の整数列 $T$ が与えられます。

$S$ の部分列と $T$ の部分列の組であって、整数列として等しいような組は何通りあるでしょうか。

ただし、整数列 $A$ の部分列とは、$A$ の要素を $0$ 個以上いくつか選んで削除し、残ったものを元の順序を保って並べた整数列を表します。

また、$S, T$ それぞれの部分列は、整数列として等しい場合でも、削除した要素の添字の集合が異なる場合には異なる部分列として区別してください。

答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを出力してください。

制約

• $1 \leq N, M \leq 2 \times 10^3$
• $S$ の長さは $N$ である
• $T$ の長さは $M$ である
• $1 \leq S_i, T_i \leq 10^5$
• 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$S_1$ $S_2$ $...$ $S_{N-1}$ $S_{N}$

$T_1$ $T_2$ $...$ $T_{M-1}$ $T_{M}$

出力

整数列として等しいような、$S, T$ の部分列の組の個数を $10^9+7$ で割った余りを出力せよ。

2 2
1 3
3 1

3

$S$ の部分列としては $(), (1), (3), (1, 3)$ が考えられます。

$T$ の部分列としては $(), (3), (1), (3, 1)$ が考えられます。

共に部分列が $()$ である組は $1 \times 1$ 通り、共に部分列が $(1)$ である組は $1 \times 1$ 通り、共に部分列が $(3)$ である組は $1 \times 1$ 通り考えられるので、合計 $3$ 通りの組が存在します。

2 2
1 1
1 1

6

$S$ の部分列としては $(), (1), (1), (1, 1)$ が考えられます。

$T$ の部分列としては $(), (1), (1), (1, 1)$ が考えられます。

共に部分列が $()$ である組は $1 \times 1$ 通り、共に部分列が $(1)$ である組は $2 \times 2$ 通り、共に部分列が $(1, 1)$ である組は $1 \times 1$ 通り考えられるので、合計 $6$ 通りの組が存在します。 部分列において削除する要素の添字の集合が異なるものを区別することに注意してください。

4 4
3 4 5 6
3 4 5 6

16

10 9
9 6 5 7 5 9 8 5 6 7
8 6 8 5 5 7 9 9 7

191

20 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

846527861

個数を $10^9+7$ で割った余りを出力することに注意してください。