#include <fstream>
#include <cmath>
#include <cstring>
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
#define mod 666013
char a[502], b[502];
int n, m, dp[502][502], sol[502][502];
int main()
{
    int i, j;
    fin>>a>>b;
    n=strlen(a);
    m=strlen(b);
    for(i=1; i<=max(n, m); i++)
        sol[0][i]=sol[i][0]=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][j-1]>dp[i-1][j])
                    sol[i][j]=sol[i][j-1];
                else sol[i][j]=(sol[i-1][j]+sol[i][j-1])%mod;
            }
        }
    fout<<sol[n][m];
    return 0;
}