{"code":"buses","name":"BUSES","description":"Programming competitions usually require infrastructure and organization on the part of those\r\nresponsible. A problem that frequently must be solved is regarding transportation. While participating\r\nin a recent competition, Ricardinho watched the buses and micro-buses used in the transportation of\r\ncompetitors, all lined up one behind the other as competitors disembarked. The vehicles were all from\r\nthe same company, although had different paintings. Ricardinho began to wonder how many ways\r\nthat line could be formed using buses and minibuse from that company.\r\n\r\nJach bus is 10 meters long, each minibus is 5 meters long. Given the total length of a line of buses\r\nand minibuses, and the number of diferent colors each buse or minibus may be painted, Ricardinho\r\nwants to know in how many ways such a line can be formed.\r\n\r\n

Input

\r\n\r\n- The input contains a single line, containing three integers $N, K$ and $L$, representing respectively the\r\ntotal length, in meters, of the line Ricky is considering, $K$ indicates the number of diferent colors for\r\nmicro-buses, and $L$ represents the number of different colors for buses. Note that, as integers $N, K$\r\nand $L$ may be very large, the use of 64 bits integers is recormrnended.\r\n\r\n

Output

\r\n\r\n- As the number of diferent ways of forming the line can be very large, Ricardinho is interested in the\r\nlast 6 digits of that quantity. Thus, your program should produce a single line containing exactly 6\r\ndigits, corresponding to the last digits of the solution.\r\n\r\n\r\n

Constants

\r\n\r\n- $5 \\le N \\le 10^{15}$ and $N$ is multiple of 5\r\n- $1 \\le K \\le 10^{15}$\r\n- $1 \\le L \\le 10^{15}$\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 25 5 5\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 006000\r\n ```\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 5 1000 1000\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 001000\r\n ```\r\n\r\n!!! question \"Test 3\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 20 17 31\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 111359\r\n ```\r\n\r\n\r\n!!! question \"Test 4\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 15 9 2\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 000765\r\n ```","points":350.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}