Background

Willow flowers, green hills, and moonlight.

The scent of wine in poems, and the scent of wine outside poems.

The sky inside the city, and the sky outside the city.

Word by word, stroke by stroke, what is understood, what is still hazy.

Look and look, learn and learn. The world is like murky wine; you only know its taste after you drink it.

Problem Description

Define the extension operation on a string $S$ as:

• Find the longest $\text{border}$ $T$ of $S$.

• Set $S'\leftarrow S+T$.

Note: in this problem, $\text{border}$ means a proper $\text{border}$ (that is, the string itself is not counted as a $\text{border}$).

Let the weight of an extension operation be the length of the string after extension, i.e. $|S'|$. Please compute the sum of weights from the $L$-th extension of string $S$ to the $R$-th extension.

Since the result may be very large, output the answer modulo $998244353$.

Input Format

The first line contains a string $S$.

The second line contains two integers $L,R$.

Output Format

Output one number, i.e. the answer modulo $998244353$.

ababcab
1 3

39

aa
3 5

59

Hint

Explanation for Sample 1

The $1$-st extension: ababcab[ab], with weight $9$.

The $2$-nd extension: ababcabab[abab], with weight $13$.

The $3$-rd extension: ababcabababab[abab], with weight $17$.

The sum of weights is $9+13+17=39$.

Constraints

For $30\%$ of the testdata, $1 \le |S| \le 100$ and $1 \le L,R \le 10$.

For $60\%$ of the testdata, $1 \le L,R \le 10^6$.

For the other $10\%$ of the testdata, $\text{border}_{S}=|S|-1$.

For $100\%$ of the testdata, $1 \le |S| \le 10^6$ and $1 \le L \le R \le 10^9$. The input consists only of integers and lowercase letters.

Translated by ChatGPT 5