e-olymp
Соревнования

Dynamic programming on Trees - Top Level

Бинарное дерево

Бинарное дерево - древовидная структура данных, где каждый узел имеет не более двух детей, которые являются левым и правым ребенком. Узел, имеющий детей, называется родителем этих детей.

Строка с инструкциями состоит из букв L, R и U. L означает Левый, R означает Правый, а U означает Верх. Их значения будут изложены ниже.

Однажды я нарисовал бесконечно большое бинарное дерево. В этом дереве каждая вершина имела в точности двух детей (левого и правого ребенка), каждый из которых имел отца. В этой задаче отцом корня будем считать сам корень. Я ставлю ручку в корень и следую строке инструкций S. То есть смотрим на ее первый символ и если он равен L, то двигаемся к левому сыну, если он равен R, то двигаемся к правому сыну, если он равен U, то двигаемся к предку. Если в корне придет команда U, то остаемся в корне, так как предком корня является он сам.

Пусть имеется другая строка инструкций T. Стартуя с вершины, в которой мы остановились после выполнения строки инструкций S, будем выполнять команды строки T. Однако теперь мы можем пропускать любое количество инструкций из T (и даже все). Необходимо определить во сколько различных вершин можно попасть, выполняя команды из T (и пропуская их в любом порядке).

Например:

Пусть S = L и T = LU. Ответ равен 3. Обработав S, мы остановимся в левом сыне корня. Обработать инструкции из T можно 4 вариантами:

  1. Пропустить все буквы: остаемся в той же вершине.
  2. Пропустить L и выполнить U: окажемся в корне.
  3. Выполнить L и пропустить U: окажемся в левом сыне текущей вершины.
  4. Выполнить L и U: остаемся в той же вершине, как в случае 1.

Так как мы можем попасть в 3 различные вершины после выполнения T, то ответ равен 3.

Входные данные

Первая строка содержит количество тестов n (n 15). Каждый тест состоит из двух непустых строк. Первая строка содержит набор инструкций S, а вторая набор инструкций T. Строки не содержат никаких других букв кроме L, R или U. Длины строк не более 100000.

Выходные данные

Для каждого теста вывести его номер и количество достижимых вершин. Поскольку ответ может быть большим, вывести его по модулю 21092013.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
2
L
LU
L
L
Выходные данные
Case 1: 3
Case 2: 2
Источник 2013 ACM Southwestern Europe Regional Contest (SWERC), November 17