[Solution] Ela Goes Hiking Codeforces Solution

E. Ela Goes Hiking

time limit per test

2.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

She puts 

𝑛$n$ cannibalistic ants in a line on a long wooden stick. Initially, the ants have the same weight of 1$1$. The distance between any two consecutive ants is the same. The distance between the first ant in the line to the left end and the last ant in the line to the right end is also the same as the distance between the ants. Each ant starts moving towards the left-end or the right-end randomly and equiprobably, at the same constant pace throughout the experiment. Two ants will crash if they are standing next to each other in the line and moving in opposite directions, and ants will change direction immediately when they reach the end of the stick. Ela can't determine the moving direction of each ant, but she understands very well their behavior when crashes happen.

• If a crash happens between two ants of different weights, the heavier one will eat the lighter one, and gain the weight of the lighter one. After that, the heavier and will continue walking in the same direction. In other words, if the heavier one has weight 𝑥$x$ and walking to the right, the lighter one has weight 𝑦$y$ and walking to the left (𝑥>𝑦$x>y$), then after the crash, the lighter one will diminish, and the heavier one will have weight 𝑥+𝑦$x+y$ and continue walking to the right.
• If a crash happens between two ants with the same weight, the one walking to the left end of the stick will eat the one walking to the right, and then continue walking in the same direction. In other words, if one ant of weight 𝑥$x$ walking to the left, crashes with another ant of weight 𝑥$x$ walking to the right, the one walking to the right will disappear, and the one walking to the left will have to weight 2𝑥$2x$ and continue walking to the left.

Please, check the example in the "Note" section, which will demonstrate the ants' behavior as above.

We can prove that after a definite amount of time, there will be only one last ant standing. Initially, each ant can randomly and equiprobably move to the left or the right, which generates 2𝑛$2^n$ different cases of initial movements for the whole pack. For each position in the line, calculate the probability that the ant begins in that position and survives. Output it modulo 109+7${10}^9+7$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Formally, let 𝑀=109+7$M={10}^9+7$. It can be shown that the answer can be expressed as an irreducible fraction 𝑝𝑞$\frac{p}{q}$, where 𝑝$p$ and 𝑞$q$ are integers and 𝑞≢0(mod𝑀)$q\not\equiv 0(\mathrm{mod}M)$. Output the integer equal to 𝑝⋅𝑞−1mod𝑀$p\cdot q^{-1}modM$. In other words, output such an integer 𝑥$x$ that 0≤𝑥<𝑀$0\le x<M$ and 𝑥⋅𝑞≡𝑝(mod𝑀)$x\cdot q\equiv p(\mathrm{mod}M)$.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡$t$ (1≤𝑡≤103$1\le t\le {10}^3$). The description of the test cases follows.

The only line of each test contains an integer 𝑛$n$ (1≤𝑛≤106$1\le n\le {10}^6$) — the number of ants in the experiment.

It is guaranteed that the sum of 𝑛$n$ in all tests will not exceed 106${10}^6$.

Output

For each test, print 𝑛$n$ lines. 𝑖$i$-th line contains a single number that denotes the survival probability of the 𝑖$i$-th ant in the line modulo 109+7${10}^9+7$.