During its early years, Raushan's Candy Store offered only two flavors of candies - Coconut and Spearmint. The Candy Store is popular for its "2 Coconut 1 Spearmint" promo. You can buy a strip containing one Spearmint candy and two Coconuts for just the price of the Coconuts! Talk about a steal!

Raushan has a machine that packs candies into capsules. These were known as candy strips. He just enters what flavors goes into a strip and the machine does it. But one day, the machine just malfunctioned and packed the candies randomly into one big strip. But that day, a high demand for the promo was met. And Raushan went into a panic.

Now, Raushan's idea is this: instead of throwing away the big strip and start anew, he should just trim the strip so that for every Spearmint candy, there's two Coconut candies in the strip.

For example, if the strip was SSCCSCSCC, he could trim it from the left by removing the two Spearmint candies. Then, trim it from the right and remove one Coconut candy. Thus, he's left with a strip looking like CCSCSC. This strip has one Spearmint candy for every two Coconut candies.

As he recalls the fond memories of his newly-opened shop, he wondered how many ways he could trim each strip so that he could sell the remainder under the "2 Coconut 1 Spearmint" promo.

Input
The first line contains a single integer, which is T.

The second line contains a string of length T, consisting of S and C.

Output
Output a single line containing how many ways he can trim the strips in order to make it sellable under the "2 Coconut 1 Spearmint" promo.

Constraints
1<=N<=10^6