#include <iostream>
#include <cstring>
#include <fstream>
 using namespace std;

 int main(){
   const int mod = 666013;
   const int MAX = 505;
    char a[MAX], b[MAX];
    int dp[MAX][MAX];
    int v[MAX][MAX];

    ifstream fin("subsir.in");
    ofstream fout("subsir.out");

    fin>>a;
    fin>>b;

    int n = strlen(a);
    int m = strlen(b);

    for(int i =0;i<=n;i++){
        v[i][0] = 1;
        dp[i][0]=0;
    }
    for(int j=0;j<=m;j++){
        v[0][j] = 1;
        dp[0][j] = 0;
    }

    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;
                v[i][j] = v[i-1][j-1];
            }else{
                if(dp[i-1][j]>dp[i][j-1]){
                    dp[i][j]=dp[i-1][j];
                    v[i][j] = v[i-1][j];
                }else if(dp[i-1][j] < dp[i][j-1]){
                    dp[i][j] = dp[i][j-1];
                    v[i][j] = v[i][j-1];
                }else{
                    dp[i][j] = dp[i-1][j];
                    v[i][j] = (v[i-1][j] + v[i][j-1] - v[i-1][j-1]) % mod;
                    if(v[i][j] < 0){
                        v[i][j] += mod;
                    }
                }
            }
        }
    }

    fout<< v[n][m] % mod;
    fin.close();
    fout.close();

 }