牢，悬棺

#include<bits/stdc++.h>
#define int long long
#define la i&1^1
#define no i&1
#define mod 100000000
using namespace std;
int n,m,dp[2][5005],sum[2][5005];
string a,b;
signed main(){
	cin>>a>>b;n=a.size()-1,m=b.size()-1;a=' '+a,b=' '+b;
	for(int i=0;i<=m;i++) sum[0][i]=1;sum[1][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(a[i]==b[j]){
				dp[no][j]=dp[la][j-1]+1;
				sum[no][j]=dp[la][j-1]%mod;
				if(dp[no][j]==dp[la][j]) (sum[no][j]+=sum[la][j])%=mod;
				if(dp[no][j]==dp[no][j-1]) (sum[no][j]+=sum[no][j-1])%=mod;
			}
			else{
				dp[no][j]=max(dp[la][j],dp[no][j-1]);
				if(dp[la][j]>dp[no][j-1]) sum[no][j]=sum[la][j]%mod;
				else if(dp[la][j]<dp[no][j-1]) sum[no][j]=sum[no][j-1]%mod;
				else if(dp[no][j]!=dp[la][j-1]) sum[no][j]=(sum[no][j-1]+sum[la][j])%mod;
				else sum[no][j]=((sum[no][j-1]+sum[la][j]-sum[la][j-1])%mod+mod)%mod;
			}
		}
	cout<<dp[n&1][m]<<endl;
	cout<<sum[n&1][m]<<endl;
    return 0; 
}