C11ID - Mã số

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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

Dữ liệu

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

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 10 9 .

Ví dụ 

Input 1:
2
1
3

Output 1:
2
Input 2:
4
4
4
4
4 
Output 2:
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 ≤ 10 5 .
  • 1 ≤ max i ≤ 10 9 .

  • Người up: tohuuquan