Лабіринт Хрестики - Нулики
Бесі обожнює розв'язувати лабіринти та грати в "хрестики-нулики". Фермер Джон вигадав для неї спосіб поєднати обидві ці гри!
Спочатку про "хрестики-нулики": замість традиційних X і O на решітці розміром 3 * 3, корови грають з символами М і О. Під час свого ходу корова може поставити М або О в будь-яку порожню клітинку (на відміну від стандартної гри, де один гравець завжди ставить X, а інший - O). Переможцем стає той, хто першим складе слово 'MOO' горизонтально, вертикально або по діагоналі. Також виграшною комбінацією вважається 'OOM'. Як і в звичайній грі, можливо, що все поле буде заповнено, але ніхто не виграє. Хід у грі позначається 3 символами M[ij] або O[ij], де i і j - це індекси рядка і стовпця (від 1 до 3), в які ставиться відповідний символ 'M' або 'O'.
Фермер Джон створив для Бесі квадратний лабіринт, що складається з n * n клітинок. Деякі з них, включаючи всі крайні клітинки, містять великі стоги сіна, які заважають Бесі заходити в ці клітинки. Бесі може вільно пересуватися по всіх інших клітинках лабіринту, роблячи кроки в напрямках північ, південь, захід або схід. У деяких клітинках розміщені листки паперу з ходами для "хрестиків-нуликів". Коли Бесі потрапляє на таку клітинку, вона повинна зробити відповідний хід у грі "хрестики-нулики", яку вона грає паралельно з рухом по лабіринту. Якщо відповідна клітинка в "хрестиках-нуликах" вже зайнята, вона не робить жодних дій. У неї немає суперника в цій грі, але деякі клітинки лабіринту можуть заважати їй скласти слово 'MOO'.
Якщо Бесі зупиняє гру "хрестики-нулики" відразу після перемоги, визначте кількість різних виграшних конфігурацій у "хрестиках-нуликах", які вона може створити, рухаючись по лабіринту.
Вхідні дані
Перша рядок містить n (3 ≤ n ≤ 25).
Лабіринт описується наступними n рядками, кожен з яких містить 3n символів. Кожна клітинка описується блоком з 3 символів: '###' для стіни, '...' для порожньої клітинки, 'BBB' для клітинки, з якої Бесі починає свій шлях. Рівно одна клітинка містить 'BBB'.
Вихідні дані
Виведіть кількість різних виграшних комбінацій для "хрестиків-нуликів" (можливо 0), які Бесі може створити, зупинившись після перемоги.
Приклад
У цьому прикладі є 8 виграшних комбінацій, які Бесі може досягти:
O.M .O. MOM O.. .O. .OM O.M .O. .OM O.. .O. MOM O.. ... OOM ..M .O. OOM ... .O. OOM ... ... OOM
Пояснення до однієї з них:
O.. ... OOM
Тут Бесі спочатку відвідує клітинку O11, потім рухається в нижній коридор, відвідуючи O32, M33, O31. Гра припиняється, оскільки Бесі виграла.