题目描述

给定大小为 $n$ 的集合 $a$，保证其中元素互不相同且均为正整数。

如果我们从中按顺序取出三个元素 $a, b, c$，则共有 $n \cdot (n-1) \cdot (n-2)$ 种不同的选择方案。

现在对于一种选择方案 $(a,b,c)$，定义其权值为 $\Bigl\lfloor\dfrac{a}{b}\Bigr\rfloor\Bigl\lfloor\dfrac{a}{c}\Bigr\rfloor\Bigl\lfloor\dfrac{b}{c}\Bigr\rfloor$。

你需要对所有的选择方案计算权值的总和，你只需输出这个总和对 $2^{32}$ 取模的结果。

注：$\lfloor a\rfloor$ 表示不大于 $a$ 的最大整数。如 $\lfloor 2.4\rfloor=2$、$\lfloor 5\rfloor=5$。

输入格式

第一行，一个正整数 $n$，表示序列的长度。

第二行，$n$ 个正整数 $a_1, a_2, \ldots, a_n$，每个数描述了集合 $a$ 的一个元素，这些数互不相同。

输出格式

输出一行一个整数，表示答案对 $2^{32}$ 取模的结果。

4
1 2 3 4

36

6
8 6 4 2 10 15

268

提示

【样例解释 #1】

对于样例 #1，权值不为 $0$ 的选择方案只有以下几种：

• $(3,2,1)$，权值为 $6$。
• $(4,2,1)$，权值为 $16$。
• $(4,3,1)$，权值为 $12$。
• $(4,3,2)$，权值为 $2$。

因此，样例 #1 的答案为 $6+16+12+2=36$。

【数据范围】

对于 $100\%$ 的数据，$1 \le n, a_i \le 5000$。

本题采用捆绑测试。

特殊性质 A：保证 $a_i=i$。

【提示】

本题中大部分算法都拥有较小的常数，请相信你的复杂度。