405331: GYM101908 A Slackline Adventure

Memory Limit:1024 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Slackline Adventuretime limit per test0.5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

Beltrano recently became interested in slacklining. Slacklining is a balance sport on an elastic Ribbon stretched between two fixed points, which allows the practitioner to walk and do maneuvers over the tape. During vacations all Beltrano wants to do is to practice, and that is why he went to a friend's farm, where there is a plantation of eucalyptus trees.

The Plantation is very well organized. The eucalyptus trees are arranged in $$$N$$$ rows with $$$M$$$ trees in each. There is a space of one meter between each row and the trees in different rows are all perfectly aligned with a space of one meter between them.

Beltrano will setup the slackline using two trees. When setting the slackline Beltran doesn't want the distance between the two trees to be too small, since the best maneuvers require the tape to have at least $$$L$$$ meters. Also you cannot stretch it too much because it has a maximum length of $$$R$$$ meters. Note that to stretch the tape between the two chosen trees there can be no other tree in the line formed, otherwise it would not be possible to use the whole tape for the maneuvers.

Beltrano would like to know in how many different ways you can setup the slackline using trees from the farm. Two forms are considered different if at least one of the trees where the tape was tied is different.

Input

The input consists of a single line containing four integers, $$$N, M, L, R$$$, representing respectively the number of rows and columns of the plantation and the minimum and maximum lengths of slackline ($$$1 \leq N, M \leq 10^5$$$; $$$1 \leq L, R \leq 10^5$$$).

Output

Your program should produce a single line with an integer representing in how many different ways the slackline can be set. As the result can be large, the answer must be module $$$10^9 + 7$$$.

ExamplesInput
2 2 1 1
Output
4
Input
2 3 1 4
Output
13
Input
1 2 1 1
Output
1

加入题单

上一题 下一题 算法标签: