#include <fstream>
#include <string.h>
using namespace std;

ifstream f ("subsir.in");
ofstream g ("subsir.out");

int n,m,rez=0;;
char c1[502],c2[502];
int submax[502][502],comunmax[505][100],lmax;
int lasta[502][27],lastb[502][27];

void citire()
{
    int i=1;
    char c;
    while(f.get(c) && c!='\n') c1[i++]=c;
    n=i; i=1;
    while(f.get(c)) c2[i++]=c;
    m=i-1;
}
void dinamic()
{
    char ch;
    int i,j;
    submax[0][0]=0;
    for(i=1;i<n;i++)
        for(j=1;j<m;j++)
        {
            if(c1[i]==c2[j]) submax[i][j]=1+submax[i-1][j-1];
            else if(submax[i][j-1]>submax[i-1][j]) submax[i][j]=submax[i][j-1];
                else submax[i][j]=submax[i-1][j];
        }
        for(i=1;i<n;i++)
        {
            lasta[i][c1[i]-'a']=i;
            for(ch='a';ch<='z';ch++)
            {
                if(ch==c1[i]) continue;
                lasta[i][ch-'a']=lasta[i-1][ch-'a'];
            }
        }
        for(i=1;i<m;i++)
        {
            lastb[i][c2[i]-'a']=i;
            for(ch='a';ch<='z';ch++)
            {
                if(ch==c2[i]) continue;
                lastb[i][ch-'a']=lastb[i-1][ch-'a'];
            }
        }
    for(i=1;i<n;i++)
        for(j=1;j<m;j++)
        {
            if(c1[i]==c2[j])
            {
                if(submax[i][j]==1) {comunmax[i][j]=1; continue;}
                int ii,jj;
                for(ch='a';ch<='z';ch++)
                {
                    ii=lasta[i-1][ch-'a'];
                    jj=lastb[j-1][ch-'a'];
                        if(submax[ii][jj]==submax[i][j]-1)
                                comunmax[i][j]=(comunmax[i][j]+comunmax[ii][jj])%666013;
                }
            }
        }
    for(i=1;i<n;i++)
        for(j=1;j<m;j++)
            if(comunmax[i][j] && submax[i][j]==submax[n-1][m-1])
                if(lasta[n-1][c1[i]-'a']==i && lastb[m-1][c1[i]-'a'==j])
                    rez+=comunmax[i][j]%666013;
    g<<rez<<"\n";
    g.close();
}
int main()
{
    citire();
    dinamic();
    g.close();
    return 0;
}