Cho số nguyên tố k, tìm số nguyên dương m nhỏ nhất sao cho k×m tạo thành một số có tất cả các chữ số giống nhau.

Yêu cầu:

Tìm phần dư nhận được trong phép chia m cho 10^9+7.

Dữ liệu:

Vào từ tệp văn bản CAU5.INP một số nguyên tố k (1 ≤ k ≤ 10^9).

Kết quả:

Ghi ra tệp văn bản CAU5.OUT một số nguyên là đáp số của bài toán.

Ví dụ 1:

CAU5.INP

13

CAU5.OUT

8547

Ví dụ 2:

CAU5.INP

23

CAU5.OUT

797103822

Ràng buộc:

- Có 50% số test ứng với 50% số điểm của bài có k×m≤10^9;
- Có 50% số test ứng với 50% số điểm của bài không có ràng buộc gì thêm.