#include <fstream>
#include <iostream>
#include <cstring>
#define MOD 666013
 
using namespace std;
 
ifstream f("subsir.in");
ofstream g("subsir.out");
 
pair <int, int> dp[505][505];
char s1[505], s2[505];
 
int main()
{
    f >> 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;
                        }
                    //cout << dp[i+1][j+1].second << ' ';
                }
            //cout << '\n';
        }
    g << dp[strlen(s1)][strlen(s2)].second << '\n';
    return 0;
}