問題文

長さ N の正整数列 A = (A_1, \dots, A_N) と N の正の約数 K が与えられます。(1, 2,\dots, N) を並べ替えて得られる数列 P に対し、以下のように P のスコアを定めます。

i = 1, \dots, N に対し、B_i = A_{P_i} と定める。
i = 1, \dots, \frac{N}{K} に対し、G_i = \gcd(B_{(i - 1)K + 1}, B_{(i - 1)K + 2} \dots, B_{iK}) と定める。
\mathrm{lcm}(G_1, \dots, G_{\frac{N}{K}}) が P のスコアである。

P としてあり得るものは N! 通りありますが、それら全てに対する P のスコアの総積を \bold{10^9 + 7} で割った余りを求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• K は N の正の約数
• 1 \leq A_i \leq 2 \times 10^5
• 入力は全て整数

入力例 1

4 2
1 2 3 4

出力例 1

256

例えば、P = (2, 4, 1, 3) のスコアは次のように計算できます。

B = (2, 4, 1, 3) である。
G = (\gcd(B_1, B_2), \gcd(B_3, B_4)) = (2, 1) である。
P のスコアは \mathrm{lcm}(G_1, G_2) = 2 である。

入力例 2

9 3
12 6 8 9 10 16 4 18 15

出力例 2

822906664