D-幂运算_2023河南萌新联赛第（四）场：河南大学

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小 T 最近在学习离散数学，书上有一句话:

n 个命题变项只能生成 $2^{2^{n}}$ 个真值不同的命题公式。

现在小 T 想要知道，对于两个给定的正整数 n, p, n 个命题变项在模 p 意义下能生成多少个真值不同的命题公式？

形式化的说，对于两个给定的正整数 n, p：计算 $2^{2^{n}}\mod p$ 的值

取模运算的定义为 $a\mod b = a - \lfloor \frac{a}{b} \rfloor \times b$

数据保证 $1 \le n \le 10^6, 1 \le p \le 2^{31} - 1$

一行，两个正整数 n, p

一行，一个整数表示

示例1

复制

3 1223

复制