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

int a[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++)
            for(int j=0; j<m; j++)
                        {if(s1[i]==s2[j])
                                    a[i+1][j+1]=a[i][j]+1;
                        else
                                    {if(a[i+1][j]>a[i][j+1])
                                                a[i+1][j+1]=a[i+1][j];
                                    else
                                                a[i+1][j+1]=a[i][j+1];
                                    }
                        }
g<<a[n][m]%666013;


return 0;
}