Бинарное дерево - древовидная структура данных, где каждый узел имеет не более двух детей, которые являются левым и правым ребенком. Узел, имеющий детей, называется родителем этих детей. Строка с инструкциями состоит из букв \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}.