17301번 - NC 문자열

문제

2019 shake!의 성사를 위해 바쁘게 뛰어다니던 준서는 문득 엔씨소프트의 NC가 무엇의 약자인지 궁금해졌다. "Next Company", "Next Cinema" 등 자신이 아는 단어를 조합해봤지만, 정답이 무엇인지는 모른다. 어쩌면 N과 C로 시작하는 단어만 사용하는 게 아니라 "nullpoiNter exCeption"과 같은 이름도 가능하지 않을까?

고민하던 준서는 우선 자신이 알고 있는 단어 중 N이나 C가 들어간 단어를 목록으로 나열해보았다. 그 후 목록에 있는 총 N개의 단어로 만들 수 있는 모든 NC 문자열을 적어 엔씨소프트에 문의하기로 했다. 준서가 만들 수 있는 NC 문자열이란 다음과 같다.

• 준서의 목록 중 임의 개수만큼 단어를 고른다.
• 한 문자열에서 같은 단어는 한 번만 사용할 수 있다.
• 고른 단어를 임의 순서로 배치하여 문자열을 만든다.
• 만들어진 문자열에 N과 C가 등장하고, N보다 뒤에 등장하는 C가 있다면 이는 NC 문자열이다.

예를 들어 준서가 알고 있는 단어가 {"NEVER", "ENDING", "CHANGE", "NCSOFT"}라면 이 중 임의 단어를 선택해 배치한 "NCSOFT", "NEVER ENDING CHANGE" 등은 모두 NC 문자열이다. 하지만 "CHANGE ENDING"은 NC 문자열이 아니다.

또한 NC 문자열은 단어 사이를 띄어쓰기 때문에 {"NC", "NCNC", "NCNCNC"}라는 단어가 있을 때 {"NC NCNC", "NCNC NC", "NCNCNC"}는 모두 다른 NC 문자열이다.

준서는 자신이 만들 수 있는 NC 문자열이 얼마나 많은지 궁금해졌다. 준서가 만들 수 있는 NC 문자열의 총 개수를 세어보자. 단, 터무니없이 많은 조합이 생길 수 있으니 1,000,000,007로 나눈 나머지로 계산하자.

입력

첫 줄에 준서가 알고 있는 단어의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.

이후 N 줄에 걸쳐 서로 다른 N개의 단어가 주어진다. 모든 단어의 길이는 1 이상 10 이하이며, 알파벳 대문자로만 구성되어있다. 하나의 단어는 적어도 하나 이상의 N이나 C를 포함한다.

출력

한 줄에 준서가 만들 수 있는 NC 문자열 총 가짓수를 1,000,000,007로 나눈 나머지를 출력한다.

제한

힌트