题目描述

在一个幻想世界的运动竞技场中，有一项受到广泛关注的比赛——网球迷宫。这是一项独特而充满挑战的竞技项目，参与者需要将一个特殊的魔法网球从迷宫的起点击出，并通过巧妙的移动，将球移出迷宫的边界。

你是一位年轻而富有天赋的网球选手，渴望在网球迷宫比赛中获得荣耀。迷宫被设计成一个 $m×n$ 的网格，每个格子代表迷宫中的一个位置。你站在迷宫的起点 ($x，y$)，手握着一颗神奇的网球，这个球具有魔法力量，可以在网格中自由滚动。

然而，挑战在于你只能最多移动球 $c$** 次。每次移动，你可以将球击向四个方向中的一个，并且球会沿着该方向滚动到达相邻的格子。

你需要计算出有多少种不同的路径可以将球移出迷宫边界，并将最终结果对 $10^9 + 7$ 取模，以确保结果的准确性和可控性。

输入

第 $1$ 行，两个整数 $m$ $n$ 表示场地大小。

第 $2$ 行，两个整数 $x$ $y$ 表示迷宫的起点。

第 $3$ 行，$c$ 表示最多移动球的次数。

输出

将球移出迷宫的边界的不同路径数量。

样例

输入复制

2 2 
0 0
2

输出复制

6

输入复制

1 3
0 1
3

输出复制

12

说明

【样例 $1$ 解释】

从 $0,0$ 位置开始，$2$ 次以内，把网球移出边界，可以有 $6$ 种方法。

如下图所示：

【样例 $2$ 解释】

从 $0,1$ 位置开始，$3$ 次以内，把网球移出边界，可以有 $12$ 种方法。

如下图所示：

【数据范围】

$1≤m,n≤50$,

$0≤x<m , 0≤y<n$。

$0≤c≤50$。