There are N different games available to play in a school.
You love to play all of the N games , but your coach asked you to focus only on 2 different games a and b. Therefore, you cannot play any other game under your coach's presence. You play a single game for 1 hour and then move on to any other game. Also, you need to play both the games suggested by your coach at different times in your coach's presence.
You have to make a program which can calculate the number of possible schedules which allow you to play 2 or more games without playing any game for consecutive hours.
For the total time duration T for which you will play in school, your coach is only present for \(1^{st}\) and \(T^{th}\) hour.
Input
First line contains a single integer N (Total Number of games).
Second line contains a single integer T (Time Duration).
Third line contains a single integer a (Game 1 recommended by your coach).
Fourth line contains a single integer b (Game 2 recommended by your coach).
Output
Print a single number, the number of schedules modulo \(10^9 + 7\) .
Constraints
- \(2 \leq N \leq 64\)
- \(2 \leq T \leq 10^{18}\)
- \(1 \leq a, b \leq N\)
7 possible schedules are :
1 - 2 - 3 - 4
1 - 2 - 1 - 4
1 - 3 - 2 - 4
1 - 3 - 1 - 4
1 - 4 - 1 - 4
1 - 4 - 2 - 4
1 - 4 - 3 - 4
Other 7 schedules are just mirror cases of above permutations.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor