#include <fstream>
#include <cstring>

using namespace std;

const int MOD = 666013;
const int SMAX = 501;

string s1, s2;
int C[SMAX][SMAX], nr[SMAX][SMAX];
int main()
{
    ifstream in("subsir.in");
    ofstream out("subsir.out");
    in >> s1 >> s2;
    for(int i = 0; i <= s1.size(); ++i)
        nr[i][0] = 1;
    for(int j = 0; j <= s2.size(); ++j)
        nr[0][j] = 1;
    for(int i = 1; i <= s1.size(); ++i)
        for(int j = 1; j <= s2.size(); ++j)
        {
            if(s1[i - 1] == s2[j - 1])
            {
                C[i][j] = 1 + C[i - 1][j - 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] + nr[i][j - 1]) % MOD;
                    if(C[i - 1][j - 1] == C[i - 1][j])
                        nr[i][j] = (nr[i][j] - nr[i - 1][j - 1] + MOD) % MOD;
                }
                else
                    if(C[i - 1][j] > C[i][j - 1])
                        nr[i][j] = nr[i - 1][j];
                    else
                        nr[i][j] = nr[i][j - 1];
            }
        }
    out << nr[s1.size()][s2.size()];
    return 0;
}