Bánh kẹo ngày Tết được xem như một biểu tượng của sự may mắn trong năm mới. Quầy hàng của Tèo chỉ bán ~N~ viên kẹo, nhưng số vị của kẹo có thể lên đến ~10^9~ loại. Với số tiền lì xì hiện có của mình, Tí chỉ có thể mua ~M~ viên kẹo bất kì từ quầy hàng của Tèo, biết rằng xác suất chọn ~M~ viên kẹo từ ~N~ viên kẹo là như nhau. Tí rất "mê tín", nên tin rằng độ may mắn của mình trong năm mới sẽ tỉ lệ thuận với số vị kẹo khác nhau mà Tí bốc được bất kì từ quầy hàng của Tèo.
Yêu cầu: Bạn hãy giúp Tí tính giá trị kỳ vọng của số vị kẹo khác nhau mà Tí có thể bốc được với ~M~ từ ~1~ đến ~N~.
Dữ liệu vào
- Dòng đầu tiên chứa một số nguyên ~N~ ~(1 \le N \le 10^5)~ là số viên kẹo mà quầy hàng của Tèo có.
- Dòng thứ hai chứa ~N~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~ là vị kẹo của viên kẹo thứ ~i~.
Dữ liệu ra
Một dòng gồm ~N~ số nguyên, số nguyên thứ ~i~ ~(1 \le i \le N)~ là giá trị kì vọng của số vị kẹo khác nhau mà Tí có thể bốc được khi Tí chỉ có khả năng bốc ~i~ viên. Kết quả chia dư cho ~10^9 + 33~.
Ví dụ:
Dữ liệu vào
6
2 3 1 2 2 8
Kết quả ra
1 400000015 350000014 3 500000020 4
Giải thích
Với ~M = 1~, Tí có thể bốc ~1~ viên kẹo bất kì từ ~6~ viên kẹo trên, số vị kẹo khác nhau luôn là ~1~, nên giá trị kì vọng là ~1~.
Với ~M = 2~, các trường hợp mà Tí có thể bốc được như sau:
- Viên kẹo ~1~ và ~2~, có ~2~ vị khác nhau
- Viên kẹo ~1~ và ~3~, có ~2~ vị khác nhau
- Viên kẹo ~1~ và ~4~, có ~1~ vị khác nhau
- Viên kẹo ~1~ và ~5~, có ~1~ vị khác nhau
- ...
- Viên kẹo ~5~ và ~6~, có ~2~ vị khác nhau
Vậy giá trị kì vọng có thể được tính như sau: ~2 * \frac{1}{15} + 2 * \frac{1}{15} + 1 * \frac{1}{15} + 1 * \frac{1}{15} + ... + 2 * \frac{1}{15} = \frac{9}{5}~. Kết quả in ra là ~\frac{9}{5}~ ~mod~ ~(10^9 + 33) = 400000015~
Tương tự với ~M = 3~, ~M = 4~, ~M = 5~, ~M = 6~.
Comments