String Splitting with Strictly Increasing Substring Occurrences

You are given a string (a) and one of its substrings (b). Define (c(s,b)) as the maximum number of non-overlapping occurrences of (b) in the string (s), where the occurrences are chosen greedily. You need to partition (a) into (k) non-empty segments (p_1, p_2, \dots, p_k) such that:

1. (k \ge 2),
2. (c(p_1,b) \ge 1), and
3. (c(p_{i+1},b) > c(p_i,b)) for every (1 \le i < k).

Two partitions are considered different if the number of segments (k) differs or there exists an index (i) for which (c(p_i,b)) is different between the partitions.

Output the total number of different partitioning schemes modulo (899678209).

inputFormat

The input consists of two lines. The first line contains the string (a). The second line contains the string (b), which is guaranteed to be a substring of (a).

outputFormat

Output a single integer representing the number of valid partitioning schemes modulo (899678209).

sample

abab
ab

0