#include <fstream>
#include <cstring>

using namespace std;

int main()
{
    ifstream in("subsir.in");
    ofstream out("subsir.out");
    const int Nmax=502, MOD=666013;
    char a[Nmax],b[Nmax];
    int cnt[Nmax][Nmax],rez[Nmax][Nmax],n,m;
    in.getline(a,Nmax);
    in.getline(b,Nmax);
    n=strlen(a);
    m=strlen(b);
    for(int i=0;i<n;i++)
        cnt[i][0]=1;
    for(int i=0;i<n;i++)
        cnt[0][i]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(a[i-1]==b[j-1])
            {
                rez[i][j]=rez[i-1][j-1]+1, cnt[i][j]=cnt[i-1][j-1];
            }
            else
                if(rez[i-1][j]==rez[i][j-1])
                {
                    rez[i][j]=rez[i-1][j];
                    cnt[i][j]=(cnt[i-1][j]+cnt[i][j-1])%MOD;
                    if(rez[i-1][j-1]==rez[i-1][j])
                        cnt[i][j]=(cnt[i][j]-cnt[i-1][j-1]+MOD)%MOD;
                }
                else
                    if(rez[i][j-1]>rez[i-1][j])
                        rez[i][j]=rez[i][j-1], cnt[i][j]=cnt[i][j-1];
                    else
                        rez[i][j]=rez[i-1][j], cnt[i][j]=cnt[i-1][j];
        }
    out<<cnt[n][m];
    return 0;
}