偶数個ある要素は打ち消されて 00 になるので、それぞれの要素を最大 11 個選べると思うことにする。

この数列はOEISにあるため、解ける。 O(N)O(N)

(XORの性質を観察すると,2N2^N 未満から KK 個選んで 00 以外を作る場合の通り数はすべて同じことがわかる。)