#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
ifstream fin ("subsir.in");
ofstream fout("subsir.out");
int n,m,i,j,sol[502][502],d[502][502];
const int MOD=666013;
string a,b;
int main()
{
    fin>>a;
    fin>>b;
    n=a.size();
    m=b.size();
    a="0"+a;
    b="0"+b;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(a[i]==b[j])
            {
                sol[i][j]=sol[i-1][j-1]+1;
                d[i][j]=max(d[i-1][j-1],1);
            }
            else
            {
                if(sol[i-1][j]==sol[i][j-1])
                {
                    d[i][j]=d[i-1][j]+d[i][j-1];
                    if(sol[i-1][j]==sol[i-1][j-1])
                        d[i][j]-=(d[i-1][j-1]-MOD);
                }
                else
                    if(sol[i-1][j]>sol[i][j-1])
                        d[i][j]=d[i-1][j];
                    else
                        d[i][j]=d[i][j-1];
                d[i][j]%=MOD;
                sol[i][j]=max(sol[i-1][j],sol[i][j-1]);
            }

        }
    fout<<d[n][m];
    return 0;
}