题目描述

定义一个非空集合是合法的，当且仅当它满足以下两个条件。

1. 集合内所有元素 $\operatorname{and}$ 和为 $0$；
2. 它的非空子集中仅有它本身满足 1。

给出一个集合 $S$，求它的合法非空子集数。

输入格式

第一行一个正整数 $n$，表示 $|S|$。
第二行 $n$ 个非负整数 $a_i$，表示集合内的元素。

输出格式

一个整数，表示 $S$ 的合法非空子集数。答案可能很大，请 $\bmod (10^9+7)$ 之后输出。

4
1 2 4 4

5

样例解释

满足条件的集合为 $\{1,2\},\{1,4\},\{1,4\},\{2,4\},\{2,4\}$。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 10^3$，$0\le a_i < 2^{10}$。

题目来源

By hzq84621