#include <cstdio>
#include <string>

const int MAX_N = 512;
const int MOD = 666013;

char sir1[MAX_N], sir2[MAX_N];
int lung[MAX_N][MAX_N], rez[MAX_N][MAX_N];

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

    fgets(sir1 + 1, MAX_N, stdin);
    fgets(sir2 + 1, MAX_N, stdin);

    int N = strlen( sir1 + 1 ) - 1;
    int M = strlen( sir2 + 1 ) - 1;

    for (int i = 0; i <= N || i <= M; ++i)
        (i <= N ? rez[ i ][0] = 1 : 0), (i <= M ? rez[ 0 ][ i ] = 1 : 0) ;

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            if (sir1[ i ] == sir2[ j ])
            {
                lung[ i ][ j ] = lung[i - 1][j - 1] + 1;
                rez[ i ][ j ] = rez[i - 1][j - 1];
            }
            else
                if (lung[i - 1][ j ] == lung[ i ][j - 1])
                {
                    lung[ i ][ j ] = lung[i - 1][ j ];
                    rez[ i ][ j ] = rez[i - 1][ j ] + rez[ i ][j - 1], rez[ i ][ j ] %= MOD;

                    if (lung[i - 1][j - 1] == lung[i - 1][ j ])
                        rez[ i ][ j ] -= rez[i - 1][j - 1], rez[ i ][ j ] += MOD, rez[ i ][ j ] %= MOD;
                }
                else
                    if (lung[i - 1][ j ] > lung[ i ][j - 1])
                    {
                        lung[ i ][ j ] = lung[i - 1][ j ];
                        rez[ i ][ j ] = rez[i - 1][ j ];
                    }
                    else
                        if (lung[i - 1][ j ] < lung[ i ][j - 1])
                        {
                            lung[ i ][ j ] = lung[ i ][j - 1];
                            rez[ i ][ j ] = rez[ i ][j - 1];
                        }

    printf("%d", rez[ N ][ M ]);

    return 0;
}