题目描述

求C(n,0)*C(n,0)+C(n,1)*C(n,1)…+C(n,n)*C(n,n)，对 $10^9+7$ 取模

输入格式

第一行一个数 $T$

之后每行一个数 $n$

输出格式

对于每组数据输出一个数表示答案

输入样例

5
1
2
100
100000
500000000	

输出样例

2
6
407336795
879467333
643554692

数据规模：

对于30%的数据, $T\le500,n\le10000$

对于80%的数据, $n\le1000000$

对于90%的数据, 保证至多只有1000组数据 $n>10^6$

对于100%的数据, $T\le100000,n\le5\times10^8$ , 保证至多只有1000组数据 $n>10^7$

代码

#include <stdio.h>
int main(){
	int t, n, sum;
	scanf("%d", &t);
	while (t--){
		scanf("%d", &n);
		int *a = new int[n + 1];
		*a = 1;
		for (int i = 1; i < n || i == n; i++){
			for (int j = n - 1; j; j--){
				a[j] = (a[j] + a[j - 1]) % 1000000007;
			}
			a[i] = 1;
		}
		if (n % 2){
			sum = 0;
		}
		else{
			sum = ((long long)(a[n / 2]) * a[n / 2]) % 1000000007ll;
		}
		for (int i = n / 2 + 1; i < n || i == n; i++){
			sum = (2ll * a[i] * a[i] + sum) % 1000000007ll;
		}
		delete[] a;
		printf("%d\n", sum);
	}
	return 0;
}

样例过了，但是会超时，请问怎么样优化代码？