Problem I
The Last Crusade

Scootaloo’s parents, Snap Shutter and Mane Allgood, have been away for many, many moons, venturing across the land in search of exotic flora and fauna for the advancement of Equestrian science and medicine. The gravity of their profession meant that they could never find the time to return home, but a recent trough in their workload finally gave them the chance to visit their daughter.

Figure 1: Illustration by Kyle Coate.

Reunited at last, Scootaloo spent the weekend with her parents, going to the movies, watching buckball games and having dinners at the local greasy spoons. But these moments were fleeting and they could never be enough; tomorrow, her parents must depart to continue their work in the treacherous jungles of Shire Lanka.

Scootaloo wants to count the number of days before her parents return.

A jungle is a network of one or more junctions connected by zero or more paths, such that each path connects two distinct junctions and from any junction it is possible to reach any other junction by treading a series of one or more paths. The complexity rating of a jungle is simply the number of junctions it has.

A jungle is called safely navigable if, when one starts at any junction and repeatedly treads paths starting from this junction, never treading the most recently trodden path, one is guaranteed to eventually reach a junction where he or she is unable to tread a path. Safely navigable jungles mitigate a lot of risk for adventurers as they minimize the chances of getting lost; one simply needs to keep treading paths, only taking note of the most recently trodden path, and he or she will always eventually end at a junction. The junctions that one can possibly end at (for some starting junction and series of paths) are called terminal junctions. The safety rating of a safely navigable jungle is simply the number of terminal junctions it has; jungles with fewer terminal junctions are naturally less complex, as one is guaranteed to end at one of them eventually and hence can simply map out safe exit strategies from these terminal junctions in advance!

Two jungles are called identical if

1. they have the same number of junctions, say $n$, and

2. if we arbitrarily label the junctions of the first jungle as $j_1, j_2, \dots , j_ n$ and the junctions of the second jungle as $j’_1, j’_2, \dots , j’_ n$, then there exists a permutation $p$ of $1, 2, \dots , n$ such that for every pair of distinct junctions $j_ a$ and $j_ b$ in the first jungle, the number of paths between them is equal to the number of paths between junctions $j’_{p_ a}$ and $j’_{p_ b}$ in the second jungle.

In essence, two jungles are identical if they have the same structure.

Scootaloo knows that Snap Shutter and Mane Allgood will trek through a single Shire Lankan jungle every day, and that they will choose only jungles which are

1. safely navigable,

2. sufficiently complex (complexity rating at least $C$), but not so complex as to be unapproachable (complexity rating at most $C’$),

3. sufficiently safe (safety rating at least $S$), but not so safe as to be vapid (safety rating at most $S’$), and

4. not identical to any jungle they have trekked previously.

Scootaloo does not know much about the jungles in Shire Lanka, so she can only assume that every possible jungle with any possible structure exists. What is the maximum number of days it could take for her parents to finish all their treks?

Input

The first and only line of input contains four integers, $C$, $C’$ ($1 \leq C \leq C’ \leq 10^{18}$) and $S$, $S’$ ($1 \leq S \leq S’ \leq 5$), the minimum and maximum allowable complexity ratings and the minimum and maximum allowable safety ratings, respectively.

Output

Output the a single integer on a line by itself, the maximum number of days it could take for Scootaloo’s parents to finish all their treks.

Since this number can be quite large, you should output only the remainder after dividing this number by $10^9+7$.

7 10 2 4

72