Cho số nguyên tố ~k~, tìm số nguyên dương ~m~ nhỏ nhất sao cho ~k \times 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

Gồm một số nguyên tố ~k~ (~1 \le k \le 10^9~).

Kết quả

In ra một số nguyên là đáp số của bài toán.

Ví dụ

Ví dụ 1

BAI5.INP

13

BAI5.OUT

8547

Giải thích: ~13 \times 8547 = 111111~.

Ví dụ 2

BAI5.INP

23

BAI5.OUT

797103822

Giới hạn

• Subtask 1 (50% số điểm): ~k \times m \le 10^9~.
• Subtask 2 (50% số điểm): không có ràng buộc gì thêm.