007 - 桁

a

# いにしえの HOJ に入っていた問題ですがあるジャンルとして典型なのでぜひ解きましょう．
# 既出だったら消して

いつかの数オリの問題に「整数 1 以上 999 以下の数のうち 9 が含まれる数はいくつあるか答えろ」
とあったのですがどこにあるか忘れました．
これは簡単だと思ったところに以下のような問題を思いつきました．
「整数 a 以上 b 以下の数の桁に k (0 ≦ k ≦ 9) が含まれている数はいくつあるか答えろ」

問題

整数 a, b が与えられる．
a ≦ i ≦ b となる整数 i のいずれかの桁に整数 k が含まれるような i がいくつあるか求めよ．
答えは巨大になる可能性があるので 1,000,000,007 で割った余りを出力しろ．

入力

a
b
k

• 整数 a, b, k がそれぞれ改行区切りで与えられる．

制約

• 1 ≦ a ≦ b ≦ 10¹⁰⁰⁰⁰⁰
• 0 ≦ k ≦ 9

ただし 1 点分は以下の制約を満たす．

• 1 ≦ a ≦ b ≦ 10⁵

出力

• 1 行に 10⁹ +7 で割った余りを出力しろ．

入出力例

入力例1

1
123
3

出力1

22

入力例2

810
893
1

出力2

18

入力例3

1919
114514
0

出力3

45127

• 入力例 3 は部分点の制約を満たさない