#include <iostream>
#include <fstream>
#include <vector>
#define nl '\n'

using namespace std;

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

const int NMAX = 10, MOD = 666013;

string a, b;
int n, m, dp[NMAX][NMAX], ways[NMAX][NMAX], lastFrA[30], lastFrB[30];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fin >> a >> b;
    n = a.size();
    m = b.size();
    a = ' ' + a;
    b = ' ' + b;
    ways[0][0] = 1;
    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;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if (a[i] == b[j])
            {
                if (dp[i][j] == 1)
                    ways[i][j] = 1;
                else
                {
                    for (int k = 0; k < 26; k++)
                    {
                        int x = lastFrA[k];
                        int y = lastFrB[k];
                        if (dp[x][y]+1 == dp[i][j])
                            ways[i][j] = (ways[i][j]+ways[x][y])%MOD;
                    }
                }
            }
            lastFrB[b[j]-'a'] = j;

        }
        if (i != n)
            for (int k = 0; k < 26; k++)
                lastFrB[k] = 0;
        lastFrA[a[i]-'a'] = i;
    }
    int ans = 0;
    for (int k = 0; k < 26; k++)
    {
        int x = lastFrA[k];
        int y = lastFrB[k];
        if (dp[x][y] == dp[n][m])
            ans = (ans+ways[x][y])%MOD;
    }
    fout << ans;
    return 0;
}