SP11830 DOJ1 - DOJO Corridor I

在道场的大厅里有一条长方形走廊，其中一个位置已经被一个魔法半畳（1×1 的正方形）固定占用。你需要用榻榻米（1×2 的矩形）将走廊的其余部分完全覆盖。有时这种覆盖是可行的，有时则无法实现。

第一行包含一个整数 $T$，表示测试用例的个数。接下来的 $T$ 行中，每行包含五个整数：$N, M$ 代表走廊的大小；$I, J$ 是魔法半畳所在的坐标；$K$ 用于计算输出时的模数。

对于每一个测试用例，输出一种合法铺设方案的数量，并对 $K$ 取模。

$$1 \le T \le 10^5, \quad 1 \le N, M \le 100, \quad 1 \le I \le N, \quad 1 \le J \le M, \quad 1 \le K \le 10^9$$ **本翻译由 AI 自动生成**