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(\mathrm{mod}1234567891)$.

For $n={10}^{18}+3$, find $a_{n}mod1234567891$.