#include <iostream>
#include <fstream>
#include <cstring>

#define MOD 666013

using namespace std;

int mat[505][505],nr[505][505];
char a[505],b[505];

int main()
{
    ifstream fin ("subsir.in");
    ofstream fout ("subsir.out");
    int n,m;
    fin.getline(a, 505);
    n=strlen(a);
    fin.getline(b, 505);
    m=strlen(b);

    for (int i=0;i<=n;i++)
    nr[i][0]=1;
    for (int j=0;j<=m;j++)
    nr[0][j]=1;

    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            if (a[i-1]==b[j-1])
            {
                mat[i][j]=mat[i-1][j-1]+1;
                nr[i][j]=nr[i-1][j-1];
            }
            else
            {
                mat[i][j]=max(mat[i-1][j],mat[i][j-1]);
                if (mat[i-1][j]==mat[i][j])
                nr[i][j]+=nr[i-1][j]%MOD;
                if (mat[i][j-1]==mat[i][j])
                nr[i][j]+=nr[i][j-1]%MOD;
                if (mat[i-1][j-1]==mat[i][j])
                nr[i][j]-=nr[i-1][j-1]%MOD;

                if (nr[i][j]<0)
                    nr[i][j]+=MOD;
            }
        }
    /*for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        fout<<nr[i][j]<<' ';
        fout<<'\n';
    }*/
    fout<<nr[n][m]<<'\n';
    return 0;
}