无额外样例。

问题描述

2k 个人围成一圈，按顺时针方向依次编号为 1 ~ 2k，其中编号为 1, 2, ……, k 的全是好人，编号为 k+1, k+2, …… , 2k 的全是坏人。

从编号为 1 的好人开始，按顺时针方向，从 1 开始报数，报到 m 的人就被杀掉，然后下一个人重新开始从 1 报数，每次报到 m 的人就被杀掉，……，如此循环报数。

你要确定一个最小的 m，使得 k 个坏人全被杀死前没有一个好人被杀死，这样等坏人全部被杀光之后，就不用再杀人了。

输入

一个 k

输出

一个满足题目要求的最小的 m

样例1

输入

3

输出

5

样例2

输入

11

输出

459901

数据范围

1 ≤ k ≤ 15

注：赛后会进行代码查验，如发现打表，本题将被判 0 分。