Giải bài trực tuyến

Nhân dịp Noel sắp đến, Vịt Nhỏ muốn xây hàng rào cho nhà mình. Hàng rào là 1 dãy thanh gỗ xếp sát nhau. Vịt Nhỏ đã mua W thanh gỗ màu trắng, B thanh gỗ màu xanh và R thanh gõ màu đỏ. Vì đã mất tiền mua nên Vịt Nhỏ sẽ dùng hết số gỗ này để xây hàng rào.

Để cho hàng rào đặt biệt Vịt Nhỏ quyết định sơn hàng rào theo 2 nguyên tắc sau :

-       Ở bất cứ đoạn hàng rào độ dài K nào cũng có ít nhất 1 thanh gỗ được sơn màu xanh hoặc đỏ.

-       Có đúng M vị trí i ( 1 <= i < (W + B + R) ) mà a[i] sơn xanh, a[i+1] sơn đỏ hoặc a[i] sơn đỏ và a[i+1] sơn xanh.

          Trên thực tế có thể có rất nhiều cách xây thỏa mãn điều kiện nên Vịt Nhỏ muốn đếm xem có bao nhiêu cách xây có thể. Vì kết quả có thể rất lớn nên chỉ cần đưa ra module 1000000007 ( 10^9+7 );

Input

-       1 dòng duy nhất chứa 5 số nguyên W B R K M như đã miêu tả.

-       1 <= W, B, R <= 100;

-       60% test W = 0.

Output

-       Số hàng rào có thể xây module 10^9+7. Luôn đảm bảo có ít nhất 1 cách.

Example

Input:
2  1  2  2  1

Output:
10

Giải thích :
WRWBR
WRBWR
RWBRW
RBWRW
WRWRB
WRRBW
RWRBW
WBRWR
WBRRW
BRWRW