{"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 有一个空的 $n \\times m$ 网格,他想用一些 $1 \\times 2$ 和 $2 \\times 1$ 多米诺骨牌来覆盖 \u003cb\u003e整个\u003c/b\u003e 网格。在网格中,每个多米诺骨牌必须覆盖恰好两个相邻的方格,并且每个方格必须被恰好一个多米诺骨牌覆盖,其中两个方格相邻的条件是它们共享一个公共边。\u003cbr\u003e\u003cbr\u003e显然,只有当 $n$ 和 $m$ 中至少有一个是偶数时,他才能实现这一点。如果 $n$ 和 $m$ 都是奇数,则总会有一个方格必须留空。因此,他想知道他可以用多少种方式覆盖整个网格。如果存在两个多米诺骨牌,分别来自一种方式,且它们恰好覆盖同一个位置的一个方格,则这两种方式被视为不同。\u003cbr\u003e\u003cbr\u003e你能帮他确定答案吗?答案可能非常大,因此他只要求你告诉他答案对一个 \u003cb\u003e质数\u003c/b\u003e $p$ 取模后的结果。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行包含一个整数 $T~(1 \\leq T \\leq 20\\,000)$,表示问题的数量。\u003cbr\u003e\u003cbr\u003e接下来的 $T$ 行中,每行包含三个整数 $n~(1 \\leq n \\leq 35)$、$m~(1 \\leq m \\leq 10^{18})$ 和 $p~(2 \\leq p \\leq 2^{30})$,表示他想问你的一个问题。\u003cbr\u003e\u003cbr\u003e保证不超过 $1\\,000$ 个案例满足 $n \u0026gt; 5$ 或 $m \u0026gt; 10^9$。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个问题,输出一行中的一个整数,表示答案对 $p$ 取模后的结果。\u003cbr\u003e"}},{"title":"示例","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"}},{"title":"提示","value":{"format":"HTML","content":"\u003cbr\u003e以下图像显示了 3×4 网格的所有可能方式(共 11 种)。\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/7d9d517d0aa5e2608dd163a72d1b6950?v\u003d1722518462\"\u003e\u003c/center\u003e\u003cbr\u003e"}}]}