Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

Duck Latin

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 256 megabytes
Time limit: 1.0 seconds

The Ducks are trying to send a secret message to Chris so he can rescue them from Thomas' ownership. They have decided to use a code known as 'Duck Latin' to encode their message.

For this question, we define a vowel as any of letters a,e,i,o,u . A consonant is any other letter that is not a vowel. A word is any non-empty sequence of lower-case letters.

'Duck Latin' works as follows:

  • For words that begin with consonants, all letters before the first vowel are placed at the end of the word. Then, uack is added to the end of the word.
    • For example, 'waddle' becomes 'addlewuack', 'train' becomes 'aintruack', and 'q' becomes 'quack'.
  • For words that begin with a vowel, all letters before the first consonant are placed at the end of the word. Then ck is added to the end of the word.
    • For example, 'aqua' becomes 'quaack' and 'a' becomes 'ack'.

But Thomas is extra crafty, and he may have cracked the Duck Latin code! To make sure their message is extra secure, the ducks may encode some words of the message in 'Goose Latin' instead. 'Goose Latin' works as follows:

  • For words that contain vowels, you add a lf (lower-case letters L and F) after each vowel and then add that same vowel again.
    • For example, 'a' becomes 'alfa' and 'honk' becomes 'holfonk'.
  • If there are no vowels, then onk is added to the end of the word.
    • For example, 'h' become 'honk'

Chris want to decode the message. However, some words can be decoded in a number of ways. Additionally, the message could have been corrupted, so some received words might not be valid Goose or Duck Latin. If there are too many possible decodings for the message, then Chris won't be able to figure out what the original message was. For any encoded word in the message, he wants to know how many decodings there are. Do you have what it takes to quack the code?

Input

Each test case consists of a single word from the message.

  • The first line will contain the length of that word, L
    • 1 \le L \le 100,000
  • The following line contains the word. Each word will only contain the lower-case letters a-z.

Output

Output one line containing a single integer, indicating the number of possible translations there are for the respective word. Output a zero (0) to indicate that the word cannot be valid Duck or Goose Latin.

Subtasks

  • Subtask 1 (+15%): L\le500, and every received word ends with 'onk'. This includes the word 'onk' by itself.
  • Subtask 2 (+35%): L\le500, and none of the received words have Duck Latin decodings.
  • Subtask 3 (+30%): L\le500.
  • Subtask 4 (+20%): No further constaints apply.

Sample Explanations

Sample 1

  • There is only one possible Goose Latin decoding of 'honk': 'h'. There are zero possible Duck Latin decodings.

Sample 2

  • There are three possible decodings for 'aintruack', all in Duck Latin: 'train', 'ntrai' and 'raint'.

Sample 3

  • 'blah' is not a valid Duck or Goose Latin word, so there are zero possible decodings.
  • Sample Input 1

    4
    honk
    

    Sample Output 1

    1
    
  • Sample Input 2

    9
    aintruack
    

    Sample Output 2

    3
    
  • Sample Input 3

    4
    blah
    

    Sample Output 3

    0