#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");
char x[1001],y[1001];
int n,i,j,c[1001][1001],m,MAX,k,l,nrs[1001][1001];
int main()
{
    f.getline(x,1001);
    f.getline(y,1001);
    n=strlen(x);
    m=strlen(y);
    for(j=0;j<m;j++)
        if(x[n-1]==y[j])
            {
                c[n-1][j]=1;
                nrs[n-1][j]=1;
            }
        else
            c[n-1][j]=0;
    for(i=0;i<n;i++)
        if(x[i]==y[m-1]){
            c[i][m-1]=1;
            nrs[i][m-1]=1;
        }
        else
            c[i][m-1]=0;
    for(i=n-2;i>=0;i--)
        for(j=m-2;j>=0;j--)
            if(x[i]==y[j]){
                MAX=0;
                nrs[i][j]=1;
                for(k=i+1;k<n;k++)
                    for(l=j+1;l<m;l++)
                        if(1+c[k][l]>MAX){
                            MAX=1+c[k][l];
                            nrs[i][j]=nrs[k][l];
                        }
                        else if(1+c[k][l]==MAX){
                            nrs[i][j]+=nrs[k][l];
                            nrs[k][l]%=666013;
                        }
                c[i][j]=MAX;
            }
    int MAX=c[0][0],poz1=0,poz2=0;
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            if(MAX<c[i][j]){
                MAX=c[i][j];
                poz1=i;
                poz2=j;
            }
    int rez=0;
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            if(c[i][j]==MAX){
                rez+=nrs[i][j];
                rez%=666013;
            }
    cout<<rez<<'\n';
    return 0;
}