门格海绵（Menger sponge）是一种简单的三维分形。其 $L$ 级近似可以通过以下算法构造：

从一个单一的实心 $1 \times 1 \times 1$ 立方体开始，其相对顶点位于 $(0, 0, 0)$ 和 $(1, 1, 1)$。 对于每次迭代 $i = 1, \dots, L$： 对于每个立方体： 将立方体切割成 $3 \times 3 \times 3$ 的 27 个子立方体网格。 删除不与父立方体边缘接触的 7 个子立方体（参见插图）。

$L$ 级门格海绵中的点是指在运行上述算法后保留下来的点。恰好位于保留在海绵中的立方体边界上的点也属于海绵的一部分。

上图展示了 $L = 0$ 到 $L = 3$ 的结果。

给定级别 $L$ 和一个由三个有理数坐标给出的空间点，确定该点是否在 $L$ 级门格海绵中。

输入格式

输入包含一行，包含七个整数 $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$

其中 $L$ 是门格海绵的级别，所求点为 $\left( \frac{x_{\text{num}}}{x_{\text{denom}}}, \frac{y_{\text{num}}}{y_{\text{denom}}}, \frac{z_{\text{num}}}{z_{\text{denom}}} \right)$。

输出格式

输出一个整数，如果该点在 $L$ 级门格海绵中，则输出 1，否则输出 0。

样例

样例输入 1

1000 1 3 1 3 1 3

样例输出 1

1

样例输入 2

2 49 81 5 6 20 81

样例输出 2

1

样例输入 3

3 49 81 5 6 20 81

样例输出 3

0