J :: Hanoi Towers in Detail

Time Limit: 5 Seconds    Memory Limit: 32768 KB

Consider the famous Hanoi Towers puzzle. There are pegs 1, 2, 3 and a pyramid of N discs of different sizes, initially collected at some peg - for example 1 - with the smallest disc at the top and the largest one at the bottom. The discs should be transferred to another peg - for example 3 - using the intermediate peg - for example 2 - by moving one disc at a time and placing a smaller disc either on top of a larger one or on an empty peg.

Given the number of discs N, and the indexes of the initially full S, and the destination pegs D and a disc index i(1<=i<=N), you should print three numbers indicating that how many times the specified disc i was moved to pegs 1, 2 and 3 respectively, if you move all discs from peg S to peg D optimally (i.e. using minimum number of moves). As these three numbers can be very large, you should print them modulo 1000000007.

 

Input

The first line of input contains a single integer T, the number of test cases to follow. The only line of each test case contains four integers, N, S, D and i as mentioned above.

T ≤ 100000 , 1<=N<=1000000000 and S ≠ D.

 

Output

For each test case print three space separated numbers, as explained above.

 

Sample Input

5
3 1 3 1
3 1 3 2
6 3 2 6
5 2 1 2
2 2 3 1

Sample Output

1 1 2
0 1 1
0 1 0
3 2 3
1 0 1

Submit

Source: 12th Iran Nationwide Internet Contest III