#include<fstream>
#include<cstring>
using namespace std;
#define MOD 666013
ifstream fin("subsir.in");
ofstream fout("subsir.out");
int n,m,A[505][505],N[505][505];
char a[506],b[506];
int main()
{
    int i,j;
    fin>>(b+1)>>(a+1);
    n=strlen(a+1), m=strlen(b+1);
    for (i=0;i<=n;++i)
        N[i][0]=1;
    for (j=0;j<=m;++j)
        N[0][j]=1;
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
        {
            if (a[i]==b[j])
            {
                A[i][j]=1+A[i-1][j-1];
                N[i][j]=N[i-1][j-1];
            }
            else
            {
                if (A[i][j-1]==A[i-1][j])
                {
                    A[i][j]=A[i][j-1];
                    N[i][j]=(N[i][j-1]+N[i-1][j])%MOD;
                    if (A[i-1][j-1]==A[i][j-1])
                        N[i][j]=(N[i][j]-N[i-1][j-1]+MOD)%MOD;
                }
                else
                {
                    if (A[i][j-1]>A[i-1][j])
                        A[i][j]=A[i][j-1],
                        N[i][j]=N[i][j-1];
                    else
                        A[i][j]=A[i-1][j],
                        N[i][j]=N[i-1][j];
                }
            }
        }
    fout<<N[n][m]<<"\n";
    return 0;
}