시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

10 233333

예제 출력 1

50