给出两个长度分别为 和 的整数序列 和 ,它们均由 到 (含 )之间的整数组成。
求在 子序列和 子序列中,有多少对两个子序列的内容相同。
子序列的说明:
的子序列是指通过从删除零个或多个元素而不改变顺序而获得的序列。我们额外定义空序列是任何整数序列的子序列(即元素可以删光)
对于和而言,如果子序列的内容相同,但是被删除元素的索引集(位置)不同,也当成两个不同的子序列。
输出答案模 的结果
第一行两个整数 和
接下来两个分别是整数序列 和
输出一个整数表示答案
样例输入 1
2 2 1 3 3 1
样例输出 1
3
样例输入 2
2 2 1 1 1 1
样例输出 2
6
样例输入 3
4 4 3 4 5 6 3 4 5 6
样例输出 3
16
样例输入 4
10 9 9 6 5 7 5 9 8 5 6 7 8 6 8 5 5 7 9 9 7
样例输出 4
191
样例输入 5
20 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
样例输出 5
846527861
对于的数据满足