겨울 축제

민철이는 국내 최고의 공원인 'Minchul Park'의 설립자이자 주인이다. 민철이는 다가오는 겨울 시즌을 기념하여 공원에서 $M$개의 축제를 개최할 예정이다. 축제가 일어난다는 소식을 들은 전국 각지의 수많은 팀들이 Minchul Park에서 공연하기 위해 오디션에 참가했다. 민철이는 오디션 결과에 따라 각 팀에 '감동 수치'를 부여했다. 각 팀의 감동 수치는 $0$ 이상 $N$ 이하의 정수이다. 감동 수치가 $i$인 팀은 관객들에게 $K^i$만큼의 감동을 줄 수 있다. 민철이는 다음 두 조건을 만족하도록 $M$개의 축제에 이 팀들을 적절히 배치하려고 한다.

• 각 축제에서 주는 감동의 크기는 같아야 한다.
• 한 팀은 최대 하나의 축제에서만 단 한 번 공연할 수 있다. 두 조건을 모두 만족시키려면 공연하지 못하는 팀이 생길 수 있다.

이 때, 하나의 축제에서 줄 수 있는 감동의 최대 크기를 구하여라.

첫 번째 줄에는 세 정수 $N, M, K$가 공백으로 구분되어 입력된다. $(0 \leq N \leq 10^6, 1 \leq M \leq 10^{9}, 2 \leq K \leq 10)$

두 번째 줄에는 '감동 수치'가 $i(0 \leq i \leq N)$인 팀의 수인 $A\_i(0 \leq A\_i \leq 10^{9})$가 입력된다.

하나의 공연에서 선사할 수 있는 최대의 감동을 $K$진법으로 한 줄에 출력한다. 만약 $1$ 이상의 감동을 선사할 방법이 없다면 $0$을 출력한다. 이 경우를 제외하면 출력은 $0$으로 시작하지 않아야 한다.