#P13769. [2019年备战北大冬令营]飞机
[2019年备战北大冬令营]飞机
题目描述
飞机的关键部位数 可以是 到 中的任意一个整数。对于固定的 ,将这些部位视为彼此可区分。有 个彼此可区分的零件,每个零件可以被丢弃,或装在 个部位中的任意一个。每个部位可以装多个零件,也可以空着。
飞机的上天值是所有已安装零件的权值按位或所得的结果。没有安装任何零件时,上天值为 。求对所有 的方案中,上天值恰好为 的方案总数。
输入格式
第一行四个整数 ,其中 是零件权值的最大可能值。第二行 个整数,依次表示各零件的权值 。
输出格式
输出一行一个整数,表示答案对 取模的结果。
数据范围
所有数据满足 ,,,,。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 20 | |
| 2 | , | |
| 3 | ||
| 4 | ||
| 5 | 无 |