What's this test??
My code:
#include <string>
#include <algorithm>
#include <iostream>
#define N 2222
#define MOD 1000000007ll
using namespace std;
long long f[N][N],d[N][N];
int n,m;
string s1,s2;
void init(){
getline(cin,s1);
getline(cin,s2);
n=s1.length(),m=s2.length();
}
int main(){
init();
for (int i=0;i<=n;i++) d[i][0]=i;
for (int i=0;i<=m;i++) d[0][i]=i;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (s1[i-1]==s2[j-1]) d[i][j]=d[i-1][j-1]+1;
else d[i][j]=min(d[i-1][j],d[i][j-1])+1;
for (int i=0;i<=n;i++) f[i][0]=1;
for (int i=0;i<=m;i++) f[0][i]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
if (d[i][j]==i || d[i][j]==j) f[i][j]=1;
else{
if (s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1];
else f[i][j]=f[i-1][j]+f[i][j-1];
}
f[i][j]%=MOD;
}
cout<<f[n][m]<<endl;
}
