#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<typename T>void read(T&x){
	x=0;char ch=getchar();bool f=0;
	while(!isdigit(ch))f|=ch=='-',ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	x=f?-x:x;
}
const int M=1e6+5,P=2333,MOD=899678209;
char str1[M],str2[M];ull ha[M],pw[M];ll dp[2][M];
int main(){
	scanf("%s%s",str1+1,str2+1);
	int l1=strlen(str1+1),l2=strlen(str2+1);
	for(int i=1;i<=l1;i++)ha[i]=ha[i-1]*P+str1[i]-'a';
	ull ha2=0;
	for(int i=1;i<=l2;i++)ha2=ha2*P+str2[i]-'a';
	pw[0]=1;for(int i=1;i<=l1;i++)pw[i]=pw[i-1]*P;
	int n=0;
	for(int i=1;i+l2-1<=l1;i++){
		//[i,i+l2-1]
		if(ha2==ha[i+l2-1]-ha[i-1]*pw[l2])n++;
	}
	if(!n){
		puts("0");return 0;
	}
	//cout<<"n"<<n<<endl;
	dp[0][0]=1;
	ll ans=0;
	for(int i=1;n-i*(i-1)/2>0;i++){
		//cout<<i<<endl;
		int c=i&1;
		for(int j=0;j<i;j++)dp[c][j]=0;
		for(int j=i;j<=n;j++)
			dp[c][j]=(dp[!c][j-1]+dp[c][j-i])%MOD;//,cout<<i<<' '<<j<<':'<<dp[c][j]<<endl;
		for(int j=max(n-(i-1)-i*(i-1)/2,1);j<=n-i*(i-1)/2;j++)
			ans=(ans+dp[c][j])%MOD;
	}
	printf("%d",(ans-1+MOD)%MOD);
	return 0;
}