#include <fstream>
#include <cstring>
#define mod 666013
using namespace std;
ifstream cin("subsir.in");
ofstream cout("subsir.out");
int n,m,dp[505][505],sol[505][505];
char a[505],b[505];
int main()
{
    cin>>a>>b;
    n=strlen(a);
    m=strlen(b);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(a[i-1]==b[j-1]){
                dp[i][j]=dp[i-1][j-1]+1,sol[i][j]=sol[i-1][j-1];
                if(dp[i][j]==1)
                    sol[i][j]=1;
            }else{
                if(dp[i-1][j]==dp[i][j-1])
                    dp[i][j]=dp[i-1][j],sol[i][j]=(sol[i-1][j]+sol[i][j-1])%mod;
                else if(dp[i-1][j]>dp[i][j-1])
                    dp[i][j]=dp[i-1][j],sol[i][j]=sol[i-1][j];
                else
                    dp[i][j]=dp[i][j-1],sol[i][j]=sol[i][j-1];
            }
        }
    cout<<sol[n][m];
    return 0;
}