#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

ifstream is("subsir.in");
ofstream os("subsir.out");

char s1[502];
char s2[502];
vector <pair<int,int> > v;

#define s1 (s1+1)
#define s2 (s2+1)

int dp[502][502];

int main()
{
    is >> s1 >> s2;
    int n = strlen(s1);
    int m = strlen(s2);
    for ( int i = -1; i < n; ++i )
        for ( int j = -1; j < m; ++j )
        {
            if ( i == -1 )
                dp[i+1][j+1] = 0;
            if ( j == -1 )
                dp[i+1][j+1] = 0;
            if ( i != -1 && j != -1 )
            {
                if ( s1[i] != s2[j] )
                    dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
                else
                {
                    dp[i+1][j+1] = dp[i][j] + 1;
                    v.push_back(make_pair((i+1),(j+1)));
                }

            }
        }
    int x,y;
    int cnt(0);
    for ( int i = 0; i < v.size(); ++i )
    {
        if ( dp[v[i].first][v[i].second] == dp[n][m] )
        {
            if ( dp[v[i].first-1][v[i].second] == dp[n][m]-1 )
                if ( dp[v[i].first][v[i].second-1] == dp[n][m]-1 )
                cnt++;
        }
    }
    os << cnt%666013;

    return 0;
}