Description

有$n$个数分别为$a_1,a_2,...,a_n$，他们都是$[1,n]$的数

小a和小b打算分掉这些数，小a取一个集合的数，小b取一个集合的数，选的集合不能相交并且不需要把所有数选完

请问有多少种情况小a选的数的异或和大于小b选的数的异或和

由于情况可能有很多种，输出对$998244353$取模的结果就可以了

Input

第一行一个整数$n$

第二行$n$个整数，分别代表$a_1,a_2,a_3,...a_n$

Output

一个整数表示答案，对$998244353$取模

Sample Input

3

1 2 3

Sample Output

9

Constraints

本题使用Subtask评测

Subtask1（10pts）： $n\leq 15$

Subtask2（20pts）： $n\leq 100$

Subtask3（30pts）： $n\leq 3000$

Subtask4（40pts）： $n\leq 1000000$