P7420 "PMOI-2" Splitting

### If you do not read the hints in the sample explanation, you will most likely be unable to solve it. 

lhm has a string $a$ and its substring $b$. Now you need to split the string $a$. Let $c(s,b)$ denote the maximum number of substrings that can be selected from string $s$ such that they are pairwise non-overlapping and equal to $b$. If we split $a$ into $k$ groups, and denote the $i$-th group as $p_i$, you need to ensure: - $k \geq 2$, - $c(p_{i+1},b) > c(p_i,b)\ (i \in [1,k-1])$, - $c(p_1,b) \geq 1$. Two splitting plans are different if and only if the number of groups after splitting is different, or $\exist i$ such that the corresponding $c(p_i,b)$ values are different. Find the total number of different splitting plans, and output the answer modulo $899678209$.

The input consists of two lines. The first line contains a string $a$, with the meaning as described in the problem. The second line contains a string $b$, with the meaning as described in the problem.

The output consists of one line. Print one integer, representing the number of splitting plans modulo $899678209$.

[Sample Explanation] The splitting methods are: `noi noinonoi noiionoinoinoionoi`, with counts $1,2,5$. `noi noinonoin oiionoinoinoionoi`, with counts $1,2,4$. `noino inonoinoiion oinoinoionoi`, with counts $1,2,3$. `noi noinonoinoi ionoinoinoionoi`, with counts $1,3,4$. `noi noinonoinoiionoinoinoionoi`, with counts $1,7$. `noinoi nonoinoiionoinoinoionoi`, with counts $2,6$. `noinoinonoi noiionoinoinoionoi`, with counts $3,5$. `noin oinonoinoiionoinoinoionoi`, with counts $1,6$. `noinoinono inoiionoinoinoionoi`, with counts $2,5$. `noinoinonoin oiionoinoinoionoi`, with counts $3,4$. **Hint: The sample explanation is enough to show that splitting inside a substring is allowed.** [Constraints] Please read this section carefully. **This problem uses bundled testdata.** Let $n = c(a,b)$, $|a| = l_1$, and $|b| = l_2$. | Subtask | Special Property | Memory Limit | Score | | :----------: | :----------: | :----------: | :----------: | | 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 | None | 64MiB | 26 | For $100\%$ of the testdata, $0 \le n \le 2\times10^5$, $2 \le l_2 \le l_1 \le 10^6$, $b_1 \neq b_{l_2}$, and both $a$ and $b$ contain only lowercase letters. Translated by ChatGPT 5