Description

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

1、集合内所有元素and和为0

2、它的非空子集中仅有它本身满足1

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

Format

Input

第一行一个正整数n,表示|S|

第二行n个非负整数ai，表示集合内的元素。

n≤1000，ai<1024

Output

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

Samples

4
1 2 4 4

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