给定一个字符串 $S[1 \dots n]$。我们将它的子串记为 $S[l \dots r]$，当 $l > r$ 时，该子串定义为空串。令 $$f(i, j) = \max \{k \mid 0 \le k \le j - i, S[i \dots i + k - 1] = S[j - k + 1 \dots j]\}$$ 输出 $\sum_{1 \le i < j \le n} f(i, j)$。

字符串 $S$ 按如下方式生成。值 $n$ 和 $seed$ 是生成器的参数。

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

输入格式

第一行包含两个整数：$n$ 和 $seed$ ($1 \le n \le 10^6$, $0 \le seed \le 10^9 + 6$)。

输出格式

输出答案。

样例

输入 1

10 233333

输出 1

50