Farmer John kaufte einen schicken neuen programmierbaren Traktor. Er tippt eine Zeichenfolge der Länge $N$, $1 \le N \le 100,000$, nur aus F, $L$ und $R$. F fährt eine Einheit vorwärts, $L$ und $R$ drehen jeweils links und rechts um $90^\circ$. Der Traktor beginnt im Ursprung $(0,0)$ nach Norden gerichtet.

Nach der Eingabe erinnert FJ sich an genau ein falsch eingegebenes Zeichen, weiß aber nicht welches! Etwa F oder $L$ statt $R$. Zähle die verschiedenen möglichen Endpositionen in der Ebene (die Endrichtung spielt keine Rolle).

Eingabe

• Zeile 1: Farmer Johns beabsichtigte Befehlsfolge.

Ausgabe

• Zeile 1: Zahl der möglichen Endpositionen bei einem vertippten Zeichen.

Beispiele

Eingabe 1

FF

Ausgabe 1

3

Hinweis

Farmer John will zweimal vorwärts fahren, idealerweise bis $(0,2)$.

Die vier falschen Folgen sind FL, FR, LF, RF, mit Endpunkten $(0,1)$, $(0,1)$, $(-1,0)$, $(1,0)$: drei verschiedene Positionen.

Aufgabenautor: Brian Dean, 2012