using namespace std;

#include<iostream>
#include<fstream>
#include<cstring>
#define mod 666013
char a[505],b[505];
int dp[505][505],rez[505][505],N,M;
ofstream fout("subsir.out");
void solve()
{int i,j;
      rez[0][0]=1;
      for(i=0;i<=N;i++)
       rez[i][0]=1;
       for(i=0;i<=M;i++)
       rez[0][i]=1;
    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;
           rez[i][j]=rez[i-1][j-1];}
          else
           if(dp[i-1][j]>dp[i][j-1])
            {dp[i][j]=dp[i-1][j];
            rez[i][j]=rez[i-1][j];
            }
            else if(dp[i-1][j]<dp[i][j-1])
                {dp[i][j]=dp[i][j-1];
                rez[i][j]=rez[i][j-1];
                }
                else
                {dp[i][j]=dp[i][j-1];
                rez[i][j]=(rez[i][j-1]+rez[i-1][j])%mod;
                if(dp[i-1][j]==dp[i-1][j-1])
                rez[i][j]=(rez[i][j]-rez[i-1][j-1]+mod)%mod;
                }


     }
    fout<<rez[N][M]<<"\n";
}

void cit()
{int i;
    ifstream fin("subsir.in");
    fin.getline(a,505);
    N=strlen(a);
    for(i=N;i>=1;i--) a[i]=a[i-1];
    fin.getline(b,505);
    M=strlen(b);
    for(i=M;i>=1;i--) b[i]=b[i-1];
    fin.close();
}

int main()
{

    cit();
    solve();
    fout.close();
    return 0;
}