Bạn được cho một dãy số nguyên dương \(a_1, a_2, ... a_n\) độ dài \(n\). Đếm số cách chọn ra một tập con từ dãy số \(a\) (có thể không liên tiếp) sao cho giá trị trung bình của tập con đó là một số nguyên.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương \(n\) (\(1 \leq n \leq 100\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_i\) (\(1 \leq a_i \leq 10^9\)).

Dữ liệu ra

• Một dòng duy nhất là kết quả bài toán modulo 998244353.

Ví dụ

Notes

Ở ví dụ 1, ta có thể chọn các tập:

\(\dfrac{a_1}{1} = 2\) là một số nguyên.

\(\dfrac{a_2}{1} = 6\) là một số nguyên.

\(\dfrac{a_3}{1} = 2\) là một số nguyên.

\(\dfrac{a_1 + a_2}{2} = 4\) là một số nguyên.

\(\dfrac{a_1 + a_3}{2} = 2\) là một số nguyên.

\(\dfrac{a_2 + a_3}{2} = 4\) là một số nguyên.

\(\dfrac{a_1 + a_2 + a_3}{3} = \dfrac{10}{3}\) không phải là một số nguyên, nên ta không chọn tập này.