B. Лиса и минимальный путь
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лисица Сиель хочет сделать задачку программистам на контест. Задача звучит так: «Дан простой неориентированный граф, состоящий из n вершин. Каждое его ребро имеет длину 1. Надо посчитать количество кратчайших путей между вершиной 1 и вершиной 2».

Как и все авторы, она хочет, чтобы некоторые из выходных данных были особенными: например, ее день рождения или количество ее друзей. Можете ли вы помочь ей составить такой тест для задачи, чтобы ответ на него был ровно k?

Входные данные

В первой строке записано единственное целое число k (1 ≤ k ≤ 109).

Выходные данные

Выведите граф G с n вершинами (2 ≤ n ≤ 1000). Между вершинами графа 1 и 2 должно быть ровно k наикратчайших путей.

В первой строке должно быть записано целое число n. Затем надо вывести матрицу смежности графа G, состоящую из n строк и n столбцов. Каждый элемент матрицы должен равняться 'N' или 'Y'. Если Gij равняется 'Y', то граф G имеет ребро, соединяющее вершину i и вершину j. Считайте, что вершины графа пронумерованы от 1 до n.

Граф должен быть неориентированным и простым: должны выполняться условия Gii = 'N' и Gij = Gji. Также, должен быть хотя бы один путь между вершинами 1 и 2. Гарантируется, что ответ существует. Если есть несколько правильных ответов, можно вывести любой из них.

Примеры
Входные данные
2
Выходные данные
4
NNYY
NNYY
YYNN
YYNN
Входные данные
9
Выходные данные
8
NNYYYNNN
NNNNNYYY
YNNNNYYY
YNNNNYYY
YNNNNYYY
NYYYYNNN
NYYYYNNN
NYYYYNNN
Входные данные
1
Выходные данные
2
NY
YN
Примечание

В первом примере есть 2 кратчайших пути: 1-3-2 и 1-4-2.

Во втором примере есть 9 кратчайших путей: 1-3-6-2, 1-3-7-2, 1-3-8-2, 1-4-6-2, 1-4-7-2, 1-4-8-2, 1-5-6-2, 1-5-7-2, 1-5-8-2.