BOOM! Your daring explosion shook the alien ship, but wasn't enough to break through its hull. Suddenly, an alien storms in and pushes your team down a long hall. They don't seem angry, more... curious. Maybe you've earned their respect?

You are ushered into a dim room, where a single alien stands cloaked in dark robes. The captain, no doubt.

They start communicating in a strange series of bleeps, which you record carefully. After hours of work, you manage to translate their speech into an English string. However, the translation is noisy, and you might have some extra characters due to transcription.

How many ways can you remove zero or more characters from the recorded string to make the word "PEACE"? This value is the aliens' "peacefulness".

Input

The first line consists of a single integer, ~n~ ~(1 \leq n \leq 10^5)~, the number of characters in the alien's monologue.

The next line consists of a single string ~S~ of length ~n~, containing the alien's monologue. This string strictly consists of uppercase, English characters.

Output

Output the number of ways you can remove some set of characters from ~S~ to spell out the word "PEACE".

Example

Input 1

15
HEYPEHELLOAHICE

Output 1

2

"PEACE" can be created in two ways, by removing the following characters from the aliens' speech:

Input 2

5
PEACE

Output 2

1

"PEACE" can only be created one way, by removing no characters.

Input 3

5
AEECP

Output 3

0

The string "PEACE" does not exist in this speech.

Input 4

26
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Output 4

0

Input 5

10
PPEEAACCEE

Output 5

32

Input 6

10
PPPPPPEACE

Output 6

6