#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 ] ,  
      lastA [ 1 + MAXN ] [ 'z' - 'a' + 1 ] , lastB [ 1 + MAXN ] [ 'z' - 'a' + 1 ] ,  
      count [ 1 + MAXN ] [ 1 + MAXN ] , i , j , k, ii, jj, ans ;  
  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 ( j = 0 ; j <= 'z' - 'a' ; j ++ ) {  
    lastA [ 0 ] [ j ] = - 1 ;  
    lastB [ 0 ] [ j ] = - 1 ;  
  }  
  for ( i = 1 ; i <= lenA ; i ++ ) {  
    for ( j = 0 ; j <= 'z' - 'a' ; j ++ ) {  
      lastA [ i ] [ j ] = lastA [ 0 ] [ j ] ;  
      lastA [ 0 ] [ A [ - 1 + i ] - 'a' ] = i ;  
    }  
  }  
  for ( i = 1 ; i <= lenB ; i ++ ) {  
    for ( j = 0 ; j <= 'z' - 'a' ; j ++ ) {  
      lastB [ i ] [ j ] = lastB [ 0 ] [ j ] ;  
      lastB [ 0 ] [ B [ - 1 + i ] - 'a' ] = i ;  
    }  
  }  
  for ( i = 1 ; i <= lenA ; i ++ ) {
    for ( j = 1 ; j <= lenB ; j ++ ) {  
      count [ i ] [ j ] = 0 ;  
      if ( A [ - 1 + i ] == B [ - 1 + j ] ) {  
         if ( 1 == lcs [ i ] [ j ] ) {  
           count [ i ] [ j ] = 1 ;  
         } else {  
          for ( k = 0 ; k <= 'z' - 'a' ; k ++ ) {  
            ii = lastA [ i ] [ k ] ; jj = lastB [ j ] [ k ] ;  
            if( - 1 != ii && - 1 != jj && lcs [ ii ] [ jj ] + 1 == lcs [ i ] [ j ] ) {  
              count [ i ] [ j ] += count [ ii ] [ jj ] ;  
              count [ i ] [ j ] %= MODULO ;  
            }  
          }  
        }  
      }  
    }  
  }  
  lastA [ lenA ] [ A [ - 1 + lenA ] - 'a' ] = lenA ;  
  lastB [ lenB ] [ B [ - 1 + lenB ] - 'a' ] = lenB ;  
  ans = 0 ;  
  for ( k = 0 ; k <= 'z' - 'a' ; k ++ ) {  
    ii = lastA [ lenA ] [ k ] ; jj = lastB [ lenB ] [ k ] ;  
    if ( - 1 != ii && - 1 != jj && lcs [ ii ] [ jj ] == lcs [ lenA ] [ lenB ] ) {
      ans += count [ ii ] [ jj ] ;  
      ans %= MODULO ;  
    }
  }  
  io = fopen ( "subsir.out" , "w" ) ;  
  fprintf ( io , "%d\n" , ans ) ;  
  fclose ( io ) ;  
  return 0;  
}