String Extension Weight Sum

Given a string \(S\), define its extension operation as follows:

1. Compute the longest proper border \(T\) of \(S\). (A proper border is a non-empty substring that is both a prefix and a suffix of \(S\), but not equal to \(S\) itself.)
2. Set \(S' = S + T\), i.e. concatenate \(T\) to the end of \(S\).

The weight of an extension operation is defined as the length of the resulting string \(|S'|\). Given the initial string \(S\) and two positive integers \(L\) and \(R\), your task is to compute the sum of the weights of the extension operations from the \(L\)th extension to the \(R\)th extension (inclusive). Formally, if \(S_0 = S\) and \(S_i\) is obtained by applying the extension operation on \(S_{i-1}\), and its weight is \(|S_i|\), you need to output \[ \sum_{i=L}^{R} |S_i| \mod 998244353. \]

Note: If at any step the longest proper border is an empty string, then the extension operation will not change \(S\); hence all subsequent extensions will have the same weight.

inputFormat

The input consists of two lines:

• The first line contains the initial string \(S\) (non-empty).
• The second line contains two integers \(L\) and \(R\) (with \(1 \le L \le R\)).

outputFormat

Output a single integer, which is the sum \(\sum_{i=L}^{R} |S_i|\) modulo \(998244353\).

sample

abc
1 3

9