Bugaboo: A Two‐Set Asymmetric Game

Ysuperman has discovered an asymmetric game called Bugaboo. The game is played by two players, Qingshan and Daniel, starting with two sets of positive integers. Initially, Qingshan has a set S and Daniel has a set T (both are chosen as arbitrary subsets of a given set R of positive integers). The players take turns – Qingshan moves first. In each move, the current player chooses any two different numbers x and y from his own set (his set may include numbers he obtained earlier) such that their absolute difference d = |x − y| is not present in the other player’s set. He then adds d to the other player’s set. The first player who cannot make a move loses.

Ysuperman now considers all 2^|R| possible choices for S and independently all 2^|R| possible choices for T. Your task is to count in how many of these configurations Qingshan has a winning strategy, modulo 998244353.

Important note: A move is legal for a player if and only if his current set contains at least two numbers and there exists a pair (x, y) (with x ≠ y) with |x − y| not already in the opponent’s set. Furthermore, when a set contains at least two numbers, its gcd (greatest common divisor) is the smallest positive number that will eventually appear in its closure under absolute differences. In an optimal play the current player will always add \gcd(S) (if playing from set S) to his opponent’s set provided it is missing, and similarly Daniel will add \gcd(T) if possible. Thus, if Qingshan’s initial set S (of size at least 2) has g_S = \gcd(S) and g_S is not in T then Qingshan can make a move. After his move, T becomes T \cup {g_S}. Then, if T has at least two numbers and its gcd g_T = \gcd(T) is not in S, Daniel can move by adding g_T to S. With both players playing optimally, Qingshan wins if and only if the following conditions hold:

1. S has at least two elements and \gcd(S) is not contained in T, and
2. Either T has fewer than two elements, or if T has at least two elements then \gcd(T) is already in S.

Count the number of pairs (S, T) (with S and T being any subsets of R) for which Qingshan wins. Since the answer might be very large, output it modulo 998244353.

inputFormat

The input begins with an integer n (1 ≤ n ≤ 10) denoting the number of elements in R. The next line contains n distinct positive integers separated by spaces (the elements of R).

outputFormat

Output a single integer – the number of winning initial configurations for Qingshan modulo 998244353.

sample

2
1 2

2