Задачи
Бинарное дерево
Бинарное дерево
Бинарное дерево - древовидная структура данных, где каждый узел имеет не более двух детей, которые являются левым и правым ребенком. Узел, имеющий детей, называется родителем этих детей.
Строка с инструкциями состоит из букв \textbf{L}, \textbf{R} и \textbf{U}. \textbf{L} означает Левый, \textbf{R} означает Правый, а \textbf{U} означает Верх. Их значения будут изложены ниже.
Однажды я нарисовал бесконечно большое бинарное дерево. В этом дереве каждая вершина имела в точности двух детей (левого и правого ребенка), каждый из которых имел отца. В этой задаче отцом корня будем считать сам корень. Я ставлю ручку в корень и следую строке инструкций \textbf{S}. То есть смотрим на ее первый символ и если он равен \textbf{L}, то двигаемся к левому сыну, если он равен \textbf{R}, то двигаемся к правому сыну, если он равен \textbf{U}, то двигаемся к предку. Если в корне придет команда \textbf{U}, то остаемся в корне, так как предком корня является он сам.
Пусть имеется другая строка инструкций \textbf{T}. Стартуя с вершины, в которой мы остановились после выполнения строки инструкций \textbf{S}, будем выполнять команды строки \textbf{T}. Однако теперь мы можем пропускать любое количество инструкций из \textbf{T} (и даже все). Необходимо определить во сколько различных вершин можно попасть, выполняя команды из \textbf{T} (и пропуская их в любом порядке).
Например:
Пусть \textbf{S} = \textbf{L} и \textbf{T} = \textbf{LU}. Ответ равен \textbf{3}. Обработав \textbf{S}, мы остановимся в левом сыне корня. Обработать инструкции из \textbf{T} можно \textbf{4 }вариантами:
\begin{enumerate}
\item Пропустить все буквы: остаемся в той же вершине.
\item Пропустить \textbf{L} и выполнить \textbf{U}: окажемся в корне.
\item Выполнить \textbf{L} и пропустить \textbf{U}: окажемся в левом сыне текущей вершины.
\item Выполнить \textbf{L} и \textbf{U}: остаемся в той же вершине, как в случае \textbf{1}.
\end{enumerate}
Так как мы можем попасть в \textbf{3} различные вершины после выполнения \textbf{T}, то ответ равен \textbf{3}.
\InputFile
Первая строка содержит количество тестов \textbf{n} (\textbf{n }≤ \textbf{15}). Каждый тест состоит из двух непустых строк. Первая строка содержит набор инструкций \textbf{S}, а вторая набор инструкций \textbf{T}. Строки не содержат никаких других букв кроме \textbf{L}, \textbf{R} или \textbf{U}. Длины строк не более \textbf{100000}.
\OutputFile
Для каждого теста вывести его номер и количество достижимых вершин. Поскольку ответ может быть большим, вывести его по модулю \textbf{21092013}.
Входные данные #1
2 L LU L L
Выходные данные #1
Case 1: 3 Case 2: 2