Young hackers club is a school for training hackers. At the club's graduation ceremony, known as capping, the hackers line up and place a cap on each of their heads that will determine their future. The hats are white or black. White hats aim to help society and black hats have another goal (?).

The number of graduates this year
n
n people are in stock
w
w white hat and
b
b There is a black hat. All the graduates are also aware of the inventory. In the queue, each person only knows the color of the hats of the people in front of him and does not even know the color of his own hat. It means that the person who stands at the beginning of the queue does not know the color of anyone's hat, and the person who is at the end of the queue knows the color of everyone's hat except himself.

At the end of the hat ceremony, people leave the ceremony one by one and from the end of the queue. Before leaving, each person, if he is sure of his hat color, announces his hat color and gets a pizza as a reward (it should be said that hackers are very fond of pizza!). Of course, due to the club's lack of funds, they only give pizza to the first person who guesses the color of his hat correctly. If a person is also not sure about the color of his hat, he loudly and proudly announces that he does not know the color of his hat to inform the rest of the ceremony (the people who were in the queue in front of him) of his misfortune.

Amir Nafer
i
The i th row is from the end. For example, if Amir is at the end of the queue,
i
=
1
i=1. In how many cases does Amir become the owner of the pizza? Two hats are different if there is a hacker who wears a white hat in one and a black hat in the other. Given that this value can be large, take its remainder
1
0
9
+
7
10
9
 Count +7.

Pay attention to the input and output descriptions of the sample!

input
In the first line of input four integers and non-negative numbers respectively
b
b, the number of black hats,
w
w, number of white hats,
n
n, the number of graduates and
i
i, Amir's place is relative to the end of the queue.
0
≤
b
,
w
,
n
≤
2

000
0≤b,w,n≤2000
1
≤
i
≤
n
≤
b
+
w
1≤i≤n≤b+w

output
On the only output line, print the answer to the problem.

Sub-issues
Constraint score subproblem
1 30
b
,
w
,
n
≤
20
b, w, n≤20
2 70 without additional restrictions
Example
Sample entry 1
1 1 2 1
Plain text
Sample output 1
2
Plain text
In this example, there is a white hat and a black hat, so the color of the hat of the first and second person is different. When the first person is asked the color of his hat, he can determine the color of his hat by seeing the color of the next person's hat and knowing that there is only one hat of each color.

Sample input 2
1 1 2 2
Plain text
Sample output 2
0
Plain text
Sample entry 3
2 1 2 1
Plain text
Sample output 3
1
Plain text
Sample entry 4
2 2 3 2
Plain text
Sample output 4
4
Plain text
In this example, one of the possible situations is that the color of the hat of the first and third person is white and the color of the hat of the second person is black. In this case, they ask the first person to say the color of his hat. The first person sees a white hat and a black hat in front of him and knows that there are two white hats and two black hats in total. So he is not sure about the color of his hat and proudly announces this. After that, they ask the second person to say the color of his hat. The second person sees a white hat in front of him. On the other hand, he knows that the first person could not say the color of his hat, so he concludes that the color of his hat is not white, because if it was white, the previous person, seeing two white hats, would have concluded that the color of his hat is black. So the second person says that his hat is black and gets the pizza. c++