#include <fstream>
#include <cstring>
#define M 666013
#define maxim(a, b) ((a > b) ? a : b)
using namespace std;
string a,b;
typedef struct{
  int x,y,suma;
} verif;
verif solutii[250001];
int ok,t,maxx,sol,sir1[501][27],sir2[501][27],m,n,i,j,ii,jj;
int c[501][501],nr[501][501],k;
int main()
{
    ifstream fi("subsir.in");
    ofstream fo("subsir.out");
    getline(fi,a);
    getline(fi,b);
    m=a.size(); n=b.size();

    for(i=1;i<=m;i++)
         for(j=1;j<=26;j++) if(a[i-1]==j+96) sir1[i][j]=i; else sir1[i][j]=sir1[i-1][j];
    for(i=1;i<=n;i++)
         for(j=1;j<=26;j++) if(b[i-1]==j+96) sir2[i][j]=i; else sir2[i][j]=sir2[i-1][j];

    maxx=-int(2e9);
    for(i=1;i<=m;i++)
      for(j=1;j<=n;j++)
        {
          if (a[i-1] == b[j-1])
                c[i][j] = 1 + c[i-1][j-1];
            else
                c[i][j] = maxim(c[i-1][j], c[i][j-1]);
        if(a[i-1]==b[j-1])
        {
        for(k=1;k<=26;k++)
        {
          ii=sir1[i-1][k];
          jj=sir2[j-1][k];
          if((!ii)||(!jj)) continue;
          if(c[i][j]==c[ii][jj]+1) nr[i][j]=(nr[i][j]+nr[ii][jj])%M;
        }
        if(!nr[i][j]) nr[i][j]=1;
        if(c[i][j]>maxx) maxx=c[i][j];
        }
        }
    k=0;
    for(i=m;i>=1;i--)
      for(j=n;j>=1;j--)
      {
        ok=1;
        for(t=1;t<=k;t++)
        {
          if((a[i-1]==solutii[t].suma)&&((solutii[t].x>=i)||(solutii[t].y>=j))) {ok=0; break;
          }
        }
        if((a[i-1]==b[j-1])&&(c[i][j]==maxx)&&(ok==1)) {sol=(sol+nr[i][j])%M;
        solutii[++k].x=i;
        solutii[k].y=j;
        solutii[k].suma=a[i-1];
        }
      }
    fo<<sol%M<<"\n";
    return 0;
}