你听说过 Nim 游戏吗？答案大概是肯定的，但我敢打赌你一定没听说过一种叫 “Steins;Game” 的新游戏！这个游戏之所以这样命名，是因为它是一个用许多堆石头进行的游戏，而 “Stein” 在德语中意为石头。

Alice 和 Bob 现在想玩这个游戏。游戏规则如下：

有 $n$ 堆石头排成一排。每堆石头被染成白色或黑色。第 $i$ 堆石头包含 $a_i$ 个石头。游戏从 Alice 开始，两人轮流进行操作，每次可以选择以下其中一种：

• 从最小的黑色石堆（即所有黑色石堆中石头数量最少的那一堆）中取走任意数量的石头；或者
• 从任意白色石堆中取走任意数量的石头。

当没有剩余石头时游戏结束，最后进行操作的玩家输掉游戏。

现在所有石堆的大小已经固定，但尚未染色。Bob 贿赂了裁判，获得了亲自为所有石堆染色的机会。现在他想知道，有多少种染色方案能让他获胜（假设 Alice 和 Bob 都采取最优策略）？由于答案可能很大，你只需要输出其对 $1\,000\,000\,007$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示游戏中的石堆数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{18}$)，表示每堆石头的数量。

输出格式

输出一行一个整数，表示 Bob 获胜的染色方案数，对 $1\,000\,000\,007$ 取模。

样例

样例输入 1

2
1 1

样例输出 1

4

样例输入 2

2
1 2

样例输出 2

1

样例输入 3

1
3

样例输出 3

0

说明

对于第一个测试用例，Bob 在所有四种染色方案下都能获胜。

对于第二个测试用例，Bob 获胜的唯一方法是将两堆石头都染成黑色，这样 Alice 在第一步被迫取走第一堆，然后 Bob 可以取走第二堆的所有石头并赢得游戏。

对于第三个测试用例，无论 Bob 如何给这唯一的一堆石头染色，Alice 都可以取走整堆石头并赢得游戏。