#include<fstream>
#include<cstring>
#include<iostream>
#define DN 605
#define M 666013
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");
int n,m,dp1[DN][DN],dp2[DN][DN],l1[35][DN],l2[35][DN],p1,p2;
char a[DN],b[DN];
int main()
{
    fin>>a+1>>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<26;h++)
                if(l1[h][i]>0&&l2[h][j]>0)
                {
                    p1=l1[h][i]-1;
                    p2=l2[h][j]-1;
                    if(dp1[p1][p2]==dp1[i][j]-1)
                        dp2[i][j]=(dp2[i][j]+dp2[p1][p2])%M;
                }
        }
    if(dp1[n][m]==0)
        dp2[n][m]=0;
    fout<<dp2[n][m];
}