#include <fstream>
using namespace std;
ifstream cin("subsir.in");
ofstream cout("subsir.out");
string a,b;
int n,m;
int dp[503][503];
long long sol[503][503];
const long long M=666013;
int main()
{
    cin>>a;
    cin>>b;
    n=a.size();
    m=b.size();
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        if(a[i-1]==b[j-1])
        {
          dp[i][j]=dp[i-1][j-1]+1;
          sol[i][j]=max((long long) 1,sol[i-1][j-1]);
        }
        else
         if(dp[i-1][j]>dp[i][j-1])
         {
            dp[i][j]=dp[i-1][j];
            sol[i][j]=sol[i-1][j];
         }
        else
         if(dp[i-1][j]<dp[i][j-1])
         {
             dp[i][j]=dp[i][j-1];
             sol[i][j]=sol[i][j-1];
         }
        else
         {
             dp[i][j]=dp[i-1][j];
             sol[i][j]=(sol[i-1][j]%M+sol[i][j-1]%M)%M;
             if(sol[i-1][j-1]==sol[i-1][j])
                sol[i][j]=(sol[i][j]%M-sol[i-1][j]%M)%M;
            while(sol[i][j]<0)
              sol[i][j]=sol[i][j]+M;
         }
    cout<<sol[n][m];
    return 0;
}