weqd gọi 1 số là bình phương giai thừa nếu nó có thể được viết dưới dạng $(k!)^2$.

Bạn được weqd cho bạn 1 dãy số $a$ gồm $n$ số nguyên không âm và 1 số nguyên dương $k$. Nhiệm vụ của bạn là đếm số lượng dãy $p$ độ dài $k$ (không nhất thiết liên tiếp) thỏa mãn:

• $p$ là dãy con (không nhất thiết liên tiếp) của tập {$1,2,\dots,n$}
• Gọi $A=(a_{p_1}+a_{p_2})\times (a_{p_1}+a_{p_2}+a_{p_3})\times \dots \times(a_{p_1}+a_{p_2}+\dots+a_{p_k})$ và $B=(\frac{1}{a_{p_1}}+\frac{1}{a_{p_2}})\times (\frac{1}{a_{p_1}}+\frac{1}{a_{p_2}}+\frac{1}{a_{p_3}})\times \dots \times(\frac{1}{a_{p_1}}+\frac{1}{a_{p_2}}+\dots+\frac{1}{a_{p_k}})$ thì $A\times B=(k!)^2$

Vì kết quả có thể rất lớn nên bạn hãy xuất kết quả sau khi $mod\ 10^9+7$

3
4 2
1 2 3 4
6 2
1 3 2 2 1 2
4 3
2 1 2 2

0
4
1