#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
#define MOD 666013
int l[1010][1010], n ,m, nr[1010][1010];
string a, b;
pii crd[1010][1010][26];


ifstream fin("subsir.in"); ofstream fout("subsir.out");
#define cin fin
#define cout fout


int32_t main(){
INIT
cin>>a>>b;
n=a.length(); m=b.length();
int res=0;
for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
        for(char c='a'; c<='z'; c++){
            crd[i][j][(int)(c-'a')]=crd[i][j][(int)(c-'a')];
            if( crd[i][j-1][(int)(c-'a')].ft>crd[i][j][(int)(c-'a')].ft || (crd[i][j-1][(int)(c-'a')].ft==crd[i][j][(int)(c-'a')].ft && crd[i][j-1][(int)(c-'a')].sc>crd[i][j][(int)(c-'a')].sc  )  ){
                crd[i][j][(int)(c-'a')]=crd[i][j-1][(int)(c-'a')];
            }
            if( crd[i-1][j-1][(int)(c-'a')].ft>crd[i][j][(int)(c-'a')].ft || (crd[i-1][j-1][(int)(c-'a')].ft==crd[i][j][(int)(c-'a')].ft && crd[i-1][j-1][(int)(c-'a')].sc>crd[i][j][(int)(c-'a')].sc  )  ){
                crd[i][j][(int)(c-'a')]=crd[i-1][j-1][(int)(c-'a')];
            }
        }
            if(a[i-1]==b[j-1]){

                l[i][j]=l[i-1][j-1]+1;
                for(char c='a'; c<='z'; c++){
                    if(l[crd[i][j][c-'a'].ft ][crd[i][j][c-'a'].sc ]==(l[i][j]-1) ){
                        nr[i][j]+=nr[crd[i][j][c-'a'].ft ][crd[i][j][c-'a'].sc ];
                    }
                }
                nr[i][j]=max(nr[i][j],(int) 1);
                nr[i][j]%=MOD;

                crd[i][j][a[i-1]-'a' ]=mp(i, j);
            }
            if(l[i-1][j]>l[i][j]){
                l[i][j]=l[i-1][j]; nr[i][j]=nr[i-1][j];
            }

            if(l[i][j-1]>l[i][j]){
                l[i][j]=l[i][j-1]; nr[i][j]=nr[i][j-1];
            }
            if(l[i-1][j-1]>l[i][j]){
                l[i][j]=l[i][j]-1; nr[i][j]=nr[i-1][j-1];
            }
    }
}


int lm=l[n][m];

cout<<nr[n][m];



return 0;
}