Given ~N~ lowercase strings from ~s_1~ to ~s_n~, you are to take a substring ~p_i~ from each string (substring can be empty), and concatenate them ~p_1+p_2+p_3... p_n~ to form a new string ~t~. How many distinct strings ~t~ can you form, modulo ~10^9+7~?

Input Specification

The first line will contain ~N~ ~(1 \leq N \leq 10^6)~, the number of lowercase strings.

The next ~N~ lines will contain a lowercase string ~s_i~. It is guaranteed that the sum of the length of the strings will not exceed ~10^6~.

Output Specification

Output one integer, representing the number of distinct strings ~t~ that can be formed, modulo ~10^9+7~.

Subtasks

Subtask 1 [30%]

~1 \leq N \leq 10~

The sum of the length of the lowercase strings will not exceed ~10^3~.

Subtask 2 [70%]

No further constraints.

Sample Input 1

2
bbbcc
bb

Sample Output 1

30