题目描述
在比赛中，两人不分胜负，两人玩得非常开心，当然也非常累，于是他们睡了一觉。当他们醒来时，他们发现有一串数字包围了他们：2.2360679774997896964091736687313…乔普一眼认出了这是sqrt(5)的小数部分。大家都知道这是无限不循环小数，所以普雷斯提议计算(3+sqrt(5)) n次幂的整数部分。这可难倒的乔普啊，聪明的你来帮帮乔普吧！
输入
一个整数n，表示n次幂。
输出
结果的整数部分最后3位。如果结果不超过2位，请补足前导0。
样例输入
【样例1】
2
【样例2】
5
样例输出
【样例1】
027
【样例2】
935
提示
【样例说明】
样例1： 3+sqrt(5)的2次方约等于27.41640786，因此整数部分最后3位补足前导0之后是027;
样例2：(3+sqrt（5))^5约等于3935.739820, ，因此整数部分最后3位是935。
【数据范围约定】
30% 2≤ n ≤ 10；
50% 2≤ n ≤ 50；
70% 2≤ n ≤ 10000；
100% 2≤ n ≤ 2000000000。
来源/分类