#include <iostream>
#include <fstream>
using namespace std;
const int mod=666013;
struct state
{
    int b,m;
}dp[505][505],ans;
int lst[2][505][30];
string a[2];
int n,m,i,j,k;
void prp(state &unu,state doi)
{
    if(doi.b+1>unu.b)
        unu.b=doi.b+1,unu.m=0;
    if(doi.b+1==unu.b)
    {
        unu.m+=doi.m;
        if(unu.m>=mod)
            unu.m-=mod;
    }
}
int main()
{
    ifstream f("subsir.in");
    ofstream g("subsir.out");
    f>>a[0];
    f>>a[1];
    n=a[0].size();m=a[1].size();
    for(i=0;i<2;i++)
    {
        for(j=1;j<=a[i].size();j++)
      {
        for(k=0;k<26;k++)
            lst[i][j+1][k]=lst[i][j][k];
        lst[i][j+1][a[i][j-1]-'a']=j;
      }
      for(k=0;k<26;k++)
        lst[i][a[i].size()+1][k]=lst[i][a[i].size()][k];
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
    {
        if(a[0][i-1]==a[1][j-1])
        {
            dp[i][j].b=dp[i][j].m=1;
            for(k=0;k<26;k++)
                if(lst[0][i][k]&&lst[1][j][k])
                    prp(dp[i][j],dp[lst[0][i][k]][lst[1][j][k]]);
        }
    }
    for(k=0;k<26;k++)
        prp(ans,dp[lst[0][n+1][k]][lst[1][m+1][k]]);
    g<<ans.m;
    return 0;
}