#include <iostream>
#include<cstdio>
#include<cstring>
#define mod 666013
using namespace std;
int best[505][505],c=1;
int maxim(int a,int b)
{

    if(a>b)
        return a;
        else
            if(a==b)
        {
            c++;
            return a;
        }

    return b;
}
int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    char s1[505],s2[505],j,n,m,i;
    gets(s1);
    gets(s2);
    n=strlen(s1);
    m=strlen(s2);

    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            if(s1[i]==s2[j])
                c=1,best[i][j]=1+best[i-1][j-1];
            else
                best[i][j]=maxim(best[i-1][j],best[i][j-1]);
    /*for(i=0;i<n;i++,cout<<endl)
        for(j=0;j<m;j++)
            cout<<best[i][j]<<" ";*/
cout<<c%mod;
    return 0;
}