자릿수 합 DP

문제

정수 $L$, $R$, $K$가 주어질 때, $L$ 이상 $R$ 이하의 정수 중 각 자릿수의 합이 $K$인 수의 개수를 구하여라.

입력

첫째 줄에 세 정수 $L$, $R$, $K$가 공백으로 구분되어 주어진다.

제한

• $1 \le L \le R \le 10^{18}$
• $1 \le K \le 162$

출력

조건을 만족하는 정수의 개수를 출력한다.

예제 입력 1

1 99 10

예제 출력 1

9

예제 입력 2

1 100 10

예제 출력 2

9