uCoder | 1311 | Nível: 6 | Tempo Limite: 5
Ônibus
Adaptado por Erich Rodrigues
Competição: Maratona de Programação da SBC 2013
Competições de programação normalmente exigem infraestrutura e organização por parte dos responsáveis. Um problema que frequentemente deve ser resolvido é em relação ao transporte. Ao participar de uma competição recente, Ricardinho ficou observando os ônibus e micro-ônibus utilizados no transporte dos competidores, todos enfileirados um atrás do outro enquanto os competidores desembarcavam. Os veículos eram todos de uma mesma empresa, embora tivessem pinturas distintas. Ricardinho começou a se perguntar de quantas maneiras aquela fila poderia ser formada, usando ônibus e micro-ônibus daquela empresa.
Cada ônibus tem 10 metros de comprimento. Já os micro-ônibus possuem 5 metros de comprimento. A partir de um dado comprimento total a ser alcançado com ônibus e micro-ônibus enfileirados, e das quantidades de cores diferentes para ônibus e micro-ônibus, Ricardinho quer saber de quantas formas uma fila pode ser formada.
Entrada
A entrada é composta por apenas uma linha, contendo três inteiros N, K e L, separados por espaço. O inteiro N representa o comprimento total, em metros, da fila que Ricardinho está considerando. K e L representam o número de cores distintas disponı́veis para micro-ônibus e ônibus, respectivamente. Note que, como os inteiros N, K e L podem ser muito grandes, recomenda-se o uso de inteiros de 64 bits.
Saída
Como o número de formas diferentes de se formar a fila pode ser muito grande, Ricardinho está interessado nos últimos 6 dígitos da quantidade. Assim, para cada caso de teste, seu programa deve produzir uma única linha contendo exatamente 6 dígitos, correspondentes aos últimos dígitos da solução
Restrições
• 5 ≤ N ≤ 1015 e N é múltiplo de 5
• 1 ≤ K ≤ 1015
• 1 ≤ L ≤ 1015
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
5 1 1 |
000001 |
|
5 1000 1000 |
001000 |
|
25 5 5 |
006000 |