All submissions for this problem are available.
Since this year Ojass is celebrating celestial voyage to support the ongoing space missions. Aditya, a member of Planning and Development team decided to send some of the participants to the space (lucky ones :P). For this he has asked for a spaceship from ISRO.
Now the spaceship has p rows from front to back. And a total of q lucky participants will get a chance to be in the spaceship.
Spaceship has 2 entrants, one in very front and one in the very back of the ship.
Each participants has some assigned seat. It is possible for multiple participants to have the same assigned seat (Aditya is careless). The participants will then board the plane one by one starting with participant 1. Each participant can independently choose either the front entrance or back entrance to enter the ship.
When a participant walks into the ship,they will walk directly to their assigned seat. If the seat is preoccupied they will keep moving in the same direction. A participant will get upset if they reach the end of the row without finding a seat.
Find the number of ways to assign seats to the participants and board the ship without anyone getting upset.Two ways are different if there exists a participant who chose a different entrance of ship in both ways, or the assigned seat is different. Print this number modulo 10^9+7.
The first line of input will contain t, the number of test cases. Each line of test case will contain two space-separated integers p and q, the number of seats, and the number of passengers, respectively.
Print a single number, the number of ways, modulo 10^9+7.
- 1 ≤ T ≤ 10^3
- 1 ≤ q ≤ p ≤ 10^6
Input: 1 3 3 Output: 128
Here, we will denote a participants by which seat they were assigned, and which side they came from (either "F" or "B" for front or back).
For example, one valid way is 1F, 1F, 1F (i.e. all participants were assigned seat 1 and came from the front entrance). Another valid way would be 2F, 1B, 3F.
One invalid way would be 2F, 2F, 2F, since the third passenger would get to the back without finding a seat.
|Tags||com2018, kornalaarun, maths, medium, number-theory|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6|
Fetching successful submissions