The only difference between the easy version and the hard version of the problem is the constraints on $$$n$$$, $$$k$$$, and $$$a_i$$$.
It's the year 2125, and e-archaeologists have uncovered remnants of what they believe was known as the "troll face". They believe that the troll face was represented by a non-degenerate $$$k$$$-sided polygon that could be inscribed in a circle.
So far, the e-archaeologists have discovered $$$n$$$ line segments, each of which has a length $$$a_i$$$. Now, the e-archaeologists are wondering: how many $$$k$$$-size subsets of their $$$n$$$ line segments could be used to create a troll face? Output your answer in mod $$$10^9+7$$$.
Consider all line segments to be unique, even if 2 have the same length.
The first line of input contains 2 integers, $$$n$$$ and $$$k$$$ ($$$3\le k\le n\le 100$$$) — the number of line segments and the number of sides in a troll face, respectively.
The second line of input contains $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^4$$$) — the lengths of the $$$n$$$ line segments.
Output a single integer in mod $$$10^9+7$$$, the number of $$$k$$$-size subsets that could be used to create a troll face.
5 31 2 3 3 3
7
6 41 5 2 3 4 1
12
In the first test case, there are 7 unique subsets (Note that all the 3's are considered to be distinct):
