## Table of Contents

**The Magical Stone Solution Codechef**

Initially, there is a magical stone of mass 2N 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 M2 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 [L,R], find out the number of stones present at each of the coordinates in the range [L,R]. As the number of stones can be very large, output them modulo (10^{9}+7).

**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 (Râˆ’L+1) space-separated integers. The i^{th} integer will denote the number of stones present at X=(L+iâˆ’1) coordinate. As the number of stones can be very large, output them modulo (10^{9}+7).

**Constraints**

1â‰¤Tâ‰¤100

1â‰¤Nâ‰¤10^{6}

âˆ’Nâ‰¤Lâ‰¤Râ‰¤N

Sum of (Râˆ’L+1) 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: {0,0,1,0,0}

t=1: {0,1,0,1,0}

t=2: {1,0,2,0,1}

We have to output the number of stones at x=âˆ’2 to x=2, which is {1,0,2,0,1}.

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

**SOLUTION**

**Program:** **The Magical Stone Solution **in Python

```
x = int(1e9 + 7)
factorial = [1]
for i in range(1, 1000001):
factorial.append((factorial[-1]*i)%x)
for _ in range(int(input())):
n, l, r = map(int, input().split())
while l <= r:
if (l+n)%2 == 0:
c = (l+n)//2
val = factorial[n] * pow(factorial[c], x-2, x) * pow(factorial[n-c], x-2, x)
print(val%x, end=' ')
else:
print(0, end=' ')
l += 1
print()
```

**Related**:

*Alternating Diameter ALTDIA Solution Codechef**Mystical Numbers XORGAND Solution Codechef**Pushpa PUSH7PA Solution Codechef**The Attack of Queen Solution Codechef**Sugarcane Juice Business Solution Codechef**In The Green Zone ITGRZN Solution Codechef**Four Arrays FOURARR Solution Codechef**Miami GP F1RULE Solution Codechef**Football Cup FOOTCUP Solution Codechef*