UNIST는 무엇의 약자일까?

UNIST는 Ulsan National Institute of Science and Technology의 약자이다. 어느 날 원이는 약자가 UNIST가 되는 다른 단어가 있는지 궁금해졌다.

단어 $a$의 길이를 $\operatorname{len}(a)$로 표기하자. $N$개의 단어 $W_1, W_2, \dots, W_N$이 주어질 때, 단어 $W_i$ $(1 \le i \le N)$에서 앞에서 0글자 이상 $\operatorname{len}(W_i)$글자 이하를 택해 만든 문자열을 $P_i$라 하자. 다시 말해, $P_i$는 $W_i$의 길이 $\operatorname{len}(P_i)$인 접두사이다.

$P_i$ $(1 \le i \le N)$들을 적당히 정하여 $P_1+P_2+\dots+P_N$이 UNIST가 되도록 하는 경우의 수를 구해보자. 단, 연산 $+$는 문자열 연결(string concatenation) 연산이다.

첫 줄에 단어의 수 $N$이 주어진다.

이후 $N$개의 줄에 한 줄에 하나씩 $N$개의 단어 $W_1, W_2, \dots, W_N$가 주어진다.

$W_i$ $(1 \le i \le N)$는 1개 이상의 영문 대문자로만 이루어진 문자열이다.

$P_1+P_2+\dots+P_N$이 UNIST가 되도록 $P_1, P_2, \dots, P_N$을 결정하는 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

• $1 \le N \le 100,000$
• $\operatorname{len}(W_i) \le 25$