1492:tql的分身

时间限制: 3 S | 内存限制: 65536 KB
Accept: 8 | Submit: 30
[提交] [状态] [讨论版]
描述

新年到来之际,tql想给大家拜年,但是要拜年的人数很多,一个一个拜实在是太慢了,所以她想到了一个好主意:分身去拜年。
tql打算用一个长度不超过n、且子序列包含"tql"、仅由小写字母组成的字符串表示自己,只要你能从这个字符串的子序列中找到tql,那么就说明这是tql的分身,那么有多少个字符串满足条件呢?
这个数字可能很大,所以答案要对1e9+7取模。

输入

第一行是一个正整数T代表测试案例的数量。(1<=T<=20)
从第二行到第T+1行,每行是1个正整数n。(1<=n<=1000000)

输出
一个整数,为满足条件的字符串数量对1e9+7 取模的值。
样例输入

2
3
4

样例输出

1
102

HINT

所谓子序列,指一个字符串删除部分字符(也可以不删)得到的字符串。
对于第一组案例长度为3且包含tql的字符串只有tql本身。
对于第二组案例长度为4且包含的tql有4种情况,共有4*26种满足条件的字符串,但存在3种重复的情况,所以满足条件长度为4的字符串有101种,再加上长度为3的1种,共102种。
_tql     t_ql     tq_l      tql_

来源
Hello winter vacation Round#6