题解 | 变化的数组

const MOD = 1000000007n;
const MAX_COMB = 31n; // 对应 C++ 循环上限 31
const inv2 = 500000004n; // 2 的逆元 mod 1e9+7

// 快速幂（BigInt 实现，避免溢出）
function powMod(a, b) {
    let res = 1n;
    a = a % MOD;
    b = BigInt(b);
    while (b > 0n) {
        if (b & 1n) {
            res = (res * a) % MOD;
        }
        a = (a * a) % MOD;
        b = b >> 1n;
    }
    return res;
}

// 组合数 C(n, m)（完全复刻 C++ cal 函数）
function comb(n, m) {
    n = BigInt(n);
    m = BigInt(m);
    if (m < 0n || m > n) return 0n;
    let res = 1n;
    for (let i = 1n, j = n - m + 1n; i <= m; i++, j++) {
        const invI = powMod(i, MOD - 2n);
        res = (res * j) % MOD;
        res = (res * invI) % MOD;
    }
    return res;
}

// 主函数：完全对齐 C++ 执行流程
function main() {
    const fs = require('fs');
    const data = fs.readFileSync(0, 'utf8'); // 读取所有输入（兼容所有环境）
    const tokens = data.trim().split(/\s+/).filter(Boolean);
    let ptr = 0n;

    try {
        // 严格按 C++ 解析输入（n, m, k 为大整数）
        const n = BigInt(tokens[ptr++]);
        const m = BigInt(tokens[ptr++]);
        const k = BigInt(tokens[ptr++]);
        const A = [];
        for (let i = 0n; i < n; i++) {
            A.push(BigInt(tokens[ptr++]));
        }

        // 预计算概率 p[0..31]（完全复刻 C++ 逻辑）
        const p = new Array(32).fill(0n);
        const pow2k = powMod(2n, k);
        const inv2k = powMod(pow2k, MOD - 2n); // 1/(2^k) mod MOD

        // p[i] = C(k,i) * inv2k mod MOD
        for (let i = 0n; i <= 30n; i++) {
            const c = comb(k, i);
            p[Number(i)] = (c * inv2k) % MOD;
        }

        // p[31] = 1 - sum(p[0..30]) mod MOD
        let sumP = 0n;
        for (let i = 0n; i <= 30n; i++) {
            sumP = (sumP + p[Number(i)]) % MOD;
        }
        p[31] = (1n - sumP + MOD) % MOD;

        // 计算答案（完全复刻 C++ 循环）
        let ans = 0n;
        for (const x of A) {
            let currentX = x;
            for (let j = 0n; j <= 31n; j++) {
                // 计算 currentX * p[j] mod MOD（处理负数）
                const xMod = ((currentX % MOD) + MOD) % MOD;
                const term = (xMod * p[Number(j)]) % MOD;
                ans = (ans + term) % MOD;
                // 更新 currentX = currentX + (currentX & m)
                currentX += (currentX & m);
            }
        }

        // 输出结果（转为 Number 避免 BigInt 后缀）
        console.log(Number(ans % MOD));
    } catch (e) {
        console.log(0);
    }
}

main();