#include <bits/stdc++.h>

#define MOD 666013
#define NMAX 505
using namespace std;

ifstream fin("subsir.in");
ofstream fout("subsir.out");

string a, b;
int dp[NMAX][NMAX], nr[NMAX][NMAX];

int main()
{
    fin >> a >> b;

    int n = a.size();
    int m = b.size();
    a = "0" + a;
    b = "0" + b;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            if(a[i] == b[j]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if(nr[i - 1][j - 1])
                    nr[i][j] = nr[i - 1][j - 1];
                else nr[i][j] = 1;
            }
            else {
                if(dp[i - 1][j] > dp[i][j - 1]){
                    dp[i][j] = dp[i - 1][j];
                    nr[i][j] = (nr[i][j] + nr[i - 1][j]) % MOD;
                }
                else {
                    if(dp[i - 1][j] == dp[i][j - 1]){
                        dp[i][j] = dp[i - 1][j];
                        nr[i][j] = (nr[i][j] + nr[i - 1][j] + nr[i][j - 1]) % MOD;
                    }
                    else {
                        dp[i][j] = dp[i][j - 1];
                        nr[i][j] = (nr[i][j] + nr[i][j - 1]) % MOD;
                    }
                    if(dp[i - 1][j] == dp[i][j - 1] && dp[i][j] == dp[i - 1][j - 1])
                        nr[i][j] = (nr[i][j] - nr[i - 1][j - 1] + MOD) % MOD;
                }
            }
        }

    fout << nr[n][m] << '\n';
    return 0;
}