Cherry Sigma

题号：NC231886
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

嘤嘤最近迷上了会员购，正好趁着年终降价，天天都在买福袋，结果这些福袋开出来的全都是嘤桃，他粗略的估计了一下，若买 $x$ 个福袋，他将得到 $Cherry(x)$ 个嘤桃，他想知道每天他会开出多少个嘤桃？由于这个答案可能会很大，所以嘤嘤想知道 $Cherry(x)$ 对 $1000000007$ 取模后的结果。

$Cherry(x) = \sum_{i=1}^x Lex(x,i)$

$Lex(x,i) = \sum_{j=i}^x Burner(j)$

$Burner(i)=\left\{ \begin{aligned} -i*20000000\ \ \ \ \ \ \ \ \ \ \ i\le0 \\ i\ \ \ \ \ \ \ \ \ \ \ \ 0 < i \le 10^9 \\ i*20000000 \ \ \ \ \ \ \ \ i>10^9 \end{aligned} \right.$

输入描述:

第一行一个整数 $T(1 \le T < 10^5)$ 表示嘤嘤买了 $T$ 天的福袋。

接下来 $T$ 行，每行一个 $x_i(1 \le x_i \le 10^9)$ 表示嘤嘤这天买了 $x_i$ 个福袋。

输出描述:

共  行，每行输出一个对  取模后的整数表示嘤嘤当天开出了多少个嘤桃。

示例1

输入

复制

2
1
1000000000

输出

复制

1
999999916