配点 : 600 点
問題文
长度 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
- 所有输入均为整数
入力
输入将以以下形式通过标准输入给出。
N K A_1 \ldots A_N
出力
输出答案。
入力例 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