30994번 - 지도에 얼룩과 잉크를 더하며 스페셜 저지

문제

한별이는 확통 수업을 듣다가, 우연히 어떤 문제를 보게 되었다.

50ドル\times 50$개의 칸으로 구성된 지도가 있다. 지도의 $i$행 $j$열에 있는 칸의 좌표를 $(i,j)$라고 표기하자. $(i,j)$에서 $(i+1,j)$과 $(i,j+1)$로 이동할 수 있을 때, $(1,1)$에서 $(50,50)$으로 가는 방법은 몇 가지인가?

이 문제가 너무나 쉽다고 생각한 한별이는, 문득 칸들 중 일부에 얼룩과 잉크를 더해서, 이동할 수 없도록 하면 재미있겠다고 생각했다. 이에 한별이는 그녀의 친구 두별이에게 문제를 만들어달라고 하였다. 구체적으로, 두별이가 문제를 만들고 한별이가 이를 푸는 과정은 다음과 같다.

• 두별이가 각각의 $(i,j)(1\le i\le 50,1\le j\le 50)$에 얼룩 혹은 잉크를 칠하거나, 혹은 칠하지 않는다. 얼룩 혹은 잉크가 칠해진 칸으로는 이동할 수 없을 때, 한별이가 $(1,1)$에서 $(50,50)$으로 이동하는 경우의 수를 구한다. $(1,1)$ 혹은 $(50,50)$이 얼룩 혹은 잉크로 칠해져 있는 경우, 경우의 수는 0이다.

두별이는 한별이를 위해 문제를 몇 개 만들어 줬는데, 한별이가 계속해서 답을 틀린다는 사실을 알게 되었다. 두별이는 한별이가 답을 틀려서 속상해하는 걸 원치 않았기 때문에, 점성술을 사용해 어떤 답을 말할지 미리 알아내어 그에 알맞게 지도에 얼룩과 잉크를 칠하기로 마음먹었다. 그러나, 한별이가 말할 답에 알맞게 지도에 얼룩과 잉크를 칠하는 것은 결코 쉽지 않았다... 두별이를 대신해서 지도에 얼룩과 잉크를 대신 칠해 주자!

입력

첫 번째 줄에 한별이가 말할 정수 $K$가 주어진다.

출력

두별이가 만들 지도의 상태를 출력한다. 50ドル$개의 줄에 걸쳐 줄당 50ドル$개의 정수를 공백으로 구분하여 출력해야 하며, $i$행의 $j$번째 정수가 1ドル$이면 아래에서 $i$번째 행,왼쪽에서 $j$번째 열에 얼룩 혹은 잉크를 칠했다는 것이고, 0ドル$이라면 얼룩 혹은 잉크를 칠하지 않았다는 것이다.

두별이가 출력하는 지도에서 주어진 조건에 따라 목적지에 도착하는 경우의 수가 $K$여야 한다.

제한

• 1ドル\le K\le 10^{18}$

노트

위의 예제는 이해를 돕기 위한 것으로, 실제로는 출력이 50ドル\times 50$의 행렬이 아니기 때문에 올바른 출력이 아니다.

여담으로, 원래 문제의 답은 100891344545564193334812497256ドル$이다.