#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;

const int N = 502, Sigma = 'z' - 'a' + 1, mod = 666013;

char sirA[N], sirB[N];
int best[N][N], count[N][N], prevA[N][Sigma], prevB[N][Sigma];

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

int calc(int i, int j){
    int ans = (best[i][j] == 1);
    for (int k = 0 ; k < Sigma ; k++)
        if ( best[ prevA[i][k] ][ prevB[j][k] ] + 1 == best[i][j] )
            ans = (ans + count[ prevA[i][k] ][ prevB[j][k] ]) % mod;
    return ans;
}

void generatePrev(char sir[], int prev[][Sigma]){
    for (int i = 1 ; sir[i] ; i++)
        prev[i + 1][ sir[i] - 'a' ] = i;

    for (int i = 1 ; sir[i] ; i++)
        for (int k = 0 ; k < Sigma ; k++)
            if (prev[i][k] == 0)
                prev[i][k] = prev[i - 1][k];
}

int main(){
    in >> (sirA + 1) >> (sirB + 1);

    strcat(sirA + 1, "a");
    strcat(sirB + 1, "a");

    generatePrev(sirA, prevA);
    generatePrev(sirB, prevB);

    ///longest common subsequence
    for (int i = 1 ; sirA[i] ; i++)
        for (int j = 1 ; sirB[j] ; j++)
            if ( sirA[i] != sirB[j] )
                best[i][j] = max(best[i - 1][j], best[i][j - 1]);
            else
                best[i][j] = 1 + best[i - 1][j - 1];

    ///unique common subsequence
    for (int i = 1 ; sirA[i] ; i++){
        for (int j = 1 ; sirB[j] ; j++){
            if ( sirA[i] == sirB[j] )
                count[i][j] = calc(i, j);
            //cout << count[i][j] << ' ';
        }
        //cout << '\n';
    }

    out << count[ strlen(sirA + 1) ][ strlen(sirB + 1) ] << '\n';

    return 0;
}