### PROBLEM LINK:

**Author:** Full name

**Tester:** Full name

**Editorialist:** Oleksandr Kulkov

### DIFFICULTY:

EASY

### PREREQUISITES:

Fermat’s little theorem, modular arithmetics, basic combinatorics

### PROBLEM:

You’re given sequence of distinct integers a_1,\dots,a_N and integer K. For each of its subsequences of size K you have to calculate product of all the elements except for minimum and maximum ones. After that you have to calculate product of these values among all subsequences.

### QUICK EXPLANATION:

Sort the sequence, after that multiply all elements raised to power \binom{N-1}{K-1}-\binom{i-1}{K-1}-\binom{N-i}{K-1} using Fermat’s theorem.

### EXPLANATION:

Since it doesn’t matter in this problem if we consider subsequences or subsets, we can suppose that array is sorted. Now element a_i will occur in \binom{N-1}{K-1} subsequences. Among them in \binom{i-1}{K-1} it will be the maximum element and in \binom{N-i}{K-1} it will be minimum element, so you should subtract these values from \binom{N-1}{K-1} to get number of subsequences in which particular element a_i will actually be counted in product. Now to calculate final product we can raise each element to the power equals to number of subsequences it will be counted in. To do this we’ll use Fermat’s little theorem:

Which is true for prime p and a \neq 0 \pmod p. Since 1=a^0 for any a, we could say that a^x=a^{x \pmod{p-1}}\pmod p. Now the only thing left to do for us is to calculate binomial coefficients modulo p-1. This is not prime number thus we can’t do it by calculating factorials and their reverses in advance but since N is sufficiently small, we can just calculate all binomial coefficients in N^2 using following recurrent formula:

This one is very famous, has many interpretations and can be easily proven. For example, number of ways to choose r items among n can be split between subsets having n-th item and subsets which don’t have it. Number of first ones is \binom{n-1}{r-1} and number of second ones is \binom{n-1}{r}. Given all that you can solve the problem precalculating all binomial coefficients modulo p-1 and using binary exponentiation to raise a_i in corresponding powers. Complexity of whole solution should be O(N^2+N \log p).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.