자릿수 거듭제곱 수열

자연수 N에 대해 S_K(N)을 N의 각 십진수 자리수를 K제곱한 값들의 합이라고 하자. 예를 들어 S_2(65) = 6^2 + 5^2 = 61이다.

이제 수열 N, S_K(N), S_K(S_K(N)), ...을 만든다. 세 정수 A, B, K가 주어졌을 때, A <= N <= B인 모든 자연수 N에 대해 이 수열을 만들고, 각 수열에 등장하는 가장 작은 값을 구한다. 그 값들의 합을 출력하는 프로그램을 작성하시오.

첫째 줄에 세 정수 A, B, K가 주어진다.

첫째 줄에 정답을 출력한다.

• 1 <= A <= B <= 1,000,000
• 1 <= K <= 6