#include <iostream>
#include <fstream>
#include <cstring>
#define MOD 666013
using namespace std;
ifstream f ("subsir.in");
ofstream g ("subsir.out");
char s1[501],s2[501];
int dp[501][501],rasp[501][501];
int l1,l2;
int main()
{
    f >> s1+1 >> s2+1;
    l1 = strlen(s1+1);
    l2 = strlen(s2+1);
    /// initializam matricea de rasp cu 0 pe margini deoarece cu fiecare indice i = 0 si j = 0 avem un sir de lungime maxima
    for(int i = 0;i<=l1;i++)
        rasp[i][0] = 1;
    for(int i = 0;i<=l2;i++)
        rasp[0][i] = 1;
    /// facem algoritmul clasic de cel mai lung subsir comun dar construim si o matrice de raspunsuri in paralel
    for(int i = 1;i<=l1;i++)
    {
        for(int j = 1;j<=l2;j++)
        {
            if(s1[i] == s2[j])
            {

                dp[i][j] = dp[i-1][j-1]+1;
                /// daca literele sunt egale luam raspunsul de pe i-1 si j-1
                rasp[i][j] = rasp[i-1][j-1];
            }
            else
            {
                dp[i][j]= max(dp[i-1][j],dp[i][j-1]);
                /// in caz ca ambele locuri au subiruri de lungime egala le adunam pe ambele
                if(dp[i-1][j] == dp[i][j-1])
                {
                    rasp[i][j] = (rasp[i][j-1]+rasp[i-1][j])%MOD;
                    ///dar in caz ca sunt 3 egale inseamna cu una dintre cele 2 egale de mai sus a provenit din cea din colt
                    /// prin formula max(dp[i-1][j],dp[i][j-1]) asa ca o scadem
                    if(dp[i-1][j] == dp[i-1][j-1])
                    {
                        rasp[i][j] = (rasp[i][j]-rasp[i-1][j-1]+MOD)%MOD;
                    }
                }
                /// in alte cazuri luam subsirul cu lungimea maxima
                else
                    if(dp[i-1][j]>dp[i][j-1])
                        rasp[i][j] = rasp[i-1][j];
                else
                    rasp[i][j] = rasp[i][j-1];
            }

        }
    }
    g << rasp[l1][l2];
}