1602: 小球移动

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:20 Solved:14

Description

      给定一个大小为NxM的网格和一个球。球的起始坐标为 (Row,Col) 。我们可以将球移到在四个方向上相邻的单元格内(也可以穿过网格边界到达网格之外)。现在,小球最多可以移动maxMove次球。现在,给到五个整数 N、M、maxMove、Row 和 Col ,找出并返回可以将球移出边界的路径数量。因为答案可能非常大,返回对 109 + 7 取模后的结果。

图示1:

当:N=2    M=2    maxMove=2   Row = 0    Col=0 

结果为:6


图示2:

当:N=1    M=3    maxMove=3   Row = 0    Col=1 

结果为:12


Input

输入一行,依次输入题意的行数N、列数M、最大移动次数maxMove、起点行Row、起点列Col。

(1 <= N, M<=50 ,   0 <=maxMove<=50 , 0<=Row<N  ,  0<= Col<M)

Output

一行,输出对 109+7 取模后的结果值。

Sample Input Copy

2 2 2 0 0

Sample Output Copy

6

HINT

【样例输入2】

1 3 3 0 1

【样例输出2】

12