Putnam 2004 A4

Show that for any positive integer $n$ there is an integer $N$ such that the product $x_1 x_2 \cdots x_n$ can be expressed identically in the form $$x_1 x_2 \cdots x_n = \sum_{i=1}^N c_i ( a_{i1} x_1 + a_{i2} x_2 + \cdots + a_{in} x_n )^n$$ where the $c_i$ are rational numbers and each $a_{ij}$ is one of the numbers $-1, 0, 1$.