Numb

Time limit1sMemory limit512 MB

Summary

Build an n-digit binary string whose prefixes all leave distinct remainders mod n and whose whole value is divisible by n.

Level: Medium6 of 10
Topics: Greedy, Math, Number theory, Implementation
Solved: No attempts yet

Problem

You are given an even integer $n$ . Construct a binary number $a = \overline{a_1 a_2 \ldots a_n}$ consisting of $n$ binary digits such that $a$ is divisible by $n$ , and all numbers $\overline{a_1 a_2 \ldots a_i}$ (the prefixes of $a$ in binary notation) for $i = 1, 2, \ldots, n$ have distinct remainders modulo $n$ .

Input

The only line of input contains an integer $n$ ( $2 \le n \le 1000$ , $n$ is even).

Output

Print the desired number $\overline{a_1 a_2 \ldots a_n}$ as a string of $n$ binary digits. Leading zeroes are disallowed. If there are several possible answers, print any one of them. It is guaranteed that at least one answer exists under these constraints.

Examples2

Example 1
Input
```
2
```
Expected output
```
10
```
Example 2
Input
```
4
```
Expected output
```
1100
```