#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++)
    {b[i][0]=1;
      for(j=1;j<=m;j++)
      if(s[i-1]==s1[j-1])
      a[i][j]=a[i-1][j-1]+1;
    else
        if(a[i-1][j]>a[i][j-1])
        a[i][j]=a[i-1][j];
    else
        if(a[i][j-1]>a[i-1][j])
        a[i][j]=a[i][j-1];
        if(s[i-1]==s1[j-1])
            b[i][j]=b[i-1][j-1];
        else
            {if(a[i][j-1]==a[i][j])
            b[i][j]=(b[i][j]+b[i][j-1])%666013;
            if(a[i-1][j]==a[i][j])
                b[i][j]=(b[i][j]+b[i-1][j])%666013;
            if(a[i][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]);
}