#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("subsir.in");
ofstream fout("subsir.out");

char s1[503],s2[503];
int sol[503][503],nr[503][503];

int main()
{
    fin.getline(s1+1,503);
    fin.getline(s2+1,503);
    int n=strlen(s1+1);
    int m=strlen(s2+1);
    for(int i=0;i<=n;i++)
        nr[i][0]=1;
    
    for(int i=0;i<=m;i++)
        nr[0][i]=1;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(s1[i]==s2[j])
            {sol[i][j]=sol[i-1][j-1]+1;
                nr[i][j]=nr[i-1][j-1];}
            else if(sol[i-1][j]>sol[i][j-1]){
                sol[i][j]=sol[i-1][j];
                nr[i][j]=nr[i-1][j];
            }
            else if(sol[i][j-1]>sol[i-1][j])
            {
                sol[i][j]=sol[i][j-1];
                nr[i][j]=nr[i][j-1];
            }
            else{
                sol[i][j]=sol[i][j-1];
                nr[i][j]=(nr[i][j-1]+nr[i-1][j])%666013;
                if(sol[i-1][j-1]==sol[i][j-1])
                    nr[i][j]=(nr[i][j]-nr[i-1][j-1]+666013)%666013;
            }
        }
    fout<<nr[n][m];
    
}