Một số nguyên dương được gọi là số zigzag nếu khi viết số đó trong hệ thập phân, không có chữ số \(0\) ở đầu, rồi đọc các chữ số theo thứ tự từ trái sang phải, các bước tăng và giảm luân phiên nhau. Các bước tăng và giảm đều là nghiêm ngặt.

Ví dụ, \(2947\) là số zigzag vì dãy chữ số \(2 \to 9 \to 4 \to 7\) lần lượt tăng, giảm, rồi tăng. Số \(71946\) cũng là số zigzag vì các bước lần lượt là giảm, tăng, giảm, rồi tăng. Ngược lại, \(123\), \(71446\), \(71442\) và \(88\) không phải số zigzag. Mọi số nguyên dương có một chữ số đều được coi là số zigzag.

Yêu cầu

Đếm số zigzag là bội của \(M\) trong đoạn từ \(A\) đến \(B\), kể cả hai đầu mút, rồi lấy phần dư khi chia số lượng đó cho \(10000\).

Dữ liệu vào

Dữ liệu vào gồm \(3\) dòng, mỗi dòng chứa một số nguyên dương. Ba dòng lần lượt chứa \(A\), \(B\) và \(M\).

Lưu ý rằng \(A\) và \(B\) có thể không nằm trong phạm vi biểu diễn của các kiểu dữ liệu số nguyên thông thường.

Dữ liệu ra

In ra một dòng chứa phần dư khi chia số lượng các số zigzag là bội của \(M\) trong đoạn \([A,B]\) cho \(10000\).

Ràng buộc

• \(1 \le A \le B \le 10^{500}\).
• \(1 \le M \le 500\).
• \(A\), \(B\) và \(M\) đều là số nguyên dương.

Ví dụ

100
200
5

13

6
1234567
3

246