Республиканская олимпиада по информатике 2009 год

Задача D. Путь в дереве

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Бесконечным троичным деревом назовем дерево, каждая вершина которого имеет ровно $3$ потомка. В вершинах дерева написаны числа по следующему правилу:

• в корне дерева написано $1$;
• пусть в некоторой вершине написано $X$, тогда в левом сыне этой вершины будет написано $X \cdot 3$, в среднем — $X \cdot 3 + 1$, в правом — $X \cdot 3 + 2$.

\includegraphics[width=150mm,height=40mm,trim=-130mm 200mm 0 0,clip]{images/ternary.eps} Шаблоном пути назовем строку длины $N$, состоящую из символов $L$, $C$, $R$, $S$, $*$. Первой вершиной пути является корень дерева. Каждый символ строки показывает, куда следует идти на очередном шаге:

• $L$ — в левого сына
• $C$ — в среднего сына
• $R$ — в правого сына
• $S$ — стоять на месте
• $*$ — означает любой из предыдущих символов ($L$, $C$, $R$, $S$)

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

Формат входного файла

Входной файл содержит строку длиной от $1$ до $2000$ символов — шаблон пути.

Формат выходного файла

В выходной файл выведите одно число без ведущих нулей — ответ к задаче.

Пример:

Вход

*LS

Ответ

55

Гарантируется, что в некотором подмножестве тестов, суммарно не превышающих $50$ баллов $N \le 14$.