#P18220. Donkey, Keep Watch
Donkey, Keep Watch
Donkey, Keep Watch
Donkey、Shrek 和 Puss in Boots 潜入了仙女教母的魔药工厂。他们没能找到需要的魔药,只能自己调配。
工厂里有 瓶魔药,第 瓶的效力为整数 。他们需要选取一个非空的魔药子集混合。混合后的魔药具有三个属性:
- 甜度:所选魔药效力的按位异或(XOR);
- 香气:所选魔药效力的按位与(AND);
- 持续时间:所选魔药效力的按位或(OR)。
当且仅当甜度与香气的普通算术和等于持续时间时,得到的是好魔药。求有多少种选择方法,对 取模。
换言之,求数组 的非空子序列 中,满足
$$\operatorname{XOR}(s)+\operatorname{AND}(s)=\operatorname{OR}(s)$$的个数。按下标选择;即使两瓶魔药效力相同,它们仍是不同的魔药。不要求选择连续的一段。
输入格式
第一行包含整数 。
第二行包含 个整数 。
本题只有一组数据。
输出格式
输出一个整数,表示答案对 取模的结果。
数据范围
- ;
- 。
样例
5
1 2 3 4 5
11
样例说明
任意选择两瓶魔药都满足条件,共有 种。另外,选择效力为 的三瓶也满足条件,因此答案是 。
例如 的按位或为 ,按位与为 ,按位异或为 ,所以 ,能调配出好魔药。