偶数個ある要素は打ち消されて 000 になるので、それぞれの要素を最大 111 個選べると思うことにする。
この数列はOEISにあるため、解ける。 O(N)O(N)O(N)
(XORの性質を観察すると,2N2^N2N 未満から KKK 個選んで 000 以外を作る場合の通り数はすべて同じことがわかる。)