#include <fstream>
#include <cstring>
 
using namespace std;
char s1[600];
char s2[600];
int sir[600][600];
int Nr[600][600];

void read()
{
    ifstream f("subsir.in");
    f.getline(s1+1,599);
    f.getline(s2+1,599);
}
 
void solve1()
{
    int x=strlen(s1+1);
    int y=strlen(s2+1);
    for(int i = 1; i <= x; ++i) {
        for(int j = 1; j <= y; ++j) {
            if(s1[i] == s2[j]) {
                sir[i][j] = sir[i-1][j-1] + 1;
            } else {
                sir[i][j] = max(sir[i-1][j], sir[i][j-1]);
            }
        }
    }
}
 
void solve2()
{
    ofstream g("subsir.out");
 
    int x=strlen(s1+1);
    int y=strlen(s2+1);
    for(int i = 1; i <= x; ++i) {
        for(int j = 1; j <= y; ++j) {
 
            if( i == 1 || j == 1) {
                Nr[i][j] = 1;
                continue;
            }
            Nr[i][j]=0;
            if (s1[i] == s2[j]) {
                Nr[i][j] = Nr[i-1][j-1];
            } else {
                if(sir[i][j] == sir[i-1][j]) {
                    Nr[i][j] += Nr[i-1][j];
                }
                if(sir[i][j] == sir[i][j-1]) {
                    Nr[i][j] += Nr[i][j-1];
                }
                if(sir[i][j] == sir[i-1][j-1]) {
                    Nr[i][j] = Nr[i][j] + 666013 - Nr[i-1][j-1]
                };
            }
            Nr[i][j]= Nr[i][j] % 666013;
        }
    }
    g << Nr[x][y] << endl;
}
 
int main()
{
    read();
    solve1();
    solve2();
    return 0;
}