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

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

    ifstream f("subsir.in");
    ofstream g("subsir.out");

    f>>(a+1);
    f>>(b+1);

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

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

    for (int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]==b[j]){
                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;
                    }
                }
            }
        }
    }

    g<< v[n][m] % mod;
    f.close();
    g.close();

 }