DCCT2
Cho số nguyên dương \(n, m\), dãy số nguyên \(a_1,a_2,…,a_n\) và dãy số nguyên dương \(b_1,b_2,…,b_n.\)
Dãy \(c_1,c_2,…,c_k\) là dãy con chung của \(a\) và \(b\) thì dãy \(c_1,c_2,…,c_k\) là dãy con của dãy \(a\) và \(c_1,c_2,…,c_k\) là một dãy con của dãy \(b\). Lưu ý dãy rỗng là dãy thỏa điều kiện là dãy con chung theo đề.
Yêu cầu: Đễm số lượng dãy con chung của \(a\) và \(b.\)
Input
Dòng thứ nhất chứa số nguyên dương \(n,m (n, m ≤ 2*10^3).\)
Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (1≤a_i≤10^5).\)
Dòng thứ ba chứa \(m\) số nguyên \(b_1,b_2,…,b_m (1≤b_i≤10^5 ).\)
Output
- Số lượng dãy con chung theo đề của \(a\) và \(b\). Lấy kết quả mod (\(10^9+7\)).
Sample Input
2 2
1 2
2 1Sample Output
3Sample Input
2 2
1 1
1 1Sample Output
6
Comments