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