#include <iostream>
#include <fstream>
#include <cstring>

#define MOD 666013

using namespace std;

char a[501], b[501];
int dp[501][501], nr[501][501];

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

void citire (int &n, int &m)
{
    fin.getline(a+1,501);
    fin.getline(b+1,501);

    n=strlen(a+1);
    m=strlen(b+1);
}

void dyn_prog (int n, int m)
{
    for (int i=0; i<=n; i++)
        for (int j=0; j<=m; j++)
    {
        if (i==0||j==0)
        {
            dp[i][j]=0;
            nr[i][j]=1;
        }

        if (a[i]==b[j]&&i&&j)
        {
            dp[i][j]=dp[i-1][j-1]+1;
            nr[i][j]=nr[i-1][j-1]%MOD;
        }

        else
        {
            dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
            if (dp[i][j]==dp[i-1][j]) nr[i][j]+=nr[i-1][j];
            else if (dp[i][j]==dp[i][j-1]) nr[i][j]+=nr[i][j-1];
            else if (dp[i][j]==dp[i-1][j-1]) nr[i][j]-=nr[i-1][j-1];
        }
        nr[i][j]+=MOD;
        nr[i][j]=nr[i][j]%MOD;
    }
}

int main()
{
    int n, m;

    citire(n,m);

    dyn_prog(n,m);

    fout<<nr[n][m];
    return 0;
}