#include <bits/stdc++.h>
#define md 666013
#define mp make_pair
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
typedef int matrice[501][501];
matrice dp,sol;
typedef char cuv[501];
cuv a,b;
int i,n,m,j;
queue <pair <int, int> >coada;
void afis(matrice a)
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)cout<<dp[i][j]<<" ";
        cout<<"\n";
    }
}
int main()
{
    fin>>a+1>>b+1;
    n=strlen(a+1);
    m=strlen(b+1);
    for(i=1;i<=max(n,m);i++)sol[i][0]=sol[0][i]=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        if(a[i]==b[j])dp[i][j]=1+dp[i-1][j-1],sol[i][j]=sol[i-1][j-1];
        else
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(dp[i-1][j]>dp[i][j-1])sol[i][j]=sol[i-1][j];
            else
            if(dp[i-1][j]<dp[i][j-1])sol[i][j]=sol[i][j-1];
            else
            {
                sol[i][j]=(sol[i-1][j]+sol[i][j-1])%md;
                if(dp[i-1][j-1]==dp[i-1][j])
                    sol[i][j]=(sol[i][j]-sol[i-1][j-1]+md)%md;
            }
        }
    fout<<sol[n][m]<<"\n";
    return 0;
}