对于给定的长度为 的数组 和一个整数 ，保证全部非负。你需要执行 次操作，每一次操作如下： 对数组中的每一个元素 ，投掷一次硬币，若硬币为正则将这个元素修改为 ；反之，则不操作； 在全部 次操作完成后，求解数组元素和的期望。 在本题中， 运算即按位与运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki上的相关章节 。

输入描述:

第一行输入三个整数 代表数组中的元素数量、修改公式中的定值、操作次数。第二行输入 个整数 代表数组元素。

输出描述:

在一行上输出一个整数，代表  次操作完成后数组元素和的期望。可以证明答案可以表示为一个不可约分数 ，为了避免精度问题，请直接输出整数 作为答案，其中 ， 是满足 的整数。