#include <fstream>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstring>

#define MAXN 502

using namespace std;

char strA[MAXN];
char strB[MAXN];

short lcs[MAXN][MAXN];

unsigned long Count[MAXN][MAXN];

const int c_MOD = 666013;

int main()
{
    int n;
    int m;
    fstream fin("subsir.in", fstream::in);
    fstream fout("subsir.out", fstream::out);

    fin >> strA + 1;
    fin >> strB + 1;

    n = strlen(strA + 1);
    m = strlen(strB + 1);

    //cout << strA + 1 << endl;
    //cout << strB + 1 << endl;
    
    for (int i=0; i<=n; ++i)
    {
        Count[0][i] = 1;
    }
    
    for (int i=0; i<=m; ++i)
    {
        Count[i][0] = 1;
    }

    for (int i=1; i<=n; ++i)
    {
        for (int j=1; j<=m; ++j)
        {
            if (strA[i] == strB[j])
            {
                lcs[i][j] = lcs[i-1][j-1] + 1;
                
                Count[i][j] = Count[i-1][j-1];
            }
            else
            {
                lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);

                if (lcs[i-1][j] == lcs[i][j-1])
                {
                    // Count[i][j] = (Count[i-1][j] + (lcs[i-1][j-1] != lcs[i-1][j]) * Count[i][j-1]) % c_MOD;
                    Count[i][j] = (Count[i-1][j] + Count[i][j-1]) % c_MOD;
                    if (lcs[i-1][j-1] == lcs[i-1][j])
                    {
                        Count[i][j] = (Count[i][j] - Count[i-1][j-1] + c_MOD) % c_MOD;
                    }
                }
                else
                {
                    Count[i][j] = max(Count[i-1][j], Count[i][j-1]);
                }
            }
        }
    }

    /*ostream_iterator<short> itOut(cout, " ");
    
    int len = max(n, m);
    for (int i=0; i<=len+1; ++i)
    {
        copy_n(lcs[i], len + 1, itOut);
        cout << endl;
    }*/
    
    fout << Count[n][m] << "\n";

    return 0;
}