And Equals Or

Chef has a ($0$-indexed) **binary** string $S$ of length $N$ such that $N$ is a **power of $2$**. Chef wants to find the number of pairs $(i, j)$ such that: - $0 \leq i,j \lt N$ - $S_{i|j} = S_{i\&j}$ (Here $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR) and $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND))