While busy running around to make the 2019 shake! a success, Junseo suddenly wondered what the "NC" in NCSOFT stands for. He tried combining words he knew, such as "Next Company" or "Next Cinema," but he didn't know the correct answer. Perhaps it isn't limited to words starting with N and C; could names like "nullpoiNter exCeption" also be possible?

After pondering this, Junseo first listed all the words he knew that contained either an N or a C. He then decided to write to NCSOFT with all possible "NC strings" that could be formed using the $N$ words in his list. An NC string that Junseo can create is defined as follows:

• Choose an arbitrary number of words from the list of words Junseo knows.
• Each word can be chosen at most once in a single string.
• Arrange the chosen words in any order to form a string.
• A string is an NC string if it contains both N and C, and there is at least one C that appears after an N.

For example, if Junseo's word list is {"NEVER", "ENDING", "CHANGE", "NCSOFT"}, then strings like "NCSOFT" or "NEVER ENDING CHANGE" formed by selecting and arranging these words are all NC strings. However, "CHANGE ENDING" is not an NC string.

Also, since NC strings include spaces between words, if the list contains {"NC", "NCNC", "NCNCNC"}, then {"NC NCNC", "NCNC NC", "NCNCNC"} are all considered different NC strings.

Junseo became curious about how many NC strings he could create. Let's count the total number of NC strings Junseo can make. Since the number of combinations can be extremely large, calculate the result modulo $1,000,000,007$.

Input

The first line contains the number of words $N$ ($1 \le N \le 100,000$) that Junseo knows.

Following this are $N$ lines, each containing a distinct word. All words have a length between $1$ and $10$ and consist only of uppercase English letters. Each word contains at least one N or C.

Output

Output the total number of NC strings Junseo can create, modulo $1,000,000,007$.

Examples

Input 1

4
NEVER
ENDING
CHANGE
NCSOFT

Output 1

55

Input 2

3
NC
NCNC
NCNCNC

Output 2

15