Count Unique Arrays

You are given an array of length \(N\) along with two integers \(K\) and \(M\). Your task is to determine the number of unique arrays that can be formed if you keep exactly \(K\) elements unchanged and replace the remaining \(N-K\) elements with any integer from \(1\) to \(M\) (inclusive). The resulting answer can be calculated using the formula:

[ \binom{N}{K} \times M^{N-K} ]

Note that the provided array is not used in the computation and can be ignored.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \(T\), the number of test cases.
• Each test case consists of two lines:
• The first line contains three integers: \(N\), \(K\), and \(M\).
• The second line contains \(N\) space-separated integers representing the array (which is not used in the computation).

outputFormat

For each test case, output a single line to stdout containing the number of unique arrays that can be formed using the formula:

[ \binom{N}{K} \times M^{N-K} ]

sample

1
5 2 5
2 3 1 4 5

1250