#include <iostream>
#include <fstream>
#include <cstring>
#define mod 666013

using namespace std;

char a[505],b[505];
int sol[505][505],nr[505][505],n,m;

int maxim(int x,int y)
{
    if(x>y)
        return x;
    return y;
}

int main()
{
    ifstream fin("subsir.in");
    fin>>a;
    n=strlen(a);
    fin>>b;
    m=strlen(b);
    for(int i=0;i<n;i++)
        if(sol[i-1][0]||a[i]==b[0])
            sol[i][0]=1;
    for(int i=0;i<m;i++)
        if(sol[0][i-1]||a[0]==b[i])
            sol[0][i]=1;
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
            if(a[i]==b[j])
                sol[i][j]=sol[i-1][j-1]+1;
            else
                sol[i][j]=maxim(sol[i-1][j],sol[i][j-1]);
    for(int i=0;i<n;i++)
        nr[i][0]=1;
    for(int j=0;j<m;j++)
        nr[0][j]=1;
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
            if(a[i]==b[j])
                nr[i][j]=nr[i-1][j-1]%mod;
            else
            {
                if(sol[i][j]==sol[i-1][j])
                    nr[i][j]=nr[i][j]+nr[i-1][j];
                if(sol[i][j]==sol[i][j-1])
                    nr[i][j]=nr[i][j]+nr[i][j-1];
                if(sol[i][j]==sol[i-1][j-1])
                    nr[i][j]=nr[i][j]-nr[i-1][j-1];
                nr[i][j]+=mod;
                nr[i][j]=nr[i][j]%mod;
            }
    ofstream fout("subsir.out");
    fout<<nr[n-1][m-1];
    return 0;
}