#include <iostream>
#include <fstream>
#include <string.h>
#include <algorithm>
using namespace std;
const int mod=666013;
ifstream in ("subsir.in");
ofstream out("subsir.out");
int dp[503][503], dp2[503][503];
int lastMet[2][27][503];
string s1, s2;
int nr=0;
int main()
{
    in>>s1>>s2;

    for(int i=1; i<=(int)s1.size(); i++)
    {
        for(int ch=1; ch<=26; ch++)
            lastMet[0][ch][i]=lastMet[0][ch][i-1];
        lastMet[0][s1[i-1]-'a'+1][i]=i;
    }

    /*for(int j=1; j<=s1.size(); j++)
    {
        for(int i=1; i<=26; i++)
            cout<<lastMet[0][i][j]<<" ";
        cout<<"\n";
    }*/


    for(int i=1; i<=(int)s2.size(); i++)
    {
        for(int ch=1; ch<=26; ch++)
            lastMet[1][ch][i]=lastMet[1][ch][i-1];
        lastMet[1][s2[i-1]-'a'+1][i]=i;
    }

    for(int i=1; i<=(int)s1.size(); i++)
        for(int j=1; j<=(int)s2.size(); j++)
            if(s1[i-1]!=s2[j-1])
                dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
            else
            {
                if(i==1||j==1)
                {
                    dp[i][j]=dp2[i][j]=1;

                    continue;
                }
                dp[i][j]=dp[i-1][j-1]+1;
                if(dp[i][j]==1)
                    dp2[i][j]=1;
                for(int ch=1; ch<=26; ch++)
                {
                    int p1=lastMet[0][ch][i-1];
                    int p2=lastMet[1][ch][j-1];

                    if(p1!=0&&p2!=0)
                        if(dp[p1][p2]==dp[i][j]-1)
                            dp2[i][j]+=dp2[p1][p2], dp2[i][j]%=mod;
                }
            }


    /*for(int i=1; i<=s1.size(); i++)
    {
        for(int j=1; j<=s2.size(); j++)
        {
            cout<<dp2[i][j]<<" ";
        }
        cout<<"\n";
    }*/

    for(int i=1; i<=26; i++)
    {
        int p1=lastMet[0][i][s1.size()];
        int p2=lastMet[1][i][s2.size()];
        if(p1!=0&&p2!=0&&dp[p1][p2]==dp[s1.size()][s2.size()])
            nr+=dp2[p1][p2], nr%=mod;
    }
    out<<nr;
    return 0;
}