You are given regular -gon. Each vertex of the -gon was randomly colored with one of colors. Your task is to find the number of special subsets of polygon vertices. Each special subset must meet all the requirements:

• The subset must contain at least two vertices.
• If vertices belonging to the subset are erased from the polygon (note, that the adjacent edges of those vertices will also get erased), the remaining vertices and edges form some continuous paths. None of those paths should contain two vertices of the same color.

Please, calculate the number of described special subsets and print it modulo .

Input Format

The first line contains an integer . The next line contains space-separated integers . Integer denotes the color of the -th polygon vertex. All the vertices of the polygon are numbered from to in clockwise order.

You may assume that each was generated randomly, uniformly and independently from other values. For example, you may assume that for each . Where function returns uniform integer from to .

Output Format

Print a single integer the answer to the problem modulo .

Sample Input #1

4
1 1 1 1

Sample Output #1

7

Sample Input #2

4
4 2 3 1

Sample Output #2

11