Sum of LCP and LCS Products Under Thresholds

Given a string s of length n and two integers k1 and k2, we define two functions:

• \(lcp(i,j)\): The length of the longest common prefix between the suffixes starting at positions \(i\) and \(j\) in s (1-indexed).
• \(lcs(i,j)\): The length of the longest common suffix between the prefixes ending at positions \(i\) and \(j\) in s (1-indexed).

For example, for \(lcp(i,j)\), we compare the substrings \(s[i\ldots n]\) and \(s[j\ldots n]\), and for \(lcs(i,j)\) we compare \(s[1\ldots i]\) and \(s[1\ldots j]\) from the end.

Your task is to compute:

[ \sum_{1\leq i< j \leq n} lcp(i,j) \cdot lcs(i,j) \cdot [lcp(i,j) \leq k1] \cdot [lcs(i,j) \leq k2] \mod 2^{64} ]

Here, the notation \([P]\) is the indicator function which equals 1 if the predicate \(P\) is true, and 0 otherwise. The modulo \(2^{64}\) means that you can allow natural overflow as with an unsigned 64-bit integer.

inputFormat

The input consists of two lines:

1. The first line contains the string s (with length n).
2. The second line contains two space-separated integers k1 and k2.

outputFormat

Output a single integer: the computed sum modulo \(2^{64}\).

sample

ababa
2 3

8