Problem J
Menger Sponge

The Menger sponge is a simple 3D fractal. Its level-$L$ approximation can be constructed with the following algorithm:

• Start with a single solid $1\times 1\times 1$ cube with opposite corners at $(0, 0, 0)$ and $(1, 1, 1)$.

• For each iteration $i = 1,\ \dotsc \ ,L$:

  • For each cube:

    • Cut the cube into a regular $3\times 3\times 3$ grid of $27$ subcubes.

    • Delete the seven subcubes that don’t touch an edge of the parent cube (see illustration).

The points in the level-$L$ Menger sponge are those that remain after running the above algorithm. Points exactly on the boundary of cubes that remain in the sponge are part of the sponge.

The picture below shows the result for $L = 0$ through $L = 3$:

Given a level $L$ and a point in space given by three rational coordinates, determine if the point is in the level-$L$ Menger sponge.

Input

The single line of input contains seven integers $L$, $x_{\text{num}}$, $x_{\text{denom}}$, $y_{\text{num}}$, $y_{\text{denom}}$, $z_{\text{num}}$, $z_{\text{denom}}$:

• $0 \le L \le 10^5$

• $0 < x_{\text{num}} < x_{\text{denom}} \le 10^6$

• $0 < y_{\text{num}} < y_{\text{denom}} \le 10^6$

• $0 < z_{\text{num}} < z_{\text{denom}} \le 10^6$

where $L$ is the level of the Menger Sponge and the point in question is $\left(\frac{x_{\text{num}}}{x_{\text{denom}}},\frac{y_{\text{num}}}{y_{\text{denom}}},\frac{z_{\text{num}}}{z_{\text{denom}}}\right)$.

Output

Output a single integer, which is $1$ if the point is in the level-$L$ Menger Sponge, or $0$ if not.

1000 1 3 1 3 1 3

1

2 49 81 5 6 20 81

1

3 49 81 5 6 20 81

0