MOUNTAIN OR SEA

Two friends are planning to go on vacation together. Since one of them prefers mountain vacations, while the other prefers seaside vacations, they decide to spend half of their vacation days in the mountains and the other half by the sea. They contact their travel agent, and since their budgets are limited, they ask him to find the cheapest room they can book for each day of the year. Some days, this room is in the mountains, and other days, it's by the sea.

Find how many different ways the two friends can go on vacation for a continuous period of days, staying in the cheapest room each day and ensuring that half of the days are in the mountains and the other half are by the sea.

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that, after reading the location of the cheaper room for each day in the time period of interest, will print the number of different ways the two friends can go on vacation.

Input Files:

The input files with the name mntsea.in are text files with the following structure: The first line contains an integer N (where 1 ~\le~ N ~\le~ 1.000.000), the number of days in the time period of interest. The next line contains N characters, each of which is either 'm' (mountain) or 's' (sea). Each character represents the location of the cheaper room for the respective day.

Output Files:

The output files with the name mntsea.out are text files consisting of a single line with a single integer: the number of different ways the two friends can go on vacation.

Examples of Input - Output Files:

1o

STDIN (mntsea.in)

5
msmsm

STDOUT (mntsea.out)

6

Explanation: The two friends can go on vacation in four ways for a duration of two days and in two ways for a duration of four days.

2o

STDIN (mntsea.in)

10
msmsmssmmm

STDOUT (mntsea.out)

16

3o

STDIN (mntsea.in)

10
ssssssssss

STDOUT (mntsea.out)

16

Explanation: There is no way for the two friends to go on vacation, as there is no available affordable room on the mountain.

Notes:

Formatting: In both the input and the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: mntsea *)

for PASCAL coders

/* USER: username
LANG: C
TASK: mntsea */

for C coders

/* USER: username
LANG: C++
TASK: mntsea */

for C++ coders

/* USER: username
LANG: Java
TASK: mntsea */

for Java coders

# USER: username
# LANG: Python
# TASK: mntsea

for Python coders