Дужковий лабірінт
Є куб розміром n * n * n. Починаючи з комірки (1, 1, 1), Вам слід прийти до комірки (n, n, n). З кожної комірки можна рухатися до сусідньої у напрямку зростання x, y або z координати. Кожна клітинка куба містить один із символів: '(', ')' або '.'. Шляхом будемо називати послідовність комірок, відвідуваних при русі. Необхідно знайти кількість шляхів з (1, 1, 1) до (n, n, n), які описують правильну дужкових структуру. Правильною дужковою структурою називається вираз, що породжується граматикою:
::= empty-string | "("")" | "." |
Вираз може містити довільну кількість точок, які не враховуються при визначенні його правильності. Наприклад, рядки "(())", "....", ".()." і "().(.)" є правильними дужкових структурами.
Символи рядкуа maze відповідають координатам комірок куба наступним чином:
(1, 1, 1), (1, 1, 2), ..., (1, 1, n), (1, 2, 1), (1, 2, 2), ...,
(1, n, n), (2, 1, 1), ..., (n, n, n)
Вхідні дані
Кожний рядок містить натуральне число n (1 ≤ n ≤ 13) та рядок maze, який складається в точності з n^3 символів.
Вихідні дані
Для кожного тесту в окремому рядку вивести кількість шляхів з (1, 1, 1) до (n, n, n), які описують правильну дужкову структуру. Якщо шляхів більше за 1,000,000,000, то слід вивести -1.