#include <bits/stdc++.h>
using namespace std;
ifstream fin ("subsir.in");
ofstream fout ("subsir.out");


const int MOD=666013;
const int LMAX=512;

short dp[LMAX][LMAX],n,m;
int moduri[LMAX][LMAX];
string s1,s2;

int main()
{
    fin >>s1>>s2;

    n=s1.size ();
    m=s2.size ();
    for (int i=0;i<=n;++i){
        moduri[i][0]=1;
    }
    for (int i=0;i<=m;++i){
        moduri[0][i]=1;
    }

    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            if (s1[i-1]=s2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
                moduri[i][j]=moduri[i-1][j-1];
            }
            else{
                if (dp[i-1][j]>dp[i][j-1]){
                    dp[i][j]=dp[i-1][j];
                    moduri[i][j]=moduri[i-1][j];
                }
                else{
                    if (dp[i][j-1]>dp[i-1][j]){
                        dp[i][j]=dp[i][j-1];
                        moduri[i][j]=moduri[i][j-1];
                    }
                    else{
                        dp[i][j]=dp[i-1][j];
                        moduri[i][j]=(moduri[i-1][j]+moduri[i][j-1])%MOD;
                        if (dp[i-1][j]==dp[i-1][j-1]){
                            moduri[i][j]=(moduri[i][j]-moduri[i-1][j-1]+MOD)%MOD;
                        }

                    }
                }
            }
        }
    }
    fout <<moduri[n][m];
    fin.close ();
    fout.close ();
    return 0;
}