急急急！大一C语言编程题降低时间复杂度？

Question

这道题要求运行时间在1s内，现在一直是三秒左右，我是大一学生，样例能通过，可就是时间超限，要怎么修改可以降到一秒
代码如下：
#include
#include

int fun(int n) {
long int sum=0;
if(n==1)return 0;
else if(n==2)return 1;
else {
sum=fun(n-1)+2*fun(n-2)+pow(n,3)+2*n+1;
return(sum%1000000007);
}
}
int main() {
int m,n;
scanf("%d",&m);
for(int i=0; i<m; i++) {
scanf("%d",&n);
printf("%d\n",fun(n));
}
return 0;

}

Answer 1

int a = 0;
int b = 1;
for (int i = 2; i <= n; i++)
{
sum=b+2*a+pow(n,3)+2*n+1;
a = b;
b = sum%1000000007;
}