[ABC130E] Common Subsequence

给出两个长度分别为N和M的整数序列S和T，它们均由 $1$ 到 $10 ^ 5$（含 $10 ^ 5$ ）之间的整数组成。 求在S子序列和T子序列中，有多少对两个子序列的内容相同。 **子序列的说明:** A的子序列是指通过从A删除零个或多个元素而不改变顺序而获得的序列。 对于S和T而言，如果子序列的内容相同，但是被删除元素的索引集(位置)不同，也当成两个不同的子序列。 ### 输出答案模 $10 ^ 9 + 7$ 的结果

[problemUrl]: https://atcoder.jp/contests/abc130/tasks/abc130_e $ 1 $ 以上 $ 10^5 $ 以下の整数から成る、長さ $ N $ の整数列 $ S $ と 長さ $ M $ の整数列 $ T $ が与えられます。 $ S $ の部分列と $ T $ の部分列の組であって、整数列として等しいような組は何通りあるでしょうか。 ただし、整数列 $ A $ の部分列とは、$ A $ の要素を $ 0 $ 個以上いくつか選んで削除し、残ったものを元の順序を保って並べた整数列を表します。 また、$ S,\ T $ それぞれの部分列は、整数列として等しい場合でも、削除した要素の添字の集合が異なる場合には異なる部分列として区別してください。 答えは非常に大きくなることがあるので、$ 10^9+7 $ で割った余りを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ 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

2 2
1 1
1 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

### 制約 - $ 1\ \leq\ N,\ M\ \leq\ 2\ \times\ 10^3 $ - $ S $ の長さは $ N $ である - $ T $ の長さは $ M $ である - $ 1\ \leq\ S_i,\ T_i\ \leq\ 10^5 $ - 入力は全て整数である ### Sample Explanation 1 $ S $ の部分列としては $ (),\ (1),\ (3),\ (1,\ 3) $ が考えられます。 $ T $ の部分列としては $ (),\ (3),\ (1),\ (3,\ 1) $ が考えられます。 共に部分列が $ () $ である組は $ 1\ \times\ 1 $ 通り、共に部分列が $ (1) $ である組は $ 1\ \times\ 1 $ 通り、共に部分列が $ (3) $ である組は $ 1\ \times\ 1 $ 通り考えられるので、合計 $ 3 $ 通りの組が存在します。 ### Sample Explanation 2 $ S $ の部分列としては $ (),\ (1),\ (1),\ (1,\ 1) $ が考えられます。 $ T $ の部分列としては $ (),\ (1),\ (1),\ (1,\ 1) $ が考えられます。 共に部分列が $ () $ である組は $ 1\ \times\ 1 $ 通り、共に部分列が $ (1) $ である組は $ 2\ \times\ 2 $ 通り、共に部分列が $ (1,\ 1) $ である組は $ 1\ \times\ 1 $ 通り考えられるので、合計 $ 6 $ 通りの組が存在します。 部分列において削除する要素の添字の集合が異なるものを区別することに注意してください。 ### Sample Explanation 5 個数を $ 10^9+7 $ で割った余りを出力することに注意してください。