#include <bits/stdc++.h>
#define Nmax 505
#define MOD 666013
using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");
char s1[Nmax],s2[Nmax];
int pd[Nmax][Nmax],nr[Nmax][Nmax];
int main()
{
    f>>(s1+1)>>(s2+1);
    int i,j,n,m;
    n=strlen(s1+1);
    m=strlen(s2+1);
    for(i=0;i<=n;i++)
        nr[i][0]=1;
    for(i=0;i<=m;i++)
        nr[0][i]=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        if(s1[i]!=s2[j])
        {
            if(pd[i][j-1]>pd[i-1][j])
            {
                pd[i][j]=pd[i][j-1];
                nr[i][j]=nr[i][j-1];
            }
            if(pd[i-1][j]>pd[i][j-1])
            {
                pd[i][j]=pd[i-1][j];
                nr[i][j]=nr[i-1][j];
            }
            if(pd[i-1][j]==pd[i][j-1])
            {
                pd[i][j]=pd[i-1][j];
                nr[i][j]=(nr[i][j-1]+nr[i-1][j])%MOD;
                if(pd[i][j]==pd[i-1][j-1]) nr[i][j]=(nr[i][j]-nr[i-1][j-1]+MOD)%MOD;
            }
        }
        else
        {
            pd[i][j]=pd[i-1][j-1]+1;
            nr[i][j]=nr[i-1][j-1];
        }
    g<<nr[n][m];

    return 0;
}