Задача C. Слишком много способов

Автор:М. Спорышев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Однажды школьник Вася пришел в недавно построенное новое здание университета на мастер-класс по информатике. Здание имеет форму куба, составленного из одинаковых аудиторий также кубической формы. Каждой аудитории присвоены три номера x, y, z — порядковые номера по ширине, длине и высоте соответственно. Самая первая аудитория имеет номера 1, 1, 1. Из каждой аудитории можно перейти в любую соседних, имеющих с ней общую стену.

Вася находится в аудитории (xB, yB, zB). Мастер-класс пройдет в аудитории (xM, yM, zM). Вася решил посчитать, сколькими способами можно попасть из текущей аудитории в ту, где проходит мастер-класс, за наименьшее число переходов между аудиториями.

Однако Вася частенько прогуливает мастер-классы и не знает как это сделать, поэтому он отправил смс-ку вам, в надежде, что вы подскажете ему ответ.

Формат входного файла

Входной файл содержит 6 целых чисел xM yM zM xB yB zB.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество способов. Так как ответ на вопрос Васи может быть слишком большим, выведите в его остаток от деления на 109 + 7.

Ограничения

1 ≤ xM, yM, zM, xB, yB, zB ≤ 1000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1 1 2 2 2
6
2
1 1 1 3 3 3
90

0.087s 0.013s 13