Define $a_n = b_n+2^n$. We find that the sequence $(b_n)_{n\ge 1}$ obeys the recursion \[ b_{n+3} - 7b_{n+2}+11b_{n+1}-5b_n=0, \]with initial values $b_1=0$, $b_2=16$ and $b_3=48$. The characteristic equation of $b_n$ is $\lambda^3-7\lambda^2+11\lambda-5=0$, with roots $\lambda =5$ and a double root at $\lambda=1$. So, $b_n=a\cdot 5^n + b+cn$ for some $a,b,c$. Solving, we find $a=1/5$, $b=-13$ and $c=12$. Thus, \[ a_n = 5^{n-1}+2^n +12n-13. \]With this, integrality is immediate. Set $p=673$, note that $p$ is a prime. By Fermat, $5^{p-1}\equiv 1\pmod{p}$ and $2^p\equiv 2\pmod{p}$. So, $a_p \equiv 1 + 2-13 \equiv -10\pmod{p}$.