Робот ходить на картатий полі розміром \(N\) на \(M\) клітин. Йому потрібно перейти з клітини з координатами (\(A, B\)) в клітинку з координатами (\(C, D\)). Нумерація рядків та стовпців починається з лівого верхнього кута, перша координата – рядок, друга – стовпець. Лівий верхній кут поля має координати (1, 1) . За один крок Робот може переміститися на одну клітинку праворуч, ліворуч, вгору або вниз, але не по діагоналі.

Визначте, скількома способами він може виконати завдання, зробивши рівно \(K\) кроків.

Формат вхідних даних

У першому рядку вводяться розміри поля – кількість рядків \(N\) та кількість стовпців \(M\) ( \(1 \le N , M \le 16 \)).

У другому рядку записані координати \(A\) та \(B\) початкової клітини, а у третьому рядку – координати \(C\) та \(D\) кінцевої клітини, до якої має прийти Робот.

У четвертому рядку записано кількість кроків \(K\) ( \(1 \le K \le 100\) ).

Формат вихідних даних

Програма повинна вивести одне число: кількість різних способів переходу з клітини з координатами ( \(A , B\) ) в клітину з координатами ( \(C , D\) ) за \(K\) кроків.

Приклад вхідних даних

16 16
2 2
5 6
13

Приклад вихідних даних

464750