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.

Input

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

Output

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

Example

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.