Mã số

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đất nước C11 sắp tiến hành cấp ~N~ mã số khác nhau cho ~N~ người dân để tiện việc quản lí. Để việc cấp mã số mang tính dân chủ, mỗi người dân được quyền chọn một số ~max~ và chính quyền sẽ cấp cho người đó một mã số là một số tự nhiên có giá trị từ ~1~ đến ~max~.

Nhiệm vụ của bạn là đếm xem có bao nhiêu cách cấp mã số khác nhau cho ~N~ người này.

Input

  • Dòng ~1~: Số nguyên dương ~N~.
  • Dòng ~i~ trong ~N~ dòng tiếp theo: Số nguyên dương ~max_{i}~.

Output

  • Phần dư khi chia số cách cấp mã số khác nhau cho ~k~. Với ~k~ là số nguyên tố nhỏ nhất lớn hơn ~10^{9}~.

Giới hạn

  • ~1 \leq N \leq 10^{5}~.
  • ~1 \leq max_{i} \leq 10^{9}~.

Sample Input 1

2
1
3

Sample Output 1

2

Sample Input 2

4
4
4
4
4

Sample Output 2

24

Note

- Ví dụ ~1~: Có ~2~ cách cấp mã số là ~\{1, 2\}~ hoặc ~\{1, 3\}~.

- Ví dụ ~2~: Số cách cấp mã số là số hoán vị của tập ~(1~, ~2~, ~3~, ~4)~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.