Udda mullvadar

Axel har en oändlig endimensionell trädgård som löper över tallinjen. Eftersom han inte orkar lägga för mycket tid på att sköta om den (en oändlig trädgård kräver en hel del tid) så är den dock full med mullvadar. Närmare bestämt så bor det en mullvad på varje position $x$, där $x$ är ett heltal (även negativa heltal). Vi kallar mullvaden på position $x$ för $m_ x$.

Detta stör inte Axel så länge mullvadarna är lugna och håller sig i sina bon, men då och då så får mullvadarna för sig att börja festa och allting spårar ur. En mullvadsfest går till på följande sätt:

1. Vid tid $t=0$ startar några mullvadar festen genom att sticka upp sina huvuden ovanför marken och dansa på stället. Detta räknas för mullvadar som att vara aktiv i festen.

2. För varje tidpunkt $t > 0$ så bestämmer sig varje mullvad för om de ska vara aktiva eller inte, baserat på hur festen såg ut vid tidpunkt $t-1$. Eftersom de gillar udda tal så kommer mullvad $m_ i$ att vara aktiv vid tidpunkt $t$ om det vid tidpunkt $t-1$ var ett udda antal (1 eller 3) aktiva mullvadar i närheten. I närheten av $m_ i$ räknas dels $m_ i$ själv samt dess två grannar ett steg till höger respektive vänster, $m_{i-1}$ och $m_{i+1}$.

För att Axel ska hinna stoppa festen i tid behöver han veta hur många mullvadar som kommer vara aktiva vid en viss tid $t$. Hjälp honom genom att räkna ut detta.

Indata

På första raden finns en sträng bestående av $N$ tecken som beskriver området där festen startar, "A" för en aktiv mullvad och "." för en inaktiv. Notera att detta bara är området där festen startar, det är inte garanterat att festen stannar inom detta område. Den andra raden består av talet $t$.

Utdata

Skriv ut ett tal på en rad, antalet aktiva mullvadar vid tid $t$.

Delpoäng

• För 20% av poängen så är den första raden alltid ett ’A’ (en enda mullvad startar festen) medan $0 \leq t \leq 10^{18}$.

• För 80% av poängen så gäller det att godtyckligt många mullvadar kan starta festen, $1 \leq N \leq 100$ och $0 \leq t \leq 10^{18}$.

Exempel

Nedan följer en illustration av en exempelfest (Exempelindata 1):

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

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

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

A.AAA
2

6

.
1337

0

.A.A..AAA.AA.A...AAA.A.A.A
537

126