#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <algorithm>
#include <utility>
#include <string>
#include <functional>
#include <sstream>
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
#define FOR(i,a,b) for (i=a;i<=b;i++)
#define fori(it,v) for (it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fs first
#define ss second
#define all(c) c.begin(),c.end()
#define pf push_front
#define popb pop_back
#define popf pop_front
FILE *in,*out;
char s1[630],s2[630];
int x,y,i,j,k;
int a[600][600],b[600][600],nr1[600][30],nr2[600][30];
int main()
{
	in=fopen("subsir.in","r");
	out=fopen("subsir.out","w");
	fgets(s1+1,600,in);
	fgets(s2+1,600,in);
	s1[0]=strlen(s1+1);
	s2[0]=strlen(s2+1);
	FOR(i,1,s1[0])
	{
		FOR(j,1,s2[0])
			if (s1[i]==s2[j])
			{
				a[i][j]=a[i-1][j-1]+1;
			}
			else
				a[i][j]=max(a[i-1][j],a[i][j-1]);
	}
	FOR(i,2,s1[0])
	{
		FOR(j,0,25)
			if (s1[i-1]==j+'a')
				nr1[i][j]=i-1;
			else
				nr1[i][j]=nr1[i-1][j];
			
	}

        FOR(i,2,s2[0])
        {
                FOR(j,0,25)
                        if (s2[i-1]==j+'a')
                                nr2[i][j]=i-1;
                        else
                                nr2[i][j]=nr2[i-1][j];

        }
	FOR(i,1,s1[0])
		FOR(j,1,s2[0])
		{
			if (s1[i]!=s2[j])
				continue;
			if (a[i][j]==1)
			{
				b[i][j]=1;
				continue;
			}
			FOR(k,0,25)
			{
				x=nr1[i][k];
				y=nr2[j][k];
				if (a[x][y]+1!=a[i][j])
					continue ;
				b[i][j]+=b[x][y];
				b[i][j]%=666013;
			}
		}
	fprintf(out,"%d\n",b[s1[0]][s2[0]]);
	fclose(in);
	fclose(out);
	return 0;
}