#include<fstream>
#define mod 666013
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
int last_a[505][26],last_b[505][26];
int D[505][505],cnt[505][505];
int main()
{
    int n,m;
    string a,b;
    fin>>a>>b;
    n=a.size();
    m=b.size();
    a=" "+a;
    b=" "+b;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<26;j++)
          last_a[i][j]=last_a[i-1][j];
        last_a[i][a[i]-'a']=i;
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<26;j++)
          last_b[i][j]=last_b[i-1][j];
        last_b[i][b[i]-'a']=i;
    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        if(a[i]==b[j])
        {
            D[i][j]=D[i-1][j-1]+1;
            for(int ch=0;ch<26;ch++)
            {
                int ii=last_a[i-1][ch];
                int jj=last_b[j-1][ch];
                if(D[i][j]==D[ii][jj]+1)
                {
                    cnt[i][j]+=cnt[ii][jj];
                    cnt[i][j]%=mod;
                }
            }
            if(cnt[i][j]==0)
              cnt[i][j]=1;
        }
        else
          D[i][j]=max(D[i-1][j],D[i][j-1]);
    int sol=0;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        if(i==last_a[n][a[i]-'a']&&j==last_b[m][b[j]-'a']&&D[i][j]==D[n][m])
        {
            sol+=cnt[i][j];
            sol%=mod;
        }
    fout<<sol;
    return 0;
}