题目背景

如果您不看样例解释中的提示，那么您极可能做不出来！

题目描述

lhm 手中有一个字符串 $a$ 和它的子串 $b$，现你需要拆分字符串 $a$。

设 $c(s,b)$ 表示从字符串 $s$ 中选出一些互不重叠的、与 $b$ 相同的子串的最大子串数量。

若将 $a$ 拆分为 $k$ 组，第 $i$ 组记为 $p_i$，你需要保证：

• $k \geq 2$，
• $c(p_{i+1},b)>c(p_i,b)\ (i \in[1,k-1])$，
• $c(p_1,b)\geq 1$。

两种拆分方案不同当且仅当拆分出的组数不等或 $\exist i$，对应的 $c(p_i,b)$ 不等。

求不同的拆分方案总数，答案对 $899678209$ 取模。

输入格式

输入数据共两行。

第一行一个字符串 $a$，含义如题所示。

第二行一个字符串 $b$，含义如题所示。

输出格式

输出数据共一行。

一行一个整数，表示拆分的方案数对 $899678209$ 取模的结果。

noinoinonoinoiionoinoinoionoi
noi

10

提示

【样例解释】

拆分的方式分别为：

noi noinonoi noiionoinoinoionoi，个数分别为 $1,2,5$。

noi noinonoin oiionoinoinoionoi，个数分别为 $1,2,4$。

noino inonoinoiion oinoinoionoi，个数分别为 $1,2,3$。

noi noinonoinoi ionoinoinoionoi，个数分别为 $1,3,4$。

noi noinonoinoiionoinoinoionoi，个数分别为 $1,7$。

noinoi nonoinoiionoinoinoionoi，个数分别为 $2,6$。

noinoinonoi noiionoinoinoionoi，个数分别为 $3,5$。

noin oinonoinoiionoinoinoionoi，个数分别为 $1,6$。

noinoinono inoiionoinoinoionoi，个数分别为 $2,5$。

noinoinonoin oiionoinoinoionoi，个数分别为 $3,4$。

提示：样例解释足以说明可以拆分子串。

【数据规模与约定】

请仔细阅读本栏。

本题采用捆绑测试。

设 $n = c(a,b)$，$|a|=l_1$，$|b|=l_2$。

Subtask	特殊性质	空间限制	分值
1	$l_1\leq 30$	256MiB	9
2	$n \le 300$		11
3	$n \le 2000$		17
4	$n \le 25000$		37
5	无	64MiB	26

对于 $100\%$ 的数据，$0\le n\le2\times10^5$，$2\le l_2\le l_1\le10^6$，$b_1 \neq b_{l_2}$，$a$ 和 $b$ 只包含小写字母。