놀이공원

시간 제한1초메모리 제한128 MB

요약

최대 10000개 정수로 이루어진 두 목록이 공유하는 서로 다른 최장 공통 부분 수열의 개수를 1000000007로 나눈 나머지를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

바이타자르(Bajtazar)와 바이토니(Bajtoni)가 놀이공원에 놀러 갔습니다. 두 사람은 이곳을 여러 번 방문해서 모든 놀이기구를 잘 알고 있고, 그래서 각자 순서대로 타고 싶은 좋아하는 놀이기구 목록을 미리 만들어 두었습니다. 두 목록은 서로 달랐기 때문에, 친구들은 목록에서 일부 항목을 지워 두 목록을 완전히 똑같게 만들기로 했습니다. 이때 각 목록의 원래 순서는 바꾸지 않습니다. 또한 합의된 계획이 가능한 한 길기를 바랍니다. 이렇게 해서 만들 수 있는 서로 다른 계획은 몇 가지일까요?

입력

첫 번째 줄에는 두 정수 $n_1$ 과 $n_2$ ( $1 \le n_1, n_2 \le 10000$ )가 주어지며, 각각 바이타자르와 바이토니의 목록 길이를 나타냅니다. 이어지는 두 줄에는 각 사람이 제시한 놀이기구 목록이 주어집니다. 각 줄은 $[1, 10000]$ 범위의 정수를 공백 하나로 구분해 나열한 것이며, 길이는 각각 $n_1$ 과 $n_2$ 입니다. 각 정수는 놀이공원의 놀이기구 하나를 나타냅니다.

출력

표준 출력의 첫 번째이자 유일한 줄에 정수 하나를 출력하세요. 이는 두 친구가 각자의 목록에서 항목을 지워 만들 수 있는, 서로 다른 가장 긴 놀이공원 관람 계획의 개수를 $1000000007$ 로 나눈 나머지입니다.

예제3

예제 1
입력
```
4 5
1 2 3 1
1 1 3 2 1
```
예상 출력
```
2
```
예제 2
입력
```
3 3
1 2 3
1 2 3
```
예상 출력
```
1
```
예제 3
입력
```
2 2
1 2
2 1
```
예상 출력
```
2
```