Hai thí sinh gx và lc tham gia kỳ thi sơ loại OLP, trong đó có một dạng bài là trắc nghiệm đơn chọn – mỗi câu chỉ có một đáp án đúng.

Đề gồm \(n\) câu hỏi, câu thứ \(i\) có \(a_i\) lựa chọn (đánh số từ \(1\) đến \(a_i\)). Mỗi phương án đều có xác suất đúng như nhau.

• lc làm bài bằng cách chọn ngẫu nhiên một đáp án cho mỗi câu → kỳ vọng làm đúng:
  \[\sum_{i=1}^{n} \frac{1}{a_i}\]

• gx thì làm bài nghiêm túc, làm đúng hết. Nhưng khi chép đáp án sang phiếu trả lời thì lại chép lệch:

  • Đáp án câu thứ \(i\) bị ghi vào vị trí câu thứ \(i+1\)
  • Đáp án câu thứ \(n\) bị ghi nhầm vào vị trí câu thứ \(1\)

Vì thế, gx muốn biết kỳ vọng số câu mình làm đúng sau khi bị lệch như vậy.

Giả sử gx làm đúng hết nhưng chỉ chép lệch vị trí, hãy tính kỳ vọng số câu đúng sau khi nộp bài.

Định dạng vào

• Một dòng chứa 5 số nguyên: n A B C a₁
• Dãy a được sinh như sau:

scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
for (int i = 2; i <= n; i++)
    a[i] = ((long long) a[i - 1] * A + B) % 100000001;
for (int i = 1; i <= n; i++)
    a[i] = a[i] % C + 1;

Định dạng ra

• In ra một số thực, là kỳ vọng số câu gx làm đúng (sau khi chép lệch).
• Làm tròn đến 3 chữ số thập phân.

Input 1

3 2 0 4 1

Output 1

1.167

Giải thích

Với \(a = \{2,3,1\}\), tổng cộng có 6 tổ hợp đáp án đúng có thể xảy ra, mỗi tổ hợp xác suất \(\frac{1}{6}\). Tính số câu đúng với từng tổ hợp sau khi chép lệch → kỳ vọng = \(\frac{7}{6} \approx 1.167\)

Ràng buộc

• Với 30% dữ liệu: \(n \le 10\), \(C \le 10\)
• Với 80% dữ liệu: \(n \le 10^4\), \(C \le 10\)
• Với 90% dữ liệu: \(n \le 5 \times 10^5\), \(C \le 10^8\)
• Với 100% dữ liệu: \(2 \le n \le 10^7\), \(0 \le A,B,C \le 10^8\), \(1 \le a_i \le 10^8\)