URI Online Judge | 2876

Aventurando-se no Slackline

Por BR Brazil

Timelimit: 1

Beltrano recentemente se interessou por slackline. Slackline é um esporte de equil´ıbrio sobre uma fita elástica esticada entre dois pontos fixos, o que permite ao praticante andar e fazer manobras em cima da fita. Durante as férias tudo que Beltrano quer fazer é praticar, e para isso ele foi para a fazenda de um amigo, onde há uma plantação de eucaliptos. A plantação é muito bem organizada. Os eucaliptos estãp dispostos em N fileiras com M árvores em cada. Há um espaço de um metro entre cada fileira e as árvores nas diferentes fileiras estão todas perfeitamente alinhadas com um espa¸co de um metro entre elas. Beltrano vai montar o slackline usando duas árvores. Ao montar o slackline Beltrano não gosta que a distância entre as duas árvores seja muito pequena, já que as melhores manobras exigem que a fita tenha pelo menos L metros. Também não é possível esticar demais a fita já que ela tem um comprimento máximo de R metros. Note que ao esticar a fita entre as duas árvores escolhidas não pode haver nenhuma outra árvore na linha formada, caso contrário não seria possível utilizar a fita toda para as manobras. Beltrano gostaria de saber de quantas formas diferentes é possível montar o slackline usando as árvores da fazenda. Duas formas são consideradas diferentes se pelo menos uma das árvores onde a fita foi amarrada é diferente.

Entrada

A entrada consiste de uma única linha que cont´em quatro inteiros, N, M, L, R, representando respectivamente o número de linhas e colunas da plantação o e os comprimentos mínimo e máximo do slackline (1 ≤ N, M ≤ 105 ; 1 ≤ LR ≤ 105 ).

Saída

Seu programa deve produzir uma única linha com um inteiro representando de quantas formas diferentes o slackline pode ser montado. Como o resultado pode ser grande, a resposta deve ser esse número módulo 109 + 7.

Exemplos de Entrada Exemplos de Saída

2 2 1 1

4

2 3 1 4

13

3 4 1 4

49