Однажды, во время вечерней прогулки по лесу, мальчик Вова пришел к реке и увидел, что на другом берегу застрял его друг Ваня. Вове нужно спасти его друга, так как тот не умеет плавать! В реке находится n × (n + 1) островов в виде сетки. Однако между ними нет мостов! Там же на берегу Вова встретил злого волшебника Зедикуса, который согласился помочь только при условии, что Вова решит одну непростую задачу. Вове нужно посчитать количество способов построить мосты так, чтобы существовал хотя бы один путь с одного берега на другой. Помогите Вове решить эту задачу. Вове разрешено строить мосты только между соседними островами.

Более формально, каждый остров имеет координаты (r, c) (1 ≤ r ≤ n, 1 ≤ c ≤ n + 1), где r — номер строки, а c — номер столбца. Если остров имеет координаты (r, c), то соседние острова имеют координаты (r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1), если таковые существуют. Острова, которые находятся в первом и последнем столбце, то есть острова с координатами (r, c), где (т. e. c равно либо 1, либо n + 1), уже соединены с берегами.

Путем с одного берега на другой является такая последовательность островов (r₁, c₁), (r₂, c₂), ..., (r_k, c_k), что для каждого i (1 ≤ i < k) существует мост между островами (r_i, c_i) и (r_i + 1, c_i + 1), также остров (r₁, c₁) находится в первом столбце (c₁ = 1), а остров (r_k, c_k) находится в последнем столбце (c_k = n + 1).

Два способа построить мосты считаются различными, если найдется такой мост, что в одном из способов он построен, а в другом нет. Для лучшего понимания условия смотрите иллюстрацию ниже. На иллюстрации приведен один из способ построить мосты, чтобы перейти с одного берега на другой.

На данной иллюстрации присутствуют два берега, описанные в условии. Левый берег обозначен через L, а правый через R. Островами на данной иллюстрации являются зеленые кружки. Мостами являются прямоугольники с закругленными углами. Как можно видеть, данная конфигурация мостов содержит путь между левым берегом и правым. Напомним, что мосты между берегом L и левым столбцом островов присутствуют изначально. Тоже самое для правого берега R и правого столбца островов. Также стрелки rows и columns соответствуют осям координат для строк и столбцов.