#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
using namespace std;

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

const int mx = 510, mod=666013;
char a[mx], b[mx];
int n,m,c[mx][mx],len;


void lcs()
{
    memset(c,sizeof(c), 0);
    int i,j;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            if(a[i-1]==b[j-1]) c[i][j]=c[i-1][j-1]+1;
            else
            {
                if(c[i][j-1]>c[i-1][j]) c[i][j]=c[i][j-1];
                    else c[i][j]=c[i-1][j];
            }
        }
    len = c[n][m];
}

long get(int i, int j)
{
    if(j==0 || i==0) return 0;
    if(a[i-1] == b[j-1]) return 1+get(i-1, j-1);

    long r=0;
    if(c[i][j-1] >= c[i-1][j]) r+= get(i,j-1);
    if(c[i][j-1] <= c[i-1][j]) r+= get(i-1,j);
    return r;
}

void read()
{
    in >> a >> b;
    n = strlen(a);
    m = strlen(b);
}


int main()
{
    read();
    lcs();
    long x=get(n,m)/len;
    x=x%mod;
    out<<x;
    return 0;
}