Fox and Minimal path

题意翻译

要求构造一个含有$N(1\le N\le 1000)$个节点的简单无向图，使得从$1$号节点到$2$号节点恰有$K$条最短路径（$1\le K\le 10^9$）。输出你构造图的邻接矩阵表示。

题目描述

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^{9} $ ).

输出格式

You should output a graph $ G $ with $ n $ vertexes ( $ 2<=n<=1000 $ ). There must be exactly $ k $ shortest paths between vertex 1 and vertex 2 of the graph. The first line must contain an integer $ n $ . Then adjacency matrix $ G $ with $ n $ rows and $ n $ columns must follow. Each element of the matrix must be 'N' or 'Y'. If $ G_{ij} $ is 'Y', then graph $ G $ has a edge connecting vertex $ i $ and vertex $ j $ . Consider the graph vertexes are numbered from 1 to $ n $ . The graph must be undirected and simple: $ G_{ii} $ = 'N' and $ G_{ij}=G_{ji} $ must hold. And there must be at least one path between vertex 1 and vertex 2. It's guaranteed that the answer exists. If there multiple correct answers, you can output any of them.

输入输出样例

输入样例 #1

2

输出样例 #1

4
NNYY
NNYY
YYNN
YYNN

输入样例 #2

9

输出样例 #2

8
NNYYYNNN
NNNNNYYY
YNNNNYYY
YNNNNYYY
YNNNNYYY
NYYYYNNN
NYYYYNNN
NYYYYNNN

输入样例 #3

1

输出样例 #3

2
NY
YN

说明

In first example, there are 2 shortest paths: 1-3-2 and 1-4-2. In second example, there are 9 shortest paths: 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.