Очень напряженный момент: n ковбоев стоят по кругу, и каждый направил свой кольт на соседа. Каждый ковбой может направить кольт либо на следующего за ним по часовой стрелке, либо на предыдущего ковбоя. Как и положено в настоящем вестерне — человеческая жизнь не имеет никакой ценности.

Картина меняется ежесекундно! Каждую секунду ковбои оценивают ситуацию, и, если пара ковбоев понимает, что они целятся друг в друга, то они разворачиваются. За одну секунду разворачиваются все такие пары соседних ковбоев, в которых ковбои целятся друг в друга. Все действия во время каждой секунды происходят мгновенно и одновременно.

Обозначим символом «A» ковбоя, который целится в своего соседа по часовой стрелке, а символом «B» — ковбоя, который целится в своего соседа против часовой стрелки. Тогда строка из букв «A» и «B» будет обозначать круг ковбоев, запись производится от первого из них по часовой стрелке.

Например, через одну секунду круг вида «ABBBABBBA» примет вид «BABBBABBA», а круг вида «BABBA» примет вид «ABABB».

Картинка иллюстрирует, как круг «BABBA» преобразуется в «ABABB»

Прошла секунда, и теперь состояние ковбоев описывается строкой s. Ваша задача — определить количество различных состояний, которые через секунду приводят к s. Два состояния считаются различными, если существует ковбой, который в одном состоянии целится в своего соседа по часовой стрелке, а в другом — в своего соседа против часовой стрелки.