19018번 - Border 다국어

문제

You are given a string $S[1 \ldots n]$. We denote its substrings as $S[l \ldots r],ドル and when $l > r,ドル such substring is defined to be an empty string. Let $$f(i, j) = \max \left\{k~|~0 \leq k \leq j-i,~S[i \ldots i+k-1] = S[j-k+1 \ldots j]\right\} \text{.}$$

Output $\sum\limits_{1 \leq i < j \leq n} f(i, j)$.

The string $S$ is generated in the following way. The values $n$ and $\mathit{seed}$ are the parameters of the generator.

long long seed;
for (int i = 1; i <= n; i++) {
 seed = (seed * 13331 + 23333) % 1000000007;
 s[i] = 'a' + (seed & 1);
}

입력

The first line contains two integers: $n$ and $\mathit{seed}$ (1ドル \leq n \leq 10^6,ドル 0ドル \leq \mathit{seed} \leq 10^9 + 6$).

출력

Output the answer.

제한

힌트