Painter's Studio

The Painter's Studio is preparing to mass-produce paintings. The paintings are made with the help of square matrices of various sizes. A matrix of size $i$ has $2^i$ rows and $2^i$ columns, with holes at the intersections of some rows and columns. A matrix of size $0$ is a single cell and has exactly one hole.

For $i > 0$, a matrix of size $i$ is built from four squares of size $2^{i-1} \times 2^{i-1}$. The top-left square has no holes, while the top-right, bottom-left, and bottom-right squares are each a matrix of size $i-1$.

A painting is made as follows. First we fix three non-negative integers $n$, $x$, and $y$. We take two matrices of size $n$, lay one on top of the other, and shift the upper one $x$ columns to the right and $y$ rows up. We place this pattern on a white canvas and paint the overlapping region yellow wherever a hole of the upper matrix meets a hole of the lower matrix. Each such coincidence leaves one yellow stain.

For example, take two matrices of size $2$ and shift the upper one $2$ columns right and $2$ rows up.

In this case the holes coincide in exactly three places.

Write a program that reads the size of the two matrices and the shift amounts and prints the number of yellow stains.

The first line contains one integer $n$ ($0 \le n \le 100$), the size of the matrices. The second line contains one integer $x$ and the third line one integer $y$ ($0 \le x, y \le 2^n$). The upper matrix is shifted $x$ columns to the right and $y$ rows up.

Print a single line with the number of yellow stains on the canvas.