Calculate Serial

Time Limit: 30000 ms

Memory Limit: 65535 ms

Description

Since it can be quite large, it is enough to compute the answer modulo given natural number m.

1 <= a2,m<= 10^9, 2 <= n <= 10^9

One day, Pandadiscovere an interesting array.

1. the length of a1 is always 1 .

2. the length of a2 is given number.

3. an (n > 2) = 2*a2*(an-1)-(an-2)

So he want to know Sum(a1*a1…an*an).

Busy as he is ,he give the mission to snow. And snow is busy eating so he comes to you for help.

Input

firstline:case number t then t lines, each line three number :a2,n,m

Output

rt

Sample Input

3
2 3 100
1 4 1000
3 3 1000000000

Sample Output

54
4
299

Hint

Source

panda

提交代码