Спасти котёнка
Артур принимает участие в телешоу, в котором участникам необходимо выполнять различные интеллектуальные и физические задания, чтобы зарабатывать очки. В одном из таких заданий Артуру необходимо спасти маленького котёнка.
Поле для выполнения задания представляет собой прямоугольник размером n×m метров, разбитый на квадраты единичной площади. В одном из квадратов исходно находится Артур, в некотором другом квадрате находится котёнок. Кроме того, один из квадратов содержит лифт, встав на который вместе с котёнком, Артур успешно выполняет задание.
За один шаг Артур может перемещаться на любой квадрат, имеющий общую сторону с тем, на котором он стоит. После этого квадрат, на котором перед этим шагом стоял Артур, исчезает и больше на него вставать нельзя. Таким образом исчезают в том числе и квадрат, на котором исходно стоял Артур, и квадрат с котёнком. Цель Артура — дойти до котёнка, взять его и затем дойти до лифта. При этом очки за выполнение задания, зависят от числа шагов, которое сделает Артур, поэтому ему необходимо сделать минимальное число шагов.
Выяснив, сколько шагов ему придётся сделать, Артур заинтересовался, сколько существует различных способов дойти до котёнка, а затем с ним до лифта, сделав в сумме минимальное число шагов. Помогите ему это выяснить. Это число может быть довольно большим, поэтому Артур просит найти его по модулю 10^9+7.
Входные данные
Первая строка входного файла содержит два натуральных числа n и m — размеры поля для выполнения задания (2 ≤ n, m ≤ 100).
Вторая строка содержит два целых числа x_A и y_A — координаты квадрата, на котором исходно находится Артур (1 ≤ x_A ≤ n, 1 ≤ y_A ≤ m). Третья строка содержит два целых числа x_K и y_K — координаты квадрата, на котором сидит котенок (1 ≤ x_K ≤ n, 1 ≤ y_K ≤ m). Четвертая строка содержит два целых числа x_E и y_E — координаты квадрата, на котором находится лифт (1 ≤ x_E ≤ n, 1 ≤ y_E ≤ m). Эти три квадрата попарно различны.
Выходные данные
В единственной строке выходного файла выведите одно число — число способов дойти до котенка и затем до лифта, не наступая на один квадрат два раза, совершив при этом минимальное количество шагов. Число необходимо вывести по модулю 10^9+7.
Примечание к примеру
Два способа для поля, приведённого в примере.