#include <fstream>

using namespace std;

ifstream in("subsir.in");
ofstream out("subsir.out");
string s1, s2;
int dp[505][505];
int sol[505][505];
int MOD = 666013;

int main()
{
    in>>s1>>s2;

    s1 = '$' + s1;
    s2 = '$' + s2;

    for(int i = 1; i<s1.size(); i++)
    {
        for(int j = 1; j<s2.size(); j++)
        {
            if(s1[i] == s2[j])
            {
                dp[i][j] = max(dp[i - 1][j - 1], 1);
                sol[i][j] = sol[i - 1][j - 1] + 1;
            }
            else
            {
                if(sol[i - 1][j] == sol[i][j - 1])
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    sol[i][j] = sol[i - 1][j];

                    if(sol[i - 1][j] == sol[i - 1][j - 1])
                    {
                        dp[i][j] -= dp[i - 1][j - 1];
                    }
                }
                else if(sol[i - 1][j] > sol[i][j - 1])
                {
                    dp[i][j] = dp[i - 1][j];
                    sol[i][j] = sol[i - 1][j];
                }
                else
                {
                    dp[i][j] = dp[i][j - 1];
                    sol[i][j] = sol[i][j - 1];
                }

                dp[i][j] = dp[i][j] % MOD;

                while(dp[i][j] < 0)
                {
                    dp[i][j] += MOD;
                }
            }
        }
    }

    out<<dp[s1.size() - 1][s2.size() - 1];
    return 0;
}