#include<fstream>
#include<cstring>
#include<iostream>
#define DN 505
#define M 666013
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
int n,m,dp1[DN][DN],dp2[DN][DN],l1[30][DN],l2[30][DN];
char a[DN],b[DN];
int main()
{
    fin.getline(a+1,DN);
    fin.getline(b+1,DN);
    n=strlen(a+1);
    m=strlen(b+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<30;j++)
            l1[j][i]=l1[j][i-1];
        l1[a[i]-'a'][i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<30;j++)
            l2[j][i]=l2[j][i-1];
        l2[b[i]-'a'][i]=i;
    }
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            if(i==0||j==0)
            {
                dp1[i][j]=0;
                dp2[i][j]=1;
                continue;
            }
            if(dp1[i-1][j]>dp1[i][j-1])
                dp1[i][j]=dp1[i-1][j];
            else
                dp1[i][j]=dp1[i][j-1];
            if(a[i]==b[j])
                if(dp1[i-1][j-1]+1>dp1[i][j])
                    dp1[i][j]=dp1[i-1][j-1]+1;
            if(dp1[i][j]==0)
            {
                dp2[i][j]=1;
                continue;
            }
            for(int h=0;h<30;h++)
                if(l1[h][i]&&l2[h][j])
                    if(dp1[l1[h][i]-1][l2[h][j]-1]==dp1[i][j]-1)
                        dp2[i][j]=(dp2[i][j]+dp2[l1[h][i]-1][l2[h][j]-1])%M;
        }
    fout<<dp2[n][m];
}