题目描述
小蓝同学在玩一个养成类游戏,他的梦想是收集到所有的卡牌。现在小蓝同学手上有 nnn 张不同的一级卡牌,在这个游戏中相同等级的两张卡牌可以合成一张新的卡牌,且新合成的卡牌等级提升 111 ,只要合成所使用的卡牌不一样,那么合成出来的卡牌也不一样,比如说 aaa , bbb , ccc , ddd 是四张不一样的且等级相同的卡牌,那么 a+ba+ba+b , a+ca+ca+c , a+da+da+d , b+cb+cb+c , b+db+db+d , c+dc+dc+d ('+' 表示前后两张卡牌合成) 都会产生一张全新的卡牌,用这些全新的卡牌去合成又会产生一些新的卡牌,对于将要合成的两张卡牌来说,合成的结果与放入顺序无关, a+ba+ba+b 与 b+ab+ab+a 合成的结果一样,但是对于一个更高等级的卡牌来说,它由 aaa , bbb , ccc , ddd 四张同级卡牌而来,但是由于次级卡牌的合成结果不同最后产生的卡牌也不相同,即 {a+b}\{a+b\}{a+b} +++ {c+d}\{c+d\}{c+d} 与 {a+c}\{a+c\}{a+c} +++ {b+d}\{b+d\}{b+d} 不同。
小蓝同学是一个手残党,只要有能合成的卡牌他就会将他们合成,直到所有卡牌之间都不能合成为止。小蓝同学想知道最后他手上剩下的卡牌有多少种可能。只要存在一张卡牌种类或者等级不同则视为不同的结果。该结果可能很大,所以你只需要输出答案对 109+710^9+7109+7 取模的结果。
输入
本题包含多组测试样例，第一行包含一个正整数 ttt (t≤105)(t\le10^5)(t≤105) 表示 ttt 组数据。
每组数据一行包含一个整数 nnn (1≤n≤105)(1 \le n \le 10^5)(1≤n≤105) 表示开始时一级道具的数量.
输出
t 行,每行一个整数表示答案对 10^9+7109+7 取模的结果。
样例输入 Copy
5
1
2
3
4
5
样例输出 Copy
1
1
3
3
15
提示
n 等于 333 时,假设初始卡牌分别为 aaa, bbb , ccc 。
最后可能的结果为:
111 . {a+b}\{a+b\}{a+b} , ccc
222 . {a+c}\{a+c\}{a+c} , bbb
333 . {b+c}\{b+c\}{b+c} , aaa
nnn 等于 444 时,假设初始卡牌分别为 aaa , bbb , ccc , ddd 。
最后可能的结果为:
111 . {a+b}+{c+d}\{a+b\} + \{c+d\}{a+b}+{c+d}
222 . {a+c}+{b+d}\{a+c\} + \{b+d\}{a+c}+{b+d}
333 . {a+d}+{b+c}\{a+d\} + \{b+c\}{a+d}+{b+c}