Мирас пишет олимпиаду по программированию, и он уже дошёл до задачи $$$B$$$! Но продолжить ему не дают первокурсники, которые пришли к нему просить помощи с упражнением на тему «Форма Бэкуса–Наура» (Backus–Naur Form). Вот условие упражнения:

Дана формула, описывающая множество строк в алфавите $$$\{a, b, c\}$$$: $$$$$$ \lt string \gt ::= \{a | b\} c \{a | b\}$$$$$$ Подсчитать количество строк длины $$$n$$$ в данном множестве слов.

Мирас согласился помочь и уже объяснил условие задачи:

1. Запись $$$\{word\}$$$ обозначает конкатенацию (присоединение) нескольких строк $$$word$$$, то есть $$$$$$\{word\} = word^k,$$$$$$ где $$$k = 0, 1, \dots$$$. Например, $$$\{ab\}$$$ обозначает слова: пустое, $$$ab$$$, $$$abab$$$, $$$ababab$$$ и т.д.
2. Запись $$$word_1 | word_2$$$ обозначает альтернативу из двух вариантов: $$$word_1$$$ или $$$word_2$$$. Например, $$$ab | ba$$$ обозначает одно из двух слов: $$$ab$$$ или $$$ba$$$.

В частности, заданное множество содержит строку $$$baacab$$$. Помогите первокурсникам решить их упражнение, чтобы Мирас не отвлекался и всё-таки сдал задачу $$$B$$$!