#include <bits/stdc++.h>

using namespace std;

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

int i,j,l1,l2,l[501][501],n[501][501],mod=666013;

string s1,s2;
int main()
{
    fin>>s1>>s2;
    l1=s1.size();
    l2=s2.size();
    for (i=0;i<l1;i++)
        for (j=0;j<l2;j++)
        if (s1[i]==s2[j])
    {
        n[i][j]=n[i-1][j-1];
        if (n[i][j]==0) n[i][j]=1;
        l[i][j]=l[i-1][j-1]+1;
    }
        else
        {
            if (l[i-1][j]>l[i][j-1]) { l[i][j]=l[i-1][j]; n[i][j]=n[i-1][j];}
            if (l[i-1][j]<l[i][j-1]) { l[i][j]=l[i][j-1]; n[i][j]=n[i][j-1];}
            if (l[i-1][j]==l[i][j-1]) { l[i][j]=l[i-1][j]; n[i][j]=n[i-1][j]+n[i][j-1]; if (l[i-1][j-1]==l[i-1][j]) n[i][j]=(n[i][j]-n[i-1][j-1]+mod)%mod;}
        }
    fout<<n[l1-1][l2-1];
    return 0;
}