Let's represent the mirror as a circle with $$$N$$$ points at the circumference. First, one should notice that a circumscribed triangle (triangle whose vertices lie on the circumference of a circle) is a right triangle if only if one side of the triangle is the diameter of the circle. That means, for a single colour, there exists a right triangle with this colour if and only if both of the following conditions are satisfied:
- There exists two diametrically opposite points with this colour.
- This colour occurs in $$$3$$$ or more points.
Let's call a pair of diametrically opposite points as a diameter pair. From the above information, we can see that if we colour the points in a diameter pair with the same colour, all other points must not have that colour. If that condition is satisfied for all diameter pairs, there cannot be a right triangle with the same colour.
Let's find the number of diameter pairs in the circle and the number of points that do not belong to a diameter pair. Let the two values be $$$cntPair$$$ and $$$cntAlone$$$. One can find $$$cntPair$$$ and $$$cntAlone$$$ with two pointers or binary search using the prefix sum of the array $$$D$$$.
To find the number of colouring configurations, we can iterate $$$i$$$ from $$$0$$$ to $$$\min(cntPair, M)$$$. In each iteration, we calculate the number of configurations that have exactly $$$i$$$ diameter pairs with the same colour on both of its points. It is calculated as follows:
- There are $$$\binom{cntPair}{i}$$$ ways to choose which diameter pairs have the same colour.
- Notice that each diameter pair with the same colour must have a different colour from each other. So there are $$$\binom{M}{i} \times i!$$$ ways to choose which colour is assigned to each diameter pair with the same colour.
- There are only $$$M-i$$$ available colours for colouring the remaining points. Each diameter pair with different colours can be coloured in $$$(M-i) \times (M-i-1)$$$ ways and each of the remaining points can be coloured in $$$M-i$$$ ways.
- So the total number of ways is: \begin{align} \binom{cntPair}{i} \times \binom{M}{i} \times i! \times ((M — i) \times (M — i — 1))^{cntPair — i} \times (M — i)^{cntAlone} \end{align}
Time complexity: $$$O((N+M) \log N)$$$