【样例说明】
样例1：$(3+\sqrt{5}{)}^2\approx 27.41640786$，因此整数部分最后3位补足前导0之后是027;
样例2：$(3+\sqrt{5}{)}^5\approx 3935.739820$, ，因此整数部分最后3位是935。
【数据范围约定】
30%   2≤ n ≤ 10；
50%   2≤ n ≤ 50；
70%   2≤ n ≤ 10000；
100%  2≤ n ≤ 2000000000。