Elizur has an empty n×m grid and he wants to use some 1×2 and 2×1 dominoes to cover the entire 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.
Obviously, 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.
Can you help him determine the answer? The answer may be exceedingly large, so he only requests you to tell him the answer modulo a prime number p.
3071: Domino Covering
| Time Limit | $6$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $0$ | 正确数量 | $0$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
Description
Input
The first line contains a single integer T (1≤T≤20000), indicating the number of questions.
In the next T lines, each line contains three integers n (1≤n≤35), m (1≤m≤1018) and p (2≤p≤230), representing a question he wants to ask you.
It is guaranteed that no more than 1000 cases satisfy n>5 or m>109.
In the next T lines, each line contains three integers n (1≤n≤35), m (1≤m≤1018) and p (2≤p≤230), representing a question he wants to ask you.
It is guaranteed that no more than 1000 cases satisfy n>5 or m>109.
Output
For each question, output a single integer in one line, denoting the answer modulo p.
Sample Input复制
6
2 2 23
2 3 233
3 3 2333
3 4 23333
4 4 2332333
5 251346744251346744 998244353
Sample Output复制
2
3
0
11
36
295381485
提示
The following image shows all possible ways (11 in total) for the 3×4 grid. 
推荐代码 查看3071 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$ $ms] | |||
| 内存最少[$ $KB] | |||
| 第一AC | |||
| 第一挑战 |
赛题来源/所属竞赛 2019 Multi-University Training Contest 10 N/A
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|