#include <fstream>
#include <cstring>

#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;
    cin >> b;
    int n = strlen(a);
    int m = strlen(b);
    for(int i = 0; i <= n; ++i)
        Ans[i][0] = 1;
    for(int j = 0; j <= m; ++j)
        Ans[0][j] = 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])
                Ans[i][j] = Ans[i - 1][j];
            else
            if(D[i][j - 1] > D[i - 1][j])
                Ans[i][j] = Ans[i][j - 1];
            else{
                D[i][j] = min(D[i - 1][j], D[i][j - 1]);
                Ans[i][j] = D[i - 1][j] + D[i][j - 1];
                if(D[i - 1][j] == D[i][j - 1])
                    Ans[i][j] -= D[i - 1][j - 1];
            }
            Ans[i][j] %= Mod;
        }
    cout << Ans[n][m];
    return 0;
}