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

Бінарне дерево — це структура даних, де кожен вузол має не більше двох нащадків: лівого та правого. Вузол, що має нащадків, називається їхнім батьком.

Рядок інструкцій складається з літер $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$.