#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],rez,v1[300],v2[300],maxv;
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);
	if (s1[s1[0]]=='\n')
		s1[0]--;
	s2[0]=strlen(s2+1);
	if (s2[s2[0]]=='\n')
		s2[0]--;
	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,1,s1[0])
	{
		FOR(j,0,25)
			if (s1[i]==j+'a')
				nr1[i][j]=i;
			else
				nr1[i][j]=nr1[i-1][j];
			
	}

	FOR(i,1,s2[0])
	{
		FOR(j,0,25)
			if (s2[i]==j+'a')
				nr2[i][j]=i;
			else
				nr2[i][j]=nr2[i-1][j];
	}
	FOR(i,1,s1[0])
		FOR(j,1,s2[0])
		{
			
			if (a[i][j]==1)
			{
				b[i][j]=1;
				continue;
			}
			FOR(k,0,25)
			{
				x=nr1[i-1][k];
				y=nr2[j-1][k];
				if (a[x][y]+1!=a[i][j])
					continue ;
				b[i][j]+=b[x][y];
				b[i][j]%=666013;
			}
			if (a[i][j]==a[s1[0]][s2[0]]&&i==nr1[s1[0]][s1[i]-'a']&&j==nr2[s2[0]][s2[j]-'a'])
				rez+=b[i][j];
		}
/*	for(i=s1[0];i>=1;i--)
		if (!v1[s1[i]])
			v1[s1[i]]=i;
	for(i=s2[0];i>=1;i--)
		if (!v2[s2[i]])
			v2[s2[i]]=i;
	FOR(i,'a','z')
		if(v1[i]&&v2[i]&&a[v1[i]][v2[i]]==maxv)
		{
			rez+=b[v1[i]][v2[i]];
			rez%=666013;
		}
	*/
	fprintf(out,"%d\n",rez);
	fclose(in);
	fclose(out);
	return 0;
}