#206. Easy Sequence

Easy Sequence

Easy Sequence

题目描述

有如下数列:

{{1,1}{1,2,4}{1,3,9,27}{1,4,16,64,256}{1,5,25,125,625,3125}\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.

输出第 nn 个数列的各个数字之和。结果对 PP 取余。

输入格式

多组数据,每组数据读入 22 个整数 n,Pn, P

输出格式

每组测试数据独立成行,输出第 nn 个数列的各个数字之和,结果对 PP 取余。

样例 #1

样例输入 #1

2 7
5 17

样例输出 #1

0
13

提示

【样例解释】

n=5n = 5 时,数列为:{1,5,25,125,625,3125}\{1 , 5 , 25 , 125 , 625 , 3125\}

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

【数据范围】

测试点编号 NN \le TT \le
11 100100
252 \sim 5 101810^{18} 1010
696 \sim 9 10610^6

对于 100%100\% 的数据,2n1018,1T106,2P1092 \le n \le 10^{18}, 1 \le T \le 10^6, 2 \le P \le 10^9gcd(n1,P)=1\gcd(n - 1, P) = 1

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