#include <iostream>
#include <string.h>
#include <fstream>
#define NMax 505
#define mod 666013
using namespace std;
char y[NMax],x[NMax],a[NMax],b[NMax];
int d[NMax][NMax],nr[NMax][NMax],n,m;

int main()
{
    ifstream g("subsir.in");
    ofstream f("subsir.out");
    g.getline(a+1,NMax);
    g.getline(b+1,NMax);
    m=strlen(a+1),n=strlen(a+1);
    for(int i=0;i<=max(m,n);i++)
        nr[0][i]=nr[i][0]=1;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if(a[i]==b[j])
            {
                d[i][j]=d[i-1][j-1]+1;
                nr[i][j]=nr[i-1][j-1];
            }
            else
                if(d[i][j-1]==d[i-1][j])
                {
                    d[i][j]=d[i][j-1];
                    nr[i][j]=(nr[i][j-1]+nr[i-1][j])%mod;
                    if(d[i][j]==d[i-1][j-1])
                        nr[i][j]=(nr[i][j]-nr[i-1][j-1]+mod)%mod;
                }
            else
                if(d[i][j-1]>d[i-1][j])
                {
                    d[i][j]=d[i][j-1];
                    nr[i][j]=nr[i][j-1];
                }
            else
                if(d[i-1][j]>d[i][j-1])
                {
                    d[i][j]=d[i-1][j];
                    nr[i][j]=nr[i-1][j];
                }
        f<<nr[m][n];

}