RT

#include<bits/stdc++.h>
using namespace std;
const int mod=1e8;
char s1[5005],s2[5005];
int f[5005][2],g[5005][2];
int main(){
	scanf("%s%s",s1+1,s2+1);
	int len1=strlen(s1+1)-1,len2=strlen(s2+1)-1;
	for(int i=0;i<=len2;i++) g[0][i]=1;
	g[1][0]=1;
	for(int i=1;i<=len1;i++){
		for(int j=1;j<=len2;j++){
			int x=i&1;
			g[x][j]=0;
			f[x][j]=max(f[x^1][j],f[x][j-1]);
			if(s1[i]==s2[j]){
				f[x][j]=max(f[x][j],f[x^1][j-1]+1);
				g[x][j]+=g[x^1][j-1];
			}
			if(f[x][j]==f[x^1][j]) g[x][j]+=g[x^1][j];
			if(f[x][j]==f[x][j-1]) g[x][j]+=g[x][j-1];
			if(f[x][j]==f[x^1][j-1]) g[x][j]-=g[x^1][j-1];
			g[x][j]%=mod;
		}
	}
	printf("%d\n%d\n",f[len1&1][len2],g[len1&1][len2]);
	return 0;
}