This page is still under construction.

Parts of this page are still being built. What you see may change.

Wrong Directions

Time limit1sMemory limit128 MB

Summary
Given a command string of F, L, and R, count the distinct final positions reachable by changing exactly one character to a different one.
Level

Medium7 of 10

Topics
Simulation, Hash map, Prefix sum, Math
Solved
No attempts yet

Problem

Farmer John has a new programmable tractor. To drive it, he types a command string of length NN (1≤N≤100,0001 \le N \le 100{,}000) made up only of the characters F, L, and R. An F moves the tractor forward one unit in the direction it currently faces; an L turns it 90 degrees to the left and an R turns it 90 degrees to the right (turning does not change its position). The tractor starts at the origin (0,0)(0,0) facing north.

After typing his intended command string, Farmer John realizes he mistyped exactly one character, but he cannot remember which one. A mistyped character is one of the two characters other than the one he intended (for example, where he meant to type R, he might have typed F or L instead). Considering every way that exactly one character could have been mistyped, determine how many distinct final positions the tractor could end up at. The direction it faces at the end does not matter.

Input

A single line containing Farmer John's intended command string (its length is NN).

Output

Print a single integer: the number of distinct positions at which the tractor could end up if exactly one character of the command string is mistyped.

Hint

In the sample, Farmer John intended to move forward twice, ending at (0,2)(0,2). Mistyping exactly one character yields four possible strings, FL, FR, LF, and RF, which end at (0,1)(0,1), (0,1)(0,1), (−1,0)(-1,0), and (1,0)(1,0) respectively, for a total of 33 distinct locations.

Examples1

  1. Example 1

    Input
    FF
    
    Expected output
    3