#include <bits/stdc++.h>

using namespace std;
ifstream in("secv.in");
ofstream out("secv.out");
const int skibidi_freddyFazbear=666013;
int v[505][505],idk[505][505];
string a,b;
int main()
{
    in>>a>>b;
    int n=a.size();
    int m=b.size();
    a="0"+a;
    b="0"+b;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]==b[j]){
                idk[i][j]=idk[i-1][j-1]+1;
                v[i][j]=max(v[i-1][j-1],1);
            }
            else{
                if(idk[i-1][j]==idk[i][j-1]){
                    v[i][j]=v[i-1][j]+v[i][j-1];
                    if(idk[i-1][j]==idk[i-1][j-1])
                        v[i][j]-=(v[i-1][j-1]-skibidi_freddyFazbear);
                }
                else
                    v[i][j]=max(v[i-1][j],v[i][j-1]);
                v[i][j]%=skibidi_freddyFazbear;
                idk[i][j]=max(idk[i-1][j],idk[i][j-1]);
            }
        }
    }
    out<<v[n][m];
    return 0;
}