US-TST 2008 Problem 9

Let $n$ be a positive integer. Given an integer coefficient polynomial $f(x)$ , define its signature modulo $n$ to be the (ordered) sequence $f(1), \ldots , f(n)$ modulo $n$ . Of the $n^n$ such $n$ -term sequences of integers modulo $n$ , how many are the signature of some polynomial $f(x)$ if a) $n$ is a positive integer not divisible by the square of a prime. b) $n$ is a positive integer not divisible by the cube of a prime.