#include using namespace std; typedef long long ll; ll const mod = 1000000007; int const MAX_N = 3000000; ll fact[MAX_N+1]; void build_factrial(){ fact[0] = fact[1] = 1; for(ll i = 1; i < MAX_N; i++){ fact[i+1] = fact[i]*(i+1)%mod; } } ll extgcd(ll a, ll b, ll& x, ll& y) { ll d = a; if(b != 0){ d = extgcd(b,a%b,y,x); y -= (a/b)*x; } else { x=1; y=0; } return d; } ll inv_[MAX_N+1]; void build_inverse(){ inv_[1] = 1; for(int i = 2; i <= MAX_N; i++){ inv_[i] = inv_[mod%i]*(mod-mod/i)%mod; } } ll mod_inverse(ll n, ll m) { ll x, y; extgcd(n, m, x, y); return (m+x%m) % m; } ll inv(ll n){ if(n <= MAX_N) return inv_[n]; return mod_inverse(n,mod); } ll nPr(ll n, ll r){ if(r < 0 || n < r) return 0; return fact[n] * inv(fact[n-r]) % mod; } ll nCr(ll n, ll r){ if(r < 0 || n < r) return 0; return nPr(n,r) * inv(fact[r]) % mod; } ll nHr(ll n, ll r){ if(n==0 && r==0) return 1; return nCr(n+r-1,r); } int main(){ // build_inverse(); build_factrial(); int T; while(cin >> T){ for(int i=0;i