Bob 在元音城中遇到了一个难题。

他有一个长度为 n 的小写字符串 S，他的任务是将 S 切成若干个段，使得每段恰好包含 k 个元音。

元音指的是 `a`, `e`, `i`, `o`, `u` 共五个字母，并且保证 S 中的元音数量是 k 的正倍数。

请求出有多少种不同的分段方案。

由于答案可能很大，你只需要求出其对 10^9+7 取模后的值。

第一行一个整数 T 表示数据组数。

对于每组数据：

第一行两个整数 n,k。

第二行一个长度为 n 的小写字符串 S。

对于每组数据，输出一行一个整数表示答案对 10^9+7 取模后的值。

数据范围

对于 40\% 的数据，1\leq T\leq 10，1\leq n\leq 20。

对于 100\% 的数据，1\leq T\leq 100，1\leq n\leq 10^6，1\leq k\leq n，\sum n\leq 10^6，保证 S 中的元音数量是 k 的正倍数。