Problem Definition

The task involves processing multiple queries where, for a given integer n, we must compute the sum of squared binomial coefficients: $\sum_{i=0}^{n} \binom{n}{i}^2$. The result should be returned modulo $10^9 + 7$. Constraints allow for n up to $10^6$, necessitating an efficient algorithm.

Naive Approach: Dynamic Programming

For lower constraints, one can utilize Pascal's Identity to compute binomial coefficients via dynamic programming. The recurrence relation is defined as:

dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

By filling a 2D array, we can sum the squares of the n-th row. However, this method has a time complexity of $O(n^2)$ and a space complexity of $O(n^2)$, which fails for large inputs due to memory and time limits.

Optimized Approach: Combinatorial Identity

To handle the upper constraints efficiently, we leverage Vandermonde's Identity. Specifically, the sum of the squares of binomial coefficients for a given n equals the central binomial coefficient:

\sum_{i=0}^{n} \binom{n}{i}^2 = \binom{2n}{n}

Combinatorial Proof: Consider selecting n items from a pool of 2n items. If we divide the pool into two distinct groups of size n, selecting i items from the first group necessitates selecting n-i items from the second group. Summing the product of choices $\binom{n}{i}\binom{n}{n-i}$ for all $i$ yields the total number of combinations $\binom{2n}{n}$.

Implementation Strategy

The problem reduces to calculating $\binom{2n}{n}$ efficiently. We precompute factorials and inverse factorials modulo $10^9 + 7$ up to $2 \times 10^6$. Modular inverses are calculated using Fermat's Little Theorem, optimized by precomputing the inverse of the maximum factorial and iterating backwards.

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;
const int LIMIT = 2000005;

long long fact[LIMIT];
long long inv_fact[LIMIT];

long long mod_pow(long long base, long long exp) {
    long long result = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

void init() {
    fact[0] = 1;
    for (int i = 1; i < LIMIT; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    inv_fact[LIMIT - 1] = mod_pow(fact[LIMIT - 1], MOD - 2);
    for (int i = LIMIT - 2; i >= 0; --i) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    }
}

long long combination(int n, int k) {
    if (k > n || k < 0) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    init();
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << combination(2 * n, n) << '\n';
    }
    return 0;
}

This approach ensures $O(N)$ preprocessing time and $O(1)$ time per query, comfortably handling the constraints where $N \le 10^6$.