#include <fstream>
#include <cstring>
#include <algorithm>
#define NMAX 509
#define MOD 666013
using namespace std;
int d[NMAX][NMAX],r[NMAX][NMAX],v1[NMAX],v2[NMAX];
int main()
{
    int i,j,n,m;
    ifstream f("subsir.in");
    ofstream g("subsir.out");
    char a[NMAX],b[NMAX];
    f>>a>>b;
    n=strlen(a);
    m=strlen(b);
    for(i=1;i<=n;i++)
        v1[i]=a[i-1]-'a'+1;
    for(i=1;i<=m;i++)
        v2[i]=b[i-1]-'a'+1;
    for(i=0;i<=n;i++)
    {
        d[0][i]=0;
        d[m+1][i]=0;
        r[0][i]=1;
        r[m+1][i]=1;
    }
    for(i=0;i<=m;i++)
    {
        d[i][0]=0;
        d[i][n+1]=0;
        r[i][0]=1;
        r[i][n+1]=1;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(v1[i]==v2[j])
                d[i][j]=d[i-1][j-1]+1;
            else
                d[i][j]=max(d[i-1][j],d[i][j-1]);
        }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(d[i][j]==d[i-1][j]&&d[i][j]==d[i][j-1]&&d[i][j]==d[i-1][j-1])
            {
                r[i][j]=r[i-1][j]+r[i][j-1]-r[i-1][j-1];
                r[i][j]=(r[i][j]) % MOD;
            }
            else
            {
                if(d[i][j]==d[i-1][j]&&d[i][j]==d[i][j-1])
                {
                    r[i][j]=r[i-1][j]+r[i][j-1];
                    r[i][j]=(r[i][j]) % MOD;
                }
                else
                {
                    if(d[i][j]==d[i-1][j])
                    {
                        r[i][j]=r[i-1][j];
                        r[i][j]=(r[i][j]) % MOD;
                    }
                    else
                    {
                        if(d[i][j]==d[i][j-1])
                        {
                            r[i][j]=r[i][j-1];
                            r[i][j]=(r[i][j]) % MOD;
                        }
                        else
                        {
                            r[i][j]=r[i-1][j-1];
                            r[i][j]=(r[i][j]) % MOD;
                        }
                    }
                }
            }
        }
    if(r[n][m]<0)
        r[n][m]+=MOD;
    g<<r[n][m]<<"\n";
    return 0;
}