Cho ba số nguyên ~L~, ~R~, ~k~, hãy đếm số lượng số đẹp trong đoạn ~[L, R]~. Số đẹp là số nguyên mà biểu diễn thập phân của nó chứa số nguyên ~k~ (ví dụ nếu ~k = 13~ thì ta có các số đẹp là ~12\textbf{13}~, ~1\textbf{13}~, ~234\textbf{13}~, ~\dots~).

Input

Gồm ba dòng, mỗi dòng lần lượt chứa số nguyên ~L~, ~R~, ~k~.

Điều kiện:

• ~1 \le L \le R \le 10^{100000}~

• ~1 \le k \le R~

• ~log_{10}(k) \cdot log_{10}(R) \le 5 \cdot 10^6~

Output

Gồm một số nguyên duy nhất là số lượng số đẹp trong khoảng ~[L, R]~ lấy phần dư với phép chia ~10^9+7~.

Scoring

Subtask ~1~ ~(20\%)~:

• ~k \le R \le 10^9~

• ~R - L \le 10^6~

Subtask ~2~ ~(80\%)~: Không có giới hạn gì thêm.

Sample Input 1

1
142
13

Sample Output 1

12