#include <bits/stdc++.h>
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
#define MOD 666013
int n,m,dp[505][505],nr[505][505];
char a[505],b[505];
int main()
{
    fin.getline(a,505);
    fin.getline(b,505);
    n=strlen(a);
    m=strlen(b);
    for (int i=0;i<=n;i++)
        nr[i][0]=1;
    for (int j=0;j<=m;j++)
        nr[0][j]=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            if (a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1] + 1;
                nr[i][j]=nr[i-1][j-1];
            }
            else{
                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                if (dp[i][j]==dp[i][j-1])
                    nr[i][j]+=nr[i][j-1]%MOD;
                if (dp[i][j]==dp[i-1][j])
                    nr[i][j]+=nr[i-1][j]%MOD;
                if (dp[i][j]==dp[i-1][j-1])
                    nr[i][j]-=nr[i-1][j-1]%MOD;
                if (nr[i][j]<0)
                    nr[i][j]+=MOD;
            }
        }
        fout<<nr[n][m]<<'\n';
    return 0;
}