该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

积少成多

时间限制：$1000ms$

空间限制：$512MiB$

题目背景

前情提要.

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

例如, 在一次操作后, 3 可以变成[2, 4, 6], 而 4 可以变成[2, 3, 5, 8].

现在 lhy 想要知道, 对于一个闭区间[l, r], 他最少可以在多少次操作后遍历整个区间中的每一个整数. 注意, lhy 可以从这个闭区间的任何一个点出发, 而且他选择的初始点视为已经被遍历.

书接上回.

由于 lhy 的新手期过了, 这次他不能再随意的使用这些操作了.

题目描述

对于一个整数 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$ 这样的操作都是不被允许的.

数据格式

输入

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

输出

一行, 一个正整数表示至少需要的力量.

样例

输入

1 5 11

输出

10

样例解释

按照如下顺序进行[1, 2, 3, 4, 5], 每步需要的力量依次为 3, 6, 2, 10. 可以证明这是需要的最少力量.

数据范围及约定

$1 \le l \le r \le l + 10^5 \le 10^9$

$1 \le k \le 10^9$