VM 09 Bài 04 - Self-divisible Number

View as PDF

Submit solution

Points: 1.80 (partial)
Time limit: 9.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Marathon 2009Round 1Problem Setter: Khúc Anh Tuấn
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.