#include <fstream>
# include <string>

using namespace std;
string a, b;
int n,m,i,d[510][510],e[510][510],j;
int main()
{
    ifstream f("subsir.in");
    ofstream g("subsir.out");
    f>>a;
    f>>b;
    n=a.size();
    m=b.size();
    for (i=0; i<=m; i++)
         e[0][i]=0;
    for (i=1; i<=n; i++)
    {
        e[i][0]=1;
        for (j=1; j<=m; j++)
             {
                if (a[i-1]==b[j-1])
                     d[i][j]=d[i-1][j-1]+1;
                 else
                  d[i][j]=max(d[i-1][j],d[i][j-1]);

                if (a[i-1]==b[j-1])
                     e[i][j]=e[i-1][j-1];
                else
                {
                    e[i][j]=0;
                    if (d[i][j]==d[i-1][j])
                        e[i][j]=(e[i][j]+e[i-1][j])%666013;
                     if (d[i][j]==d[i][j-1])
                        e[i][j]=(e[i][j]+e[i][j-1])%666013;
                     if (d[i][j]==d[i-1][j-1])
                        e[i][j]=(e[i][j]-e[i-1][j-1]+666013)%666013;
                }
             }
    }
    g<<e[n][m];
    g<<'\n';
    return 0;
}