#include <fstream>
#include <string.h>
using namespace std;

ifstream fin("subsir.in");
ofstream fout("subsir.out");
int l[501][501],nr[501][501],n,m;
char a[501],b[501];
int main()
{

    fin.getline(a+1,501);
    n=strlen(a+1);
    fin.getline(b+1,501);
    m=strlen(b+1);
    int i,j;
    for(i=0; i<=m; i++)
        nr[0][i]=1;
    for(i=0; i<=n; i++)
        nr[i][0]=1;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(a[i]==b[j])
            {
                l[i][j]=l[i-1][j-1]+1;
                nr[i][j]=nr[i-1][j-1];
            }
            else if(l[i-1][j]>l[i][j-1])
            {
                l[i][j]=l[i-1][j];
                nr[i][j]=nr[i-1][j];
            }
            else if(l[i][j-1]>l[i-1][j])
            {
                l[i][j]=l[i][j-1];
                nr[i][j]=nr[i][j-1];
            }
            else
            {
                l[i][j]=l[i-1][j];
                nr[i][j]=(nr[i][j-1]+nr[i-1][j])%666013;
                if(l[i-1][j-1]==l[i-1][j]) nr[i][j]=((nr[i][j]-nr[i-1][j-1])+666013)%666013;
            }
    fout<<nr[n][m];
    return 0;
}