Migrated from Lutece 1488 柱爷搞搞搞搞搞xxxxoooorrrrr

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

给你$N$个限制条件$Limit[i]$，表示第$i$个数的取值范围在$[0,Limit[i]]$内，现在柱爷想知道有多少种取值方法能使这些数异或起来等于$0$

当然柱爷早就知道了答案，柱爷现在想问你知道吗

Input

输入第一行有一个整数$N$.$( 1 \leq N \leq 28 )$

第二行有$N$个整数，表示$Limit[i]$.$( 0 \leq Limit[i] \leq 10^9 )$

Output

输出一行表示答案对$10^9+7$取模后的值

Samples

3
1 2 3

6

Note

柱爷：你能很轻易的设计出复杂度为$O(\prod_{i=1}^n(Limit[i]+1))$的算法

Resources

每周一题 Div3