「PMOI-2」拆分

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

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$ | 256MiB | 11 | | 3 | $n \le 2000$ | 256MiB | 17 | | 4 | $n \le 25000$ | 256MiB | 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$ 只包含小写字母。