# PROBLEM LINK:

* Author:* Anay Karnik

*Shashwat Chandra, Bharat Goyal, Taranpreet Singh*

**Testers:***Anay Karnik*

**Editorialist:**# DIFFICULTY:

Medium

# PREREQUISITES:

Basics of polynomial expansion, binomial coefficients, modular exponentiation

# PROBLEM:

Let P be a polynomial in n variables given by:

Here n, k and m are positive integers. Find the sum of all coefficients of the terms of the polynomial which have even powers in each of the n variables and output it modulo 10^9 + 7.

# QUICK EXPLANATION:

Find the sum of all values of P(x_1, x_2, \ldots,x_{n}) where x_i \in \{-1, 1\} and divide it by 2^n to find the answer. Find this in O(n \log m) by considering how many times each value repeats.

# EXPLANATION:

Letâ€™s first solve the problem for n = 1. We can divide the terms of the polynomial in 2 categories, terms with even powers and terms with odd powers. We observe that P(1) is the sum of all coefficients of terms of the polynomial and P(-1) is the sum of coefficients of terms with even powers subtracted by the sum of coefficients of terms with odd powers. Thus the required sum will be:

Now letâ€™s try to generalize this for any n. Say we divide the terms of the polynomial in 2^n categories according to the parities of the powers of the n variables

For a particular value of P(x_1,x_2,,x_n) where x_i \in \{1,-1\}, we see that terms of a particular category are either added or subtracted depending on whether the number of variables having odd power in the term and having value = -1 are even or odd respectively.

Consider the sum S of all 2^n values of P(x_1,x_2,\ldots,x_n) where x_i \in \{1,-1\}. Observe that the terms with even powers in all the variables will always be added. Thus, they will appear 2^n times. For terms of any other category, say a category with i > 0 variables having odd powers, the terms will be added if j of these i terms have value -1 where j is a even number. Thus, the terms will be added A times where,

And the terms will be subtracted B times where,

But we know

This has various proofs.

Thus, these terms will be added and subtracted equal number of times and the final sum S will just be equal to 2^n times the sum of coefficients of all terms with even powers in all the variables. Our required sum will then be \frac{S}{2^n}.

We can find S in O(n \log{m}) by observing that the value (k + n - 2i)^{m} appears {n}\choose{i} times.

# SOLUTIONS:

This was my first time setting a problem, so I hope you enjoyed it. I would love to hear your thoughts on it.