#P17818. [ONTAK 2023]WIE

[ONTAK 2023]WIE

题目描述

有 nn 头编号不同的宇宙鲸鱼,第 ii 头的质量为 mim_i。你要选出三头不同的鲸鱼,使新建的星球能够稳定地放在它们的背上。

质量分别为 a,b,ca,b,c 的三头鲸鱼能够使星球稳定,当且仅当 a⊕b⊕ca\oplus b\oplus c 是 a+b+ca+b+c 的正因数。这里 ⊕\oplus 表示按位异或;异或值为 00 时不满足条件。

求合法的选择方案数。只按选中的鲸鱼编号集合区分方案,不区分选择顺序;不同鲸鱼可以具有相同质量。

输入格式

第一行一个整数 nn。第二行 nn 个整数 m1,…,mnm_1,\ldots,m_n。

输出格式

输出合法三元组数量,不取模。

数据范围

1≤n≤1061\le n\le10^6,1≤mi<2111\le m_i<2^{11}。

样例

6
6 2 3 1 4 1
4