#include <bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");

///subsir

int mod = 666013;

string a,b;
int dp[505][505];
int nrmod[505][505];

main()
{
    f>>a>>b;

    a = ' '+a;
    b = ' '+b;

    for(int i=1;i<b.size();++i)
    {
        dp[1][i]= (a[1] == b[i]);
        nrmod[1][i]=1;
    }

    for(int i=1;i<a.size();++i)
    {
        dp[i][1] = (a[i] == b[1]);
        nrmod[i][1] = 1;
    }


    for(int i=2;i<a.size();++i)
        for(int j=2;j<b.size();++j)
        {
            if(a[i] == b[j])
            {
                dp[i][j] = dp[i-1][j-1]+1;
                nrmod[i][j] = nrmod[i-1][j-1];
            }
            else
            {
                if(dp[i-1][j]==dp[i][j-1])
                {
                    nrmod[i][j] = nrmod[i-1][j] + nrmod[i][j-1];
                    nrmod[i][j] %= mod;
                    dp[i][j] = dp[i-1][j];

                    if(dp[i-1][j] == dp[i-1][j-1])
                    {
                        nrmod[i][j] = ( nrmod[i][j]-nrmod[i-1][j-1]+mod)%mod;
                    }

                }
                else if(dp[i-1][j]>dp[i][j-1])
                {
                    nrmod[i][j] = nrmod[i-1][j];
                    dp[i][j] = dp[i-1][j];
                }
                else if(dp[i-1][j]<dp[i][j-1])
                {
                    nrmod[i][j] = nrmod[i][j-1];
                    dp[i][j] = dp[i][j-1];
                }
            }
        }

    int mx = 0 ,ans = 0;

    g<<nrmod[a.size()-1][b.size()-1]<< ' ';

    return 0;
}