#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("subsir.in");
ofstream fout("subsir.out");

const int nmax = 500;

int d[nmax + 5][nmax + 5];
int nr[nmax + 5][nmax + 5];
int l[27];
int c[27];

const int mod = 666013;

char a[nmax + 5];
char b[nmax + 5];

int main()
{
    fin>>(a+1);
    fin>>(b+1);
    int n = 0;
    int m = 0;
    for(int i=1;a[i];i++)
    {
        n=i;
        memset(c,0,sizeof(c));
        for(int j=1;b[j];j++)
        {
            m=j;
            if(a[i]==b[j]){
                d[i][j] = d[i-1][j-1]+1;
                if(d[i][j]==1)
                    nr[i][j]=1;
                else
                    for(int ch=0;ch<26;ch++)
                        if(d[l[ch]][c[ch]] + 1 == d[i][j])
                            nr[i][j]=(nr[i][j] + nr[l[ch]][c[ch]])%mod;
            }
            else
                d[i][j]=max(d[i-1][j],d[i][j-1]);
            c[b[j]-'a']=j;
        }
        l[a[i]-'a']=i;
    }
    int sol =0;
    int lmax = 0;
    for(int i=0;i<26;i++)
        if(d[l[i]][c[i]]==d[n][m])
            sol =(sol+ nr[l[i]][c[i]])%mod;
    fout<<sol;
}