bee 1474 - Buses

Programming competitions usually require infrastructure and organization on the part of those responsible. A problem that frequently must be solved is regarding transportation. While participating in a recent competition, Ricardinho watched the buses and micro-buses used in the transportation of competitors, all lined up one behind the other as competitors disembarked. The vehicles were all from the same company, although had different paintings. Ricardinho began to wonder how many ways that line could be formed using buses and minibuse from that company. Each bus is 10 meters long, each minibus is 5 meters long. Given the total length of a line of buses and minibuses, and the number of different colors each buse or minibus may be painted, Ricardinho wants to know in how many ways such a line can be formed.

Input

The input contains several test cases and ends with EOF. Each test case is composed of a single line, containing three integers N(5 ≤ N ≤ 10¹⁵ and N is multiple of 5), K(1 ≤ K ≤ 10¹⁵) and L(1 ≤ L ≤ 10¹⁵), representing respectively the total length, in meters, of the line Ricky is considering, K indicates the number of different colors for micro-buses, and L represents the number of different colors for buses. Note that, as integers N, K and L may be very large, the use of 64 bits integers is recommended.

Output

As the number of different ways of forming the line can be very large, Ricardinho is interested in the last 6 digits of that quantity. Thus, your for each test case your program must produce a single line containing exactly 6 digits, corresponding to the last digits of the solution.

Sample Input	Sample Output
25 5 5 5 1000 1000 20 17 31 15 9 2	006000 001000 111359 000765