Леді розважається в системі координат. Починаючи з точки (0, 0), вона хоче досягти точки (~N,M~) рівно за ~K~ секунд. Кожної секунди Леді може збільшити свою координату ~x~ щонайбільше на ~A~, а ~y~-координату не більше ніж на ~B~. Формально, якщо Леді знаходиться в клітинці (~x, y~), вона може стрибнути за одну секунду в клітинку (~x', y'~), тільки якщо ~x \le x' \le x+A~ і ~y \le y' \le y+B~.

Напишіть програму, яка знаходить кількість способів, якими дівчина може досягти своєї мети. Зауважте, що протягом секунди Леді може вирішити не змінювати одну (або обидві) свої координати, але вона не може їх зменшити.

Оскільки відповідь може бути дуже великою - виведіть її за модулем 1000000007 (~10^9 + 7~).

Обмеження

• ~1 \le N, M, A, B, K \le 10 000~

Підзадачі та оцінювання

Щоб отримати бали за підзадачу, ваша програма повинна пройти всі тести в ній. Підзадачі:

Підзадача Бали ~N, M, A, B, K \le~

1       8       8
2       11      50
3       15      300
4       20      1000
5       16      3000
6       30      10000

Input

У першому рядку містяться числа ~N, M, A, B~ і ~K~.

Output

У першому рядку виведіть число - кількість способів, якими дівчина досягне своєї мети.

Sample Input 1

3 1 2 3 2

Sample Output 1

4

Sample Input 2

100 100 30 30 10

Sample Output 2

957270726

Notes

Усі серії стрибків для досягнення мети в першому тесті:

(0,0) → (1,0) → (3,1)

(0,0) → (1,1) → (3,1)

(0,0) → (2,0) → (3,1)

(0,0) → (2,1) → (3,1)