#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]=max(1,sol[i-1][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];
                    if(dp[i-1][j]==dp[i-1][j-1])
                        sol[i][j]-=sol[i-1][j-1];
                    sol[i][j]%=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;
}