← 返回题目列表

AtCoder · nadafes2022_day2_i

I. GCD LCM产品

中文机器翻译题面 查看原题

配点 : 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