P5115 Check, Check, Check one two!

You are listening to くらげP’s チェチェ・チェック・ワンツー!, and suddenly the head teacher pushes the door open. So you have to pretend that you are working on a string problem. ~~(But the head teacher sees through this easy problem at a glance, and you get criticized for doing easy problems when you had nothing to do.)~~

You are given a string. We define $lcp(i,j)$ as the length of the longest common prefix of the suffix starting at position $i$ of the string and the suffix starting at position $j$. We define $lcs(i,j)$ as the length of the longest common suffix of the prefix ending at position $i$ of the string and the prefix ending at position $j$. Now you are given a string of length $n$, and you need to compute $$\sum_{1\leq i < j \leq n}lcp(i,j)lcs(i,j)[lcp(i,j)\leq k1][lcs(i,j) \leq k2]$$ modulo $2^{64}$ (that is, natural overflow of unsigned long long is sufficient). $[lcs(i,j) \leq k]$ means that if the proposition $lcs(i,j) \leq k$ is true, then this term equals 1; otherwise it equals 0. The other bracket is defined similarly.

The first line contains a string $S$, guaranteed to consist only of lowercase English letters. The second line contains two positive integers $k1,k2$, representing the constraints in the statement.

Output a single positive integer, which is the value of the given expression modulo $2^{64}$.

Let $n$ denote the length of the string. Test point 10 is worth 1 point, and for this test point, $n \leq 1000$. For all test points, $$1 \leq n \leq 10^5,1\leq k1 , k2 \leq n$$ Translated by ChatGPT 5