问题 I: 键帽

部分键帽缺乏职业道德

题目描述

Nyamu 是网络知名键盘侠，她在敲键盘时发现：

如果一个只由小写字母组成的字符串中不存在超过 $k$ 个元音相邻，那么这个字符串就是好串。

Nyamu 想知道长度为 $n$ 的字符串中，有多少个好串。

由于这个答案可能很大，因此你需要将答案对 109+7109+7 取模。

元音共有5个，分别为 'a' , 'i' , 'u' , 'e' , 'o' ，其他字母都为辅音。

第一行输入一个正整数 T（1≤T≤2×105）T（1≤T≤2×105） ，表示数据组数。

对于每一组数据：

在一行中输入两个正整数 n,k（1≤k≤n≤106）n,k（1≤k≤n≤106） ，表示字符串长度，好串定义。

数据保证 ∑n≤5×106∑n≤5×106 。

第一个字符为元音，第二个字符为辅音的字符串有105种。

第一个字符为辅音，第二个字符为元音的字符串有105种。

第一个字符为辅音，第二个字符为辅音的字符串有441种。

105+105+441=651