Recursions in Recursions - 2

${ \begin{aligned} a_{n} & =& 2a_{n-1} + 3 \\ b_{n} &=& b_{n-1} + b_{n-2} \\ \end{aligned} }$

For a positive integer $n$, consider the two recurrence relations above subjected to the conditions $a_1 = 0$ and $b_{1} = b_{2} = 1$.

If the value of the expression $\big(a_{b_{2015}} + 3\big)\big(a_{b_{2016}} + 3\big)$ can be expressed as $p^{b_{q}} \frac{r}{s}$, where $b_{q}$ is one of the terms in the recurrence relations sequence above and $(p, r)$ and $(r, s)$ are pairwise coprime integers.

Find the value of $(p+q+r+s) \bmod {673}$.