#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>
#define MOD 666013

using namespace std;

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

int dp[505][505];
int n,m;
char a[505],b[505];
int nr_solutions[505][505];
void read()
{
    char aux[505];
    fin.getline(a,505);
    n=strlen(a);
    strcpy(aux,a);
    strcpy(a+1,aux);
    fin.getline(b,505);
    m=strlen(b);
    strcpy(aux,b);
    strcpy(b+1,aux);
    for(int i=0;i<=n;i++)
        nr_solutions[i][0]=1;
    for(int j=0;j<=m;j++)
        nr_solutions[0][j]=1;
}
bool is_ok(int i, int j)
{
    return (i>0 && j>0)?true:false;
}
void solve()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(a[i]==b[j])
            {
                dp[i][j]=1+dp[i-1][j-1];
                nr_solutions[i][j]=nr_solutions[i-1][j-1];
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                if(dp[i][j]==dp[i-1][j])
                    nr_solutions[i][j]=(nr_solutions[i][j]+nr_solutions[i-1][j])%MOD;
                if(dp[i][j]==dp[i][j-1])
                    nr_solutions[i][j]=(nr_solutions[i][j]+nr_solutions[i][j-1])%MOD;
                if(dp[i][j]==dp[i-1][j-1])
                {
                    nr_solutions[i][j]-=nr_solutions[i-1][j-1];
                    if(nr_solutions[i][j]>0)
                        nr_solutions[i][j]%=MOD;
                    else
                         nr_solutions[i][j]+=MOD;
                }
            }
        }
}
int main()
{
    read();
    solve();
    fout<<nr_solutions[n][m];
    return 0;
}