#include <iostream>
#include <fstream>
using namespace std;
#define mod 666013
char a[505], b[505],c;
int c2[505][505], nr[505][505];
int ua[30][505], ub[30][505];
int main()
{
    ifstream fin("subsir.in");
    ofstream fout("subsir.out");

    int n=0, m=0,i,j;

    while((c=fin.get()) && (c!='\n'))
        a[++n]=c;
    while((c=fin.get()) && (c!=EOF))
        b[++m]=c;

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

    /*for(i=1;i<=n;++i)
    {
        cout<<'\n';
        for(j=1;j<=m;++j)
            cout<<nr[i][j];
    }*/
    for(i=1;i<=n;++i)
        for(j='a';j<='z';++j)
            if(a[i]==j)
                ua[j-'a'][i]=i;
            else
                ua[j-'a'][i]=ua[j-'a'][i-1];
    for(i=1;i<=m;++i)
        for(j='a';j<='z';++j)
            if(b[i]==j)
                ub[j-'a'][i]=i;
            else
                ub[j-'a'][i]=ub[j-'a'][i-1];

            int sol=0;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(a[i]==b[j])
            {
                for(int k='a';k<='z';++k)
                {
                    int x=ua[k-'a'][i-1];
                    int y=ub[k-'a'][j-1];
                    if(c2[x][y]+1==c2[i][j])
                        nr[i][j]=(nr[i][j]+nr[x][y])%mod;
                }
                if(c2[i][j]==c2[n][m] && ua[a[i]-'a'][n]==i && ub[b[j]-'a'][m]==j)
                    sol=(sol+nr[i][j])%mod;
            }

            fout<<sol;
    return 0;
}