408722: GYM103270 L Squeaky Toy War

The doggos of UTPC (Ubiquitous Toy Poodle Committee) are preparing for a war with TAMU (Terrier Alliance of Mischievous Upstarts). Every war has rules, and both sides have agreed to settle individual battles by sending $$$K$$$ canine warriors, armed to the teeth with squeaky toys, to duke it out in the dog park. Squeaky toys can be categorized into one of $$$10^9$$$ types, labeled by integers from $$$1$$$ to $$$10^9$$$ (inclusive), and two squeaky toys of the same type are indistinguishable. Furthermore, every member of UTPC and TAMU owns exactly one squeaky toy weapon.

You are an analyst for UTPC, and have been tasked with considering all possibilities for assembling an army of $$$K$$$ soldiers with their respective squeaky toys. Upper-management believes that every one of the $$$N$$$ members of the organization is effective with their own squeaky toy, and that the difference in armies solely depends on the number of users of each squeaky toy used within it. For example, with $$$K=3$$$, army $$$A = (1, 1, 2)$$$, an army with two users of squeaky toy type $$$1$$$ and one user of squeaky toy type $$$2$$$, would be considered to be the same as army $$$B = (1, 2, 1)$$$. However, armies $$$C = (1, 2, 2)$$$ and $$$D = (1, 2, 3)$$$ would be different from both $$$A$$$ and $$$B$$$.

You quickly realize that the count of possible armies would exceed any canine computational power that you could ever muster, and dogmatically insist that the best estimate for this calculation is finding the number modulo $$$31051$$$. The Council of Poodles accepts your argument, but the task ahead is still not easy!

The first line of input contains two space-separated integers $$$N$$$ ($$$1 \leq N \leq 100000$$$) and $$$K$$$ ($$$1 \leq K \leq N$$$). The second line of input contains $$$N$$$ space-separated positive integers denoting the type of the $$$i$$$-th squeaky toy owned by a member of UTPC. Each of these positive integers is at most $$$10^9$$$ in value.

Output a single integer representing the number of possible distinct armies modulo $$$31051$$$ that the UTPC can field in battle.

4 2
1 2 4 4

4

4 1
2 3 5 7

4

The prime $$$31051$$$ was chosen because $$$WOOF$$$, when written as a sequence of numbers based on $$$1$$$-indexed positions in the alphabet, becomes $$$23-15-15-6$$$, and $$$23*15*15*6+1 = 31051$$$. :)