Республиканская олимпиада по информатике 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} $L$, $C$, $R$, $S$, $*$ символдарынынан тұратын, ұзындығы $N$-ға тең жолды маршруттың шаблоны деп атайық. Маршруттың бірінші төбесі ағаштың түбірі болады. Жолдың әр символы келесі қадамда қайда жүру керек екенін көрсетеді:

• $L$ — сол ұрпағына
• $C$ — ортаңғы ұрпағына
• $R$ — оң ұрпағына
• $S$ — орында тұру
• $*$ — алдыңғы символдардың ($L$, $C$, $R$, $S$) кез-келгені

Жолдың бағасы деп жолдағы төбелердегі сандардың қосындысы (әрбір төбе бір рет саналады). Сізге осы берілген шаблон бойынша өтуге болатын маршруттардың бағаларының қосындысын табу керек.

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

Енгізу файлда ұзындығы $1$-ден $2000$-ға дейін болатын жол — маршруттың шаблоны берілген.

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

Шығыс файлда бір сан — есепке жауап шығарыңыз.

Пример:

Вход

*LS

Ответ

55

$50$ баллды аспайтың тесттердің жиынында $N \le 14$ кепілдік беріледі.