Kings-Game

Time Limit: 3 Seconds    Memory Limit: 32768 KB

Design of a game for playing two kings with each other is not easy. The game should be related to their belongings :). A two-king-player game has been designed on a one dimensional board the same as an array of integers. Regardless of how the game is played, each king has finally a pin on a cell. The first king can use all the numbers from the start of the array until his pin and the second king can use the numbers from his pin until the end of the array (one cell may be used by both). The winner is the one who achieve more distinct numbers from his cells. In order to prevent any war, the game should be ended in draw. Can you compute the number of draw states? An state is presented by (P, Q) where P is the index of the first king’s pin and Q denotes the index of the other one. For example, consider zero-indexed array A[0..5] = 3, 5, 7, 3, 3, 5.

There are exactly fourteen draw states:

(1, 4), (1, 3), (2, 2), (2, 1), (2, 0), (3, 2), (3, 1), (3, 0), (4, 2), (4, 1), (4, 0), (5, 2), (5, 1), (5, 0)

 

Input

Each test case starts with N≤100,000 as the size of the board. On the next line N integers are given as the members. The numbers are guaranteed to fit in a 32 bit signed integer. End of the input is indicated by N=0.

Output

For each test case, output the number of draw states on a single line. Since the result may be very large, print it modulo 1,000,000,007 (i.e. 10⁹+7).

Sample Input

6
3 5 7 3 3 5
12
2 6 6 1 3 4 4 5 6 4 4 1
1
1
0

Sample Output

14
5
1

Submit

Source: 12th Iran Nationwide Internet Contest IV