Электрик Вася целый день паяет платы, а если точнее, то делает разводку платы — прокладывает дорожки по ней. Частенько Васе попадается работа по проводке двух дорожек из углов платы к углам на противоположной стороне. Плату можно представить как n рядов по m участков в каждом, где некоторые участки уже содержат в себе элементы и через них дорожку проводить нельзя. Стартовые участки дорожек находятся в участках (1, 1) и (n, 1), а противоположные углы  — в (1, m) и (n, m). Нельзя допускать пересечения двух дорожек, то есть проводить дорожки через один и тот же участок. И также, по специфике обработки платы, при прокладывании путь не может отдаляться от целевой стороны. Это значит, что если последний участок пути дорожки находится в координате (r, c), то следующий участок дорожки должен быть в (r + 1, c), (r - 1, c) или (r, c + 1). Теперь Васе вдруг стало интересно, а сколькими способами он может проложить дорожки? Два способа считаются различными, если последовательность пути хотя бы одной из дорожек отличается.

Помогите Васе, найдите количество способов.