Twin Polynomials

Compare coefficients of the same power of $x$.

The coefficient of $x^k$ in $g(x)=\sum_{i=0}^n i\cdot x^{a_i}$ is the sum of all positive indices whose coefficient value is exactly $k$. The $i=0$ term contributes zero, so it does not matter inside $g$.

So a cool polynomial satisfies

$$a_k=\sum_{i>0,\ a_i=k} i$$

for every $0\le k\le n$.

Also, no positive index may have $a_i>n$. If $i>0$ and $a_i>n$, then $g(x)$ has a positive coefficient at degree $a_i$, while $f(x)$ has no such term. Dead.

Key structure

For every $i>0$, exactly one of these happens:

• $a_i=0$;
• $a_i=i$;
• $a_i=j$ and $a_j=i$ for some $j\ne i$.

So every positive index is either sent to zero, fixed by itself, or paired in a 2-cycle. No longer cycles, no weird piles, no polynomial astrology.

Why this is true: take the smallest positive index $m$ that does not fit those cases. Look at the positive indices $j$ with $a_j=m$.

If there are none, then $a_m=0$, so it fits.

If there is exactly one, say $j$, then $a_m=j$. If $j=m$, it is fixed. Otherwise $a_j=m$, so $m$ and $j$ are paired. It fits again.

If there are at least two, then $a_m=\sum_{a_j=m} j>m.$ To make the coefficient equation for this larger value work, it would need support from smaller positive indices. But all smaller positive indices already fit the three-case structure, so they only contribute to $0$, themselves, or their paired partner. They cannot create this new messy value. Contradiction.

Therefore the polynomial problem becomes a graph problem on vertices $1,2,\ldots,n$:

• vertex $i$ can be colored zero, meaning $a_i=0$;
• vertex $i$ can be colored fixed, meaning $a_i=i$;
• vertices $i,j$ can be matched, meaning $a_i=j$ and $a_j=i$.

Vertex $n$ cannot be zero, because the polynomial must have degree $n$, so $a_n\ne 0$.

What about $a_0$? After choosing states for $1..n$, it is forced:

$$a_0=\sum_{i>0,\ a_i=0} i.$$

This is always a valid non-negative integer. It may be bigger than $n$, and that is fine.

Processing fixed input values

For each known $a_i$ with $i>0$:

• if $a_i=0$, force vertex $i$ to be zero;
• if $a_i=i$, force vertex $i$ to be fixed;
• if $1\le a_i\le n$ and $a_i\ne i$, force the matching edge $(i,a_i)$, meaning also force $a_{a_i}=i$;
• if $a_i>n$, impossible.

If one vertex receives two different forced states, the answer is $0$.

After all forced states are processed, count the untouched vertices.

Let $dp_m$ be the number of ways to arrange $m$ labeled free vertices, where each vertex is either a zero singleton, a fixed singleton, or matched with another vertex.

Base cases: $dp_0=1,\qquad dp_1=2.$

For $m\ge 2$, take one vertex:

• make it a singleton: $2$ choices, leaving $m-1$ vertices;
• match it with one of the other $m-1$ vertices, leaving $m-2$ vertices.

So

$$dp_m=2dp_{m-1}+(m-1)dp_{m-2}.$$

If vertex $n$ was already forced to be non-zero, the answer is just $dp_m,$ where $m$ is the number of still-free vertices.

If vertex $n$ is still free, count all arrangements and subtract the bad ones where $n$ is the zero singleton. If there are $m$ free vertices including $n$, then the answer is

$$dp_m-dp_{m-1}.$$

Everything is modulo $10^9+7$.

The total complexity is $O(n)$ per test case after precomputing $dp$ up to $4\cdot 10^5$.