#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

#define cin fin
#define cout fout
#define mod 666013
char p1[503],p2[503];
struct
{
    int val;
    int nr;
}matr[503][503];


int main()
{
    cin.getline(p1+1,501);
    cin.getline(p2+1,501);

    int len1=strlen(p1+1);
    int len2=strlen(p2+1);

    for(int i=0; i<=len1; i++)
        matr[i][0].nr=1;
    for(int j=0; j<=len2; j++)
        matr[0][j].nr=1;

    for(int i=1; i<=len1; i++)
        for(int j=1; j<=len2; j++)
        {
            if(p1[i]==p2[j])
            {
                matr[i][j]=matr[i-1][j-1];
                matr[i][j].val++;
            }
            else
            if(matr[i-1][j].val>matr[i][j-1].val)
                matr[i][j]=matr[i-1][j];
            else
            if(matr[i-1][j].val<matr[i][j-1].val)
                matr[i][j]=matr[i][j-1];
            else
            {
                matr[i][j].val=matr[i][j-1].val;
                matr[i][j].nr=(matr[i][j-1].nr+matr[i-1][j].nr)%mod;
                if(matr[i-1][j-1].val==matr[i-1][j].val)
                    matr[i][j].nr=(matr[i][j].nr+mod-matr[i-1][j-1].nr)%mod;
            }
        }
    cout<<matr[len1][len2].nr;


    return 0;
}