#P3649. 数的表示

数的表示

数的表示

题目描述

将正整数表示为从右向左结合的幂塔

a1(a2(⋯at)),a_1^{(a_2^{(\cdots^{a_t})})},

其中 t>1t>1,每个 aia_i 都是大于1的整数。这个表示的价值为 tt。 例如 16=24=2(22)16=2^4=2^{(2^2)},最后一个表示的价值为3。 两个表示的长度不同,或相同长度下至少一个位置的整数不同,都视为不同表示。

给定一个价值为3的表示 A(BC)A^{(B^C)},求同一个整数有多少种价值至少为3的表示, 并对 pp 取模。

输入格式

第一行是形如 A^B^C 的字符串,按 A(BC)A^{(B^C)} 求值。 第二行是正整数 pp。

输出格式

输出一行一个整数,表示表示数对 pp 取模的结果。

样例

4^2^2
2
0

样例解释

目标数为256。符合条件的两个表示为 4(22)4^{(2^2)} 和 2(23)2^{(2^3)},所以模2后为0。

数据范围

2≤A,B,C≤1092\le A,B,C\le10^9,1≤p≤1091\le p\le10^9。