//Cel mai lung subsir comun

#include <iostream>
#include <fstream>
#include <string>

int main()
{
    std::ifstream in("subsir.in");
    std::ofstream out("subsir.out");

    std::string sir_1;
    std::string sir_2;
    std::getline(in, sir_1);
    std::getline(in, sir_2);

    long long s1_size = sir_1.size();
    long long s2_size = sir_2.size();
    long long max_length = 0;
    long long start = 0;
    long long fin = 0;
    long long count_max = 0;
    int DP_table[s1_size + 1][s2_size + 1] = {};
    for(int i = 1; i <= s1_size; ++i){
        for(int j = 1; j <= s2_size; ++j){
            if(sir_1[i - 1] == sir_2[j - 1]){
                DP_table[i][j] = DP_table[i - 1][j - 1] + 1;
                if(DP_table[i][j] == max_length){
                    ++count_max;
                }
                if(DP_table[i][j] > max_length){
                    max_length = DP_table[i][j];
                    start = i - max_length;
                    fin = i - 1;
                    count_max = 1;
                }
            }
        }
    }

    //for(int i = start; i <= fin; ++i){
    //    std::cout << sir_1[i];
    //}

    out << count_max % 666013;
    return 0;
}