#include <bits/stdc++.h>
#define NMAX 510
#define MOD 666013
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
char a[NMAX],b[NMAX];
int n,m;
int nr[NMAX][NMAX];
int dp[NMAX][NMAX];
void citire();
void dp1();
int main()
{citire();
 dp1();
 fout<<nr[n][m];
    return 0;
}
void citire()
{
  fin>>(a+1)>>(b+1);
  n=strlen(a+1);
  m=strlen(b+1);
}
void dp1()
{
  int i,j;
  for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(a[i]==b[j])
            {
             dp[i][j]=dp[i-1][j-1]+1;
             if(  !nr[i-1][j-1])
                nr[i][j]=nr[i-1][j-1]+1;
             else
              nr[i][j]=nr[i-1][j-1];
            }
            else
            if(dp[i-1][j]>dp[i][j-1])
            {
             dp[i][j]=dp[i-1][j];
             nr[i][j]=(nr[i][j]+nr[i-1][j])%MOD;
            }
            else
            if(dp[i-1][j]<dp[i][j-1])
            {
             dp[i][j]=dp[i][j-1];
             nr[i][j]=(nr[i][j]+nr[i][j-1])%MOD;
            }
            else
            {

                if(dp[i-1][j]==dp[i][j-1])
                {
                 dp[i][j]=dp[i-1][j];
                 nr[i][j]=(nr[i][j]+nr[i-1][j]+nr[i][j-1])%MOD;
                }
                if(dp[i-1][j]==dp[i][j-1] && dp[i][j-1]==dp[i-1][j-1])
                {
                 nr[i][j]=(nr[i][j]-nr[i-1][j-1]+MOD)%MOD;

                }
            }
}