Bạn được cho hai mảng số nguyên ~A, B~ với độ dài tương ứng ~N, M~. Mỗi mảng chỉ chứa các số nguyên dương từ 1 đến ~10^5~.

Bạn hãy đếm xem có bao nhiêu cặp dãy con không liên tiếp của ~A~ và dãy con không liên tiếp của ~B~, sao cho giá trị từng phần tử xét từ đầu đến cuối của hai dãy con này y hệt nhau (kể cả hai dãy con rỗng).

Ở đây, một dãy con không liên tiếp của mảng là một dãy con được tạo thành từ việc xóa một số phần tử trong mảng mà không thay đổi thứ tự của những phần tử còn lại.

Hai cặp dãy con không liên tiếp được xem là phân biệt nếu tập chỉ số các phần tử bị xóa ở mảng ~A~ hoặc ở mảng ~B~ của cặp này khác với cặp kia.

Do kết quả có thể khá lớn, in ra số cặp tính được modulo ~10^9 + 7~

Dữ liệu

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~M~ ~(1 \le N, M \le 2 \times 10^3)~ — độ dài mảng ~A~ và ~B~.

• Dòng tiếp theo gồm ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ ~(1 \le A_i \le 10^5)~.

• Dòng tiếp theo gồm ~M~ số nguyên ~B_1, B_2, \ldots, B_M~ ~(1 \le B_i \le 10^5)~.

Kết quả

• In ra một số nguyên là số cặp thỏa mãn modulo ~10^9 + 7~.

Ví dụ

Sample Input 1

2 2
1 2
2 1

Sample Output 1

3

Sample Input 2

2 2
1 1
1 1

Sample Output 2

6

Sample Input 3

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

Sample Output 3

191

Giải thích

• Ở test ví dụ 1:

  • ~A~ có những dãy con (), (1), (2), (1, 2)

  • ~B~ có những dãy con (), (2), (1), (2, 1)

  • Những cặp dãy con thỏa mãn là: ((), ()), ((1), (1)), ((2), (2))

  • ((1, 2), (2, 1)) không thỏa, vì nếu xét từ đầu tới cuối của hai dãy con, ta có ~A_1 = 1\ne B_1 = 2~ và ~A_2 = 2\ne B_2 = 1~.

• Ở test ví dụ 2:

  • ~A~ có những dãy con (), (1), (1), (1, 1)

  • ~B~ có những dãy con (), (1), (1), (1, 1)

  • Những cặp dãy con thỏa mãn là: ((), ()), 4 cặp ((1), (1)), ((1, 1), (1, 1)). Vì thế, có tổng cộng 6 cặp thỏa.