Swaraj and his friends have gone on a drive, they are happy listening to music and chatting with each other on the way. Now they have stoped by an ice cream parlour wanting to eat ice cream.

Each ice cream wrapper has a string written on it$.$

They want to choose the ice cream which makes them happy after reading it's wrapper's string.

The string has only English uppercase letter. Their mood $($happy or sad$)$ changes$($or stays same$)$ when they read an English uppercase letter.

Letters S and D always make them sad, H makes them happy, and every vowel $($AEl OU$)$ flips their mood and other letters do no change to their mood.

Task:

You are given an integer N$,$ among all possible $(26^$N$)$ strings with N uppercase English letters, count all such strings that will make Swaraj and his friends happy after reading it$,$ given they are happy initially$($ le before reading the string$).$ Print the Answer modulo $1$e$9+7.$

Exampe

N$=1$

The strings that will make them happy are: B$,$ C$,$ F$,$ G$,$ H$,$ J$,$ K$,$ L$,$ M$,$ N$,$ P$,$ Q$,$ R$,$ T$,$ V$,$ W$,$ X$,$ Y$,$ Z$.$

The strings $"$A$","$E$","$l$","$O$","$U$"$ shouldn't be counted because their mood is switched, as they are happy initially which is then flipped to sad.

The strings $"$S$","$D$"$ shouldn't be counted as that makes their mood sad.

Answer$=19$

Input:

The function takes a single integer N as input parameter

Constraints:

$15$N$510^15$

Output:

For each test case print the number of strings that will make Swaraj and his friends happy. Print the answer modulo $1$e$9+7.$

Sample Input$/$Output Explanation:

For N$=2,$ there are $403$ such strings: AA$,$ AE$,$ AH$,$ AI$,$ AO$,$ AU$,$ BB$,..,$ RZ$,$ SA$,$ SE$,$ SH$,$ SI$,$ SO$,$ SU$,$ TB$.$ TC$,$ TE$.$ YO$.$ YR$.$ YT$.$ YV$.$ YW YX$.$ YY YZ$,$

ZB$,$ ZG$,$ ZF$,$ ZG$,$ ZH$,$ ZJ$,$ ZK$,$ ZL$,$ ZM$,$ ZN$,$ ZP$,$ ZQ$,$

ZR$,$ ZT$,$ ZV$,$ ZW$,$ ZX$,$ ZY$,$ ZZ$.$ The string $"$AO$"$ is counted because their mood flips twice. Similarly, the string $"$SO$"$ is counted because it $\text{'}$S$\text{'}$ first makes them sad and then $\text{'}$O$\text{'}$ switches their mood

from sad to happy.

For N$=4,$ there are $226291$ such strings.

$[$execution time limit$]0\mathrm{.}5$ seconds $($cpp$)$

$[$memory limit$]1$ GB

$[$input$]$ integer$64$ n

the length of the string

$[$output$]$ integer$64$

the total number of ways Swaraj and his friends can be happy

$[$C$++]$ Syntax Tips

Answer rating: 100% (QA)

Solution to Ice Cream Happiness Problem This problem can be solved using Dynamic Programming DP Let ... View the full answer