#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream f("subsir.in");
ofstream g("subsir.out");
char s[505],s1[505];
string cuv;
map <string,bool> m;
int n,n1,i,din[505][505],q,v[505],v1[505],j,cnt[505][505],nr;
int main()
{
    f>>s;
    f>>s1;
    n=strlen(s);
    n1=strlen(s1);
    for (i=0;i<n;i++)
    {
        v[i+1]=s[i]-'a'+1;
    }
    for (i=0;i<n1;i++)
    {
        v1[i+1]=s1[i]-'a'+1;
    }
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n1;j++)
        {
            if (v[i]==v1[j])
                {
                    din[i][j]=din[i-1][j-1]+1;
                    if (cnt[i-1][j-1]!=0)
                    {
                        cnt[i][j]=cnt[i-1][j-1];
                    }
                    else
                    {
                        cnt[i][j]=1;
                    }
                }
            else
        {
            if (din[i-1][j]>din[i][j-1])
            {
                din[i][j]=din[i-1][j];
                cnt[i][j]=(cnt[i][j]+cnt[i-1][j])%MOD;
            }
            else
            {
                if (din[i-1][j]<din[i][j-1])
            {
                din[i][j]=din[i][j-1];
                cnt[i][j]=(cnt[i][j]+cnt[i][j-1])%MOD;
            }
            else
            {
                din[i][j]=din[i][j-1];
                cnt[i][j]=(cnt[i][j]+cnt[i][j-1]+cnt[i-1][j])%MOD;
            }
            if(din[i - 1][j] == din[i][j - 1] && din[i][j] == din[i - 1][j - 1])
                        cnt[i][j] = (cnt[i][j] - cnt[i - 1][j - 1] + MOD) % MOD;
            }
        }
        }
    }
    g<<cnt[n][n1];
    return 0;
}