US-TST 2007 Problem 6

For a polynomial $P(x)$ with integer coefficients, $r(2i - 1)$ (for $i = 1,2,3,\ldots,512$ ) is the remainder obtained when $P(2i - 1)$ is divided by $1024$ . The sequence $$(r(1),r(3),\ldots,r(1023))$$ is called the remainder sequence of $P(x)$ . A remainder sequence is called complete if it is a permutation of $(1,3,5,\ldots,1023)$ . Prove that there are no more than $2^{35}$ different complete remainder sequences.