#include <cstdio>
#include <cstring>
 
using namespace std;
 
int c[501][501],d[501][501];
char a[501],b[501];
 
int main()
{
    int i,j,n,m;
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    fgets(a,sizeof(a),stdin);
    fgets(b,sizeof(b),stdin);
    n=strlen(a);
    m=strlen(b);
    for(i=0;i<501;i++)
        d[i][0]=d[0][i]=1;
    for(i=0;i<n;++i)
        for(j=0;j<m;++j)
            if(a[i]==b[j])
            {
                c[i+1][j+1]=c[i][j]+1;
                d[i+1][j+1]=d[i][j];
            }
            else if(c[i+1][j]<c[i][j+1])
            {
                c[i+1][j+1]=c[i][j+1];
                d[i+1][j+1]=d[i][j+1];
            }
            else if(c[i+1][j]>c[i][j+1])
            {
                c[i+1][j+1]=c[i+1][j];
                d[i+1][j+1]=d[i+1][j];
            }
            else if(c[i+1][j]==c[i][j+1])
            {
                c[i+1][j+1]=c[i][j+1];
                d[i+1][j+1]=(d[i+1][j]+d[i][j+1])%666013;
                if(c[i][j]==c[i+1][j])
                    d[i+1][j+1]=(d[i+1][j+1]-d[i][j]+666013)%666013;
            }
    printf("%d\n",d[n][m]);
    return 0;
}