#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define LL long long #define orz cout<<"lkp AK IOI!"<<endl using namespace std; const int MAXN = 1e5+5; const int INF = 1e9+7; const int mod = 1e8; int n, m; char a[5010], b[5010]; int f[5010], Max[5050], cnt[5050], p[5050]; int read(){ int s = 0, f = 0; char ch = getchar(); while(!isdigit(ch)) f |= (ch == '-'), ch = getchar(); while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar(); return f ? -s : s; } int main() { scanf("%s", a + 1); scanf("%s", b + 1); n = strlen(a + 1), m = strlen(b + 1); memset(f, 128, sizeof f); memset(Max, 128, sizeof Max); f[0] = 0; Max[0] = 0; cnt[0] = 1; for(int l = 1; l <= n; ++l) { for(int r = 1, nowM = 0, sum = 0; r <= m; ++r) { if(nowM < Max[r - 1]) nowM = Max[r - 1], sum = cnt[r - 1]; else if(nowM == Max[r - 1]) sum = (sum + cnt[r - 1]) % mod; if(a[l] != b[r]) continue; f[r] = nowM + 1; p[r] = sum; } for(int r = 0; r <= m; ++r) { if(f[r] < 0) continue; if(Max[r] < f[r]) Max[r] = f[r], cnt[r] = p[r]; else if(Max[r] == f[r]) cnt[r] = (cnt[r] + p[r]) % mod; p[r] = 0; } } printf("%d\n", f[m] - 1 ); return 0; }