T144477 组合数问题[HardVersion]
题目背景
送温暖（出题人很良心有木有）
题目描述
给出$n$,求
$$
\sum_{k}\binom{n}{k}(-1)^{k}n\sum_{j=0}^{n}k^j
$$
输入格式
**本题有多组数据**
输入一共$T+1$行。
第一行一个整数$T$，代表样例组数。
接下来$T$行一行一个整数，为$n$。
输出格式
对于每一组数据，输出一个数为答案对$1e9+7$取模的结果
说明/提示
对于$100\%$的数据，$1\le T\le10^5$,$1\le n\le10^6$