#include <iostream>
#include <fstream>
#define kMod 666013
using namespace std;

const int NMAX = 501, MOD = 666013;
int dp[NMAX][NMAX];
int nr[NMAX][NMAX];

int main() {

    string s1, s2;
    ifstream fin("subsir.in");
    ofstream fout("subsir.out");
    fin >> s1 >> s2;
    int len1 = s1.size();
    int len2 = s2.size();


    for (int i = 0; i <= len1; i++) {
        nr[i][0] = 1;
    }
    for (int i = 0; i <= len2; i++) {
        nr[0][i] = 1;
    }
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max (dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }

    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                nr[i][j] = nr[i - 1][j - 1];
            } else {
                if(dp[i][j] == dp[i - 1][j]) {
                    nr[i][j] = (nr[i][j] + nr[i-1][j]) % MOD;
                }
                if (dp[i][j] == dp[i][j - 1]) {
                    nr[i][j] = (nr[i][j] + nr[i][j - 1]) % MOD;
                }
                if (dp[i][j] == dp[i - 1][j - 1]) {
                    nr[i][j] = (nr[i][j] - nr[i - 1][j - 1] + MOD) % MOD;
                }
                
            }
        }
    }

    fout << nr[len1][len2] << endl;
    fin.close();
    fout.close();
    return 0;
}