// 线性DP 滚动数组 O(n^2)
#include<bits/stdc++.h>
using namespace std;

const int N=5010,mod=1e8;
int n,m;
char a[N],b[N];
int f[2][N],g[2][N];

int main(){
  scanf("%s %s",a+1,b+1);
  n=strlen(a+1)-1; m=strlen(b+1)-1;
  
  for(int k=0; k<=m; k++) g[0][k]=1;
  g[1][0]=1;
  
  int u=0;
  for(int i=1; i<=n; i++){
    u^=1;
    for(int j=1; j<=m; j++){
      if(a[i]==b[j]) f[u][j]=f[u^1][j-1]+1;
      else f[u][j]=max(f[u^1][j],f[u][j-1]);
      g[u][j]=0;
      if(a[i]==b[j]&&f[u][j]==f[u^1][j-1]+1) g[u][j]+=g[u^1][j-1];
      if(f[u][j]==f[u^1][j]) g[u][j]+=g[u^1][j];
      if(f[u][j]==f[u][j-1]) g[u][j]+=g[u][j-1];
      if(f[u][j]==f[u^1][j-1]) g[u][j]-=g[u^1][j-1]; //容斥
      g[u][j]%=mod;
    }
  }
  printf("%d\n%d",f[u][m],g[u][m]);
}