After staying in Wonderland for so long, Alice wants to go back home to catch the next Codeforces Div. 2 round, but the Queen of Hearts has other plans. So, the Queen of Hearts proposes a game for them to play. If Alice wins, she gets to leave, but if she does not, she will stay in Wonderland for one more day, missing out on a potential Grandmaster performance.
In this game, each person will select 2 cards at random from a deck of $$$n$$$ cards, without replacement. The score of a single hand is calculated as the concatenation of the number on the first card and the number on the second card. The winner of the game is the person with the highest score. If the scores are identical, the result is a tie, and neither player wins.
Alice wonders how many different games she will win so that she can prepare herself in advance. Given the numbers in the deck of cards, print out the total number of unique games that she will win. As there can be many winning games, print the result in mod $$$10^9+7$$$.
A game is defined by an ordered set of numbers $$$(c_1,c_2,c_3,c_4)$$$, where $$$c_1$$$ and $$$c_2$$$ are the cards that Alice drew, in that order, and $$$c_3$$$ and $$$c_4$$$ are the cards that the Queen of Hearts drew, in that order. Two games are distinct if there exists an index $$$i$$$ $$$(1\leq i\leq 4)$$$ such that $$$c_i$$$ is different between those games.
The first line contains $$$n$$$ ($$$4\leq n\leq 10^5$$$) — the number of cards.
The second line contains $$$n$$$ unique space-seperated integers $$$a_1, a_2, \dots , a_n$$$ ($$$1\leq a_i\leq 10^9$$$) — the numbers on the cards.
Output a single integer in mod $$$10^9+7$$$, the number of unique games where Alice wins.
41 2 3 4
12
$$$(4,3,2,1)$$$ — Alice gets a score of 43, and the Queen of Hearts gets a score of 21, so Alice wins.
$$$(2,4,1,3)$$$ — Alice gets a score of 24, and the Queen of Hearts gets a score of 13, so Alice wins.
$$$(4,2,1,3)$$$ — Alice gets a score of 42, and the Queen of Hearts gets a score of 13, so Alice wins.
The above games are all unique. In total, there are 12 unique games where Alice wins.
