#include <bits/stdc++.h>
#define N 505
#define W 666013

using namespace std;

int n, m, d[N][N], nr[N][N];
char a[N], b[N];

int main()
{
    ifstream cin ("subsir.in");
    ofstream cout ("subsir.out");

    int i, j;
    cin.getline(a + 1, 501);
    cin.getline(b + 1, 501);
    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])
            {
                d[i][j] = 1 + d[i - 1][j - 1];
                nr[i][j] = nr[i - 1][j - 1];
            }
            else
            {
                d[i][j] = max(d[i][j - 1], d[i - 1][j]);
                
                if (d[i - 1][j] == d[i][j - 1]) 
                {
                    if (d[i - 1][j] == d[i - 1][j - 1])
                        nr[i][j] = (nr[i][j - 1] + nr[i - 1][j] - nr[i - 1][j - 1] + W) % W;
                    else
                        nr[i][j] = (nr[i - 1][j] + nr[i][j - 1]) % W;
                }
                else if (d[i][j - 1] > d[i - 1][j])
                    nr[i][j] = nr[i][j - 1];
                else
                    nr[i][j] = nr[i - 1][j];
            }
        
    cout << nr[n][m];
    return 0;
}