#P4762. 最小集合

    ID: 2946 传统题 3000ms 128MiB 尝试: 206 已通过: 85 难度: 9 上传者: 标签>CF2700省选/NOI-补集转化容斥原理状压 DP计数 DP滚动数组Byhzq84621

最小集合

题目描述

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

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

给出一个集合 SS,求它的合法非空子集数。

输入格式

第一行一个正整数 nn,表示 ∣S∣|S|。 第二行 nn 个非负整数 aia_i,表示集合内的元素。

输出格式

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

4
1 2 4 4
5

样例解释

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

数据规模与约定

对于 100%100\% 的数据,1≤n≤1031\le n\le 10^3,0≤ai<2100\le a_i < 2^{10}。

题目来源

By hzq84621