AT_pakencamp_2021_day3_c Sum of Digit Sum

[problemUrl]: https://atcoder.jp/contests/pakencamp-2021-day3/tasks/pakencamp_2021_day3_c 正整数 $ 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) $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ L $ $ R $ $ M $

答えを出力せよ。

### ストーリー Paken 王国では、ある正整数に対してその **ID** が下 $ M $ 桁の桁和で定義されます。ところで、 Paken 王国の住人である turtle5555 君は $ 5 $ 冪が好きです。そこで、いくつかの連続する $ 5 $ 冪についての ID の和を求めることにしました。 ### 制約 - $ 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 $ 点) 追加の制約はない。 ### Sample Explanation 1 $ f_3(25)=7,\ f_3(125)=8,\ f_3(625)=13 $ より $ 28 $ です。 この入出力はすべての小課題の制約を満たします。 ### Sample Explanation 2 この入出力は小課題 $ 1,3 $ の制約を満たします。 ### Sample Explanation 3 この入力は小課題 $ 3 $ の制約を満たします。 ### Sample Explanation 4 この入力は小課題 $ 3 $ の制約を満たします。 原案: \[turtle0123\\\_\\\_\](https://atcoder.jp/users/turtle0123\_\_)