Unique Birdwatching II

Adrian continues to organize and host a birdwatching group for his, local community. However, he has begun to notice something strange happening - every year, the birdwatching season appears to get longer and longer. Already in the previous task there were somehow birdwatching seasons over 10000 days long! Even worse, the problem appears to be accelerating at a rapid rate!

While pondering this curious phenomenon, Adrian receives another request from that same individual from the last task. He makes the same request as last time:

• They can only attend 2 days for birdwatching. The days do not need to be consecutive.
• They do not want to see any of the same birds from their 1st day of birdwatching during their 2nd day of birdwatching.
• They don't care how many birds they see total over the two days, but they don't want to birdwatch on day 1 (on which there will be zero birds).

Again, any two days which satisfy the above conditions are known as a valid pair. The person wants to know how many valid pairs exist from now until the end of the birdwatching season.

Problem Statement

You will be given n, the quantity of days within the birdwatching season, where n=1 corresponds to the first day of Spring. You must then calculate how many pairs of days exist during that time period which share no birds in common yet at least one bird can be seen.

Input Data
The first line will be Q, the quantity of testcases.
Q lines will then follow, each with a single integer n corresponding to the quantity of days within the birdwatching season.

Answer
Should consist of Q space-separated values, corresponding to the total amount of valid pairs in each testcase.
Report all answers modulo 1000000007.

Example

input data:
4
57913
680246
7654321
30303030

answer:
19437772 653973274 803628087 684390903