Mock AIME 3 2006-2007 Problems/Problem 15

Let N be the number of integers n such that 0<=n<k where k=2^3*5^2*3^4 such that there exists an integer a such that when a^2 is divided by k it leaves remainder n. Find the remainder when N is divided by 1000.