合成游戏
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小蓝同学在玩一个养成类游戏,他的梦想是收集到所有的卡牌。现在小蓝同学手上有  张不同的一级卡牌,在这个游戏中相同等级的两张卡牌可以合成一张新的卡牌,且新合成的卡牌等级提升  ,只要合成所使用的卡牌不一样,那么合成出来的卡牌也不一样,比如说 a , b , c , d 是四张不一样的且等级相同的卡牌,那么  , , , , ,   ('+' 表示前后两张卡牌合成) 都会产生一张全新的卡牌,用这些全新的卡牌去合成又会产生一些新的卡牌,对于将要合成的两张卡牌来说,合成的结果与放入顺序无关,  与  合成的结果一样,但是对于一个更高等级的卡牌来说,它由 a , b , c , d  四张同级卡牌而来,但是由于次级卡牌的合成结果不同最后产生的卡牌也不相同,即   与 不同。
小蓝同学是一个手残党,只要有能合成的卡牌他就会将他们合成,直到所有卡牌之间都不能合成为止。小蓝同学想知道最后他手上剩下的卡牌有多少种可能。只要存在一张卡牌种类或者等级不同则视为不同的结果。该结果可能很大,所以你只需要输出答案对  取模的结果。

输入描述:

本题包含多组测试样例，第一行包含一个正整数 t  表示  组数据。
每组数据一行包含一个整数 n  表示开始时一级道具的数量.

输出描述:

t 行,每行一个整数表示答案对  取模的结果。
示例1

输入

复制 
5
1
2
3
4
5

输出

复制 
1
1
3
3
15

说明

 等于  时,假设初始卡牌分别为 a, b , c 。
最后可能的结果为:
1 . \{a+b\} , c
2 . \{a+c\} , b
3 . \{b+c\} , a
 等于 4 时,假设初始卡牌分别为 a , b , c , d  。
最后可能的结果为:
1 . \{a+b\} + \{c+d\}
2 . \{a+c\} + \{b+d\}
3 . \{a+d\} + \{b+c\}