Drum

Acum că este dupa ora opt, Emilian trebuie să plece de pe Piezișă spre circul zburător, pentru a-și continua distracția futuristă în orașul Jluc.

Orașul Jluc poate fi privit ca un sistem de coordonate cu valori întregi, în care ne putem deplasa doar pe orizontală și verticală (nu și pe diagonală). Definim un drum dintr-un punct în altul ca fiind o succesiune de pași între aceste două puncte, un pas efectuându-se dintr-un punct $(x, y)$ în unul din punctele $(x, y+1)$, $(x, y − 1)$, $(x + 1, y)$ sau $(x − 1, y)$, iar lungimea unui drum ca fiind numărul de pași efectuați în ace drum. Deoarece Emilian este obosit și amețit după învățatul pentru sesiune, într-un drum putem trece prin același punct de mai multe ori, deci $(1, 1) \rightarrow (0, 1) \rightarrow (1, 1)$ este un drum valid de lungime $2$.

Dându-se coordonatele punctelor de interes, Emilian se întreabă câte drumuri de lungime $K$ există între aceste două puncte.

Date de intrare

Pe prima linie se dau $x_s$, $y_s$ coordonatele punctului de plecare, pe cea de a doua linie $x_f$, $y_f$ coordonatele punctului de sosire, iar pe a treia linie lungimea drumului $K$.

Date de ieșire

Se va afișa numărul de drumuri posibile modulo $1 \ 000 \ 000 \ 007$.

Restricții și precizări

• $−10^9 \leq x_s, y_s, x_f , y_f \leq 10^9$
• $0 \leq K \leq 10^6$

Exemplu

drum.in

2 2
3 3
2

drum.out

2

Explicație

Există două drumuri de lungime $2$: $(2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$, $(2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$.