求出 $\left \lfloor \left ( 1+\sqrt 3 \right )^n \right \rfloor \mod 1000$

样例输入 #1
2
样例输出 #1
7


样例输入 #2
12

样例输出 #2
927


样例输入 #3
123456789

样例输出 #3
920

$0 \leq n\leq 10^{12}$

给思路即可，谢谢！