Problem Description

For positive integers $ n,k $, define $ f_k(n) $ as the sum of the digits of $ n $ in base 10 for the last $ k $ digits. For example, $ f_2(314)=5, f_1(100)=0, f_{100}(1)=1 $.

Given positive integers $ L,R,M $, find $\displaystyle\ \sum_{k=L}^R\ f_M(5^k)$.

Input Format

The input is given from the standard input in the following format:

$ L $ $ R $ $ M $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

2 4
3

Sample Output #1

28

Sample Input #2

333 4444
5

Sample Output #2

77100

Sample Input #3

12 998244353
5

Sample Output #3

18717081408

Sample Input #4

12321 123456787654321
16

Sample Output #4

8395076630065056

Notes/Hints

Constraints

• $1\ \le\ L\ \le\ R\ \le\ 10^{16}$
• $1\ \le\ M\ \le\ 16$
• All inputs are integers

Subtasks

1. ($ 100 $ points) $1\ \le\ L\ \le\ R\ \le\ 10^6$
2. ($ 150 $ points) $ M=3 $
3. ($ 250 $ points) No additional constraints.

Sample Explanation 1

From $ f_3(25)=7, f_3(125)=8, f_3(625)=13 $, the sum is $ 28 $. This input and output satisfy the constraints of all subtasks.

Sample Explanation 2

This input and output satisfy the constraints of subtasks $ 1,3 $.

Sample Explanation 3

This input satisfies the constraints of subtask $ 3 $.

Sample Explanation 4

This input satisfies the constraints of subtask $ 3 $. Original idea: [MATH0]

见题面 Input 部分

见题面 Output 部分