#include<iostream>
#include<fstream>
#include<cstring>
#define M 666013
using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");
int i,j;
char sir1[501],sir2[501];
short a[501][501],nr[501][501];

int main()
{
    f>>(sir1+1)>>(sir2+1);
    for (i=0;i<=strlen(sir1+1);i++)
        nr[i][0]=1;
    for (i=0;i<=strlen(sir2+1);i++)
        nr[0][i]=1;
    for (i=1;i<=strlen(sir1+1);i++)
    for (j=1;j<=strlen(sir2+1);j++)
        if (sir1[i]==sir2[j])
        {
            a[i][j]=a[i-1][j-1]+1;
            nr[i][j]=nr[i-1][j-1];
        }
        else
        {
            a[i][j]=max(a[i-1][j],a[i][j-1]);
            if (a[i-1][j]==a[i][j-1])
            {
                nr[i][j]=(nr[i-1][j]+nr[i][j-1])%M;
                if (a[i-1][j]==a[i-1][j-1])
                    nr[i][j]=(nr[i][j]-nr[i-1][j-1])%M;
            }
            else if (a[i-1][j]>a[i][j-1])
                nr[i][j]=nr[i-1][j];
            else if (a[i][j-1]>a[i-1][j])
                nr[i][j]=nr[i][j-1];
        }
    g<<nr[strlen(sir1+1)][strlen(sir2+1)];
    /*for (i=1;i<=strlen(sir1+1);i++)
    {
        for (j=1;j<=strlen(sir2+1);j++)
            cout<<nr[i][j];
        cout<<'\n';
    }*/
    f.close();g.close();
    return 0;
}