#include <iostream>
#include <fstream>
#include <string>
#define MOD 666013

using namespace std;

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

string s , p;
int dp[505][505];
int ans[505][505];

int main()
{
    f>>s>>p;
    int n = s.length();
    int m = p.length();
    for(int  i = 0 ; i <= n ; ++i)
        ans[i][0] = 1;
    for(int j = 0 ; j <= m ; ++j)
        ans[0][j] = 1;
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= m ; ++j){
            if(s[i-1] == p[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
                ans[i][j] = ans[i-1][j-1];
            }
            else{
                dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
                if(dp[i-1][j] == dp[i][j-1]){
                    ans[i][j] = (ans[i-1][j] + ans[i][j-1]) % MOD;
                    if(dp[i-1][j] == dp[i-1][j-1]){
                        ans[i][j] = (ans[i][j] - ans[i-1][j-1] + MOD) % MOD;
                    }
                }
                else if(dp[i-1][j] > dp[i][j-1])
                    ans[i][j] = ans[i-1][j];
                else ans[i][j] = ans[i][j-1];
            }
        }
    }
    g<<ans[n-1][m-1];
    return 0;
}