No.368 LCM of K-products

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 74
作問者 : 🍡yurahuna🍡yurahuna / テスター : 🐬hec🐬hec

3 ProblemId : 1048 / 出題時の順位表

問題文

$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$ で割った余りを出力してください。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。