注意

本题需要文件读写（seminar.in / seminar.out）。

如无特殊说明，题目中出现的所有数字均为十进制数字；$\bm{10^{18} - 39}$ 进制数字会以序列的方式写出，如 $\bm{[2, 0, 100]}$ 表示十进制下的 $\bm{2 \times (10^{18} - 39)^2 + 100}$。

请注意，你需要求解的是「取模前最小的和对 $\bm{10^9 + 7}$ 取模的结果」，而非「对 $\bm{10^9 + 7}$ 取模后最小的和」。

作为提示，由 $\bm{10^{18} - 39 = (10^9)^2 - 7^2 + 10 = (10^9 + 7) \times (10^9 - 7) + 10}$ 可知 $\bm{10^{18} - 39}$ 对 $\bm{10^9 + 7}$ 取模的结果为 $\bm{10}$，因此你可以使用 $\bm{10}$ 而非 $\bm{10^{18} - 39}$ 进行计算来避免不必要的溢出问题。

题目背景纯属虚构，不影射现实中的任何个人或团体。

题目背景

>>> [1, 2, 4, 8, 16, 32, 64, 128].sort()
[1, 128, 16, 2, 32, 4, 64, 8]

一个很少有地球人知道的事实是，自 2015 年起，我们的吉祥物 Sleeping Kangaroo 每年 12 月 31 日都会乘飞机前往堪培拉，参加一场由外星人组织的星际 JavaScript 研讨会，与外星人们互相分享各自的 JavaScript 编程经验，并在随后举办的友谊赛中切磋技艺，11 年来受益匪浅。

时间来到 2026 年 1 月 6 日，这是 2025 - 2026 年度第 11 届星际 JavaScript 研讨会日程的第七天，主持人正在揭晓友谊赛的比赛成绩，而整个研讨会也将在第二天结束。

「下面揭晓各题目通过情况！问题 A，提交 4881 人，通过 4880 人……」

「啊？」Sleeping Kangaroo 大吃一惊，因为上次有人没能在友谊赛中通过问题 A 还是在 10 年前的 2015 - 2016 年度第 1 届星际 JavaScript 研讨会。

颁奖典礼结束后，Sleeping Kangaroo 找到了这位倒霉的研讨会会员，开始耐心地帮他复盘。

「我……我只是个 JavaScript 新手，很多知识点还不熟。对于场上的问题 A，我对着那个传进来的正整数数组直接调用了 sort 方法，然后……然后……」

正如你在题目背景开头看到的，JavaScript 对正整数数组的默认排序行为是对这些正整数按一般书写习惯（高位在前，省略前导 0）写成字符串后按字符串的字典序排升序，而不是按照这些正整数的实际大小排升序。

「让我来教教你吧，sort 方法在对数字排序时要用 sort((a, b) => a - b) 来按照数字大小排升序，而不能使用默认的比较方式。举个例子，对于问题 A 的样例……样例……」

咦，题目归档中的样例呢？

题目描述

由于外星人有 $10^{18} - 39$ 根手指，他们使用的 JavaScript 也是基于 $10^{18} - 39$ 进制计数的，并且字符编码中有 $10^{18} - 39$ 种对应的数字字符，字典序从小到大分别是 $0, 1, \ldots, 10^{18} - 40$。（在具体实现中，它们的编码分别为 $10^{18}, 10^{18} + 1, \ldots, 2 \times 10^{18} - 40$，每个数字字符占用 $12$ 字节空间；当然了，这对解题不重要）

问题 A 的样例中包含一个长度为 $n$ 的正整数序列，按数字从小到大分别为 $a_1, a_2, \ldots, a_n$，且其中任意两项不相等。

然而，根据这位会员在赛场上的样例自测记录，他错误地调用了 sort 方法，将这些数字按一般书写习惯（高位在前，省略前导 $0$）写成字符串后按字符串的字典序排升序，最后得到了序列 $\{a_{p_1}, a_{p_2}, \ldots, a_{p_n}\}$，其中 $p_1, p_2, \ldots, p_n$ 是一个 $1, 2, \ldots, n$ 的排列。

Sleeping Kangaroo 知道，现在要是跑去组委会获取样例的话，这位会员会等得不耐烦的。为了方便分析，你能帮 Sleeping Kangaroo 构造一个这样的序列，使得这 $n$ 个正整数的和最小吗？

由于 $\bm{10^{18} - 39}$ 进制数字难以输出，你只需要输出最小的和。

答案对 $\bm{10^9 + 7}$ 取模。

输入格式

第一行一个正整数 $n\ (1 \le n \le 10^5)$。

第二行一个 $1, 2, \ldots, n$ 的排列 $p_1, p_2, \ldots, p_n$。

输出格式

一行一个非负整数表示答案。

答案对 $\bm{10^9 + 7}$ 取模。

样例

10
1 2 3 4 5 6 7 8 9 10

55

10
10 9 8 7 6 5 4 3 2 1

111111113

10
7 9 10 5 8 4 2 1 6 3

223147

样例 1 解释

一个可能的序列 $\{a_n\}$ 是：

• $[1]$
• $[2]$
• $[3]$
• $[4]$
• $[5]$
• $[6]$
• $[7]$
• $[8]$
• $[9]$
• $[10]$

总和为 $[55] = 55$。

样例 2 解释

一个可能的序列 $\{a_n\}$ 是：

• $[2]$
• $[1, 1]$
• $[1, 0, 1]$
• $[1, 0, 0, 1]$
• $[1, 0, 0, 0, 1]$
• $[1, 0, 0, 0, 0, 1]$
• $[1, 0, 0, 0, 0, 0, 1]$
• $[1, 0, 0, 0, 0, 0, 0, 1]$
• $[1, 0, 0, 0, 0, 0, 0, 0, 1]$
• $[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]$

总和为 $[1, 1, 1, 1, 1, 1, 1, 1, 1, 10] \equiv 1{,}111{,}111{,}120 \equiv 111{,}111{,}113 \pmod{10^9 + 7}$。

样例 3 解释

一个可能的序列 $\{a_n\}$ 是：

• $[2]$
• $[1, 1]$
• $[2, 1]$
• $[1, 0, 1]$
• $[1, 0, 0, 1]$
• $[2, 0, 0, 0]$
• $[1, 0, 0, 0, 0]$
• $[1, 0, 0, 1, 0]$
• $[1, 0, 0, 0, 0, 0]$
• $[1, 0, 0, 0, 0, 1]$

总和为 $[2, 2, 3, 1, 4, 7] \equiv 223{,}147 \pmod{10^9 + 7}$。