Question
All about Average
Bob has a sequence of positive integers A=(a1,. , aN) of length N. But Bob hates non- integer number so he wants to find how many ways are there to choose one or more terms of A and have an integer- valued average?
There are a total of (2N − 1) ways to choose one or more terms of A.
As the count could be very large, so do modulo 998244353.
There are a total of (2N − 1) ways to choose one or more terms of A.
As the count could be very large, so do modulo 998244353.
Input
The first line of the input contains a single integer N.
The second line contains N integers a1,. , aN.
Constraints:
1 <= N <= 100
1 <= ai <= 10^9
All values in input are integers.
The second line contains N integers a1,. , aN.
Constraints:
1 <= N <= 100
1 <= ai <= 10^9
All values in input are integers.
Output
Print the answer in a single line.
Example
Sample Input 1:
3
2 6 2
Sample Output 1:
6
Explanation 1:
For each way to choose terms of A, the average is obtained as follows:
If just a1 is chosen, the average is a1/2 = 2/1 = 2, which is an integer.
If just a2 is chosen, the average is a2/1 = 6/1 = 6, which is an integer.
If just a3 is chosen, the average is a3/1 = 2/1 = 2, which is an integer.
If a1 and a2 are chosen, the average is (a1+a2)/2 = (2+6)/2 = 4, which is an integer.
If a1 and a3 are chosen, the average is (a1+a3)/2 = (2+2)/2 = 2, which is an integer.
If a2 and a3 are chosen, the average is (a2+a3) = (6+2)/2 = 4, which is an integer.
If a1, a2, and a3 are chosen, the average is (a1+a2+a3)/3 = (2+6+2)/3 = 10/3, which is not an integer.
Therefore, 6 ways satisfy the condition.
Sample Input 2:
5
5 5 5 5 5
Sample Output 2:
31
3
2 6 2
Sample Output 1:
6
Explanation 1:
For each way to choose terms of A, the average is obtained as follows:
If just a1 is chosen, the average is a1/2 = 2/1 = 2, which is an integer.
If just a2 is chosen, the average is a2/1 = 6/1 = 6, which is an integer.
If just a3 is chosen, the average is a3/1 = 2/1 = 2, which is an integer.
If a1 and a2 are chosen, the average is (a1+a2)/2 = (2+6)/2 = 4, which is an integer.
If a1 and a3 are chosen, the average is (a1+a3)/2 = (2+2)/2 = 2, which is an integer.
If a2 and a3 are chosen, the average is (a2+a3) = (6+2)/2 = 4, which is an integer.
If a1, a2, and a3 are chosen, the average is (a1+a2+a3)/3 = (2+6+2)/3 = 10/3, which is not an integer.
Therefore, 6 ways satisfy the condition.
Sample Input 2:
5
5 5 5 5 5
Sample Output 2:
31