Problem Description
Xiao Ming heard transported to the front to Dairy Milk. ABC would like, all meat not work. people in disaster areas also need to eat vegetables, so ABC has developed a super plant that can be used to eat. This plant from seed to germinate only 1 day time, and xth from the first day of germination, to yth days(including the yth day), every day they are breeding out of a seed, each plant will be the zth days in the germination of the harvest was sent to disaster.
0th day ABC only has a seed , ABC would like to know how many vegetables (not including seeds and which was send to disaster),in the nth day.
Input
Multiple sets of data. Each test data row contains only four positive integers x, y, z, n, separated by spaces.
Where 0 <x <= y <z <= 20,0 <n <= 1000000000.
Output
Each test data output line, contains a positive integer, denotes the nth-day how many of such vegetables. Results maybe large just output result modula 1000000007
Sample Input
1 2 3 4
Sample Output
5
