#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
#define MAX 502
#define MOD 666013
char s1[MAX], s2[MAX];
int a[MAX][MAX], b[MAX][MAX];
int last1[MAX][26], last2[MAX][26], n, m;
 
void af(int a[MAX][MAX])
{
    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(last1[i], last1[i-1], sizeof(last1[i]));
        last1[i][s1[i]-'a']=i;
    }
    for(i=1;i<=m;i++)
    {
        memcpy(last2[i], last2[i-1], sizeof(last2[i]));
        last2[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=last1[i-1][c-'a'];
                    jj=last2[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";
}