#t. King's Order

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

英国国王乔治六世有天生口吃（真有，不是编的），所以经常会把单词的尾音拖长。比如说，Let the militaryyy intelligence six come to me.，在这句话中 Militaryyy 这个单词的尾音 y 就被他拖长了两次。

好在乔治六世对于他说出的每一个单词只会拖长尾音，且最多拖长两次。现在军情六处有一件任务交给你：给定乔治六世口中单词的长度，你需要算出乔治六世可能说出的单词的数量（默认字母都是小写）。

注意，这道题中的英语单词和常规的英语单词有所不同：

不存在英语单词中必须有元音的要求（例如 dfgh，在这道题中会被算作一个英语单词）
不存在某些单词本就以两个甚至更多相同字母处于单词结尾的情况（例如employee，这本来是一个英语单词，但是在这道题中会认为这是乔治六世说employe这个单词时口吃拖长了一次尾音）
不存在尾字母不发音的情况（例如单词 intelligence 的最后一个 e 事实上是不发音的，但是在这道题中 intelligencee 和 intelligenceee 也会被认为是乔治六世口吃会说出的单词）

总结一下，你需要统计在确定长度时，满足以下条件之一的全小写字母串的个数：

由于这样的单词数量可能非常多，所以最后你只需要输出对 1000000007 取模的结果。

第一行为一个整数 $T (1 \leq T \leq 10)$ ，即军情六处的询问次数。

往下每一行为一个整数 $n (1 \leq n \leq 2000)$ ，每次提问时给出的乔治六世口中英文单词的长度。

对于每次询问输出一行，为乔治六世口中英文单词的可能个数。

2
2
4

676
456950

长度为 4 的单词，除了 aaaa,bbb,cccc,...,zzzz 都合法。