問題文

$N$個の整数$A_{1}, A_{2}, \cdots, A_{N}$と整数$K$が与えられます．

次の2つの条件を満たす，長さ$K$の整数列$P$が何通りあるか求めてください．

• $1 \leq P_{1} \lt P_{2} \lt P_{3} \lt \cdots \lt P_{K-1} \lt P_{K} \leq N$
• ${\rm gcd}(A_{P_{1}}, A_{P_{2}}, \cdots, A_{P_{K}}) = 1$

ただし，答えは非常に大きくなる場合があるため，$10^{9}+7$で割った余りを出力してください．

制約

• $1 \leq N \leq 100$
• $1 \leq K \leq N$
• $1 \leq A_{i} \leq 30$

入力

入力はすべて整数です．

出力

答えを$10^{9}+7$で割った余りを，1行に出力してください．

サンプル

3 2
3 5 9

2

$P = (1, 2)$のとき，${\rm gcd}(A_{1}, A_{2})=1$となり，条件を満たします．

$P = (2, 3)$のとき，${\rm gcd}(A_{2}, A_{3})=1$となり，条件を満たします．

$P = (1, 3)$は，${\rm gcd}(A_{1}, A_{3}) = 3$となり不適です．

よって，$(1,2), (2,3)$の2通りが答えです．

5 3
5 2 10 4 5

8

$P=(1,3,5), (2,3,4)$以外が条件を満たします．