You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

循序渐进

时间限制：$1s$

空间限制：$256MB$

题目背景

前情提要:

对于一个整数 x, 通过一次操作, 它可以变成[x / 2, x - 1, x + 1, x * 2]中的任意一个. 其中 x / 2 仅当 x 为偶数时可以使用.

当 lhy 通过任意操作使得 x 变为 y 时, 他需要拥有 $(x^y+y^x)\%k$ 的力量, 其中 k 为给定常量. 力量不够无法通行, 但是通行并不会使得力量失去.

现在, lhy 仍然希望遍历完这一整个区间 [l, r], 请问他至少需要拥有多少力量.

注意: lhy 在任意时刻都不允许遍历到不在区间 [l, r] 中的数字.比如 $l$ 变成 $l - 1$ 以及 $r$ 变成 $r + 1$ 这样的操作都是不被允许的.

书接上回:

lhy 发现自己根本没有那么多力量, 但是这时候出现了一只小精灵...

题目描述

小精灵与 lhy 约定, 此后 lhy 不再需要拥有任何力量就可以使用所有的操作. 作为补偿, lhy需要支付一定的代价.

当 lhy 使用操作使得 x 变为 y 时, 他需要拥有 $(x^y+y^x)\%k$ 的力量, 其中 k 为给定常量. 虽然现在 lhy 不需要拥有这么多力量了, 但是小精灵会将这些力量值记下, 作为收取报酬的依据. 当然小精灵也非常慷慨, 如果 lhy 在某次操作中使得 x 变为 y, 那么在此后的操作中, 无论是将 x 变为 y 还是将 y 变为 x, 这些力量值都不再被记录.

现在, lhy 仍然希望遍历完这一整个区间 [l, r]. 当 lhy 遍历完整个区间后, 小精灵的记录可以表示为 $(c_1, c_2, ..., c_m)$( $m$ 为总操作数 ). 小精灵将这组记录从大到小排序, 得到 $(c_{(1)}, c_{(2)}, ..., c_{(m)})$, 其中 $c_{(i)}$表示第 i 大的数. 小精灵所要收取的代价便是 $\sum_{i=1}^{m}(i \times c_{(i)})$.

请帮助 lhy 最小化这个代价.

注意: lhy 在任意时刻都不允许遍历到不在区间 [l, r] 中的数字.比如 $l$ 变成 $l - 1$ 以及 $r$ 变成 $r + 1$ 这样的操作都是不被允许的.

数据格式

输入

一行, 三个正整数 l, r, k.

输出

一行, 一个正整数表示需要支付的最小的代价.

样例

输入

1 5 11

输出

39

样例解释

按照如下顺序进行[1, 2, 3, 4, 5], 每步需要的力量依次为 3, 6, 2, 10. 排序后得到 10, 6, 3, 2, 所以结果为 39.

可以证明这是需要的最少代价.

数据范围及约定

$1 \le l \le r \le l + 10^5 \le 10^9$ $1 \le k \le 10^6$ 对于c++选手, 你可能需要使用64位整数进行计算.