### 问题描述

小蓝最近在学习位运算，由于他的数学不好，于是他去请教小桥，希望能得到小桥的指点。

小桥出了一道练习题：

• 给定 $n$ 个正整数序列。
• 定义 $xor_{l,r} = a_l \oplus a_{l + 1} \oplus ...\oplus a_{r - 1} \oplus a_r$ ，$\oplus$ 为异或运算符号。
• 求 $\prod_{i = 1}^{n}\prod_{j = i}^{n} xor_{l,r}$ 对 $1e9 + 7$ 取模的值。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_1,a_2,a_3,...,a_n$。

输出格式

输出一个正整数，表示 $\prod_{i = 1}^{n}\prod_{j = i}^{n} xor_{l,r}$ 对 $1e9 + 7$ 取模的值。

样例输入

3
5 27 17

样例输出

10327500

评测数据规模

对于 $100$% 的评测数据，$1\leq n \leq 10^6, 1 \leq a_i < 8192$。