Your task is to construct a building. There are \(N \) people in your city and the \(i^{th}\) person contains a string codeword \(S_i\). Each of them randomly selects a non-empty substring of his codeword and calls this substring \(Flag\). The building is constructed only if all their \(Flag\) 's are palindrome and pairwise identical.

You are not sure whether the building will get constructed. Your task is to calculate the probability that the building is constructed so that you can prepare for the next construction. It can be shown that this probability can be expressed as a fraction \(\frac{P}{Q}\), where \(P\) and \(Q\) are coprime integers, \(P \geq 0\), \(Q > 0\) and \(Q\) is coprime with \(10^9 + 7\). You should compute \((P * Q^{-1}) \mod(10^9 + 7)\), where \(Q^{-1}\) denotes the multiplicative inverse of \(Q\) modulo \(10^9 + 7\).

Input format

First line: A single integer \(N\) denoting the number of people
Next \(N\) lines: A string where the \(i^{th}\) of these lines denote the codeword of the \(i^{th}\)person

Output format

Print a single integer denoting the answer to the problem.

Constraints

\(1 \leq N \leq 10^5\)

\(1 \leq |S_i| \leq 10^6\)

\(\sum_{~i=1}^{~i=N} |S_i| \leq 10^6\)

All codewords consist of only lowercase Latin letters