Modding the Digits

Call a number $k$ AP'ED if it is of the form $k=a^b$ with $a$ and $b$ integers such that $a,b\ge2$ , $a\leq9,$ and the representation of $k$ is $\overline{N_1N_2N_3\ldots}$ where $N_1\text{ mod } a\equiv N_2\text{ mod } a\equiv N_3\text{ mod } a\equiv\ldots\neq0.$

Find the smallest AP'ED number.

I came up with this problem at the AP Calculus BC Exam today while playing around with my calculator, waiting for one of the sections to finish.