3157:tql的分身

时间限制:3 S   /  内存限制:65536 KB
AC:9   /  Submit:31
问题描述

新年到来之际,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

提示说明

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

相关

TKK寒假赛Round#6


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1