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

#include<stdio.h>
#include<math.h>

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;  
}

要是时间在1s内，可是我把样例输入都是3s多，怎样能让时间降下来，代码怎么修改

很常见的递归转非递归
https://blog.csdn.net/veaxen/article/details/69663612
看着自己慢慢弄吧☺☺