题目描述

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

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

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

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

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

输入格式

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

对于每组数据：

第一行两个整数 $n,k$。

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

输出格式

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

2 
3 1
neo
10 2
babylonian

1
2

数据范围

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

对于 $60\%$ 的数据，$1\leq T\leq 10^4$，$1\leq n\leq 10^6$，$1\leq k\leq \min(n,20)$。

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