#include <bits/stdc++.h>
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
string a,b;
int n,m,mx,d[505][505],s[505][505],cnt;

int main(){
 fin>>a;
 fin>>b;
 n=a.size();
 m=b.size();
 a="0"+a;
 b="0"+b;
 for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(a[i]==b[j]){
            d[i][j]=d[i-1][j-1]+1;
            s[i][j]=max(s[i-1][j-1],1);
        }
        else if(d[i-1][j]==d[i][j-1]){
            s[i][j]=s[i-1][j]+s[i][j-1];
            if(d[i-1][j]==d[i][j-1])s[i][j]-=(s[i-1][j-1]-666013);
        }
        else{
            if(d[i-1][j]>d[i][j-1]){
                s[i][j]=s[i-1][j];
            }
            else s[i][j]=s[i][j-1];
        }
        s[i][j]%=666013;
        d[i][j]=max(d[i-1][j],d[i][j-1]);
    }
 }
 fout<<s[n][m];
}