Cho một số nguyên ~M~ được biểu diễn bởi tích của ~N~ số nguyên dương ~A_1, A_2, ..., A_N~.

Đếm số cách phân tích số nguyên dương ~M~ thành tích của ~K~ số nguyên dương (không nhất thiết phân biệt) ?

Ví dụ ~N = 3, A[] = \{1, 3, 5\}~ và ~K = 2: M = 1 \times 3 \times 5 = 15~, có ~4~ cách phân tích số ~15~ thành tích của ~2~ số nguyên dương là ~[1,15], [3,5], [5,3]~ và ~[15,1]~.

Input

• Dòng đầu tiên chứa số bộ test ~T~ ~(1 \le T \le 100)~.

• Tiếp theo là ~T~ bộ test, mỗi bộ test bao gồm:

  • Dòng đầu tiên chứa ~2~ số nguyên dương ~N~ và ~K~ ~(1 \le N, K \le 500)~.

  • Dòng thứ hai chứa ~N~ số nguyên dương biểu diễn dãy ~A~ ~(1 \le A_i \le 10^9)~.

Output

Gồm ~T~ dòng, mỗi dòng là số cách phân tích sau khi chia dư ~10^9+7~.

Sample Input 1

1
3 2
1 3 5

Sample Output 1

4