2338: Gift

Caspar has n diamonds, and each of them has a certain value. He decides to choose some of them to form two groups, one for his girlfriend and the other for his another female friend. To make sure that his girlfriend would be satisfied, Caspar must promise that the least valuable diamond he gives to his girlfriend is more valuable than any of the diamond that the other female friend receives. Besides that, his girlfriend demands that if a diamond is given to one person, all the diamonds of the same value should be given to the person too. Would you help Caspar to calculate the number of the solutions?

There are multiple test cases. 

In each test case, the first line contains an integer n(1<=n<=10000), indicating the number of the diamonds. 

The following line contains n positive integers, which represent the value of each diamond.

For each test case, please print an integer M as the number of the solutions. Notice that M may be very large, so you just have to print M%100007

5
1 1 2 2 3

5

{3} {11}

{3}{22}

{3}{2211}

{22}{11}

{322}{11}