#include <fstream>
#include <iostream>

using namespace std;

const int MAX = 505;
const int ALFA = 26;
const int REST = 666013;

int N, M, ans;
int dp[MAX][MAX], cnt[MAX][MAX], LastA[MAX][ALFA], LastB[MAX][ALFA];
string A, B;

void citire() {
    ifstream in("subsir.in");
    in >> A >> B;
    in.close();
}

inline int MOD(int val) {
    if(val >= REST) return val - REST;
    return val;
}

void solve() {
    N = A.length(), M = B.length();
    A = " " + A; B = " " + B;
    for(int i = 1; i <= N; i++) 
        for(int j = 1; j <= M; j++)
            if(A[i] == B[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if(dp[i][j] == 1) 
                    cnt[i][j] = 1;
            }
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    for(int i = 1; i <= N; i++) 
        for(char c = 'a'; c <= 'z'; c++)
            LastA[i][ c - 'a' ] = (A[i] == c ? i : LastA[i - 1][ c - 'a' ]);
    for(int i = 1; i <= M; i++)
        for(char c = 'a'; c <= 'z'; c++)
            LastB[i][ c - 'a' ] = (B[i] == c ? i : LastB[i - 1][ c - 'a' ]);
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            if(A[i] == B[j]) {
                for(char c = 'a'; c <= 'z'; c++) {
                    int A_poz = LastA[i - 1][ c - 'a' ], B_poz = LastB[j - 1][ c - 'a' ];
                    if(dp[A_poz][B_poz] + 1 == dp[i][j]) 
                        cnt[i][j] = MOD(cnt[i][j] + cnt[A_poz][B_poz]);
                }
                if(dp[N][M] == dp[i][j] && i == LastA[ N ][ A[i] - 'a' ] && j == LastB[ M ][ B[j] - 'a' ]) 
                    ans = MOD(ans + cnt[i][j]);
            }
}

void afisare() {
    ofstream out("subsir.out");
    out << ans << "\n";
    out.close();
}

int main() {
    citire();
    solve();
    afisare();
}