Voltar

uCoder | 1336 | Nível: 4 | Tempo Limite: 5

Ginástica

Adaptado por None

Competição: Maratona de Programação da SBC 2017


Vinı́cius gosta muito de se exercitar na academia de ginástica. Ele fez um acordo com o seu treinador para ter programas de exercı́cios diferentes a cada vez que usar a bicicleta ergométrica. Um programa, na linguagem das academias, é uma sequência de nı́veis de dificuldade do exercı́cio. Os programas de Vinı́cius para a bicicleta ergométrica devem ter a mesma duração em minutos e os nı́veis de dificuldade devem mudar a cada minuto, para um nı́vel imediatamente acima ou um nı́vel imediatamente abaixo. Os nı́veis de dificuldade não podem estar abaixo de um mı́nimo e nem acima de um máximo previamente estipulados.
Seu problema é calcular o número de programas diferentes que o treinador pode construir, obedecidas as restrições acima.


Entrada

A entrada consiste de uma única linha que contém três inteiros, T, M, N (1 ≤ T ≤ 50, 1 ≤ M < N ≤ 105) em que T é o número de minutos do exercı́cio, M é o valor mı́nimo de dificuldade permitido e N é o valor máximo de dificuldade permitido.


Saída

Seu programa deve produzir uma única linha com um inteiro representando o número de programas diferentes que o treinador pode construir. Como esse número pode ser grande, a resposta deve ser esse número módulo 109 + 7.


Exemplo de Entrada Exemplo de Saída

50 1 100000

738072143

30 2 5

4356618

3 2 5

10