Salman Khan Upcoming Movie

★★★★★

0 votes

String, Dynamic Programming

Details

Problem

Salman Khan has decided to release his upcoming movie on Eid 2020.As there is enough time in release of the movie, So Salman gives a task for his fans to construct the movie name which is $N$ length long and formed using following rules:

Each letter is a vowel, i.e. is in the set { ${ a,e,i,o,u}$ }
The letter $a$ may only be followed by the letter $e$ .
The letter $e$ may only be followed by letter $a$ or $i$ .
The letter $i$ may not be next to another $i$ .
The letter $o$ may only be followed by letter $i$ or $u$ .
The letter $u$ may only be followed by letter $a$ .

Now Salman is exicted to know how many distinct movie names he will got.As the number of distinct movie names may be very large so takes modulo with $10^9+7$ .

Input
The only line contains an integer, $N$ , the length of string.

Output
print an integer that represents the number of distinct movie names possible of length $N$ , modulo $10^9+7$ .

Sample Input

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

start with the string $a$ and build to the right.
$a$ may only be followed by $e$ , so the new string can be $ae (1)$ .
start with the string $e$ and build to the right.
$e$ may only be followed by $a$ or $i$ , so the new string can be $ea$ or $ei$ $(2)$ .
start with the string $i$ and build to the right.
$i$ may not be followed by $i$ , so the new string can be $ia, ie, io, iu (4)$ .
start with the string $o$ and build to the right.
$o$ may only be followed by $u$ or $i$ , so the new string can be $ou$ or $oi$ $(2)$ .
start with the string $u$ and build to the right.
$u$ may only be followed by $a$ , so the new string can be $ua (1)$ .
Total permutations $(1+2+4+2+1) % (10^9+7)$ % $(10^9+7)=10$ .