小田的同余

mod.in mod.out

题目描述

给出一个奇数 $m$，请找出一个整数 $x(0 \le x < m)$，使得 $2x \equiv 1 (mod \; m)$，也就是 $2x$ 除以 $m$ 的余数是 $1$。你需要输出这个整数 $x$。

可以证明，这样的整数 $x$ 一定存在且唯一。

输入描述

输入包含一行。

第一行一个正整数 $m$。

输出描述

输出一个数字，表示答案。

输入输出样例

输入 #1

3

输出 #1

2

说明/提示

【样例 1 解释】

$2*2\%3 = 1$

【数据范围】 对于所有测试数据，有：$3 \le m \le 10^{12}$ 。