数的表示

时间限制:10s      空间限制:256MB

题目描述

YJC 在学完了幂函数之后表示很兴奋,他总是在琢磨如何更好的用数的整数次幂来表示一个数,比如说16 = 2^4 = 2^2^2
,于是他给每一种表示方法定义了一个价值:若一个数被表示
成a1^a2^…a^ (ai > 1, N > 1),那么这个表示方法的价值就是N(如样例中写成16 = 2^2^2的价值就是 3) ,现在 YJC向你提出了一个问题:给了你若干个数,这些数以价值为 3的表示形式给出,问有多少种不同的价值至少为3的表示方式。


输入格式

输入一个形如A^B^C的字符串和一个整数P,表示一个价值为3的表示方式。

 


输出格式


输出一行表示答案模P。


样例输入

4^2^2

样例输出

2

提示


P<=10^9


题目来源

没有写明来源