Codie Bird

All submissions for this problem are available.
Codie is a super intelligent bird stuck inside a flappy bird simulation. The game is simple: if the position of the bird is denoted by (x, y), then the bird can move in the following directions in one step:
 right — to (x + 1, y),
 upright — to (x + 1, y + 1),
 downright — to (x + 1, y  1).
The screen has width K and you are not allowed to move outside of the screen, i.e. the position of the bird must satisfy 1 ≤ y ≤ K at each moment.
Codie is moving from (1, K/2) to (N, K/2). However, there is exactly one obstacle in the simulation. This obstacle occurs at a random xcoordinate between 2 and N  1 (both inclusive), where each x has equal probability. The obstacle is composed of two vertical pipes. One of them is at the top and covers all ycoordinates between b and K (both inclusive). The other one is at the bottom and covers all ycoordinates between 1 and a (both inclusive). The pipes only allow Codie to move through ycoordinates that are ≥ a+1 and ≤ b1 at this particular xcoordinate.
Codie, being a super smart and geeky bird, is interested in finding the expected number of paths from (1, K/2) to (N, K/2). Help Codie find the answer!
Specifically, let's assume that the expected number of paths is a fraction of the form P / Q, where P and Q are coprime. Let Q^{1} be the multiplicative inverse of Q modulo 10^{9} + 7. Compute P · Q^{1} modulo 10^{9} + 7.
Input
The only line of the input contains four spaceseparated integers N, K, a and b denoting the final xcoordinate, the width of the screen, the highest coordinate blocked by the bottom pipe and the lowest coordinate blocked by the top pipe.
Output
Print a single line containing one integer — the expected number of paths from (1, K/2) to (N, K/2) modulo 10^{9} + 7.
Constraints
 3 ≤ N ≤ 10^{9}
 2 ≤ K ≤ 50
 K is even
 1 ≤ a < b ≤ K
Example
Input: 5 4 1 3 Output: 666666679
Explanation
Let X denote the starting and ending coordinate, and B denote the cells blocked by pipes.
The expected value is (7 · 1/3) + (9 · 1/3) + (7 · 1/3) = 23/3 = 666666679 (modulo 10^{9} + 7).Author:  sidhant007 
Editorial  https://discuss.codechef.com/problems/CODIE 
Tags  acm17chn, chn17rol, expectedvalue, matrixexpo, medhard, sidhant007 
Date Added:  1122017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, kotlin 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 