有一个唯一的整数序列 $a_n$ 使得

• $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}$，其中，如果 $n$ 为偶数，则 $u=1$；如果 $n$ 为奇数，则 $u=2$。

例如，$a_{13}=23321$ 和 $a_{1003}\equiv 231906014(\mathrm{mod}1234567891)$。

对于 $n={10}^{18}+3$，找到 $a_{n}mod1234567891$。