Polynomial collections!

Clearly $5^{5} > 1500$ .

So at most $P(x)$ can be a polynomial of fourth degree.

$P(x) = a_4x^{4}+a_3x^{3}+a_2x^{2}+a_1x+a_0$ $P(5) = a_4*5^{4}+a_3*5^{3}+a_2*5^{2}+a_1*5+a_0$ $1500 = (a_4*5^{4}+a_2*5^{2}+a_0) + 5(a_3*5^{2}+a_1)$ $1500 = c + 5d$

Now clearly $c$ and $d$ are integers valid in the base 25,ie,they are a number between $0$ and $24$ .Hence we can say that there is a bijection between the number of solutions $\{c,d\}$ and the number of such polynomials possible.

The value of d can clearly range between $0$ and $300$ .and for each value of c there will be corresponding value of d.

Therefore the total number of such polynomials is $300+1 = \boxed{301}$ .

$\textbf{Note:}$ You can arrive at the same solution using generating functions also.

$\textbf{Credits:}$ This problem was inspired by an old Brilliant problem and this solution approach is not mine,someone else did this on the old version of the problem half a year ago..I wish I could remember his name :(.

$P(x)\in \mathbb{Z}[x]$ and $5^5 > 1500 > 5^4$ . So $\deg{P} \le 4$ . Set $P(x)=\sum_{k=0}^4 a_k x^k$ . Then we have $1500=P(5)=625a_4 +125a_3+25a_2 +5a_1+a_0$

Note that each unique solution $(a_0,a_1,a_2,a_3,a_4)\in\mathbb{N}_0^5$ to the above equation yields a unique polynomial. Note that now $0\le a_4\le 2$ , $0\le a_3\le 12$ , $0\le a_2,a_1,a_0\le 24$ . We want the coefficient of $x^{1500}$ in the expansion of the generating function $\begin{aligned} &~&\sum_{k=0}^{2} x^{625k} \sum_{k=0}^{12} x^{125k} \sum_{k=0}^{24} x^{25k} \sum_{k=0}^{24} x^{5k} \sum_{k=0}^{24} x^k \\ &=& \dfrac{x^{1875}-1}{x^{625}-1}\cdot\dfrac{x^{1625}-1}{x^{125}-1}\cdot \dfrac{x^{625}-1}{x^{25}-1}\cdot \dfrac{x^{125}-1}{x^{5}-1}\cdot \dfrac{x^{25}-1}{x-1} \\ &=& \dfrac{(x^{1875}-1)(x^{1625}-1)}{(x^5-1)(x-1)} \\ &=& \dfrac{(x^5)^{375}-1}{x^5-1} \cdot \dfrac{x^{1625}-1}{x-1} \\ &=& \sum_{k=0}^{374} x^{5k} \sum_{k=0}^{1624} x^k \\ \end{aligned}$ And the last expression is the generating function of finding the number of non-negative integer solutions to the equation $a+5b=n$ . Setting $n=1500$ and bounding $0\le b\le 300$ , we have total $\fbox{301}$ solutions.