CODENEW - Mã mới
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Đấ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.

Yêu cầu: 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.

Dữ liệu

Dòng 1: Số nguyên dương N.
Dòng i trong N dòng tiếp theo chứa số nguyên dương maxi.

Kết quả

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

 

Ví dụ

 

Input 

2
1
3

Output 

2

Input 

4
4
4
4
4

Output

24

Giải thích:

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

Giới hạn

1 ≤ N ≤ 105.
1 ≤ maxi ≤ 109.


Nguồn: vnspoj C11

Back to Top