Chuỗi Cổng Khởi Động Lại · canuc80k5524

Một hệ thống gồm $n$ cổng kiểm tra, đánh số từ $1$ đến $n$ . Ban đầu, cổng cần vượt qua là cổng $1$ .

Mỗi ngày, hệ thống kiểm tra đúng một cổng. Khi đang ở cổng $i$ , phép kiểm tra thành công với xác suất $p_{i} /100$ :

nếu thành công và $i < n$ , ngày hôm sau chuyển sang cổng $i + 1$ ;
nếu thành công tại cổng $n$ , quá trình kết thúc;
nếu thất bại tại bất kỳ cổng nào, ngày hôm sau quay lại cổng $1$ .

Các kết quả kiểm tra ở những ngày khác nhau độc lập với nhau. Hãy tính kỳ vọng số ngày từ lúc bắt đầu cho đến khi vượt qua toàn bộ $n$ cổng.

Giả sử kỳ vọng viết dưới dạng phân số tối giản $X / Y$ , với $Y > 0$ . Hãy in số nguyên duy nhất $R$ thỏa mãn

0 \leq R < 998244353

R \cdot Y \equiv X (mod 998244353) .

Input

Dòng đầu chứa số nguyên $n$ - số cổng kiểm tra.
Dòng thứ hai chứa $n$ số nguyên $p_{1}, p_{2}, \dots, p_{n}$ ; $p_{i} /100$ là xác suất thành công tại cổng $i$ .

Output

In một số nguyên - giá trị modulo $998244353$ của kỳ vọng theo định nghĩa trên.

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$ .
$1 \leq p_{i} \leq 100$ với mọi $1 \leq i \leq n$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 8$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

3
100 50 100

Output

Giải thích: Gọi $E$ là kỳ vọng số ngày để vượt hai cổng đầu; ta có $E = 2 + E /2$ , nên $E = 4$ . Cổng cuối luôn thành công và cần thêm đúng một ngày, vì vậy đáp án là $5$ .

Hướng giải: Gọi E_i là kỳ vọng số ngày để vượt qua i cổng đầu tiên, luôn bắt đầu từ cổng 1. Đặt E_0 = 0.
Hướng giải: Xét lần thử cổng i. Trước khi hỏi cổng này, ta cần kỳ vọng E_{i-1} ngày để vượt lại các cổng trước, rồi dùng thêm một ngày cho phép kiểm tra hiện tại. Đặt
Hướng giải:

text q_i = p_i / 100. - Hướng giải: Nếu cổng i thành công thì prefix 1..i đã hoàn tất. Nếu thất bại, quá trình trở về đúng trạng thái ban đầu của E_i. Vì thế - Hướng giải:

text E_i = E_{i-1} + 1 + (1-q_i)E_i. - Hướng giải: Chuyển vế cho ta - Hướng giải:

text E_i = (E_{i-1}+1) / q_i. - Hướng giải: Duyệt các cổng theo thứ tự và cập nhật giá trị trên. Trong trường modulo, - Hướng giải:

text 1/q_i = 100 * p_i^(-1) (mod 998244353). - Hướng giải: Do 1 <= p_i <= 100, mọi p_i đều khác 0 theo modulo và có nghịch đảo. Ta tiền xử lý nghịch đảo của 1..100 rồi xử lý toàn bộ dãy trong thời gian tuyến tính. - Chứng minh đúng: Ta chứng minh bằng quy nạp rằng sau khi xử lý cổng i, biến expected bằng E_i. - Chứng minh đúng: Với i=0, chưa cần ngày nào nên E_0=0, đúng với giá trị khởi tạo. - Chứng minh đúng: Giả sử giá trị đã đúng cho E_{i-1}. Một chu kỳ thử cổng i luôn tốn kỳ vọng E_{i-1}+1 ngày. Sau chu kỳ đó, với xác suất q_i ta hoàn tất prefix i; với xác suất 1-q_i ta quay về trạng thái ban đầu và còn kỳ vọng E_i ngày. Do đó phương trình kỳ vọng ở trên là đúng và phép cập nhật tính chính xác E_i. - Chứng minh đúng: Theo quy nạp, sau cổng n, giá trị in ra bằng E_n, chính là đáp án. - Độ phức tạp: Tiền xử lý 100 nghịch đảo mất O(100 log MOD). Phần chính dùng O(n) thời gian và O(1) bộ nhớ ngoài input.