Xay hang rao

View as PDF

Submit solution

Points: 1.86 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
VOS Round 24 - Ðỗ Việt Anh
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 \le 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

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

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.

Giới hạn

  • ~1 \le W~, ~B~, ~R \le 100~;
  • ~60\%~ test ~W = 0~.

Sample Input

2 1 2 2 1

Sample Output

10

Note

  1. WRWBR
  2. WRBWR
  3. RWBRW
  4. RBWRW
  5. WRWRB
  6. WRRBW
  7. RWRBW
  8. WBRWR
  9. WBRRW
  10. BRWRW

Comments

Please read the guidelines before commenting.


There are no comments at the moment.