//oftica si durere in suflet
#include <fstream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
//d[i][j][k] = cate subsiruri comune si distincte
//folosesc prefixul [1, i] din primul sir
//folosesc prefixul [1, j] din al doilea sir
//si se termina pe pozitia a[i] == b[j]
//si au lungimea k
//d[i][j][k] = daca a[i] == b[j],
//
const int MOD = 666013;
const int NMAX = 500;
const int CHR = 256;
int d[NMAX + 1][NMAX + 1];
int d2[NMAX + 1][NMAX + 1];
int last[NMAX + 1][2];
int fr[CHR];
//pentru un d[i][j][k] se aduna cu
//d[[last[i], i - 1]][[last[j], j - 1]][k - 1]
int aib[NMAX + 3][NMAX + 3][NMAX + 1];
int n, m;
void update(int a, int b, int k, int val)
{
int i, j;
for (i = a; i <= n + 1; i += i & -i)
for (j = b; j <= m + 1; j += j & -j)
aib[i][j][k] = (aib[i][j][k] + val) % MOD;
}
int query(int a, int b, int k)
{
int i, j;
int ans = 0;
for (i = a; i >= 1; i -= i & -i)
for (j = b; j >= 1; j -= j & -j)
ans = (ans + aib[i][j][k]) % MOD;
return ans;
}
int sum(int i1, int i2, int j1, int j2, int k)
{
int ans = query(i2, j2, k);
if (i1 - 1 >= 0 and j1 - 1 >= 0)
ans = (ans + query(i1 - 1, j1 - 1, k)) % MOD;
if (j1 - 1 >= 0)
ans = (ans - query(i2, j1 - 1, k) + MOD) % MOD;
if (i1 - 1 >= 0)
ans = (ans - query(i1 - 1, j2, k) + MOD) % MOD;
return ans;
}
signed main()
{
ifstream cin("subsir.in");
ofstream cout("subsir.out");
int i, j, k;
string a, b;
cin >> a >> b;
n = a.size();
m = b.size();
a = "!" + a;//scuze Francu
b = "!" + b;
for (i = 1; i <= n; i++)
{
last[i][0] = fr[a[i]];
fr[a[i]] = i;
}
for (i = 'a'; i <= 'z'; i++)
fr[i] = 0;
for (i = 1; i <= m; i++)
{
last[i][1] = fr[b[i]];
fr[b[i]] = i;
}
update(1, 1, 0, 1);
int i1 = 0, j1 = 0;
int len = 0;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
d2[i][j] = max(d2[i - 1][j], d2[i][j - 1]);
if (a[i] == b[j])
{
d2[i][j] = max(d2[i][j], d2[i - 1][j - 1] + 1);
//d[i][j] = sum(last[i][0], i - 1, last[j][1], j - 1, d2[i][j] - 1);
d[i][j] = sum(last[i][0] + 1, i, last[j][1] + 1, j, d2[i][j] - 1);
//update(i, j, d2[i][j], d[i][j]);
update(i + 1, j + 1, d2[i][j], d[i][j]);
}
}
}
int ans = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
if (a[i] == b[j] and d2[i][j] == d2[n][m])
ans = (ans + d[i][j]) % MOD;
cout << ans;
}