#include<iostream>
using namespace std;
#include<stdio.h>
#include<string.h>
char s[500],s1[500];
int n,m,i,j,a[501][501],k,b[501][501];
FILE *f,*g;
int main()
{
    f=fopen("subsir.in","r");
    g=fopen("subsir.out","w");
    fgets(s,100,f);
     n=strlen(s);
    fgets(s1,100,f);
    m=strlen(s1);
    for(i=1;i<=n;i++)
    {
      for(j=1;j<=m;j++)
      if(s[i-1]==s1[j-1])
      {a[i][j]=a[i-1][j-1]+1;
      b[i][j]=b[i-1][j-1];}
    else
        if(a[i-1][j]>a[i][j-1])
        {a[i][j]=a[i-1][j];
        b[i][j]=b[i-1][j];}
    else
        if(a[i][j-1]>a[i-1][j])
        {a[i][j]=a[i][j-1];
        b[i][j]=b[i][j-1];}
            else
            if(a[i-1][j]==a[i][j-1])
               {b[i][j]=(b[i-1][j]+b[i][j-1])%666013;
               a[i][j]=a[i-1][j];}
              if(a[i-1][j]==a[i-1][j-1])
         b[i][j]=(b[i][j]-b[i-1][j-1]+666013)%666013;
    }
fprintf(g,"%d",b[n][m]);
}