#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_map>

#define MOD 666013

using namespace std;

ifstream cin ("subsir.in") ;
ofstream cout("subsir.out") ;

string a, b ;

int m[509][509] ;

string recur(int f, int e)
{

    if(f < 0 || e < 0)return "" ;

    if(a[f] == b[e])return recur(f - 1, e - 1) + a[f] ;
        else if(m[f - 1][e] > m[f][e - 1])return recur(f - 1, e) ;

    return recur(f, e - 1) ;

}

long long dp[509][509] ;

void scmax()
{

    for(int f = 0 ; f <= a.size() ; f ++)
        for(int e = 0 ; e <= b.size() ; e ++)
            dp[f][e] = 1 ;

    for(int f = 1 ; f <= a.size() ; f ++)
        for(int e = 1 ; e <= b.size() ; e ++)
            dp[f][e] = 0 ;

    for(int f = 1 ; f < a.size() ; f ++)
        for(int e = 1 ; e <= b.size() ; e ++)
            if(a[f] == b[e])m[f][e] = m[f - 1][e - 1] + 1, dp[f][e] = dp[f - 1][e - 1]  ;
                else
                {

                    m[f][e] = max(m[f - 1][e], m[f][e - 1]) ;

                    dp[f][e] = dp[f - 1][e] + dp[f][e - 1] ;

                    if(m[f - 1][e] == m[f][e - 1] && m[f - 1][e] == m[f - 1][e - 1])dp[f][e] -= dp[f - 1][e - 1] ;

                    dp[f][e] %= MOD ;

                }
}

int main()
{

    cin >> a >> b ;

    a = '1' + a ;
    b = '2' + b ;

    scmax() ;

    cout << dp[a.size() - 1][b.size() - 1] ;

    return 0 ;

}