#include <bits/stdc++.h>

using namespace std;

ifstream f("subsir.in");
ofstream g("subsir.out");

const int Mod = 666013;

char a[1005],b[1005];

int dp[1005][1005], dp_ways[1005][1005];

int main()
{
    f>>(a+1);
    f>>(b+1);
    int n = strlen(a+1);
    int m = strlen(b+1);
    for(int i=0;i<=n;i++)
    {
        dp_ways[i][0] = 1;
    }
    for(int j=0;j<=m;j++)
    {
        dp_ways[0][j] = 1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i]==b[j])
            {
                dp[i][j] = 1 + dp[i-1][j-1];
                dp_ways[i][j] = dp_ways[i-1][j-1];
            }
            else
            {
                if(dp[i-1][j]>dp[i][j-1])
                {
                    dp[i][j] = dp[i-1][j];
                    dp_ways[i][j] = dp_ways[i-1][j];
                }
                else if(dp[i][j-1]>dp[i-1][j])
                {
                    dp[i][j] = dp[i][j-1];
                    dp_ways[i][j] = dp_ways[i][j-1];
                }
                else
                {
                    dp[i][j] = dp[i][j-1];
                    dp_ways[i][j] = (dp_ways[i][j-1] + dp_ways[i-1][j]) % Mod;
                    if(dp[i-1][j-1]==dp[i][j-1])
                    {
                        dp_ways[i][j] = (dp_ways[i][j] - dp_ways[i-1][j-1] + Mod) % Mod;
                    }
                }
            }
        }
    }
    g<<dp_ways[n][m]<<'\n';
    return 0;
}