#include <bits/stdc++.h>
#define MOD 666013
#define NMAX 501
using namespace std;

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

int dp[NMAX][NMAX]; ///lungimea maxima a unui subsir comun
int nr_subsiruri[NMAX][NMAX]; ///numarul de subsiruri de lungime maxima

int main()
{
    string s1, s2;
    in >> s1 >> s2;
    for(int i=0; i<=s1.size(); i++)
        nr_subsiruri[i][0]=1;

    for(int j=0; j<=s2.size(); j++)
        nr_subsiruri[0][j]=1;

    for(int i=1; i<=s1.size(); i++)
    {
        for(int j=1; j<=s2.size(); j++)
        {
            if(s1[i-1]==s2[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
                nr_subsiruri[i][j]=nr_subsiruri[i-1][j-1];
            }
            else
            {
                if(dp[i-1][j]>dp[i][j-1])
                {
                    dp[i][j]=dp[i-1][j];
                    nr_subsiruri[i][j]=nr_subsiruri[i-1][j];
                }
                else if(dp[i-1][j]<dp[i][j-1])
                {
                    dp[i][j]=dp[i][j-1];
                    nr_subsiruri[i][j]=nr_subsiruri[i][j-1];
                }
                else
                {
                    dp[i][j]=dp[i-1][j];
                    nr_subsiruri[i][j]=nr_subsiruri[i-1][j]+nr_subsiruri[i][j-1];
                    if(nr_subsiruri[i][j]>=MOD) nr_subsiruri[i][j]-=MOD;

                    if(dp[i-1][j]==dp[i-1][j-1])
                    {
                        nr_subsiruri[i][j]=nr_subsiruri[i][j]-nr_subsiruri[i-1][j-1];
                    }
                    if(nr_subsiruri[i][j]<0) nr_subsiruri[i][j]+=MOD;
                }
            }
        }
    }
    out << nr_subsiruri[s1.size()][s2.size()];

    return 0;
}