#include<fstream>
#include<algorithm>
#include<string>
using namespace std;

const int MOD=666013;

int i,j,n,m,dp[505][505],nr[505][505];
string a,b;


int main()
{
  ifstream cin("subsir.in");
  ofstream cout("subsir.out");

  getline(cin,a); n=a.length();
  getline(cin,b); m=b.length();

  for(i=0;i<n;++i) nr[i][0]=1;
  for(i=0;i<m;++i) nr[0][i]=1;

  for(i=1;i<=n;++i)
   for(j=1;j<=m;++j)
   if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1,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-1]+nr[i-1][j];
          nr[i][j]%=MOD;
          if(dp[i-1][j-1]==dp[i][j-1]) nr[i][j]-=nr[i-1][j-1]-MOD,nr[i][j]%=MOD;
        }
        else if(dp[i][j-1]>dp[i-1][j]) dp[i][j]=dp[i][j-1],nr[i][j]=nr[i][j-1];
             else dp[i][j]=dp[i-1][j],nr[i][j]=nr[i-1][j];

  cout<<nr[n][m]<<'\n';

 return 0;
}