In the math class, the evil teacher gave you one unprecedented problem!
Here f(n) is the n-th fibonacci number (n >= 0)! Where f(0) = f(1) = 1 and for any n > 1, f(n) = f(n - 1) + f(n - 2). For example, f(2) = 2, f(3) = 3, f(4) = 5 ...
The teacher used to let you calculate f(n) mod p where n <= 10^18 and p <= 10^9, however , as an ACMER, you may just kill it in seconds! The evil teacher is mad about this. As you kill the Evil teacher.s problem in second too!!! now he let you calculate G(n,k) .Here G(n,0) = f(n) , G(n,i) = f( G(n,i-1) ) (k >= i >= 1). However the G(n,k) may be so large ,so you just need to output the remainder of the answer after divided by p.
Note: This problem is the evil teacher's final problem, it is really hard ! If you could solve this problem during the competition, you will be reward in the ACM_DIY gathering.