#include <fstream>
#include <string>
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
int mod= 666013;
int n,m;
int c[501][501], nr[501][501];
string a, b;
int main()
{
    fin>>a>>b;
    n=a.length();
    m=b.length();
    //a="0"+a;
    //b="0"+b;
    for ( int i= 0; i<=max(n,m); i++ )
    {
        {
            nr[i][0]=1;
            nr[0][i]= 1;
        }
    }
    for ( int i=1; i<=n; i++ )
    {
        for ( int j=1; j<=m; j++ )
        {
            if ( a[i-1]==b[j-1] )
            {
                c[i][j]= c[i-1][j-1]+1;
                nr[i][j]= nr[i-1][j-1];
            }
            else
            {
                c[i][j]= max(c[i-1][j], c[i][j-1]);
                if ( c[i-1][j]>c[i][j-1] )
                {
                    nr[i][j]= nr[i-1][j];
                }
                else
                {
                    nr[i][j]= nr[i][j-1];
                    if ( c[i-1][j]==c[i][j-1] )
                    {
                        nr[i][j]= (nr[i][j]+nr[i-1][j])%mod;
                        if ( c[i-1][j]==c[i-1][j-1] )
                        {
                            nr[i][j]= (nr[i][j]-nr[i-1][j-1]+mod)%mod;
                        }
                    }
                }
            }
        }
    }

    fout<<nr[n][m]<<"\n";

    return 0;
}