{"trustable":false,"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":"\u003cp\u003e虽然冬天很远,松鼠不得不日夜工作以节省豆类。 他们需要大量的食物来度过这漫长的寒冷日子。 一段时间后,松鼠家庭认为他们必须解决问题。 他们认为他们会在不同的树木中储存豆子。 然而,由于现在的食物不足,他们只能吃到豆子。 他们想知道有多少种方法可以在n树中保存不超过m个bean(它们是相同的)。\u003c/p\u003e\n\n\u003cp\u003e现在他们求助于你,你应该给他们答案。 结果可能非常巨大; 你应该输出模p的结果,因为松鼠无法识别大数。\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数T,表示案例数。\u003c/p\u003e\n\n\u003cp\u003e然后是T行,每行包含三个整数n,m,p,意味着松鼠将在n个不同的树中保存不超过m个相同的bean,1 \u003c\u003d n,m \u003c\u003d 1000000000,1 \u003cp \u003c100000并且p是 保证是一个素数。\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"你应该输出模p的答案。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e2\n1 2 5\n2 1 5\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e3\n3\n\n \n \u003ci style\u003d\"font-size:1px\"\u003e \u003c/i\u003e\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"提示:\n\n\u003cp\u003e对于样本1,松鼠将在一棵树中放置不超过2个豆。 由于树木不同,我们可以将它们标记为1,2 ......等等。\u003c/p\u003e\n\u003cp\u003e3种方法是:不放豆,将1个豆放在树1中,将2个豆放在树1中。对于样品2,3种方法是:\n 没有豆,把1豆放在树1中,把1豆放在树2中。\u003c/p\u003e"}}]}