#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
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;

string a;
string b;

int main()
{
    fin>>a;
    fin>>b;
    a='0'+a;
    b='0'+b;
    for(int i=1;i<a.size();i++)
    {
        memset(c,0,sizeof(c));
        for(int j=1;j<b.size();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[a.size()-1][b.size()-1])
            sol =(sol+ nr[l[i]][c[i]])%mod;
    fout<<sol;
}