#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];

void idk(){
    for(int i = 0; i < 1041; i++){
        emag[i][0] = emag[0][i] = 1;
    }
}

int main()
{
    idk();
    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-1][y-1];
            }
            emag[x][y] = z + amic;
            emag[x][y] %= amic;
        }
    }
//    for(int x = 1; x <= n; x++){
//        for(int y = 1; y <= m; y++){
//            cout << big_brain[x][y] << " ";
//        }
//        cout << "\n";
//    }
//        cout << "\n";
//    for(int x = 1; x <= n; x++){
//        for(int y = 1; y <= m; y++){
//            cout << emag[x][y] << " ";
//        }
//        cout << "\n";
//    }
    fout << emag[n][m];
    return 0;
}