#include <cstdio>  
using namespace std ;  
  
int main ( ) {  
  int const MODULO = 666013 ;  
  int const MAXN = 500 ;  
  int A [ MAXN ] , B [ MAXN ] , ch , lenA , lenB , lcs [ 1 + MAXN ] [ 1 + MAXN ] ,  
      count [ 1 + MAXN ] [ 1 + MAXN ] , i , j , t , u , x , y ;  
  FILE * io = fopen ( "subsir.in" , "r" ) ;  
  bool isLetter;  
  do { ch = fgetc ( io ) ; } while ( 'a' > ch || 'z' < ch );  
  A [ 0 ] = ch ; lenA = 1 ;  
  do {  
    ch = fgetc(io);  
    if ( isLetter = ( 'a' <= ch && 'z' >= ch ) ) {  
      A [ lenA ] = ch ;  
      ++ lenA ;  
    }  
  } while ( isLetter ) ;  
  do { ch = fgetc ( io ) ; } while ( 'a' > ch || 'z' < ch );  
  B [ 0 ] = ch ; lenB = 1 ;  
  do {  
    ch = fgetc ( io ) ;  
    if( isLetter = ( 'a' <= ch && 'z' >= ch ) ) {  
      B [ lenB ] = ch ;  
      ++ lenB ;  
    }  
  } while ( isLetter ) ;  
  fclose ( io );  
  for ( i = 0 ; i <= lenA; i ++ ) {  
    lcs [i] [0] = 0 ;  
  }  
  for ( i = 0 ; i <= lenB; i ++ ) {  
    lcs [0] [i] = 0 ;  
  }  
  for ( i = 1; i <= lenA; i ++ ) {  
    for ( j = 1; j <= lenB; j ++ ) {  
      if ( A [ -1 + i ] == B [ -1 + j ] ) {  
        lcs [ i ] [ j ] = 1 + lcs [ - 1 + i ] [ -1 + j ] ;  
      } else {  
        if ( lcs [ - 1 + i ] [ j ] > lcs [ i ] [ - 1 + j ] ) {  
          lcs [ i ] [ j ] = lcs [ - 1 + i ] [ j ] ;  
        } else {  
          lcs [ i ] [ j ] = lcs [ i ] [ - 1 + j ] ;  
        }  
      }  
    }  
  }  
  for ( i = 0 ; i <= lenA ; i ++ ) {  
    count [ i ] [ 0 ] = 1 ;  
  }  
  for ( j = 0 ; j <= lenB ; j ++ ) {  
    count [ 0 ] [ j ] = 1 ;  
  }  
  for ( i = 1 ; i <= lenA ; i ++ ) {  
    for ( j = 1 ; j <= lenB ; j ++ ) {  
      if ( A [ - 1 + i ] == B [ - 1 + j ] ) {  
        count [ i ] [ j ] = count [ - 1 + i ] [ - 1 + j ] ;
      } else {  
        if ( lcs [ - 1 + i ] [ j ] > lcs [ i ] [ - 1 + j ] ) {  
          count [ i ] [ j ] = count [ - 1 + i ] [ j ] ;  
        } else if ( lcs [ - 1 + i ] [ j ] < lcs [ i ] [ - 1 + j ] ) {  
          count [ i ] [ j ] = count [ i ] [ - 1 + j ] ;  
        } else {  
          if ( lcs [ - 1 + i ] [ - 1 + j ] == - 1 + lcs [ i ] [ j ] ) {  
            for ( t = - 2 + i ; t >= 0 && A [ t ] != B [ - 1 + j ] ; t -- ) ;  
            for ( u = - 2 + j ; u >= 0 && B [ u ] != A [ - 1 + i ] ; u -- ) ;  
            count [ i ] [ j ] = 0 ;  
            if ( 0 < t && lcs [ - 1 + i ] [ - 1 + j ] == lcs [ t ] [ - 1 + j ] ) {  
              count [ i ] [ j ] += count [ t ] [ - 1 + j ] ;  
              count [ i ] [ j ] %= MODULO ;  
            }  
            if ( 0 < u && lcs [ - 1 + i ] [ - 1 + j ] == lcs [ - 1 + i ] [ u ] ) {  
              count [ i ] [ j ] += count [ - 1 + i ] [ u ] ;  
              count [ i ] [ j ] %= MODULO ;  
            }  
          } else {  
            for ( x = - 2 + i ; x >= 0 && A [ x ] != A [ - 1 + i ] ; x -- ) ;  
            for ( y = - 2 + j ; y >= 0 && B [ y ] != B [ - 1 + j ] ; y -- ) ;  
            for ( t = - 2 + i ; t >= 0 && A [ t ] != B [ - 1 + j ] ; t -- ) ;  
            for ( u = - 2 + j ; u >= 0 && B [ u ] != A [ - 1 + i ] ; u -- ) ;  
            count [ i ] [ j ] = count [ - 1 + i ] [ - 1 + j ] ;  
            if ( ( ( 0 > x ) || ( 0 <= x && lcs [ 1 + x ] [ - 1 + j ] < lcs [ i ] [ - 1 + j ] ) ) &&  
                 ( 0 <= u && -1 + lcs [ - 1 + i ] [ - 1 + j ] == lcs [ - 1 + i ] [ u ] ) ) {  
              count [ i ] [ j ] += count [ - 1 + i ] [ u ] ;  
              count [ i ] [ j ] %= MODULO ;  
            }  
            if ( ( ( 0 > y ) || ( 0 <= y && lcs [ - 1 + i ] [ 1 + y ] < lcs [ - 1 + i ] [ j ] ) ) &&  
                 ( 0 <= t && -1 + lcs [ - 1 + i ] [ - 1 + j ] == lcs [ t ] [ - 1 + j ] ) ) {  
              count [ i ] [ j ] += count [ t ] [ - 1 + j ] ;  
              count [ i ] [ j ] %= MODULO ;  
            }  
          }  
        }  
      }  
    }  
  }  
  io = fopen ( "subsir.out" , "w" ) ;  
  fprintf ( io , "%d\n" , count [ lenA ] [ lenB ] ) ;  
  fclose ( io ) ;  
  return 0;  
}