### PROBLEM LINK:

**Author:** Dymtro Berezein

**Testers:** Istvan Nagy

**Editorialist:** Praveen Dhinwa

### DIFFICULTY:

Easy

### PREREQUISITES:

basic combinatorics, even-odd parity understanding

### PROBLEM:

You have an array A of n integers. You can choose some element in the array and multiply it by -1. You have to do this operation total K times. Find the number of different arrays you can end up with.

### QUICK EXPLANATION:

The basic idea of the problem is to choose some elements in the array and multiply by -1’s. Remaining operations can be done on a single element by making sure that its parity is not changed. If there exists a zero element in the array, the remaining operations can always be done on that element. In this case, the condition of making sure parity is unchanged is implicitly satisfied.

### EXPLANATION:

Notice that the elements of the final array will be either same, or multiplied by -1. This means, that we can replace each number in the array with 0 (if the element is zero), 1 (if the element is positive), -1 (if it is negative).

The basic idea of the problem is to choose some elements in the array and multiply by -1’s. Remaining operations can be done on a single element by making sure that its parity is not changed. If there exists a zero element in the array, the remaining operations can always be done on that element. In this case, the condition of making sure parity is unchanged is implicitly satisfied.

So, we will check whether we can change only some x non-zero elements. If there exists a zero element in the array, then it can always be done. Otherwise, if K - x is even, then also it can be done by applying the operation on same element multiple times. Number of ways of choosing x elements out n elements is denoted by C(n, k) which can be found by precomputing factorials and finding inverse modulo a number.

### Time Complexity:

\mathcal{O}(n) or \mathcal{O}(n \, log n) if you are finding inverse modulo in each call of C(n, k)