멩거 스펀지

멩거 스펀지는 간단한 3차원 프랙털이다. 레벨 $L$ 근사는 다음 알고리즘으로 만들 수 있다:

• 대각선 꼭짓점이 $(0,0,0)$과 $(1,1,1)$인 속이 찬 $1 \times 1 \times 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을 정수 하나로 출력한다.