#include <fstream>
#include <cstring>

#define MAX 512
#define REST 666013

using namespace std;

char x[MAX], y[MAX];
int n, m, res[MAX][MAX], dp[MAX][MAX];

void solve()
{
    n = strlen(x + 1), m = strlen(y + 1);
    for(int i = 0; i <= max(n, m); i++)
        res[0][i] = res[i][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(x[i] == y[j])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                res[i][j] = res[i - 1][j - 1];
            }
            else if(dp[i - 1][j] == dp[i][j - 1])
            {
                dp[i][j] = dp[i - 1][j];
                res[i][j] = (res[i - 1][j] + res[i][j - 1]) % REST;
                if(dp[i - 1][j] == dp[i - 1][j - 1])
                    res[i][j] = (res[i][j] - res[i - 1][j - 1] + REST) % REST;
            }
            else if(dp[i - 1][j] < dp[i][j - 1])
            {
                dp[i][j] = dp[i][j - 1];
                res[i][j] = res[i][j - 1];
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
                res[i][j] = res[i - 1][j];
            }
        }
}

int main()
{
    ifstream in("subsir.in");
    in.getline(x + 1, MAX);
    in.getline(y + 1, MAX);
    in.close();
    solve();
    ofstream out("subsir.out");
    out<<res[n][m]; out.close();
    return 0;
}