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$ 的正倍数。