The fastest way - not to use power of 2 at all:

static int solve(IEnumerable<long> a)
{
    ulong[] fib = new ulong[100]; fib[0] = 1; fib[1] = 2;
    int i = 2;
    ulong max = (ulong)a.Max(), nextFib = 3;
    // fill out fibonachi seq
    while (nextFib <= max) { nextFib = fib[i - 1] + fib[i - 2]; fib[i++] = nextFib; }
    // fill out bitwise future result
    var pow2 = a.Aggregate(Enumerable.Repeat(false, i).ToArray(), (xor, next)=> { zen(fib, xor, (ulong)next); return xor; });
    i = pow2.Length;
    ulong ret = 0;
    int idx = 0;
    ulong pow2_60_mod1000000007 = 536_396_504, mod = 1; // = 2^60 mod 1000000007, 2^61%1000000007=(536_396_504*2)%1000000007
    while (i > 0)
    {
        ret = (ret + mod*(Convert.ToUInt64(string.Join("", pow2.Skip((idx++) * 60).Take(60).Reverse().Select(b=>b?"1":"0")), 2)%1000000007)%1000000007)%1000000007;
        mod = (mod * pow2_60_mod1000000007) % 1000000007;
        i -= 60;
    }
    return (int)ret; // pow2.Aggregate((ulong)0, (ret, next)=>(ret + poq2mod(pow2[i], ref i))%1000000007);
}
private static void zen(ulong[] fibs, bool[] pow2, ulong next)
{
    if (next < 1) return;
    int idx = fibs.TakeWhile(n => n <= next && n > 0).Count();
    do
    {
        if(fibs[--idx] <= next)
        {
            pow2[idx] = !pow2[idx];
            next -= fibs[idx];
        }
    }
    while (next > 0);
}

Then you have just an array of bits for idx of pow 2...