Fox Ciel wants to write a task for a programming contest. The task is: "You are given a simple undirected graph with *n* vertexes. Each its edge has unit length. You should calculate the number of shortest paths between vertex 1 and vertex 2."

Same with some writers, she wants to make an example with some certain output: for example, her birthday or the number of her boyfriend. Can you help her to make a test case with answer equal exactly to *k*?
The first line contains a single integer *k* (1 ≤ *k* ≤ 10<sup class="upper-index">9</sup>).
from collections import defaultdict
# 先不最小化n
k = int(input())
m = len(bin(k)) - 3 # 节点层数
bit = [int(i) for i in bin(k)[3:]]
cur = 2 # 当前节点
g = defaultdict(list)
for i in range(m - 1):
    g[cur].append(cur + 2)
    g[cur].append(cur + 3)
    g[cur + 1].append(cur + 2)
    g[cur + 1].append(cur + 3)
    cur += 2
g[0].append(2)
g[0].append(3)
g[cur + 1].append(1)
g[cur].append(1)
cur += 2
if k == 3:
    g[0].append(1)
else:
    for b in range(m):
        if b == 0 and bit[b] == 1:
            g[0].append(cur)
            g[cur].append(4)
            g[0].append(cur + 1)
            g[cur + 1].append(4)
            cur += 2
        elif bit[b] == 1:
            g[0].append(cur)
            for i in range(b - 1):
                g[cur].append(cur + 1)
                cur += 1
            g[cur].append(2 * b + 2)
            cur += 1
grid = [['N'] * cur for _ in range(cur)]
for i in range(cur):
    for j in g[i]:
        grid[i][j] = 'Y'
        grid[j][i] = 'Y'
print(cur)
for i in range(cur):
    print(''.join(grid[i]))

