Формування потягу

Компанія, що займається перевезеннями по залізниці, отримала замовлення сформувати потяг, який складається з певного числа вагонів. Проблема у тому, що у компанії є вагони, випущені у різний час, так що кожен з вагонів може мати один з двох видів зчеплень на кожному кінці. У компанії також є один локомотив.

Зчеплення і для локомотива, і для вагонів позначені літерою $\text{A}$ або $\text{B}$. Повернути вагон чи локомотив протилежною стороною неможливо.

Задано інформацію про вагони і локомотив. Потрібно знайти кількість способів сформувати різні потяги заданої довжини з наявних видів вагонів. Додатковою вимогою є те, що тип зчеплень на кожному кінці сформованого потягу повинен відповідати типу зчеплень локомотива.

Потяги вважаються різними, якщо при їх порівнянні від одного кінця до іншого виявиться хоча б одна відмінність.

Приклад 1. Нехай у компанії є вагони $\text{AA}$, $\text{AA}$, $\text{AB}$, $\text{BA}$, $\text{BA}$ і локомотив $\text{AB}$. У потязі повинно бути $4$ вагони. Із заданих вагонів можна сформувати лише два різних потяги: $\text{BAAAABBA}$ і $\text{BAABBAAA}$. Локомотив можна приєднати до потягу як ліворуч (використовуючи зчеплення $\text{B}$), так і праворуч (використовуючи зчеплення $\text{A}$).

Приклад 2. Нехай у компанії є лише по одному вагону кожного типу ($\text{AA}$, $\text{AB}$, $\text{BA}$, $\text{BB}$) і локомотив $\text{AA}$, а потяг повинен складатись з трьох вагонів. Існує три способи сформувати потяг: $\text{AAABBA}$, $\text{ABBAAA}$ і $\text{ABBBBA}$.