CF258C Little Elephant and LCM

小象非常喜欢对非空正整数集合进行最小公倍数（LCM）操作。对于 $k$ 个正整数 $x_{1},x_{2},...,x_{k}$，它们的 LCM 是指能够被每个 $x_{i}$ 整除的最小正整数。 现在有一个整数序列 $b_{1},b_{2},...,b_{n}$。我们记它们的最小公倍数为 $lcm(b_{1},b_{2},...,b_{n})$，最大值为 $max(b_{1},b_{2},...,b_{n})$。如果对序列 $b$ 满足 $lcm(b_{1},b_{2},...,b_{n})=max(b_{1},b_{2},...,b_{n})$，那么称序列 $b$ 是好的序列。 小象有一个整数序列 $a_{1},a_{2},...,a_{n}$。请你帮助他统计有多少个好的整数序列 $b_{1},b_{2},...,b_{n}$，其中对于每个 $i$（$1 \leq i \leq n$）都有 $1 \leq b_i \leq a_i$。由于答案可能很大，请输出答案对 $1000000007$（$10^{9}+7$）取余的结果。

第一行包含一个正整数 $n$（$1 \leq n \leq 10^5$），表示序列 $a$ 的长度。 第二行包含 $n$ 个用空格分隔的整数 $a_{1},a_{2},...,a_{n}$（$1 \leq a_{i} \leq 10^5$），表示序列 $a$。

输出一行一个整数，表示答案对 $1000000007$（$10^{9}+7$）取余的结果。

由 ChatGPT 5 翻译