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~.

Giới hạn

• ~3 \leq N \leq 10^{6}~ .
• Trong ~80\%~ số test, ~N~ không vượt quá ~500~.

Sample Input

3

Sample Output

56