Many LCS

Given $K$, construct two non-empty binary strings $S$ and $T$ of length at most 8848 such that they have exactly $K$ different longest common subsequences. More formally, if $L$ is the length of the longest common subsequence of $S$ and $T$, there should exist exactly $K$ distinct binary strings of length $L$ which are subsequences of both $S$ and $T$.

It is guaranteed that under the constraints of this problem such strings always exist.

The only line of input contains a single integer $K$ ($1 \le K \le 10^9$).

Print non-empty binary strings $S$ and $T$ on separate lines. The length of each of them should not exceed 8848. They can have different lengths.

If there is more than one solution, you can print any one of them.

In the first example, the longest common subsequence of 1111 and 00 has length 0, and there is only one string of length 0 that is a subsequence of both, the empty string.

In the second example, the longest common subsequence of 10 and 01 has length 1, and there are 2 strings of length 1 that are subsequences of both $S$ and $T$: 0 and 1.

In the third example, the longest common subsequence of 010 and 1001 has length 2, and there are 3 strings of length 2 that are subsequences of both $S$ and $T$: 00, 01, and 10.

It would be disrespectful to make strings longer than Everest...