最小集合

时间限制:100s      空间限制:128MB

题目描述

定义一个非空集合是合法的,当且仅当它满足以下两个条件。
1、集合内所有元素and和为0
2、它的非空子集中仅有它本身满足1
给出一个集合S,求它的合法非空子集数。


输入格式

第一行一个正整数n,表示|S|
第二行n个非负整数ai,表示集合内的元素。
n≤1000,ai<1024


输出格式

一个整数,表示S的合法非空子集数。答案可能很大,请mod 1e9+7之后输出。


样例输入

4
1 2 4 4

样例输出

5
样例解释:满足条件的集合为{1,2},{1,4},{1,4},{2,4},{2,4}

提示

没有写明提示


题目来源

By hzq84621