Easy Sequence

题目描述

有如下数列：

$\left\{\begin{matrix}\{1, 1\} \\\{1, 2, 4\} \\\{1, 3, 9, 27\} \\\{1, 4 , 16 , 64 , 256\} \\\{1 , 5 , 25 , 125 , 625 , 3125\}\\\vdots \\\end{matrix}\right.$

输出第 $n$ 个数列的各个数字之和。结果对 $P$ 取余。

输入格式

多组数据，每组数据读入 $2$ 个整数 $n, P$。

输出格式

每组测试数据独立成行，输出第 $n$ 个数列的各个数字之和，结果对 $P$ 取余。

样例 #1

样例输入 #1

2 7
5 17

样例输出 #1

0
13

提示

【样例解释】

当 $n = 5$ 时，数列为：$\{1 , 5 , 25 , 125 , 625 , 3125\}$。

$(1 + 5 + 25 + 125 + 625 + 3125) \mod 17 = 13$

【数据范围】

对于 $100\%$ 的数据，$2 \le n \le 10^{18}, 1 \le T \le 10^6, 2 \le P \le 10^9$，$\gcd(n - 1, P) = 1$。

注：本题没有采用捆绑测试。