There is a chain of $$$n$$$ nodes with edges between nodes $$$u$$$ and $$$v$$$ such that $$$|v - u| = 1$$$. For each node $$$i$$$ ($$$1 \le i \le n$$$), you will keep it with probability $$$\frac{1}{i}$$$ or delete it with probability $$$1 - \frac{1}{i}$$$. Find the expected number of connected components after all the deletions, modulo $$$10^9+7$$$.
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ $$$(1 \leq t \leq 2 \cdot 10^5)$$$ — the number of test cases.
Each test case contains one line consisting of a single integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$ — the number of nodes in the chain.
—
Tests in subtasks are numbered from $$$1-10$$$ with samples skipped. Each test is worth $$$\frac{100}{10}=10$$$ points.
Test $$$1$$$ satisfies $$$1 \leq n \leq 15$$$.
Tests $$$2-3$$$ satisfy $$$1 \leq n \leq 100$$$.
Tests $$$4-5$$$ satisfy $$$t=1$$$.
The remaining tests do not satisfy any additional constraints.
For each test case, print a single integer — the expected number of connected components after all deletions. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{a}{b}$$$, where $$$a$$$ and $$$b$$$ are integers. Output the integer equal to $$$a \cdot b^{-1} \text{ mod } 10^9+7$$$.
41234
1 1 166666669 333333337
For the first test case in the sample test, $$$n=1$$$, so there is one node that you keep with probability $$$\frac{1}{1}=1$$$, so there can only be $$$1$$$ connected component in the final graph.
In the second test case in the sample test, $$$n=2$$$, so you keep node $$$1$$$ with probability $$$\frac{1}{1}=1$$$ and node $$$2$$$ with probability $$$\frac{1}{2}$$$. Whether node $$$2$$$ is kept or not, there will be $$$1$$$ connected component.
—
Problem Idea: willy108, Yam
Problem Preparation: Yam
Occurrences: Novice I, Advanced C
