#include <fstream>
#include <cstring>
#define MOD 666013

using namespace std;

char a[505],b[505];
int N,M,dp[505][505],nr[505][505];

inline void Read()
{
    ifstream fin("subsir.in");
    fin>>(a+1)>>(b+1);
    N=strlen(a+1); M=strlen(b+1);
    fin.close();
}

inline void Solve()
{
    int i,j;
    for(i=1;i<=M;++i)
        nr[0][i]=1;
    for(i=1;i<=N;++i)
        nr[i][0]=1;
    nr[0][0]=1;
    for(i=1;i<=N;++i)
        for(j=1;j<=M;++j)
            if(a[i]==b[j])
            {
                dp[i][j]=dp[i-1][j-1]+1;
                nr[i][j]=nr[i-1][j-1];
            }
            else
                if(dp[i-1][j]>dp[i][j-1])
                {
                    dp[i][j]=dp[i-1][j];
                    nr[i][j]=nr[i-1][j];
                }
                else
                    if(dp[i][j-1]>dp[i-1][j])
                    {
                        dp[i][j]=dp[i][j-1];
                        nr[i][j]=nr[i][j-1];
                    }
                    else
                    {
                        dp[i][j]=dp[i][j-1];
                        nr[i][j]=(nr[i-1][j]+nr[i][j-1])%MOD;
                        if(dp[i-1][j]==dp[i-1][j-1])
                            nr[i][j]=(nr[i][j]-nr[i-1][j-1]+MOD)%MOD;
                    }
    ofstream fout("subsir.out");
    fout<<nr[N][M]<<"\n";
    fout.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}