#include <bits/stdc++.h>
#define MOD 666013

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

pair <int, int> dp[505][505];
char s1[505], s2[505];

int main()
{
    fin>>s1>>s2;
    for(int i=0; i<strlen(s1); i++)
    {
        for(int j=0; j<strlen(s2); j++)
        {
            if(s1[i] == s2[j])
            {
                dp[i+1][j+1].first = (dp[i][j].first + 1) % MOD;
                dp[i+1][j+1].second = dp[i][j].second;
                if(!dp[i][j].second) dp[i+1][j+1].second++;
            }
            else
            {
                dp[i+1][j+1].first = max(dp[i+1][j].first, dp[i][j+1].first);
                if(dp[i+1][j].first == dp[i+1][j+1].first) dp[i+1][j+1].second = (dp[i+1][j+1].second + dp[i+1][j].second) % MOD;
                if(dp[i][j+1].first == dp[i+1][j+1].first) dp[i+1][j+1].second = (dp[i+1][j+1].second + dp[i][j+1].second) % MOD;
                if(dp[i][j].first == dp[i+1][j+1].first) dp[i+1][j+1].second = (MOD + dp[i+1][j+1].second - dp[i][j].second) % MOD;
            }
        }
    }
    fout<<dp[strlen(s1)][strlen(s2)].second<<'\n';
}