只要努力飞翔，即使再弱小的蝴蝶也可以飞的很高
3649 - 数的表示
YJC 在学完了幂函数之后表示很兴奋，他总是在琢磨如何更好的用数的整数次幂来表示一个数，比如说16 = 2^4 = 2^2^2 ，于是他给每一种表示方法定义了一个价值：若一个数被表示 成???a1^???a2^…a^?????? (???ai > 1, N??? > 1)，那么这个表示方法的价值就是N（如样例中写成16 = 2^2^2的价值就是 3） ，现在 YJC向你提出了一个问题：给了你若干个数，这些数以价值为 3的表示形式给出，问有多少种不同的价值至少为3的表示方式。
Input
输入一个形如A^B^C的字符串和一个整数P，表示一个价值为3的表示方式。
Output
输出一行表示答案模P???。
Examples
Input
4^2^2
Output
2
Hint
P<=10^9