#include <bits/stdc++.h>
using namespace std;
ifstream in("subsir.in");
ofstream out("subsir.out");
const int N = 505;
const int MOD = 666013;
int dp[N][N],nr[N][N],lastA[N][30],lastB[N][30];
int main()
{
    string a,b;
    int n,m;
    in >> a >> b;
    n = a.length();
    m = b.length();
    for (int i = 1; i<=n; i++)
    {
        for (int j = 0; j<26; j++)
            lastA[i][j] = lastA[i-1][j];
        lastA[i][a[i-1]-'a'] = i;
    }
    for (int i = 1; i<=m; i++)
    {
        for (int j = 0; j<26; j++)
            lastB[i][j] = lastB[i-1][j];
        lastB[i][b[i-1]-'a'] = i;
    }

    for (int i = 1; i<=n; i++)
        for (int j = 1; j<=m; j++)
            if (a[i-1] == b[j-1])
            {
                dp[i][j] = 1+dp[i-1][j-1];
                for (int k = 0; k<26; k++)
                {
                    int ii = lastA[i-1][k], jj = lastB[j-1][k];
                    if (dp[i][j] == 1+dp[ii][jj])
                        nr[i][j] = (nr[i][j]+nr[ii][jj])%MOD;
                }
                if (!nr[i][j])
                    nr[i][j] = 1;
            }
            else
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
    int ans = 0;
    for (int i = 1; i<=n; i++)
        for (int j = 1; j<=m; j++)
            if (i == lastA[n][a[i-1]-'a'] && j == lastB[m][b[j-1]-'a'] && dp[i][j] == dp[n][m])
                ans = (ans+nr[i][j])%MOD;
    out << ans;
}