#include <cstdio>
#include <cstring>
#include <algorithm>
#define NMax 505
#define Mod 666013
using namespace std;
int N, M, DP[NMax][NMax], NS[NMax][NMax];
char String[2][NMax];
void Initialize ()
{
for (int i=0; i<=N; ++i) NS[i][0]=1;
for (int i=0; i<=M; ++i) NS[0][i]=1;
}
void Solve ()
{
Initialize ();
for (int i=1; i<=N; ++i)
{
for (int j=1; j<=M; ++j)
{
if (String[0][i]==String[1][j])
{
DP[i][j]=1+DP[i-1][j-1];
NS[i][j]=NS[i-1][j-1];
continue;
}
if (DP[i][j-1]<DP[i-1][j])
{
DP[i][j]=DP[i-1][j];
NS[i][j]=NS[i-1][j];
continue;
}
if (DP[i-1][j]<DP[i][j-1])
{
DP[i][j]=DP[i][j-1];
NS[i][j]=NS[i][j-1];
continue;
}
DP[i][j]=DP[i-1][j];
NS[i][j]=(NS[i-1][j]+NS[i][j-1])%Mod;
if (DP[i-1][j-1]==DP[i-1][j])
{
NS[i][j]=(NS[i][j]-NS[i-1][j-1]+Mod)%Mod;
}
}
}
}
void Read ()
{
freopen ("subsir.in", "r", stdin);
scanf ("%s\n%s", String[0]+1, String[1]+1);
N=strlen (String[0]+1); M=strlen (String[1]+1);
}
void Print ()
{
freopen ("subsir.out", "w", stdout);
printf ("%d\n", NS[N][M]);
}
int main ()
{
Read ();
Solve ();
Print ();
return 0;
}