题目描述

Vasya 不想再使用普通的 $8\times8$ 国际象棋棋盘，于是考虑两个与整数网格对齐的正方形棋盘。

第一个棋盘大小为 $N\times N$，左下角位于 $(0,0)$。

第二个棋盘大小为 $M\times M$，其左下角相对于第一个棋盘左下角向右平移 $W$ 个单位、向上平移 $H$ 个单位，也就是位于 $(W,H)$。

两个棋盘可能相交、包含或完全分离。我们考虑两个棋盘所有格子的并集。

现在需要在这些格子中放置恰好 $K$ 个车。一个摆放方案称为和平的，当且仅当任意两个车都不在同一行且不在同一列。

注意，即使两个棋盘之间存在空白区域，只要两个车位于同一条水平线或竖直线上，它们仍然会互相攻击。

求和平摆放 $K$ 个车的方案数。

答案可能非常大，需要完整输出十进制整数。

输入格式

一行包含五个整数：

N M W H K

其中：

• $0\le N,M\le20$；
• $0\le W,H\le10^9$；
• $0\le K\le10^9$。

输出格式

输出一行一个整数，表示和平摆放恰好 $K$ 个车的方案数。

样例 1

样例输入

8 2 6 8 1

样例输出

68

样例 2

样例输入

8 8 3 4 1

样例输出

108