버스와 미니버스 줄 세우기

프로그래밍 대회를 열려면 운영진이 준비할 것이 많고, 그중 자주 문제가 되는 것이 참가자 수송이다. 리카르지뉴는 얼마 전 대회에 참가했다가 참가자를 태우고 온 버스와 미니버스가 앞뒤로 한 줄을 이룬 모습을 보았다. 차량은 모두 같은 회사 소유였지만 도색은 서로 달랐다. 리카르지뉴는 그 회사의 버스와 미니버스로 이런 줄을 만드는 방법이 몇 가지인지 궁금해졌다.

버스는 길이가 10미터, 미니버스는 길이가 5미터다. 줄의 전체 길이와 미니버스에 쓸 수 있는 색의 개수, 버스에 쓸 수 있는 색의 개수가 주어질 때, 줄을 만드는 방법의 수를 구하라.

줄은 앞에서 뒤로 순서가 있다. 두 줄은 어느 한 자리의 차종이 다르거나 색이 다르면 서로 다른 줄로 센다. 차종과 색이 같은 차량은 서로 구별하지 않는다.

첫째 줄에 정수 $N$, $K$, $L$이 공백으로 구분되어 주어진다. $N$은 리카르지뉴가 생각하는 줄의 전체 길이(미터)이고, $K$는 미니버스에 쓸 수 있는 색의 개수, $L$은 버스에 쓸 수 있는 색의 개수다. $N$, $K$, $L$은 매우 클 수 있으므로 64비트 정수를 쓰는 것이 좋다.

제한

• $5 \le N \le 10^{15}$이고 $N$은 5의 배수다
• $1 \le K \le 10^{15}$
• $1 \le L \le 10^{15}$

방법의 수가 매우 클 수 있으므로 그 수의 마지막 여섯 자리를 구한다. 한 줄에 정확히 여섯 자리를 출력하고, 앞자리가 남으면 0으로 채운다.