Por Brazil
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.
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 ≤ L ≤ R ≤ 105 ).
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 |