Border

Time limit2sMemory limit512 MB

Summary

Given a string generated from a seed, compute the sum over all pairs i<j of the longest k where the prefix starting at i of length k equals the suffix ending at j of length k.

Level: Hard8 of 10
Topics: String, String matching, Array
Solved: No attempts yet

Problem

You are given a string $S[1 \ldots n]$ . We write its substrings as $S[l \ldots r]$ , and when $l > r$ , the substring is the empty string. Define $f(i, j)$ as follows.

$f(i, j) = \max \{k \mid 0 \leq k \leq j-i, S[i \ldots i+k-1] = S[j-k+1 \ldots j]\}$

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

The string $S$ is generated as follows. The values $n$ and $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);
}

Input

The first line contains two integers $n$ and $seed$ ( $1 \leq n \leq 10^6$ , $0 \leq seed \leq 10^9 + 6$ ).

Output

Output the answer.

Examples1

Example 1
Input
```
10 233333
```
Expected output
```
50
```