#include <iostream>
#include <fstream>
using namespace std;
ifstream in ("subsir.in");
ofstream out ("subsir.out");
char a[501],b[501],v[501];
long long drum[501][501],n,m,l[501][501];

void citire(){
in>>a;
while(a[n]!=NULL) n++;
n--;
in>>b;
while(b[m]!=NULL) m++;
m--;}

 void rez(){
l[0][0]=1;
for(int i=1;i<=n;i++)l[i][0]=1;
for(int i=1;i<=m;i++)l[0][i]=1;
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        if(a[i-1]==b[j-1]){
            drum[i][j]=1+drum[i-1][j-1];
            l[i][j]=l[i-1][j-1];}
        else if(drum[i-1][j]==drum[i][j-1]){
                drum[i][j]=drum[i-1][j];
                l[i][j]=(l[i-1][j]+l[i][j-1])%666013;
                if(drum[i-1][j]==drum[i-1][j-1]) l[i][j]=(l[i][j]-l[i-1][j-1]+666013)%666013;}
                else if(drum[i-1][j]<drum[i][j-1]){
                    drum[i][j]=drum[i][j-1];
                    l[i][j]=l[i][j-1];}
                else if(drum[i-1][j]>drum[i][j-1]){
                        drum[i][j]=drum[i-1][j];
                        l[i][j]=l[i-1][j];}}


int main(){
citire();
rez();
out<<l[n][m];}