Бінарне дерево
Бінарне дерево — це структура даних, де кожен вузол має не більше двох нащадків: лівого та правого. Вузол, що має нащадків, називається їхнім батьком.
Рядок інструкцій складається з літер 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.