Migrated from Lutece 3025 落叶纷飞

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

一场秋雨过后，银杏树的叶子掉了好多！

$Ain$ 一共收集了 $n$ 片银杏树叶，并给第 $i$ 片树叶赋予了美丽值 $a_i$。

现在他想知道这些树叶的总体美丽度 $B$。总体美丽度的计算方法如下：

对于所有四元组 $(i,j,k,l)$ $(1 \le i,j,k,l \le n)$， 计算 ：

$S=(a_i \& a_j)\bigoplus \ (a_k | a_l)$

若有：

$S \ \equiv \ 0 \ (mod \ 3)$

则总体美丽度:

$B \ += {fib}_{a_i \& a_j} \times \ {fib}_{a_k | a_l}$

其中 ${fib}_i$ 代表斐波那契数列的第 $i$ 项。

由于总体美丽度可能很大，所以你只需要告诉 $Ain$ 总体美丽度对 $998244353$ 取模的结果。

Input

第一行一个整数 $n$ $(1 \le n \le 10^{6})$。 第二行 $n$ 个整数 $a_1,a_2,...,a_n$ $(1 \le a_1,a_2,...,a_n \le 2^{20}-1)$。

Output

一行一个整数，代表所求结果。

Samples

1
14

142129

Constraints

$1 \le n \le 10^{6}$，$1 \le a_1,a_2,...,a_n \le 2^{20}-1$。

Resources

2023 UESTC ICPC Training for Math