#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 550
#define MOD 666013

using namespace std;

char a[MAXN], b[MAXN];
int n, m;
int len[MAXN][MAXN], nr[MAXN][MAXN];

int solve()
{
    for (int i = 0; i <= n; i++)
		nr[0][i] = nr[i][0] = 1;
    for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
            if (a[i] == b[j]) {
				len[i][j] = (len[i-1][j-1] + 1) % MOD;
				nr[i][j] = nr[i-1][j-1];
            }
            else {
                if (len[i][j-1] < len[i-1][j])
					len[i][j] = len[i-1][j], nr[i][j] = nr[i-1][j];
                else if (len[i][j-1] > len[i-1][j])
                    len[i][j] = len[i][j-1], nr[i][j] = nr[i][j-1];
				else {
                    len[i][j] = len[i][j-1], nr[i][j] = nr[i][j-1];
                    if (len[i-1][j] == len[i-1][j-1])
                        nr[i][j] = (nr[i][j] + MOD + nr[i-1][j] - nr[i-1][j-1]) % MOD;
					else
						nr[i][j] = (nr[i][j] + nr[i-1][j]) % MOD;
				}
            }
		}
	return nr[n][m] % MOD;
}

int main()
{
	freopen("subsir.in", "r", stdin);
	freopen("subsir.out", "w", stdout);

	gets(a+1);
	gets(b+1);
	n = strlen(a+1);
    m = strlen(b+1);
    int rez = solve();
	printf("%d", rez);

    return 0;
}