{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eIn the math class, the evil teacher gave you one unprecedented problem!\u003cbr\u003e\u003cbr\u003eHere f(n) is the n-th fibonacci number (n \u0026gt;\u003d 0)! Where f(0) \u003d f(1) \u003d 1 and for any n \u0026gt; 1, f(n) \u003d f(n - 1) + f(n - 2). For example, f(2) \u003d 2, f(3) \u003d 3, f(4) \u003d 5 ...\u003cbr\u003e\u003cbr\u003eThe teacher used to let you calculate f(n) mod p where n \u0026lt;\u003d 10^18 and p \u0026lt;\u003d 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) \u003d f(n) , G(n,i) \u003d f( G(n,i-1) ) (k \u0026gt;\u003d i \u0026gt;\u003d 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.\u003cbr\u003e\u003cbr\u003eNote: This problem is the evil teacher\u0027s final problem, it is really hard ! If you could solve this problem during the competition, you will be reward in the ACM_DIY gathering. \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line is one integer T indicates the number of the test cases. (T \u0026lt;\u003d500000)\u003cbr\u003e\u003cbr\u003eThen for every case, three integers n k and p . (0 \u0026lt;\u003d n \u0026lt;\u003d 10^9,0 \u0026lt;\u003d k \u0026lt;\u003d 10^4, 1 \u0026lt;\u003d p \u0026lt;\u003d 10^8)"}},{"title":"Output","value":{"format":"HTML","content":"Output one line.\u003cbr\u003e\u003cbr\u003eFirst output “Case #idx: ”, here idx is the case number count from 1.Then output remainder of the answer after divided by p."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10 \r\n1 10000 100000000 \r\n2 3 10000 \r\n3 97 98 \r\n4 2 10 \r\n5 1 29 \r\n1234 5678 100000000 \r\n3344 5566 77889900 \r\n10000 10000 100000000 \r\n1111 10000 90000000 \r\n999 876 10000000\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 1 \r\nCase #2: 2 \r\nCase #3: 3 \r\nCase #4: 4 \r\nCase #5: 5 \r\nCase #6: 17835789 \r\nCase #7: 5381861 \r\nCase #8: 71647609 \r\nCase #9: 43710337\r\nCase #10: 9102595\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}