B. Duas assinaturas

Time limit: 3000 msMemory limit: 256 MB

Dada uma sequência de inteiros positivos $a_1,\ldots,a_n$ , conte os subconjuntos não vazios de índices $I$ para os quais

$\gcd(a_i : i\in I)=\bigoplus_{i\in I}a_i.$

O símbolo $\gcd$ representa o máximo divisor comum (MDC). O símbolo $\oplus$ representa o XOR bit a bit: em cada posição binária, o resultado tem bit $1$ se uma quantidade ímpar dos números escolhidos tem bit $1$ nessa posição. Para um único número, tanto o MDC quanto o XOR são esse número.

Subconjuntos de índices diferentes contam separadamente, mesmo se os valores correspondentes forem iguais. Imprima a resposta módulo $998\,244\,353$ .

Input

A primeira linha contém $n$ ( $1\le n\le200\,000$ ).

A segunda linha contém $n$ inteiros $a_1,\ldots,a_n$ ().

Output

Imprima a quantidade pedida, módulo $998\,244\,353$ .

Samples

Sample 1

Input

3
2 3 4

Output

São válidos os três subconjuntos com um índice e o subconjunto de índices $\{1,2\}$ : $\gcd(2,3)=2\oplus3=1$ .

Sample 2

Input

3
1 1 1

Output

B. Duas assinaturas

Input

Output

Samples

Sample 1

Sample 2

Sample 3