#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 5010

#define P 100000000

int n,m,f[][N],g[][N];

char a[N],b[N];

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj2423.in","r",stdin);

    freopen("bzoj2423.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    char c=getchar();

    while (c>='A'&&c<='Z') a[++n]=c,c=getchar();

    a[++n]=c,c=getchar();

    while (c<'A'||c>'Z') c=getchar();

    while (c>='A'&&c<='Z') b[++m]=c,c=getchar();

    b[++m]=c,c=getchar();

    for (int j=;j<=m;j++) g[][j]=;

    for (int i=;i<=n;i++)

    {

        memset(f[i&],,sizeof(f[i&]));

        memset(g[i&],,sizeof(g[i&]));

        g[i&][]=;

        for (int j=;j<=m;j++)

        if (a[i]!=b[j])

        {

            f[i&][j]=max(f[i&^][j],f[i&][j-]);

            if (f[i&^][j]==f[i&][j-])

            {

                if (f[i&^][j]==f[i&^][j-]) g[i&][j]=((g[i&^][j]+g[i&][j-])%P-g[i&^][j-]+P)%P;

                else g[i&][j]=(g[i&^][j]+g[i&][j-])%P;

            }

            else if (f[i&^][j]>f[i&][j-]) g[i&][j]=g[i&^][j];

            else g[i&][j]=g[i&][j-];

        }

        else

        {

            f[i&][j]=f[i&^][j-]+;

            g[i&][j]=g[i&^][j-];

            if (f[i&][j]==f[i&^][j]) g[i&][j]=(g[i&][j]+g[i&^][j])%P;

            if (f[i&][j]==f[i&][j-]) g[i&][j]=(g[i&][j]+g[i&][j-])%P;

        }

    }

    cout<<f[n&][m]-<<endl<<g[n&][m];

    return ;

}