#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>

using namespace std;

ifstream fin("subsir.in");
ofstream fout("subsir.out");

const int amic = 666013;

int n, m;
char ny[1041], my[1041];
int big_brain[1041][1041], emag[1041][1041];

int main()
{
    fin >> ny >> my;
    n = strlen(ny), m = strlen(my);

    for(int x = 1; x <= n; x++){
        for(int y = 1; y <= m; y++){
            int d;
            if(ny[x-1] == my[y-1]){
                d = big_brain[x-1][y-1]+1;
            }else{
                d = max(big_brain[x-1][y], big_brain[x][y-1]);
            }
            big_brain[x][y] = d;

            int z = +(big_brain[x-1][y]==big_brain[x][y])*emag[x-1][y]
                    +(big_brain[x][y-1]==big_brain[x][y])*emag[x][y-1]
                    -(big_brain[x-1][y-1]==big_brain[x][y])*emag[x-1][y-1];
            if(ny[x-1] == my[y-1]){
                z++;
            }
            emag[x][y] = z;
            emag[x][y] %= amic;
        }
    }
    fout << emag[n][m];
    return 0;
}