홀수 두더지들

Axel에게는 수직선 전체에 걸쳐 뻗어 있는 무한한 일차원 정원이 있다. 정원을 관리하는 데 너무 많은 시간을 쓰고 싶지 않기 때문에(무한한 정원은 관리하는 데 상당한 시간이 필요하다) 정원에는 두더지가 가득하다. 정확히 말하면, $x$이 정수(음의 정수도 포함)일 때 모든 위치 $x$에 두더지가 한 마리씩 산다. 위치 $x$에 있는 두더지를 $m_x$라고 부른다.

두더지들이 얌전히 굴며 굴 안에 머무르는 동안에는 Axel도 신경 쓰지 않지만, 이따금 두더지들이 파티를 벌이기로 마음먹으면 모든 것이 엉망이 된다. 두더지 파티는 다음과 같이 진행된다.

• 시각 $t=0$에 몇몇 두더지가 땅 위로 머리를 내밀고 제자리에서 춤을 추며 파티를 시작한다. 이렇게 하는 두더지는 파티에서 활성 상태인 것으로 간주한다.

• 각 시각 $t > 0$마다 모든 두더지는 시각 $t-1$의 파티 상태를 바탕으로 자신이 활성 상태가 될지 아닐지를 결정한다. 두더지들은 홀수를 좋아하므로, 시각 $t-1$에 주변의 활성 상태인 두더지 수가 홀수(1 또는 3)였다면 두더지 $m_i$는 시각 $t$에 활성 상태가 된다. $m_i$의 주변에는 $m_i$ 자신과 오른쪽과 왼쪽으로 각각 한 칸 떨어진 두 이웃 $m_{i-1}$와 $m_{i+1}$가 포함된다.

Axel이 제때 파티를 멈추려면 특정 시각 $t$에 활성 상태인 두더지가 몇 마리일지 알아야 한다. 이를 계산하여 Axel을 도와주자.

점수

여러 테스트 케이스 그룹으로 여러분의 풀이를 테스트한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$20$| $N=1$이고 첫 번째 줄은 정확히 하나의 'A'로 이루어진다.

$2$ |$80$| 추가 제한이 없다.

첫 번째 줄에는 파티가 시작되는 영역을 나타내는 $N$개($1 \leq N \leq 100$)의 문자로 이루어진 문자열이 주어진다. 활성 상태인 두더지는 A`''로, 비활성 상태인 두더지는 .`''로 나타낸다. 이는 파티가 시작되는 영역만을 나타내며, 파티가 이 영역 안에만 머문다는 보장은 없음에 유의하라.

두 번째 줄에는 파티가 지속되는 시간(초)을 나타내는 수 $t$가 주어진다 ($0 \leq t \leq 10^{18}$).

수 하나, 즉 시각 $t$에 활성 상태인 두더지의 수를 출력한다.

다음은 예제 파티를 나타낸 그림이다.

• $t=0$: ..A.AAA..

• $t=1$: .AA..A.A.

• $t=2$: A..AAA.AA