## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## The Magical Stone CodeChef Solution | CodeChef Problem Solution 2022

Initially, there is a magical stone of mass ${2}^{N}$ lying at the origin of the number line. For the next $N$ seconds, the following event happens:

• Let us define the decomposition of a magical stone as follows: If there is a magical stone of mass $M>1$ lying at coordinate $X$, then it decomposes into two magical stones, each of mass $\frac{M}{2}$ lying at the coordinates $X-1$ and $X+1$ respectively. The original stone of mass $M$ gets destroyed in the process.
• Each second, all the magical stones undergo decomposition simultaneously.

Note that there can be more than one stone at any coordinate $X$.

Given a range $\left[L,R\right]$, find out the number of stones present at each of the coordinates in the range $\left[L,R\right]$. As the number of stones can be very large, output them modulo $\left({10}^{9}+7\right)$.

### Input Format

• The first line contains a single integer $T$ - the number of test cases. Then the test cases follow.

• The first and only line of each test case contains three integers $N$$L$ and $R$, as described in the problem statement.

### Output Format

For each testcase, output in a single line a total of $\left(R-L+1\right)$ space-separated integers. The ${i}^{th}$ integer will denote the number of stones present at $X=\left(L+i-1\right)$ coordinate. As the number of stones can be very large, output them modulo $\left({10}^{9}+7\right)$.

### Constraints

• $1\le T\le 100$
• $1\le N\le {10}^{6}$
• $-N\le L\le R\le N$
• Sum of $\left(R-L+1\right)$ over all the test cases doesn't exceed ${10}^{5}$.

### Sample Input 1

3
2 -2 2
2 0 2
150000 48 48


### Sample Output 1

1 0 2 0 1
2 0 1
122830846


### Explanation

Test case 1: Let us look at the number of stones for $x=-2$ to $x=2$ as the time progresses:

$t=0$$\left\{0,0,1,0,0\right\}$

$t=1$$\left\{0,1,0,1,0\right\}$

$t=2$$\left\{1,0,2,0,1\right\}$

We have to output the number of stones at $x=-2$ to $x=2$, which is $\left\{1,0,2,0,1\right\}$.

Test case 2: Similar to first test case, We have to output the number of stones at $x=0$ to $x=2$, which is $\left\{2,0,1\right\}$.