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

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

int n,m;
char c1[502],c2[502];
int submax[502][502],comunmax[505][100],lmax;

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()
{
    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++)
        for(j=1;j<m;j++)
        {
            if(c1[i]==c2[j])
            {
                if(i==1 || j==1) {comunmax[i][j]++; continue;}
                char ch;
                int ii,jj;
                for(ch='a';ch<='z';ch++)
                {
                    ii=i-1; jj=j-1;
                    while(ii>=0 && c1[ii]!=ch) ii--;
                    while(jj>=0 && c2[jj]!=ch) jj--;
                    if(ii!=-1 && jj!=-1)
                        if(submax[ii][jj]==submax[i][j]-1)
                            {
                                comunmax[i][j]+=comunmax[ii][jj];
                                comunmax[i][j]=comunmax[i][j]%666013;
                            }
                }
            }
        }
    g<<comunmax[n-1][m-1]<<"\n";
    g.close();
}
int main()
{
    citire();
    dinamic();
    g.close();
    return 0;
}