// problema 1, pagina 255, Fundamentele Programarii

#include <stdio.h>
#include <cstring>
#define max(x,y) ((x>y)?(x):(y))
using namespace std;

char a[502], b[502];
long int m, n;
int nexta[502][27], nextb[502][27];
long int dp[502][502], nr[502][502];
long int lmax;
long int rez;

void Read();
void Do();
void Write();

int main()
{
    freopen("subsir.in", "r", stdin);
    freopen("subsir.out", "w", stdout);
    scanf("%s", &a);
    n = strlen(a);
    scanf("%s", &b);
    m = strlen(b);
    
    long int i, j, ii, jj, k;
    for ( i = 1; i <= n; i++ ) 
	{
	    for ( j = 0; j <26; j++ ) nexta[i][j] = -1;
	    for ( j = 1; j <= i; j++ ) nexta[i][a[j-1]-'a'] = j;
	}
    for ( i = 1; i <= m; i++ )
    {
        for ( j = 0; j < 26; j++ ) nextb[i][j] = -1;
        for ( j = 1; j <= i; j++ ) nextb[i][b[j-1] - 'a'] = j;
    }
    
    for ( i = 1; i <= n; i++ )
        for ( j = 1; j <= m; j++ )
        {
            if ( a[i-1] == b[j-1] )
            {
                dp[i][j] = dp[i-1][j-1] + 1;
                if ( dp[i][j] == 1 ) nr[i][j] = 1;
                for ( k = 0; k < 26; k++ )
                {
                    ii = nexta[i-1][k];
                    jj = nextb[j-1][k];
                    if ( ii > 0 && jj > 0 && dp[ii][jj] + 1 == dp[i][j] )
                        nr[i][j] = (nr[i][j] + nr[ii][jj]) % 666013;
                }     
            }
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
        
    lmax = dp[n][m];    
    rez = 0;
    for ( i = 1; i <= n; i++ )
        for ( j = 1; j <= m; j++ )
            if ( a[i-1] == b[j-1] && nexta[n][a[i-1]-'a'] == i && nextb[m][a[i-1]-'a'] == j && dp[i][j] == lmax )
                        rez = (rez + nr[i][j]) % 666013;     
    
    printf("%d\n", rez);
    
    return 0;
}