Amusement Park

Time limit1sMemory limit128 MB

Summary

Count how many distinct longest common subsequences two lists of up to 10000 numbers share, modulo 1000000007.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

Bajtazar and Bajtoni went to an amusement park. They have visited it many times and know all the attractions well, so each of them prepared in advance a list of favorite attractions they would like to ride in order. The two lists were different, so the friends decided to cross out some entries so that the lists become identical. While doing so, they do not want to change the original order within either list. In addition, they want the agreed plan to be as long as possible. How many different plans can they obtain this way?

Input

The first line contains two integers $n_1$ and $n_2$ ( $1 \le n_1, n_2 \le 10000$ ), the lengths of Bajtazar's and Bajtoni's lists. The next two lines contain the lists of attractions proposed by each of them. Each is a list of integers in the range $[1, 10000]$ separated by single spaces, of length $n_1$ and $n_2$ respectively. Each number identifies one attraction in the amusement park.

Output

On the first and only line of standard output, print a single integer. It should be the number of different longest amusement-park sightseeing plans the friends can create by crossing entries out of their proposed lists, taken modulo $1000000007$ .

Examples3

Example 1
Input
```
4 5
1 2 3 1
1 1 3 2 1
```
Expected output
```
2
```
Example 2
Input
```
3 3
1 2 3
1 2 3
```
Expected output
```
1
```
Example 3
Input
```
2 2
1 2
2 1
```
Expected output
```
2
```