#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

int a[501][501], b[501][501], n, m;
char s1[501],s2[501];

int main()
{
ifstream f("subsir.in");
ofstream g("subsir.out");
f.get(s1,500);
f.get();
f.get(s2,500);
n=strlen(s1);
m=strlen(s2);
for(int i=0; i<=n; i++)
            a[i][0]=a[0][i]=1;
for(int i=n; i<=m; i++)
            a[0][i]=1;
for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                        {if(s1[i]==s2[j])//&& s1[i]!=' ')
                                    {b[i+1][j+1]=b[i][j]+1;
                                    a[i+1][j+1]=a[i][j];
                                    }
                        else
                                    if(b[i][j+1]==b[i+1][j])
                                                {
                                                b[i+1][j+1]=b[i+1][j];
                                                a[i+1][j+1]=(a[i][j+1] + a[i+1][j]) % 666013;
                                                if(b[i][j+1]==b[i][j])
                                                            a[i+1][j+1]=(a[i+1][j+1]-a[i][j]+666013)%666013;
                                                }
                                    else
                                                {if(b[i+1][j]<b[i][j+1])
                                                            {b[i+1][j+1]=b[i][j+1];
                                                            a[i+1][j+1]=a[i][j+1];
                                                            }
                                                else
                                                            {b[i+1][j+1]=b[i+1][j];
                                                            a[i+1][j+1]=a[i+1][j];
                                                            }
                                                }
                        }
g<<a[n][m]%666013;
/*for(int i=0; i<=n; i++)
            {for(int j=0; j<=m; j++)
                        cout<<a[i][j]<<" ";
            cout<<endl;}
cout<<endl;
for(int i=0; i<=n; i++)
            {for(int j=0; j<=m; j++)
                        cout<<b[i][j]<<" ";
            cout<<endl;}
*/
return 0;
}