Description

YJC 在学完了幂函数之后表示很兴奋，他总是在琢磨如何更好的用数的整数次幂来表示一个数，比如说 $16 = 2^4 = 2^{2^2}$ ，于是他给每一种表示方法定义了一个价值：若一个数被表示 成形如

的格式，那么它的价值就为 $n$。

Input Format

第一行输入一个形如$a_1$^$a_2$^$a_3$^...^$a_n$ 的字符串。 第二行输入一个模数 $p$。

Output Format

输出一行表示答案模 $p$。

Sample Input1

4^2^2
2

Sample Output1

0

Sample Input2

3^8^2 17

Sample Output2

9

Hint

$p\le 10^9$