该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

禁用格铺砖

题目描述

有一个 $H\times W$ 的方格房间，其中一个格子被封锁，不能放置任何骨牌。按从上到下、从左到右的顺序给所有格子编号 $1$ 到 $HW$，输入编号 $P$ 表示被封锁的格子。

请使用 $A$ 张 $2\times1$ 骨牌和 $B$ 张 $1\times1$ 骨牌铺满其余格子。$2\times1$ 骨牌可以旋转。求不同铺法的数量。

保证 $2A+B=HW-1$。旋转或翻转后才重合的铺法仍视为不同铺法。

输入格式

输入五个整数 $H,W,A,B,P$（$1\le H,W$，$HW\le16$，$0\le A,B$，$1\le P\le HW$）。

输出格式

输出铺满所有未封锁格子的方案数。

输入输出样例

输入 #1

2 2 1 1 1

输出 #1

2

输入 #2

3 3 4 0 5

输出 #2

2

样例说明

第一个样例中左上角格子被封锁，剩余三个格子中只能把一张骨牌放在同一行或同一列，共 2 种。