#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#define LL long long

#define ULL unsigned long long

#define rep(i,j,k) for(int i=j;i<=k;i++)

#define dep(i,j,k) for(int i=k;i>=j;i--)

#define INF 0x3f3f3f3f

#define mem(i,j) memset(i,j,sizeof(i))

#define make(i,j) make_pair(i,j)

#define pb push_back

using namespace std;

const int mod = 1e9 + ;

LL ksm(LL a, LL b) {

    LL ans = ;

    while(b) {

        if(b & ) ans = ans * a % mod;

        a = a * a % mod;

        b >>= ;

    }

    return ans;

}

int main() {

    int n, t;

    scanf("%d", &t);

    while(t--) {

        scanf("%d", &n);

        cout << ksm(1LL * n, 1LL * ( n - )) <<endl;

    }

    return ;

}