U152953 xor问题1

给正整数序列 $a[1\sim n]$，从中选择一个子序列（可以不连续，但不能为空）使其xor和恰好为 $0$，问方案数（mod 1e9+7）。 例如 $a = [1,2,3,4,5]$，答案$ = 3$： - $\{1,2,3\}$ - $\{1,4,5\}$ - $\{2,3,4,5\}$

第一行1个整数 $n$ 第二行 $n$ 个正整数 $a[i]$

一个整数代表答案

对于20%的数据，$n,a[i]\le 100$ 对于60%的数据，$n,a[i]\le 1000$ 对于90%的数据，$n,a[i]\le 10^5$ 且满足 $\sum a[i]\le 10^6$ 对于100%的数据，$1\le n\le 10^6, 1\le a[i]\le 10^9$