#include <fstream>
# include <string>
# include <algorithm>
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.length();
    m=b.length();
    for (i=0; i<=n; i++)
         e[i][0]=1;
    for (i=0; i<=m; i++)
         e[0][i]=0;
    for (i=1; i<=n; i++)
    {
        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[i-1])
                     e[i][j]=e[i-1][j-1];
                else
                {
                    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;
}