Vowels

You are given an Integer N.

You have to find how many different strings of length N can be made using Vowels (a, e, i, o, u) only and by following given rules :

‘a’ can only be followed by ‘e’ and ‘i’.

‘e’ can only be followed by ‘i’.

‘i’ can only be followed by ‘a’, ‘e’, ‘o’, and ‘u’.

‘o’ can only be followed by ‘a’ and ‘u’.

‘u’ can only be followed by ‘o’ and ‘e’.

for example N = 2

strings starting with 'a' of length 2 are:
    1. "ae"
    2. "ai"
strings starting with 'e' of length 2 are:
    1. "ei"
strings starting with 'i' of length 2 are:
    1. "ia"
    2. "io"
    3. "iu"
    4. "ie"
strings starting with 'o' of length 2 are:
    1. "oa"
    2. "ou"
strings starting with 'u' of length 2 are:
    1. "uo"
    2. "ue"

so total number of strings can be made using vowels and following above rules will be 11.


Input Format

Given the only argument N of type Integer.

Output Format

Return a single Integer X mod (1e9 + 7), i.e number of Strings that can be made using vowels and following above rules.

Constraints

1 <= N <= 1e5
strings will have only lowercase letters.

Example

Example Input:
   N = 1
    
Example Output:
	5

Explanation:
	Strings of length 1 are :
	1. "a"
	2. "e"
	3. "i"
	4. "o"
	5. "u"

Example Input:
   N = 2
    
Example Output:
	11

Explanation:
	as explained above.
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Vowels on Interview Code Editor
Sign Up
to access hints and editorial solutions for Vowels

Discussion


Loading...
Click here to start solving coding interview questions