P10272 Outside Sifang City

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

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

The first line contains a string $S$. The second line contains two integers $L,R$.

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

### 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