{"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\"\u003eElizur has an empty $n \\times m$ grid and he wants to use some $1 \\times 2$ and $2 \\times 1$ dominoes to cover the \u003cb\u003eentire\u003c/b\u003e grid. In the grid, each domino ought to cover exactly two adjacent squares and each square ought to be covered by exactly one domino, where two squares are adjacent if and only if they share a common side.\u003cbr\u003e\u003cbr\u003eObviously, he can achieve that if and only if at least one of $n$ and $m$ is even. In case that both $n$ and $m$ are odd, there is always a square that must be left empty. Hence, he intends to know in how many ways he can cover the entire grid. Two ways are considered different if and only if there exist two dominoes, each selected from one way, satisfying that they cover exactly one square at the same position.\u003cbr\u003e\u003cbr\u003eCan you help him determine the answer? The answer may be exceedingly large, so he only requests you to tell him the answer modulo a \u003cb\u003eprime number\u003c/b\u003e $p$.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains a single integer $T~(1 \\leq T \\leq 20\\,000)$, indicating the number of questions.\u003cbr\u003e\u003cbr\u003eIn the next $T$ lines, each line contains three integers $n~(1 \\leq n \\leq 35)$, $m~(1 \\leq m \\leq 10^{18})$ and $p~(2 \\leq p \\leq 2^{30})$, representing a question he wants to ask you.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that no more than $1\\,000$ cases satisfy $n \u0026gt; 5$ or $m \u0026gt; 10^9$.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each question, output a single integer in one line, denoting the answer modulo $p$.\u003cbr\u003e"}},{"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\u003e6\r\n2 2 23\r\n2 3 233\r\n3 3 2333\r\n3 4 23333\r\n4 4 2332333\r\n5 251346744251346744 998244353\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3\r\n0\r\n11\r\n36\r\n295381485\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eThe following image shows all possible ways (11 in total) for the 3×4 grid.\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/7d9d517d0aa5e2608dd163a72d1b6950?v\u003d1726253656\"\u003e\u003c/center\u003e\u003cbr\u003e"}}]}