Background

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

Problem Description

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$.

Input Format

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.

Output Format

The output consists of one line.

Print one integer, representing the number of splitting plans modulo $899678209$.

noinoinonoinoiionoinoinoionoi
noi

10

Hint

[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$.

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