409417: GYM103535 E Link with EQ

We often say that details can reflect the level of one's EQ. For example, at BIT, when students study in classrooms (such as A105 in the General Teaching Building) or on long tables in the library, it is often embarrassing and uncomfortable (and occasionally smelly) if another student suddenly sits next to them, which we call low EQ behavior.

Now, there is a long table containing $$$n$$$ seats, and the BIT students will choose their seats in the following way in order to avoid low EQ behavior as much as possible.

• If the whole table is empty, randomly choose a position to sit.
• Otherwise, choose a position whose shortest distance to other students is maximized. If there are more than one, randomly choose one of them with equal possibility.

When the farthest distance is $$$1$$$ (i.e., he will sit next to a classmate anyway), students will sit at a different table to avoid low EQ behavior, and then we will call the table full.

Now, Link wants to know the expected number of people seated in the table when the table is full.

The input consists of multiple test cases.

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$) – the number of test cases.

For each testcase, there is only one integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) in a single line, which is the length of the table.

For each testcase, output the answer modulo $$$10^9+7$$$.

You may find the way to modulo a rational number in Problem F.

5
1
2
3
4
2021

1
1
666666673
2
420089906