Score: 1000 points
Find the number of sequences of N non-negative integers A_1, A_2, ..., A_N that satisfy the following conditions:
Since the answer can be enormous, print it modulo 10^9+7.
Input is given from Standard Input in the following format:
N M L R
Print the number of sequences of N non-negative integers, modulo 10^9+7.
4 2 3 7
105
The sequences of non-negative integers that satisfy the conditions are:
\begin{eqnarray} &(1, 1, 1, 0), (1, 1, 1, 1), (2, 1, 1, 0), (2, 1, 1, 1), (2, 2, 2, 0), (2, 2, 2, 1), \\ &(3, 0, 0, 0), (3, 1, 1, 0), (3, 1, 1, 1), (3, 2, 2, 0), (4, 0, 0, 0), (4, 1, 1, 0), \\ &(4, 1, 1, 1), (5, 0, 0, 0), (5, 1, 1, 0), (6, 0, 0, 0), (7, 0, 0, 0)\end{eqnarray}
and their permutations, for a total of 105 sequences.
2 1 4 8
3
The three sequences that satisfy the conditions are (2, 2), (3, 3), and (4, 4).
141592 6535 89793 238462
933832916