22166번 - Обратная задача о черепашке 스페셜 저지다국어

문제

Одной из задач, решаемых методом динамического программирования, является задача о черепашке. Приведем условие этой задачи.

Задано поле размером n на m клеток. При этом для каждой клетки поля задано, является она разрешенной или запрещенной (левая верхняя и правая нижняя клетки обязательно разрешены). В левой верхней клетке находится черепашка. Черепашка за один ход может переместиться в соседнюю разрешенную клетку поля, которая находится либо справа, либо снизу от клетки, в которой она сейчас находится. Необходимо определить число путей, которыми черепашка может достичь правой нижней клетки поля, начав путь из левой верхней клетки.

Вам предлагается решить обратную задачу, а именно, найти такое поле, что число путей черепашки будет равно k.

입력

Первая строка содержит число k (1 ≤ k ≤ 10¹⁸).

출력

В первой строке выведите два целых числа, разделенных пробелом, — n и m. Эти числа не должны быть менее единицы или превышать 300.

Затем выведите n строк по m символов в каждой — описание поля. Разрешенной клетке поля должен соответствовать символ «1», запрещенной — «0». Левая верхняя и правая нижняя клетки поля должны быть разрешенными.

При наличии нескольких полей, удовлетворяющих указанным требованиям, выведите любое из них. Существование хотя бы одного такого поля гарантируется.

제한

힌트