II otwarte zawody UWM o prezenty Świętego Mikołaja

Dana jest kratownica o rozmiarze NxN (gdzie 0<N<2¹⁶). Krawędzie kratownicy indeksowane są od zera do N-1. Dla danych dwóch punktów P1=(x₁,y₁), P2=(x₂,y₂) znajdź ile istnieje dróg z P1 do P2 o długości M. Poruszać można się tylko wzdłuż kratownicy, zaś każdy jej wierzchołek można odwiedzić tylko raz (punkty P1 uważa się za odwiedzony, kolejność odwiedzanych wierzchołków ma znaczenie).

Rysunek powyżej przedstawia jedną z możliwych dróg o długości M=6 z punktu (3,1) do punktu (2,4) na kratownicy N=6.

Input

Dane wejściowe rozpoczyna liczba N określająca rozmiar kratownicy. Dwie kolejne linie zawierają punkty współrzędne punktów P1 oraz P2, każde w postaci dwóch liczb 0<x,y<N oddzielonych spacją. Ostatnia linia zawiera liczbę M określającą długość drogi.

Output

Na wyjściu należy wygenerować lczbę określającą ilość możliwych dróg o długości M z punkt P1 do P2 na kratownicy o wymiarze NxN.

Example

Input:
4
1 1
3 1
4

Output:
6