//Florea Toma Eduard
# include <fstream>
# include <cstring>
# include <algorithm>

# define dim 505
# define mod 666013

using namespace std;

ifstream f("subsir.in");
ofstream g("subsir.out");

int dp[ dim ][ dim ], sol[ dim ][ dim ];
char a[ dim ], b[ dim ];

int lga, lgb;

void citire()
{
    f.getline( a , dim );
    f.getline( b , dim );

    lga = strlen( a );
    lgb = strlen( b );
}

void rezolva()
{
    int i, j, lg;

    lg = max( lga, lgb );

    for ( i = 0 ; i <= lg ; ++ i )
       sol[ i ][ 0 ] = sol[ 0 ][ i ] = 1;

    for ( i = 0 ; i < lga ; ++ i )
       for ( j = 0 ; j < lgb ; ++ j )
           if ( a[ i ] == b[ j ] )
           {
               dp[ i + 1 ][ j + 1 ] = dp[ i ][ j ] + 1;
               sol[ i + 1 ][ j + 1 ] = sol[ i ][ j ];
           }
           else
           if ( dp[ i + 1 ][ j ] ==  dp[ i ][ j + 1 ] )
           {
               sol[ i + 1 ][ j + 1 ] = ( sol[ i + 1 ][ j ] + sol[ i ][ j + 1 ] ) % mod;
               dp[ i + 1 ][ j + 1 ] = dp[ i ][ j + 1 ];
               if ( dp[ i ][ j + 1 ] == dp[ i ][ j ] )
                  sol[ i + 1 ][ j + 1 ] = ( sol[ i + 1 ][ j + 1 ] + mod - sol[ i ][ j ] ) % mod;
           }
           else
           if ( dp[ i + 1 ][ j ] < dp[ i ][ j + 1 ] )
           {
               dp[ i + 1 ][ j + 1 ] = dp[ i ][ j + 1 ];
               sol[ i + 1 ][ j + 1 ] = sol[ i ][ j + 1 ];
           }
           else
           {
               dp[ i + 1 ][ j + 1 ] = dp[ i + 1 ][ j ];
               sol[ i + 1 ][ j + 1 ] = sol[ i + 1 ][ j ];
           }

     g << sol[ lga ][ lgb ];
}



int main()
{
    citire();
    rezolva();
    return 0;
}