#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");

#define dim 502
#define MOD 666013

char s1[dim], s2[dim];
int a[dim][dim], b[dim][dim];
int x[dim][26], y[dim][26], n, m;

void af(int a[dim][dim])
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n\n";
}

int main()
{
    int i, j, ii, jj;
    fin>>(s1+1);
    n=strlen(s1+1);
    fin>>(s2+1);
    m=strlen(s2+1);
    for(i=1;i<=n;i++)
    {
        memcpy(x[i], x[i-1], sizeof(x[i]));
        x[i][s1[i]-'a']=i;
    }
    for(i=1;i<=m;i++)
    {
        memcpy(y[i], y[i-1], sizeof(y[i]));
        y[i][s2[i]-'a']=i;
    }
    s1[++n]='#';
    s2[++m]='#';
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(s1[i]==s2[j])
                a[i][j]=1+a[i-1][j-1];
            else
                a[i][j]=max(a[i-1][j], a[i][j-1]);
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(s1[i]==s2[j])
            {

                if(a[i][j]==1)
                    b[i][j]=1;
                for(char c='a';c<='z';c++)
                {

                    ii=x[i-1][c-'a'];
                    jj=y[j-1][c-'a'];
                    if(a[i][j]==a[ii][jj]+1)
                    {
                        b[i][j]+=b[ii][jj];
                        if(b[i][j]>=MOD)
                            b[i][j]-=MOD;
                    }
                }
            }
        }
    }

    fout << b[n][m] << "\n";
}