Описание пути
Вам дана сетка размером
n x n клеток. Маршрут начинается в клетке (1, 1), проходит через все клетки и заканчивается в клетке (n, 1). Двигаться можно только вправо (R), влево (L), вверх (U) или вниз (D), и при этом каждая клетка может быть посещена не более одного раза. Сам путь описывается с помощью символов LRUD, где каждый символ указывает движение в соответствующем направлении. Однако в описании пути некоторые символы заменены вопросительными знаками (?), что означает неизвестное направление.Ваша задача — определить, сколько существует различных путей, которые соответствуют данному описанию.
Входные данные
В первой строке содержится одно целое число
n (3 ≤ n ≤ 6), задающее размер сетки.
Во второй строке находится описание пути — это строка из символов L, R, U, D и ?, где каждый символ указывает направление перемещения. Длина описания пути равна .Выходные данные
Выведите одно целое число, обозначающее количество различных путей, соответствующих заданному описанию.
Примеры
Input | Output |
3
RR??LUL? | 1 |
4
??R??????????L? | 3 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB