#include <cstdlib>
#include <cstdio>
#include <cstring>

#include <algorithm>

using namespace std;

#define MAXN 500
#define MODULO 666013

char s1[MAXN + 2];
int l1;
char s2[MAXN + 2];
int l2;

int C[MAXN + 2][MAXN + 2];
int sol[MAXN + 2][MAXN + 2];

void read()
{
  scanf("%s\n%s", s1 + 1, s2 + 1);
  l1 = strlen(s1 + 1);
  l2 = strlen(s2 + 1);
}

void cmlsc()
{
  for(int i = 0; i <= l1; i++)
    C[i][0] = 0;
  for(int j = 0; j <= l2; j++)
    C[0][j] = 0;

  for(int i = 1; i <= l1; i++)
  {
    for(int j = 1; j <= l2; j++)
    {
      if(s1[i] == s2[j])
        C[i][j] = C[i - 1][j - 1] + 1;
      else
        C[i][j] = max(C[i - 1][j], C[i][j - 1]);
//      printf("%2d ", C[i][j]);
    }
//    printf("\n");
  }
//  printf("cmlsc = %d\n", C[l1][l2]);
}

void solve()
{
  for(int i = 0; i <= l1; i++)
    sol[i][0] = 1;
  for(int j = 0; j <= l2; j++)
    sol[0][j] = 1;

  for(int i = 1; i <= l1; i++)
  {
    for(int j = 1; j <= l2; j++)
    {
      if(s1[i] == s2[j])
      {
        sol[i][j] = sol[i - 1][j - 1];
      }
      else
      {
        if(C[i - 1][j] == C[i][j - 1])
        {
          sol[i][j] = sol[i - 1][j] + sol[i][j - 1];
          if(C[i - 1][j - 1] == C[i - 1][j])
            sol[i][j] -= sol[i - 1][j - 1];
        }
        else
        {
          if(C[i - 1][j] < C[i][j - 1])
            sol[i][j] = sol[i][j - 1];
          else
            sol[i][j] = sol[i - 1][j];
        }
      }
      sol[i][j] = (sol[i][j] + MODULO) % MODULO;
//      printf("%2d ", sol[i][j]);
    }
//    printf("\n");
  }

  printf("%d\n", sol[l1][l2]);
}

int main()
{
  freopen("subsir.in", "r", stdin);
  freopen("subsir.out", "w", stdout);
  read();
  cmlsc();
  solve();
  return 0;
}