Problem Statement

Counting Happy Ice Cream Wrapper Strings A group of friends is on a road trip and pulls over at a roadside stand for ice cream. Each cone comes wrapped in paper printed with a string of uppercase English letters, and reading through that string shifts the group's collective mood one letter at a time. The mood-changing rules for each letter are: H: Always makes them happy. S, D: Always makes them sad. Vowels (A, E, I, O, U): Switch the mood to its opposite, so a happy state becomes sad and a sad state becomes happy. Other consonants: Do not change their mood. They start out happy before reading anything. Given an integer N for the wrapper string's length, count how many different strings of that length leave them happy by the time the last letter is read. Print the answer modulo 10 9 + 7 . Input Format A single integer N , representing the length of the string. Output Format A single integer, the count of happy-ending strings, modulo 10 9 + 7 . Constraints 1 ≤ N ≤ 10 5 Examples Input: 1