atcoder#ABC262D. [ABC262D] I Hate Non-integer Number

[ABC262D] I Hate Non-integer Number

Score : 400400 points

Problem Statement

You are given a sequence of positive integers A=(a1,,aN)A=(a_1,\ldots,a_N) of length NN. There are (2N1)(2^N-1) ways to choose one or more terms of AA. How many of them have an integer-valued average? Find the count modulo 998244353998244353.

Constraints

  • 1N1001 \leq N \leq 100
  • 1ai1091 \leq a_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN

a1a_1 \ldots aNa_N

Output

Print the answer.

3
2 6 2
6

For each way to choose terms of AA, the average is obtained as follows:

  • If just a1a_1 is chosen, the average is a11=21=2\frac{a_1}{1}=\frac{2}{1} = 2, which is an integer.
  • If just a2a_2 is chosen, the average is a21=61=6\frac{a_2}{1}=\frac{6}{1} = 6, which is an integer.
  • If just a3a_3 is chosen, the average is a31=21=2\frac{a_3}{1}=\frac{2}{1} = 2, which is an integer.
  • If a1a_1 and a2a_2 are chosen, the average is a1+a22=2+62=4\frac{a_1+a_2}{2}=\frac{2+6}{2} = 4, which is an integer.
  • If a1a_1 and a3a_3 are chosen, the average is a1+a32=2+22=2\frac{a_1+a_3}{2}=\frac{2+2}{2} = 2, which is an integer.
  • If a2a_2 and a3a_3 are chosen, the average is a2+a32=6+22=4\frac{a_2+a_3}{2}=\frac{6+2}{2} = 4, which is an integer.
  • If a1a_1, a2a_2, and a3a_3 are chosen, the average is $\frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3} = \frac{10}{3}$, which is not an integer.

Therefore, 66 ways satisfy the condition.

5
5 5 5 5 5
31

Regardless of the choice of one or more terms of AA, the average equals 55.