#include <iostream>
#include <stdio.h>
#include <cstring>
#define MOD 666013
using namespace std;
char a[510],b[510];
int v[510][510],hmax,n,m,nr[100][100];

void cmlsc(){
    int i,j;
    hmax=0;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(a[i-1]==b[j-1]){
                v[i][j]=v[i-1][j-1]+1;
                nr[i][j]=nr[i-1][j-1];
            }else{
                v[i][j]=max(v[i-1][j],v[i][j-1]);
                if (v[i-1][j]==v[i][j])
                nr[i][j]+=nr[i-1][j]%MOD;
                if (v[i][j-1]==v[i][j])
                nr[i][j]+=nr[i][j-1]%MOD;
                if (v[i-1][j-1]==v[i][j])
                nr[i][j]-=nr[i-1][j-1]%MOD;

                if (nr[i][j]<0)
                    nr[i][j]+=MOD;

            }
            hmax=max(hmax,v[i][j]);
        }
    }
    printf("%d",nr[n][m]);
}
int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    int i,j;
    gets(a);
    gets(b);
    n=strlen(a);
    m=strlen(b);

    for(int i=0;i<=n;i++)nr[i][0]=1;
    for(int j=0;j<=m;j++)nr[0][j]=1;
    cmlsc();
    return 0;
}