Description

“所以，当他知道他要去向何处时，他是平静的，因为他已经度过了了不起的一生，充实的一生。他已经拥有了所需要的一切品性。他曾那样存在过。”​本杰明进入了梦乡，在梦境中，映入眼帘的是一个小盒子，盒子里面装着大量卡牌，但卡牌只有 $1,2,3$ 三种标号，本杰明抓取了一张 卡牌后，又看到了脚下出现了两个数字 $n$ 和 $p$，随后眼前浮现出一行字：如果你拿到了 $x$ 号卡牌，你将会获得 $2^{x^{n}}mod p$ 块金砖请问本杰明会在梦境中获得多少块金砖

Format

Input

输入三个整数 $x,n,p (1 \leq x \leq 3, 1 \leq n \leq 10^{6}, 1 \leq p < 2^{31})$，分别代表抓取的卡牌号和脚下出现的两个数字

Output

输出一个整数，表示本杰明会获得的金砖数

Samples

2 4 114514

65536

1 2 3

2

3 1 6

2

Hint