#include <fstream>
#include <string.h>
#define mod 666013
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][100],lastb[502][100];

void citire()
{
    f.getline(c1+1,502);
    f.getline(c2+1,502);
    n=strlen(c1+1);
    m=strlen(c2+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]]=i;
            for(ch='a';ch<='z';ch++)
            {
                if(ch==c1[i]) continue;
                lasta[i][ch]=lasta[i-1][ch];
            }
        }
        for(i=1;i<=m;i++)
        {
            lastb[i][c2[i]]=i;
            for(ch='a';ch<='z';ch++)
            {
                if(ch==c2[i]) continue;
                lastb[i][ch]=lastb[i-1][ch];
            }
        }
    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];
                    jj=lastb[j-1][ch];
                        if(submax[ii][jj]+1==submax[i][j])
                                comunmax[i][j]+=comunmax[ii][jj]%mod;
                }
            }
        }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(comunmax[i][j] && submax[i][j]==submax[n][m])
                if(lasta[n][c1[i]]==i && lastb[m][c1[i]]==j)
                    rez+=comunmax[i][j]%mod;
    g<<rez<<"\n";
    g.close();
}
int main()
{
    citire();
    dinamic();
    g.close();
    return 0;
}