#include <stdio.h>
#include <string.h>
#define fr(i,a,b) for(int i=a;i<b;++i)
#define max(a,b) a>b?a:b;
#define S 500
#define MOD 666013
int a[S][S],b[S][S];
char s1[S+1],s2[S+1];
int main(){
    freopen("subsir.in","r",stdin);
    freopen("subsir.out","w",stdout);
    scanf("%[^\n]s",s1);
    scanf("\n%[^\n]s",s2);
    int l1=strlen(s1),l2=strlen(s2);
    fr(i,0,l1){
        fr(j,0,l2){
            if(!i||!j){
                a[i][j]=s1[i]==s2[j];
                if(i) a[i][j]|=a[i-1][j];
                if(j) a[i][j]|=a[i][j-1];
                b[i][j]=a[i][j];
                }
            else{
                if(s1[i]==s2[j]){
                    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]+b[i][j-1];
                    if(a[i][j]==a[i-1][j-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{
                    a[i][j]=a[i][j-1];
                    b[i][j]=b[i][j-1];
                    }
                if(!b[i][j]&&a[i][j]) b[i][j]=1;
                if(b[i][j]<MOD)b[i][j]+=MOD;
                b[i][j]%=MOD;
                }
            }
        }
    printf("%i",b[l1-1][l2-1]);
    return 0;
    }