ストーリー

Paken 王国では、ある正整数に対してその ID が下 M 桁の桁和で定義されます。ところで、 Paken 王国の住人である turtle5555 君は 5 冪が好きです。そこで、いくつかの連続する 5 冪についての ID の和を求めることにしました。

問題文

正整数 n,k に対して f_k(n) を、 n の 10 進法での下 k 桁の桁和で定義します。例えば、 f_2(314)=5,f_1(100)=0,f_{100}(1)=1 です。

正整数 L,R,M が与えられるので、 \displaystyle \sum_{k=L}^R f_M(5^k) を求めてください。

制約

• 1 \le L \le R \le 10^{16}
• 1 \le M \le 16
• 入力は全て整数

小課題

1. (100 点) 1 \le L \le R \le 10^6
2. (150 点) M=3
3. (250 点) 追加の制約はない。

入力例 1

2 4
3

出力例 1

28

f_3(25)=7, f_3(125)=8, f_3(625)=13 より 28 です。

この入出力はすべての小課題の制約を満たします。

入力例 2

333 4444
5

出力例 2

77100

この入出力は小課題 1,3 の制約を満たします。

入力例 3

12 998244353
5

出力例 3

18717081408

この入力は小課題 3 の制約を満たします。

入力例 4

12321 123456787654321
16

出力例 4

8395076630065056

この入力は小課題 3 の制約を満たします。

原案: turtle0123__