[Solution] Ela Goes Hiking solution codeforces

Ela Goes Hiking solution codeforces – Ela likes to go hiking a lot. She loves nature and exploring the various creatures it offers. One day, she saw a strange type of ant, with a cannibalistic feature. More specifically, an ant would eat any ants that it sees which is smaller than it.
Curious about this feature from a new creature, Ela ain’t furious. She conducts a long, non-dubious, sentimental experiment.

Table of Contents

[Solution] Ela Goes Hiking solution codeforces

She puts 𝑛n cannibalistic ants in a line on a long wooden stick. Initially, the ants have the same weight of 11. 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𝑛2n 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+7109+7.

[Solution] Ela Goes Hiking solution codeforces

Formally, let 𝑀=109+7M=109+7. It can be shown that the answer can be expressed as an irreducible fraction 𝑝𝑞pq, where 𝑝p and 𝑞q are integers and 𝑞0(mod𝑀)q≢0(modM). Output the integer equal to 𝑝𝑞1mod𝑀p⋅q−1modM. In other words, output such an integer 𝑥x that 0𝑥<𝑀0≤x<M and 𝑥𝑞𝑝(mod𝑀)x⋅q≡p(modM).

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡1031≤t≤103). The description of the test cases follows.

The only line of each test contains an integer 𝑛n (1𝑛1061≤n≤106) — the number of ants in the experiment.

It is guaranteed that the sum of 𝑛n in all tests will not exceed 106106.

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+7109+7.

Example

input

Copy
3
4
5
2

output

[Solution] Ela Goes Hiking solution codeforces

0
250000002
250000002
500000004
0
250000002
250000002
250000002
250000002
0
1
Note

Here is the example of 66 ants moving on the branch. An ant’s movement will be denoted by either a character 𝐿L or 𝑅R. Initially, the pack of ants on the branch will move as 𝑅𝐿𝑅𝑅𝐿𝑅RLRRLR. Here’s how the behavior of the pack demonstrated:

Initially, the ants are positioned as above.

After a while, the ant with index 22 (walking to the left) will crash with the ant with index 11 (walking to the right). The two ants have the same weight, therefore, ant 22 will eat ant 11 and gain its weight to 22. The same thing happens with ant 55 and ant 44.

[Solution] Ela Goes Hiking solution codeforces

The ant 66 will walk to the end of the stick, therefore changing its direction.

After that, the ant with index 55 will crash with the ant with index 33. Since ant 55 is more heavy (weight=22) than ant 33 (weight=11), ant 55 will eat ant 33 and gain its weight to 33.

Ant 22 will walk to the end of the stick, therefore changing its direction.

[Solution] Ela Goes Hiking solution codeforces

After that, the ant with index 55 will crash with the ant with index 22. Since ant 55 is more heavy (weight=33) than ant 22 (weight=22), ant 55 will eat ant 22 and gain its weight to 55.

Lastly, after ant 55 walk to the end of the branch and changes its direction, ant 55 will eat ant 66 and be the last ant standing.

For Solution

“Click Here”

Leave a Comment