#include <fstream>
#include <cstring>
#include <algorithm>

#define NMAX 507
#define Mod 666013

using namespace std;

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

char a[NMAX], b[NMAX];
int D[NMAX][NMAX], Ans[NMAX][NMAX];

int main(){
    cin >> a + 1;
    cin >> b + 1;
    a[0] = b[0] = 1;
    int n = strlen(a + 1);
    int m = strlen(b + 1);
    for(int i = 0; i <= max(n, m); ++i)
        Ans[i][0] = Ans[0][i] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j){
            if(a[i] == b[j]){
                D[i][j] = 1 + D[i - 1][j - 1];
                Ans[i][j] = Ans[i - 1][j - 1];
            }
            else
            if(D[i - 1][j] > D[i][j - 1]){
                D[i][j] = D[i - 1][j];
                Ans[i][j] = Ans[i - 1][j];
            }
            else
            if(D[i][j - 1] > D[i - 1][j]){
                D[i][j] = D[i][j - 1];
                Ans[i][j] = Ans[i][j - 1];
            }
            else{
                D[i][j] = D[i - 1][j];
                Ans[i][j] = Ans[i - 1][j] + Ans[i][j - 1];
                Ans[i][j] %= Mod;
                if(D[i][j] == D[i - 1][j - 1])
                    Ans[i][j] -= Ans[i - 1][j - 1];
                if(Ans[i][j] < 0)
                    Ans[i][j] += Mod;
            }
            Ans[i][j] %= Mod;
        }
    cout << Ans[n][m];
    return 0;
}