#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("subsir.in");
ofstream cout("subsir.out");
const int MAX = 503, ALFA = 26, MOD = 666013;
struct cell{
    int lg, v[ALFA];
};
cell dp[MAX][MAX];
char a[MAX], b[MAX];
int main()
{
    cin >> (a + 1) >> (b + 1);
    int na = strlen(a + 1), nb = strlen(b + 1);
    for(int i = 1; i <= na; ++i)
        for(int j = 1; j <= nb; ++j)
        {
            if(a[i] == b[j]) {
                dp[i][j].lg = dp[i - 1][j - 1].lg + 1;
                if(dp[i][j].lg == 1)
                    dp[i][j].v[ a[i] - 'a' ] = 1;
                for(int k = 0; k < ALFA; ++k)
                    dp[i][j].v[ a[i] - 'a' ] = (dp[i][j].v[ a[i] - 'a' ] + dp[i - 1][j - 1].v[k]) % MOD;
            } else if(dp[i][j - 1].lg > dp[i - 1][j].lg){
                dp[i][j].lg = dp[i][j - 1].lg;
            } else {
                dp[i][j].lg = dp[i - 1][j].lg;
            }
            for(int k = 0; k < ALFA; ++k) {
                if(dp[i][j].lg == dp[i][j - 1].lg) {
                    dp[i][j].v[k] = max(dp[i][j].v[k], dp[i][j - 1].v[k]);
                }
                if(dp[i][j].lg == dp[i - 1][j].lg) {
                    dp[i][j].v[k] = max(dp[i][j].v[k], dp[i - 1][j].v[k]);
                }
            }
        }
    int ans = 0;
    for(int i = 0; i < ALFA; ++i)
        ans = (ans + dp[na][nb].v[i]) % MOD;
    cout << ans;
    return 0;
}