#include<fstream>
#include<string>
#include<iostream>
using namespace std;
ifstream in("subsir.in");
ofstream out("subsir.out");
const int MOD = 666013;
string a1,a2;

int sol[505][505],n,m,viz[30],bst = 0,sol2 = 0,pr;

void citire()
{

    in>>a1>>a2;
    n = a1.size();
    m = a2.size();
    in.close();
}

void solve()
{

    int i,j;
    for(i = 1 ; i <= n ; i++)
        for(j = 1 ; j <= m ; j++)
        if(a1[i-1]== a2[j-1]){
            sol[i][j] = 1 + sol[i-1][j-1];
            if(bst < sol[i][j]){
                bst = sol[i][j];
                sol2 = 1;
                viz[pr] = 0;
                pr = a1[i-1] - 96;
                viz[pr] = 1;
            }
            else if(bst == sol[i][j] && viz[a1[i-1] - 96] == 0){
                sol2 = (sol2+1) % MOD;
                viz[pr] = 0;
                pr = a1[i-1] - 96;
                viz[pr] = 1;
            }
        }
            else sol[i][j] = max(sol[i-1][j],sol[i][j-1]);
        out<<sol2;
        out.close();
}

int main()
{

    citire();
    solve();
    return 0;
}