Two

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Alice gets two sequences A and B. A easy problem comes. How many pair of sequence A' and sequence B' are same. For example, {1,2} and {1,2} are same. {1,2,4} and {1,4,2} are not same. A' is a subsequence of A. B' is a subsequence of B. The subsequnce can be not continuous. For example, {1,1,2} has 7 subsequences {1},{1},{2},{1,1},{1,2},{1,2},{1,1,2}. The answer can be very large. Output the answer mod 1000000007.

Input

The input contains multiple test cases.

For each test case, the first line cantains two integers

Output

For each test case, output the answer mod 1000000007.

Sample Input

3 2

1 2 3

2 1

3 2

1 2 3

1 2

Sample Output

题意：

问这两个序列中有多少对子序列相同;

思路：

dp啦,dp[i][j]表示a[1,i]与b[1,j]里面有多少对子序列相同;转移的时候就是看a[i]与b[j]相同不？

相同的话dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+dp[i-1][j-1]+1;

不同的话dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];

AC代码:

/************************************************
┆  ┏┓　　　┏┓ ┆   
┆┏┛┻━━━┛┻┓ ┆
┆┃　　　　　　　┃ ┆
┆┃　　　━　　　┃ ┆
┆┃　┳┛　┗┳　┃ ┆
┆┃　　　　　　　┃ ┆ 
┆┃　　　┻　　　┃ ┆
┆┗━┓　  　┏━┛ ┆
┆　　┃　  　┃　　┆　　　　　　
┆　　┃　  　┗━━━┓ ┆
┆　　┃　 AC代马 　　┣┓┆
┆　　┃　        　　┏┛┆
┆　　┗┓┓┏━┳┓┏┛ ┆
┆　　　┃┫┫　┃┫┫ ┆
┆　　　┗┻┛　┗┻┛ ┆      
************************************************ */ 
 
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>
 
using namespace std;
 
#define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
 
typedef  long long LL;
 
template<class T> void read(T&num) {
    char CH; bool F=false;
    for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
    for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
    F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
    if(!p) { puts("0"); return; }
    while(p) stk[++ tp] = p%10, p/=10;
    while(tp) putchar(stk[tp--] + '0');
    putchar('
');
}
 
const LL mod=1e9+7;
const double PI=acos(-1.0);
const int inf=1e9;
const int N=1e6+10;
const int maxn=1e3+14;
const double eps=1e-8;

int a[maxn],b[maxn];
LL dp[maxn][maxn];

int main()
{      
        int n,m;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            For(i,1,n)read(a[i]);
            For(i,1,m)read(b[i]);
            For(i,1,n)
            {
                For(j,1,m)
                {
                    if(a[i]!=b[j])dp[i][j]=(dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mod)%mod;
                    else dp[i][j]=(dp[i-1][j]+dp[i][j-1]+1)%mod;
                }
            }
            printf("%lld
",dp[n][m]);
        }
        return 0;
}