#include <fstream>
using namespace std;

ifstream cin("subsir.in");
ofstream cout("subsir.out");

int dp[501][501];
int cnt[501][501];
#define MOD 666013
int main()
{
    string a,b;
    int i,j,rasp=0,max1=0;
    cin>>a>>b;
    a='$'+a;
    b='@'+b;
    cnt[0][0]=1;
    for(i=1;i<b.size();i++) cnt[0][i]=1;
    for(i=1;i<a.size();i++) cnt[i][0]=1;
    for(i=1;i<a.size();i++){
        for(j=1;j<b.size();j++){
            if(a[i]==b[j]){
                dp[i][j]=dp[i-1][j-1]+1;
                cnt[i][j]=cnt[i-1][j-1];
            }else{
                if(dp[i-1][j]==dp[i][j-1]){
                    dp[i][j]=dp[i-1][j];
                    cnt[i][j]=cnt[i-1][j]+cnt[i][j-1];cnt[i][j]%=MOD;
                    if(dp[i-1][j-01]==dp[i][j-1]){
                        cnt[i][j]=(MOD+cnt[i][j]-cnt[i-1][j-1])%MOD;
                    }
                }else if(dp[i-1][j]>dp[i][j-1]){
                    dp[i][j]=dp[i-1][j];
                    cnt[i][j]=cnt[i-1][j];
                }else{
                    dp[i][j]=dp[i][j-1];
                    cnt[i][j]=cnt[i][j-1];
                }
            }
        }
    }
    cout<<cnt[a.size()-1][b.size()-1];
    return 0;
}