問題一覧 > 通常問題

No.368 LCM of K-products

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 136
作問者 : 🍡yurahuna🍡yurahuna / テスター : 🐬hec🐬hec
4 ProblemId : 1048 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-05-02 03:16:27

問題文

$N$ 個の正整数からなる数列 $A = \{a_1, a_2, \dots, a_N\}$ があります。
$A$ の添字が異なる $K$ 個の要素の積からなる集合を $B$ とします。
このとき、$B$ の全要素の最小公倍数を $10^9 + 7$ で割った余りを求めてください。

入力

$N$ $K$
$a_1$ $a_2$ ... $a_N$

1行目には数列 $A$ の要素数 $N (1 \leq N \leq 1000)$ および $K (1 \leq K \leq N )$ がスペース区切りの整数で与えられる。
2行目には数列 $A$ の要素 $a_i (1 \leq i \leq N, 1 \leq a_i \leq 10^9)$ がスペース区切りの整数で与えられる。

出力

答えを1行で出力し、改行してください。

サンプル

サンプル1
入力
3 2
2 3 5
出力
30

この例では $B = \{ a_1 \times a_2, a_1 \times a_3, a_2 \times a_3 \} = \{6, 10, 15\}$ となります。
$B$ の全要素の最小公倍数は30です。

サンプル2
入力
3 2
2 4 8
出力
32

$B = \{8, 16, 32\}$ です。

サンプル3
入力
4 3
2 2 2 2
出力
8

$B = \{ a_1 \times a_2 \times a_3, a_1 \times a_2 \times a_4, a_1 \times a_3 \times a_4, a_2 \times a_3 \times a_4 \} = \{8, 8, 8, 8\}$ です。
$B$ の作られ方に注意してください。

サンプル4
入力
3 1
2016 4 11
出力
22176

$K = 1$ なので、$B = \{ a_1, a_2, a_3 \} = \{2016, 4, 11\}$ です。

サンプル5
入力
10 7
832 223 29375 10 447239 999299573 5272 829829 6265 33
出力
738866291

$10^9 + 7$ で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。