高次幂取模的运用

高次幂取模的应用
此题乃师兄[ TT_last ]原创题！Orz膜拜一下

a simple problem
Problem Description
As we know , to caculate the sum ofis hard if the n is large,because today is Valentines Day,to make this problem more easy ,you only need to caculate the sum mod c

Input
There are multiply testcases. Each testcase, there is one line contains two integers n,c;(1<=n <= 10^1000000,1<=c <=1000000000

Output
For each testcase, output an integer, denotes the result of the sum mod c

Sample Input
2 4
3 5

Sample Output
0
2

Author
TT_last


计算这个的公式： n*2^(n-1)

高次取模降幂公式：

Phi是欧拉函数

 爽！ 爽！