There is a unique sequence of integers $a_n$ such that

• $a_1=a_2=a_3=1$, $a_4=2$;
• $a_n^2 = a_{n+2}a_{n-2} + u\cdot a_{n+1}a_{n-1}$, where $u=1$ if $n$ is even and $u=2$ if $n$ is odd.

For example, $a_{13} = 23321$ and $a_{1003} \equiv 231906014 \pmod{1234567891}$.

For $n = 10^{18} + 3$, find $a_n \bmod 1234567891$.