Giải bài trực tuyến

Bạn có thấy số 324 rất đặc biệt? Nó chia hết cho 3, 2 và 4. Một số tự nhiên chia hết cho tất cả các chữ số của nó được gọi là số tự chia hết.

Một số ví dụ khác về số tự chia hết là: 5, 12, 784, 8736. Số 102 không phải là số tự chia hết vì nó không chia hết cho 0.

Yêu cầu: Đếm số lượng số tự chia hết có đúng N chữ số. Vì kết quả có thể rất lớn, bạn chỉ cần in ra phần dư khi chia cho 10007.

Input

• Một dòng duy nhất ghi số N.

Output

• Phần dư khi chia số lượng số tự chia hết có N chữ số cho 10007.

Example

Input:

3



Output:

56

Giới hạn

• 3 ≤ N ≤ 10⁶.
• Trong 80% số test, N không vượt quá 500. Giới hạn thời gian cho các test này là 10 giây.
• Giới hạn thời gian cho các test còn lại là 30 giây.