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

using namespace std;

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

string sir1 , sir2 ;
int dp[N][N] , lg[N][N] ;

int main()
{
    int i , j ;
    fin >> sir1 ;
    fin >> sir2 ;
    sir1 = '#'+sir1 ;
    sir2 = '#'+sir2;
    for ( i = 1 ; i < sir1.size() ; i++ )
    {
        for ( j = 1 ; j < sir2.size() ; j++ )
        {
            if ( sir1[i] == sir2[j] )
            {
                lg[i][j] = lg[i-1][j-1]+1 ;
                if ( lg[i][j] == 1 )
                    dp[i][j] = 1 ;
                else
                    dp[i][j] = dp[i-1][j-1] ;
            }
            else
            {
                lg[i][j] = max(lg[i-1][j],lg[i][j-1]) ;
                if ( lg[i][j] == lg[i-1][j] )
                    dp[i][j] = dp[i][j] + dp[i-1][j] ;
                if ( lg[i][j] == lg[i][j-1] )
                    dp[i][j] = dp[i][j] + dp[i][j-1] ;
                if ( lg[i][j] == lg[i-1][j-1] && lg[i-1][j] == lg[i][j-1] )
                    dp[i][j] = dp[i][j] - dp[i-1][j-1] ;
                dp[i][j] = (dp[i][j]+MOD)%MOD ;
            }
        }
    }
    fout << dp[sir1.size()-1][sir2.size()-1] ;
}