/**
 ____ ____ ____ ____ ____
||O |||M |||E |||G |||A ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|


Se spune ca sunt vise
Si ca nu pot fi atinse
Sunt primele ce le vezi cand becurile-s stinse
Dar si cand is aprinse
Cand te trezesti cu ele-n gand
Si le vizualizezi din nou rand pe rand
Se spune ca visezi daca stai si-ti imaginezi
Ca esti altfel decat ceilalti, dar nu tre sa crezi
Continua sa lupti altfel imi vei da dreptate
Vei bea pe spate cu gandul la vise spulberate
    - "Vise" - Nane -

**/
#include<bits/stdc++.h>
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
string a,b;
int dp[505][505],dp2[505][505];
const int mod=666013;
int main(){
    fin>>a>>b;
    a.insert(0,"0");
    b.insert(0,"0");
    for(int i=0;i<=500;i++)dp2[i][0]=dp2[0][i]=1;
    for(int i=1;i<a.size();i++){
        for(int j=1;j<b.size();j++){
            if(a[i]==b[j]){
                dp[i][j]=1+dp[i-1][j-1];
                dp2[i][j]=dp2[i-1][j-1];
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                if(dp[i-1][j]==dp[i][j-1]){
                    dp2[i][j]=dp2[i-1][j]+dp2[i][j-1];
                    if(dp[i-1][j]==dp[i-1][j-1])dp2[i][j]-=dp2[i-1][j-1];
                }
                else if(dp[i-1][j]>dp[i][j-1])dp2[i][j]=dp2[i-1][j];
                else dp2[i][j]=dp2[i][j-1];
            }
            dp2[i][j]%=mod;
        }
    }
    fout<<dp2[a.size()-1][b.size()-1];
    return 0;
}