题目描述

在哈利波特的魔法世界中，有一个古老的算术魔法，它能够计算出一系列数字的和，并且能够对一个神秘的数字进行取模。这个神秘的数字是1000000007，它在魔法界中被用来防止魔法能量的溢出。 现在，让我们来探索这个魔法公式。在霍格沃茨魔法学院的算术课上，学生们被教导了一种特殊的魔法公式，用来计算从1加到n的每个数字的和，然后将这个和再进行累加。1+（1+2)+(1+2+3)+......(1+2+3+....+n)，这个公式被称为“累加求和魔法”。 魔法师们各显神通! 最后哈利波特的魔法效率最高，1秒内得到了结果。

输入格式

第一行是一个正整数T代表测试案例的数量。(1<=T<=100) 从第二行到第T+1行，每行是一个正整数n。(1<=n<=1e18)

输出格式

针对每组案例，输出这个数列的前n项累加和%1000000007的结果，然后换行。

输入数据 1

4
1
2
1000
123456789

输出数据 1

1
4
167167000
87997853

Source

比赛题