新年到来之际，tql想给大家拜年，但是要拜年的人数很多，一个一个拜实在是太慢了，所以她想到了一个好主意：分身去拜年。tql打算用一个长度不超过n、且子序列包含"tql"、仅由小写字母组成的字符串表示自己，只要你能从这个字符串的子序列中找到tql，那么就说明这是tql的分身，那么有多少个字符串满足条件呢？这个数字可能很大，所以答案要对1e9+7取模。
第一行是一个正整数T代表测试案例的数量。(1<=T<=20)从第二行到第T+1行，每行是1个正整数n。(1<=n<=1000000)
234
1102
所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。对于第一组案例长度为3且包含tql的字符串只有tql本身。对于第二组案例长度为4且包含的tql有4种情况,共有4*26种满足条件的字符串,但存在3种重复的情况，所以满足条件长度为4的字符串有101种，再加上长度为3的1种，共102种。_tql t_ql tq_l tql_