#include <cstdio>
#include <cstring>

#define maxN 510
#define mod 666013

using namespace std;

int nr[maxN][maxN], l[maxN][maxN];
char a[maxN], b[maxN];
int main ()
{
    freopen ("subsir.in", "r", stdin);
    freopen ("subsir.out", "w", stdout);
    int i, j, n, m;
    scanf ("%s\n%s\n", a + 1, b + 1);

    n = strlen (a + 1);
    m = strlen (b + 1);

    for (i = 0; i <= n; i++) nr[i][0] = 1;
    for (j = 0; j <= m; j++) nr[0][j] = 1;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            if (a[i] == b[j])
            {
                l[i][j] = l[i - 1][j - 1] + 1;
                l[i][j] %= mod;
                nr[i][j] = nr[i - 1][j - 1];
            }
            else if (l[i - 1][j] > l[i][j - 1])
            {
                l[i][j] = l[i - 1][j];
                nr[i][j] = nr[i - 1][j];
            }
            else if (l[i][j - 1] > l[i - 1][j])
            {
                l[i][j] = l[i][j - 1];
                nr[i][j] = nr[i][j - 1];
            }
            else if (l[i][j - 1] == l[i - 1][j])
            {
                l[i][j] = l[i][j - 1];
                nr[i][j] = (nr[i][j - 1] + nr[i - 1][j]) % mod;
                if (l[i][j - 1] == l[i - 1][j - 1])
                    nr[i][j] = (nr[i][j] - nr[i - 1][j - 1] + mod) % mod;
            }
        }
        printf ("%d\n", nr[n][m]);
        return 0;
}