시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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.

입력

A entrada contém vários casos de teste. Cada caso de teste é composto por apenas uma linha, contendo três inteiros N(5 ≤ N ≤ 1015 e N é múltiplo de 5), K(1 ≤ K ≤ 1015) and L(1 ≤ L ≤ 1015), 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. O final da entrada é determinado por EOF.

출력

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.

예제 입력

25 5 5

예제 출력

006000

예제 입력 2

5 1000 1000

예제 출력 2

001000

예제 입력 3

20 17 31

예제 출력 3

111359

예제 입력 4

15 9 2

예제 출력 4

000765

힌트