#include <fstream>
#include <string.h>
#include <iostream>
using namespace std;
char a[501],b[501];
int sub[501][501],nrdr[501][501];
int n,m;
int main()
{
    int i,j;
    char c;
    ifstream in("subsir.in");
    in>>a>>b;
    in.close();
    n=strlen(a);
    m=strlen(b);
    for(i=n;i>0;i--)
        a[i]=a[i-1];
    for(i=m;i>0;i--)
        b[i]=b[i-1];
    for(i=0;i<=m;i++) nrdr[0][i] = 1;
    for(i=0;i<=n;i++ ) nrdr[i][0] = 1;

    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {
    if(a[i]==b[j])
    {
    sub[i][j]=sub[i-1][j-1]+1;
    nrdr[i][j]=nrdr[i-1][j-1];
    }
    else if(sub[i-1][j]==sub[i][j-1])
    {
    sub[i][j] = sub[i-1][j];
    nrdr[i][j] = ( nrdr[i-1][j] + nrdr[i][j-1] ) % 666013;
    if( sub[i-1][j] == sub[i-1][j-1] )
    nrdr[i][j] = ( nrdr[i][j] - nrdr[i-1][j-1] + 666013 ) % 666013;
    }
    else if(sub[i-1][j]>sub[i][j-1])
    {
    sub[i][j] = sub[i-1][j];
    nrdr[i][j] = nrdr[i-1][j];
    }
    else if(sub[i][j-1]>sub[i-1][j])
    {
        sub[i][j]=sub[i][j-1];
        nrdr[i][j]=nrdr[i][j-1];
    }
    }
    ofstream out("subsir.out");
    out<<nrdr[n][m];
}