Problem Background

Willow flowers, green hills, and moonlight.

The fragrance of wine in the poem and the fragrance of wine outside the poem.

The sky within the city and the sky beyond the city.

Each word, each stroke, what is known, what is still vague.

Look and learn, the world is like turbid wine, its flavor is known only when tasted.

Problem Description

Define the extension operation of a string \( S \) as follows:

• Find the longest border \( T \) of \( S \).

• \( S' \leftarrow S + T \).

Note that the border in this problem refers to a proper border (i.e., the string itself is not considered a border).

Let the value of the extension operation be the length of the extended string \( |S'| \). Calculate the sum of the values from the \( L \)-th to the \( R \)-th extension of string \( S \).

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 \) and \( R \).

Output Format

Output a single number, which is the answer modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

ababcab
1 3

Sample Output #1

39

Sample Input #2

aa
3 5

Sample Output #2

59

Notes

Sample One Explanation

The 1st extension operation: ababcab[ab], value is \( 9 \).

The 2nd extension operation: ababcabab[abab], value is \( 13 \).

The 3rd extension operation: ababcabababab[abab], value is \( 17 \).

The sum of values is \( 9 + 13 + 17 = 39 \).

Data Range and Constraints

For 30% of the data, \( 1 \le |S| \le 100, 1 \le L, R \le 10 \).

For 60% of the data, \( 1 \le L, R \le 10^6 \).

For another 10% of the data, \( \text{border}_{S} = |S| - 1 \).

For 100% of the data, \( 1 \le |S| \le 10^6, 1 \le L \le R \le 10^9 \), the input consists of integers and lowercase letters.

见题面 Input 部分

见题面 Output 部分