Zero's Number

Xnozero is very interested in k-divide number.

A way of k-divide on a number is defined as if number N can be divide into two parts m, n, and the sum of m and n can be divided by k, then this is a way of k-divide number based k.

For example, 3 + 33 = 36 is a way of 3-divide on number 333, as you can only divide 333 into 3 and 33, and the sum of 3 and 33 is 36, which can be divided by 3.

Zero's number is defined as f(n,k), and f(n,k) is the number of ways of n divided into k-divide numbers.

As defined above, 333 can be divided into two parts in two ways 3|33 and 33|3, so f(333,3)=2.

Now give you A, B, K, can you help Xnozero compute the sum of f(i,K) (A≤i≤B)? (1 ≤ K ≤ 20, 10 ≤ A ≤ B ≤ 10¹⁷)

Multiple cases, process to the end of file.
Each line contains 3 integers A,B,K as descripted above.

Output the sum of f(i,k), one per line.

333 333 3
10 100 2

2
46

2011 Multi-University Training Contest 13 - Host by HIT