题目描述

一座城堡有 $N>1$ 个房间，编号为 $0,1,\ldots,N-1$。初始时，编号为 $x$ 的房间中恰好有 $x$ 枚金币。

骑士开始行动前必须选择一个整数 $S$，满足 $0\le S<N$，且整个过程中 $S$ 保持不变。城堡唯一的门通向房间 $1$，因此骑士从房间 $1$ 开始；当骑士回到房间 $1$ 时，可以选择离开城堡并结束行动。

骑士位于房间 $x$ 时，可以进行以下操作之一：

• 收集当前房间中尚未被收集的全部金币；
• 移动到编号为 $(xS)\bmod N$ 的房间。

每个房间的金币最多只能被收集一次。只有最终能够回到房间 $1$ 并离开城堡，收集到的金币才有效。

给定一个奇素数 $P$ 和正整数 $K$，其中 $N=2P^K$。请输出任意一个能使骑士最终带出城堡的金币总数达到最大值的 $S$。

输入格式

一行包含两个整数 $P,K$。

• $P\ge3$ 且 $P$ 为素数；
• $K\ge1$；
• $2P^K\le10^{14}$。

输出格式

输出一个整数 $S$，满足 $0\le S<N$，并且该选择能获得最大可能金币总数。

本题可能有多个正确答案，输出任意一个即可。

样例 1

输入

3 1

输出

5

样例 2

输入

7 2

输出

47

说明

样例 1 中 $N=6$。取 $S=5$ 时，房间序列为 $1\to5\to1$，骑士可以收集房间 $1$ 和 $5$ 中的金币并安全离开。