| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
SELFDIV - Self-divisible Number |
| English | Tiếng Việt |
Do you think that 324 is a special number? It is divisible by 3, 2 and 4. A non-negative integer that is divisible by all of its digits is called a self-divisible number.
Other examples of self-divisible numbers are 5, 12, 784, 8736. Please note that 102 is not a self-divisible number as it is not divisible by 0.
How many self-divisible numbers which have exactly N digits? As the result may be very large, you only need to print the result modulo 10007.
Input
- A single line consists of an integer N.
Output
- The result modulo 10007.
Example
Input:
3
Output:
56
Constraints
- 3 ≤ N ≤ 106.
- In 80% of the test cases, N does not exceed 500. The time limit for these test cases is 10 seconds.
- The time limit for the remaining test cases is 30 seconds.
ãy
| Được gửi lên bởi: | VOJ Team |
| Ngày: | 2009-07-09 |
| Thời gian chạy: | 2s-6s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
| Nguồn bài: | VNOI Marathon 2009 Round 1 Problem Setter: Khúc Anh Tuấn |
RSS