#include <stdio.h>
#include <string.h>

#define maxn 510
#define maxl 26
#define mod 666013

char a[maxn],b[maxn];
int n,m,sol,max;
int x[maxn][maxl],y[maxn][maxl];
int c[maxn][maxn],d[maxn][maxn];

void move(char a[],int n)
{
    int i;
    for (i=n;i>0;i--) a[i]=a[i-1];
    a[0]=' ';
}

void make(char a[],int n,int x[][maxl])
{
     int i,j;
     
     for (i=0;i<maxl;i++) x[n][i]=n+1;
     
     for (i=n-1;i>=0;i--)
       for (j=0;j<maxl;j++)
         if (a[i+1]-'a'==j) x[i][j]=i+1;
         else x[i][j]=x[i+1][j];
}


int main()
{
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    
    fgets(a,maxn,stdin);
    n=strlen(a)-1;
    fgets(b,maxn,stdin);
    m=strlen(b)-1;
    move(a,n);
    move(b,m);
    
    int i,j,k,p,q;
    
    make(a,n,x);
    make(b,m,y);
    
    c[0][0]=1;
    d[0][0]=0;
    for (i=0;i<n;i++)
      for (j=0;j<m;j++)
        if (c[i][j]>0)
          for (k=0;k<maxl;k++)
          {
              p=x[i][k];
              q=y[j][k];
              
              if ((p!=n+1) && (q!=m+1))
              {
                  if (d[i][j]+1==d[p][q])
                  {
                      c[p][q]+=c[i][j];
                      if (c[p][q]>mod) c[p][q]-=mod;
                  }  
                  else if (d[i][j]+1>d[p][q])
                       {
                           d[p][q]=d[i][j]+1;
                           c[p][q]=c[i][j];
                       } 
              }
          }
    
    max=0;
    for (i=1;i<=n;i++)
      for (j=1;j<=m;j++)      
		if (d[i][j]>max)
		{
		   sol=c[i][j];
		   max=d[i][j];
		}
        else if (d[i][j]==max) 
             {
                 sol+=c[i][j];
                 if (sol>mod) sol-=mod;
             } 
             
    printf("%d\n",sol);
    
    return 0;
}