A great THEORY of NUMBER!

The set of $S_j$ is made up of $S_j = [2^{j-1}, 2 \cdot 2^{j-1} - 1] \cup [3 \cdot 2^{j-1}, 4 \cdot 2^{j-1} - 1 ] ... \cup [(2^{2018 - j} - 1)2^{j-1}, 2^{2018 - j} \cdot 2^{j-1} - 1]$ . If we let $T_j = \prod_{i \in S_j} x_i,$ then $P(x_0, x_1, ..., x_{2^{2017} - 1}) = \prod_{1 \leq j \leq 2017} \left (1 - T_j \right )$ . The polynomial is $1$ if all $T_i$ are $0$ and the polynomial is $0$ if at least one $T_i$ is $1$ . Thus, we need to count the number of permutations such that all $T_i$ are zero. We can use complementary counting and PIE. Let $A_i$ denote the set of permutations where $T_i = 1$ and let $P$ be the set of all permutations. We want to compute $X = |P| - \sum |A_i| + \sum | A_i \cap A_j| - \sum |A_i \cap A_j \cap A_k| + ...$ Now observe that $|S_j| = 2^{2016}$ for all $j$ so $|A_j| = 2^{2^{2016}}$ .

Now let's consider $|A_i \cap A_j|$ . WLOG $i < j$ . Let's look at $S_i$ and $S_j$ first. Notice that in each part of $S_j$ (and each "nonpart") half of it is taken up by parts of $S_i$ . Thus, $S_j$ actually fills in half of the gaps. So, there will be $2^{2016} + 2^{2015}$ numbers here in their union. These need to be equal to $1$ . Thus, we obtain that $|A_i \cap A_j| = 2^{2^{2015}}$ .

By similar reasoning, we have that $|A_{a_1} \cap A_{a_2} \cap A_{a_3} \cap ... \cap A_{a_k} | = 2^{2^{2017 - k}}$ .

So actually, we have that $X = \sum_{i = 0}^{2017} (-1)^k \binom{2017}{k} 2^{2^{2017-k}} \equiv 2^{2^{2017}} - 2 \pmod{2017}$ . Let's compute $2^{2^{2017}}$ in modulo $2017$ . We first compute $2^{2017}$ in modulo $2016$ . I think $2016 = 2^5 \cdot 3^2 \cdot 7$ .

So, let $m = 2^{2017}$ we have

$m$ $\equiv 0 \pmod{32}$

$m$ $\equiv 2 \pmod{9}$

$m$ $\equiv 2 \pmod {7}$ Now we use Chinese Remainder Theorem, uh $m \equiv 2 \pmod{63}$

$m \equiv 128 \pmod 2016$ . Now by Fermat's Little Theorem, we want to reduce $2^{128}$ in modulo $2017$ . Thus, the answer is that minus $2$ to get $\boxed{1840}$