Codeforces ラウンド #157 (ディビジョン 1) C. 小さなゾウと LCM (数学、DP)_PHP チュートリアル

Codeforces Round #157 (Div. 1) C. Little Elephant と LCM （数学、dp）

こぞうさんは、空ではない正の整数の LCM (最小公倍数) 演算が大好きです。 k 正の最小公倍数演算の結果 整数x1,?x2,?...,?xkは 各数値 xi.

一連の整数b1,?b2,?...,?bnがあると仮定しましょう。 それらの最小公倍数を lcm(b1,?b2,?...,?bn) と表すことにします。 それらの最大値は max(b1,?b2,?...,?bn) となります。 子ゾウは、lcm(b1,?b2,?...,?bn)?=?max(b)の場合、シーケンスbが良好であるとみなします。 1、?b2、?...、?bn).

こぞうさんは、一連の整数 a1,?a2,?...,?an を持っています。 適切な整数列 b1,?b2,?...,?bn, の数を見つけるのを手伝ってください。 すべての i (1?≤?i?≤?n) にとって、次のようになります 条件が満たされます: 1?≤?bi?≤?ai。 答えはかなり大きくなる可能性があるため、1000000007 (109?+?7) で割った余りを出力します。

最初の行には、単一の正の整数 n (1?≤?n?≤?105) — シーケンス a 内の整数の数。 2 行目にはスペースで区切られた n が含まれます 整数 a1,?a2,?...,?an (1?≤?ai?≤?105) — シーケンスa.

1 行に 1 つの整数を出力します。これは、1000000007 (109?+?7) を法とする問題の答えです。