k > 2^{n-1}