AT_abc130_e [ABC130E] Common Subsequence

[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 $ で割った余りを出力せよ。

### 制約 - $ 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 $ で割った余りを出力することに注意してください。